В прошлом уроке мы поняли, зачем нужна рекурсия. Сегодня — как она записывается. Это самый важный урок модуля: каркас, который ты будешь набивать в каждом следующем шаге.

Скелет recursive CTE

Синтаксис выглядит так:

WITH RECURSIVE cte_name(col1, col2, ...) AS (
    -- Anchor: стартовое множество кортежей
    SELECT ...
  UNION ALL
    -- Recursive term: ссылается на cte_name
    SELECT ...
    FROM ... JOIN cte_name ON ...
)
SELECT * FROM cte_name;

Три обязательных компонента:

• WITH RECURSIVE — ключевое слово. Без RECURSIVE в WITH нельзя ссылаться на CTE из самого определения CTE. Это сигнал планировщику: «здесь будет цикл».
• Anchor (база рекурсии) — первый SELECT, до UNION. Не использует cte_name внутри себя. Это стартовое множество.
• Recursive term — второй SELECT, после UNION / UNION ALL. Должен ссылаться на cte_name (хотя бы один раз).

Между ними обязательно UNION или UNION ALL. Это не просто оператор — он формально определяет, как объединяются результаты шагов. О различиях между UNION и UNION ALL в рекурсии — отдельный урок 5.

Минимальный рабочий пример

Найдём всех подчинённых CEO Анны Громовой (id=1), на любой глубине.

Что мы видим в результате: 16 строк, начиная с самой Анны (level=0), её прямые подчинённые (level=1), их подчинённые (level=2), и так далее. Уровень level мы накручиваем сами — это не магия СУБД, это обычная колонка в anchor 0, в recursive term s.level + 1.

Как PostgreSQL это исполняет — пошагово

Внутри планировщика recursive CTE превращается в цикл с тремя «буферами»:

• Result table — финальный результат, который вернётся пользователю.
• Working table (рабочая) — кортежи, которые будут поданы в recursive term на следующей итерации.
• Intermediate table (промежуточная) — куда складывается то, что породил recursive term на текущей итерации.

Алгоритм:

1. Выполнить anchor. Результат → result table и working table.
2. Пока working table не пуста:
   • Выполнить recursive term, подставляя working table вместо cte_name.
   • Результат → intermediate table.
   • Скопировать intermediate в result.
   • Переписать working table содержимым intermediate (очистить intermediate).
3. Вернуть result table.

Ключевое следствие: recursive term на каждом шаге работает не со всем result, а только с новыми кортежами предыдущего шага. Это эквивалентно семантике «фронт волны» в BFS-обходе.

Если в recursive term написать SELECT ... FROM cte_name, ты получаешь именно working table. Кажется, что ссылаешься на «весь CTE», но на самом деле — только на свежий слой. Это не баг — это спецификация SQL:1999, и она интуитивно понятна, как только привык.

Терминатор: зачем уровни и фильтры

В нашем примере мы не писали никакого WHERE level < 100 — рекурсия остановилась сама. Почему?

Потому что данные конечны. После того как мы дошли до листьев дерева (сотрудников без подчинённых), recursive term ничего не возвращает: нет такого e, чтобы e.manager_id был в working table — working table содержит только листья, на которых ничего не висит. Working table становится пустой, цикл прекращается.

В дереве это работает автоматически. Но в графе с циклами (A→B→A) — нет: working table будет вечно подкидывать что-то новое. Об этом — урок 4. Сейчас запомни: в дереве терминатор не нужен, в графе — нужен.

Один практический совет: даже в дереве часто полезно ограничить глубину. Это страховка от испорченных данных. Допустим, кто-то по ошибке поставил Анне manager_id = 6 — теперь у нас цикл. Без терминатора рекурсия будет крутиться, пока не упрётся в work_mem или таймаут.

Один прыжок: посчитаем суммарную зарплату ветки

Чтобы убедиться, что результат CTE — это обычное отношение (его можно агрегировать, джойнить, оборачивать в подзапрос), посчитаем суммарную зарплату всех подчинённых VP Engineering Галины Сидоровой (id=4).

После того как CTE собрал всех «потомков» Галины (включая её саму), мы просто агрегируем — как с любой другой таблицей. Для остальной части запроса CTE — это коробка с готовыми кортежами; не важно, что внутри был цикл.

Правила, которые нельзя нарушать

PostgreSQL накладывает несколько ограничений на recursive term. Если их нарушить — будет ошибка:

1. Между anchor и recursive term — только UNION или UNION ALL. INTERSECT, EXCEPT запрещены.
2. Recursive term не может содержать:
   • LEFT/RIGHT/FULL OUTER JOIN с cte_name (только INNER JOIN или ссылка в FROM).
   • Агрегатные функции от cte_name.
   • DISTINCT (на уровне recursive term).
   • Подзапросы, в которых cte_name появляется в WHERE NOT IN () или коррелированно.
3. Anchor не должен ссылаться на сам CTE.
4. Recursive term должен ссылаться на CTE (иначе зачем RECURSIVE).

Эти ограничения связаны с тем, что recursive term должен быть монотонным — каждый шаг только добавляет кортежи, не отбирает уже добавленные. Только при этом условии фикс-точка достижима.

Что дальше

В следующем уроке применим этот каркас к двум главным задачам: иерархии сотрудников и категориям товаров. Разберём top-down vs bottom-up обход, как считать глубину и как красиво выводить «отступы» уровней.

Чек-лист урока

• WITH RECURSIVE name AS (anchor UNION ALL recursive_term) SELECT ...
• Anchor — старт без ссылок на сам CTE. Recursive term — обязательно ссылается на CTE.
• Между ними — UNION (с дедупликацией) или UNION ALL (без). Урок 5 — про различия.
• PostgreSQL исполняет это итерациями: на каждом шаге recursive term работает с working table (только новыми кортежами с прошлого шага), не со всем накопленным результатом.
• В дереве рекурсия останавливается сама (working table пустеет). В графе — нужен явный терминатор.
• Несколько синтаксических ограничений на recursive term: только INNER JOIN, без агрегатов от CTE, без DISTINCT.