Рекурсивные CTE: иерархии и графы

Спроектируй рекурсивный CTE для задачи: {{task}}. Таблица: {{table}}.

Анатомия рекурсивного CTE

WITH RECURSIVE tree AS (
  -- 1. Anchor: стартовая точка (не рекурсивна)
  SELECT id, parent_id, name, 1 AS depth, ARRAY[id] AS path
  FROM nodes
  WHERE id = :root_id

  UNION ALL

  -- 2. Recursive: ссылается на сам CTE
  SELECT n.id, n.parent_id, n.name, t.depth + 1, t.path || n.id
  FROM nodes n
  JOIN tree t ON n.parent_id = t.id
  WHERE NOT n.id = ANY(t.path)  -- cycle detection
    AND t.depth < 50            -- termination guard
)
SELECT * FROM tree ORDER BY path;

Обязательные элементы:

• UNION ALL (не UNION — он дедуплицирует и обычно делает не то)
• termination condition в recursive части (depth limit, cycle check, или предикат)
• путь ARRAY или VARCHAR для cycle detection и ordering

Типовые задачи

Все потомки узла (descend)

Anchor: WHERE id = :root. Recursive: JOIN tree t ON n.parent_id = t.id.

Путь до корня (ascend)

Anchor: WHERE id = :start. Recursive: JOIN tree t ON n.id = t.parent_id.

BFS с уровнями

Сохраняй depth, в финальном SELECT — ORDER BY depth, parent_id, id.

Shortest path в графе

Сохраняй накопленную стоимость и путь. Берёшь MIN(cost) per target после DISTINCT ON (target_id) ... ORDER BY target_id, cost. Внимание: рекурсивный CTE не делает Dijkstra — обходит все пути, потом фильтруешь. На больших графах не масштабируется.

BOM (bill of materials, развёртка с количествами)

WITH RECURSIVE bom AS (
  SELECT component_id, parent_id, qty AS total_qty, 1 AS lvl
  FROM parts WHERE parent_id = :product
  UNION ALL
  SELECT p.component_id, p.parent_id, b.total_qty * p.qty, b.lvl + 1
  FROM parts p JOIN bom b ON p.parent_id = b.component_id
  WHERE b.lvl < 20
)
SELECT component_id, SUM(total_qty) AS qty FROM bom GROUP BY component_id;

Cycle detection

Три способа:

1. Path array: WHERE NOT n.id = ANY(t.path) — простой, читабельный, работает везде
2. CYCLE clause (стандарт SQL:2016): CYCLE id SET is_cycle USING path — Postgres ≥14, чистый синтаксис
3. Depth limit: WHERE depth < N — не цикл-детект, а аварийный тормоз. Всегда добавляй как страховку

Без cycle detection планировщик может уйти в бесконечный цикл и упасть с OOM. Никогда не запускай без termination guard.

Когда CTE — плохая идея

Производительность

• Каждый шаг рекурсии = отдельный JOIN. Индекс на parent_id — обязателен
• Recursive CTE в Postgres всегда материализуется (даже без MATERIALIZED ключевого слова)
• work_mem может стать узким местом — промежуточный набор копится в памяти
• Проверяй EXPLAIN ANALYZE: смотри сколько строк прошло через CTE Scan on tree — это весь объём проделанной работы

Анти-паттерны

• ❌ UNION вместо UNION ALL — дедупликация после каждой итерации, в 10× медленнее
• ❌ Recursive CTE без termination — гарантированный OOM на циклах
• ❌ Хранение длинного пути как TEXT с разделителями вместо ARRAY — парсинг для сравнений
• ❌ Использовать recursive CTE как замену индексу — JOIN с тысячей итераций медленнее одного scan
• ❌ Считать что recursive CTE = Dijkstra — это BFS по умолчанию, без приоритетов