Рекурсивные CTE: якорь, итерация, стоп

Анатомия: якорь UNION рекурсивный терм

У рекурсивного CTE фиксированная форма. Ключевое слово — WITH RECURSIVE, а тело CTE — два запроса, объединённых через UNION или UNION ALL:

• якорный терм — нерекурсивный запрос, дающий стартовые строки (базовый случай);
• рекурсивный терм — запрос, ссылающийся на CTE по его собственному имени, выдающий следующие строки из предыдущих.

Вот «все подчинённые под Ada, с глубиной» над employees(id, manager_id, name):

WITH RECURSIVE subtree AS (
  -- якорь: старт с Ada
  SELECT id, manager_id, name, 1 AS depth
  FROM employees
  WHERE name = 'Ada'

  UNION ALL

  -- рекурсивный терм: на уровень вниз за проход
  SELECT e.id, e.manager_id, e.name, s.depth + 1
  FROM employees e
  JOIN subtree s ON e.manager_id = s.id
)
SELECT id, name, depth FROM subtree ORDER BY depth, id;

Рекурсивный терм соединяет employees с subtree — CTE, ссылающимся сам на себя — это та самая единственная самоссылка, про которую урок 01 говорил, что она легальна только здесь.

Модель выполнения через рабочую таблицу

Postgres вычисляет это не математической рекурсией и не вызовами функций. Он гоняет итеративный цикл по рабочей таблице, и понимание этой модели — разница между написанием рекурсивного SQL по ритуалу и его отладкой под нагрузкой:

1. Вычислить якорный терм. Положить его строки в результат и в рабочую таблицу.
2. Повторять: вычислить рекурсивный терм, но каждая самоссылка на CTE читает только рабочую таблицу (строки предыдущей итерации, не весь накопленный результат). Дописать новые строки в результат; они становятся новой рабочей таблицей.
3. Стоп, когда итерация даёт ноль новых строк.

Вместе эти три шага означают: каждый проход видит только свежие строки-фронтир, никогда — весь накапливающийся результат. Именно поэтому любое нужное состояние (глубину, путь) надо нести в самой строке. Без условия завершения из шага 3 бесконечный источник новых строк превращается в бесконечный цикл.

Это правило завершения — вся игра. Цикл кончается, когда рекурсивный терм не выдаёт ничего — так что если он всегда что-то выдаёт, цикл не кончается никогда.

Завершение, циклы и тормоз

В чистом дереве (у каждого узла один родитель, петель нет) рекурсия завершается естественно: рано или поздно дойдёшь до листьев, и рекурсивный терм не найдёт детей. Опасность — цикл: строка, чья цепочка родителей в итоге указывает на саму себя, обычное дело в графовых данных edges(src, dst) или при испорченном manager_id. С UNION ALL и циклом цикл бесконечно перепосещает одни и те же строки, и запрос не возвращается; он крутится, пока не исчерпает work_mem, не сольёт на диск и в итоге не упадёт или не зависнет. Нужен явный тормоз. Три варианта:

-- Вариант 1 (PG14+): клауза CYCLE делает это декларативно.
WITH RECURSIVE walk AS (
  SELECT src, dst FROM edges WHERE src = 1
  UNION ALL
  SELECT e.src, e.dst FROM edges e JOIN walk w ON e.src = w.dst
)
CYCLE dst SET is_cycle USING path        -- стоп перепосещению dst, уже бывшего на пути
SELECT * FROM walk WHERE NOT is_cycle;

-- Вариант 2 (любая версия): неси массив посещённых и исключай уже бывшие на пути узлы.
WITH RECURSIVE walk AS (
  SELECT src, dst, ARRAY[src] AS path FROM edges WHERE src = 1
  UNION ALL
  SELECT e.src, e.dst, w.path || e.src
  FROM edges e JOIN walk w ON e.src = w.dst
  WHERE NOT e.src = ANY(w.path)           -- не входи повторно в посещённый узел
)
SELECT * FROM walk;

-- Вариант 3 (жёсткий предел): неси глубину и ограничь её.
... WHERE s.depth < 50

UNION (не UNION ALL) также дедуплицирует каждый проход против накопленного результата, что останавливает простые повторы — но он медленнее и ловит не все графовые циклы, поэтому на реальных графовых данных предпочитай явную клаузу CYCLE (Postgres 14+) или массив посещённых. Предел глубины — это ремень безопасности, который добавляешь в любом случае: даже с защитой от циклов неограниченный обход огромного графа может вернуть миллионы строк, так что ограничь глубину тем, что реально нужно твоему сценарию.