Финальный урок модуля: разбираем грабли, на которые наступают почти все, кто начинает писать рекурсивные CTE на проде. И границы, за которыми этот инструмент перестаёт быть подходящим.

Граблю №1: runaway recursion

Runaway recursion — это рекурсия, которая не останавливается. Working table получает новые кортежи на каждой итерации, рекурсия крутится, пока:

• не упрётся в work_mem (PostgreSQL начнёт писать на диск, потом всё равно сломается),
• не превысит statement_timeout (если он установлен),
• не съест всю RAM сервера (если work_mem неограничен).

Три типичные причины:

1. Циклы в данных без cycle detection (см. уроки 4–5).
2. Recursive term без останавливающего условия в задачах, где терминатор не возникает сам.
3. Баги в данных: self-loop в иерархии (manager_id равен id), который теоретически невозможен, но триггер/CHECK его не ловит.

Симптом self-loop

Допустим, в employees Полина по ошибке стала собственным менеджером:

Без WHERE o.depth < 20 — бесконечный цикл. С терминатором — 21 строка повторяющейся Loopy. Это и есть «runaway, но с предохранителем».

Защита: три уровня

1. Terminator по глубине — WHERE depth < N. Самый простой, не требует знаний о структуре данных. Минус: на легитимно глубоких структурах N приходится поднимать.
2. Cycle detection через path — <> ALL(path). Точный, не зависит от выбора N. Минус: тащит лишнюю колонку.
3. CYCLE clause (Postgres 14+) — встроенный синтаксис, который делает то же, что ручной path, но синтаксически красивее.

CYCLE — современный синтаксис

PostgreSQL 14 добавил специальный синтаксис для cycle detection:

Что произошло:

• CYCLE city — список колонок, по которым определяется цикл. Если повторился по city — это цикл.
• SET is_cycle — имя «флага цикла». Колонка bool, которую SQL добавляет в результат: true, если шаг породил цикл.
• USING path — имя колонки-пути. SQL сам её ведёт.

Когда recursive term пытается добавить кортеж, для которого city уже встречался в path, PostgreSQL:

• Если ты используешь CYCLE — этот кортеж помечается is_cycle=true и не идёт в working table (рекурсия его не продолжает).
• Без CYCLE пришлось бы писать <> ALL(path) руками.

Поведение CYCLE: при попытке вставить кортеж, который замыкает цикл, он помечается is_cycle=true и в working table не идёт. То есть цикл регистрируется один раз, но дальше не раскручивается.

SEARCH — упорядочивание обхода

Ещё одна штука из Postgres 14 — SEARCH BREADTH FIRST BY ... SET ... и SEARCH DEPTH FIRST BY ... SET .... Это управление порядком, в котором кортежи попадают в финальный результат.

SEARCH BREADTH FIRST BY id SET ord — это «обходи в ширину, в каждом уровне сортируй по id, и положи позицию в колонку ord». Колонка ord — это псевдо-индекс для финальной сортировки.

Это не меняет, что возвращает CTE — только в каком порядке. Без SEARCH порядок не гарантирован, и для красивого вывода в UI приходилось бы вручную тащить depth и сортировать.

SEARCH BREADTH FIRST — это BFS. SEARCH DEPTH FIRST — это DFS. Колонка ord — обычно это массив, можно сортировать по нему, можно отображать как «вес» позиции.

Когда recursive CTE — не правильный инструмент

Recursive CTE — мощный инструмент, но не всемогущий. Несколько сценариев, где он плох:

1. Кратчайший путь в большом графе

Recursive CTE может перебрать все пути и взять минимум, но это O(V! / (V−L)!) — экспоненциально. На графе из 1000 узлов это нереально. Решения: Dijkstra/A* в PL/pgSQL или приложении; для серьёзных задач — Neo4j, ArangoDB, AGE (Apache Graph extension к PostgreSQL).

2. Очень большие иерархии с частыми запросами «всё поддерево»

Если у тебя 10 миллионов узлов и часто читают «всё поддерево узла X», recursive CTE будет медленным. Альтернативы:

• Materialized path — в каждой строке хранить путь к корню (/1/4/12/). Запрос: WHERE path LIKE '/1/4/%'. Чтение — O(log N) через index. Запись — нужно перестраивать path детей при переподчинении.
• Nested set (Celko) — каждая строка хранит lft и rgt. Запрос: WHERE lft BETWEEN .... Чтение — O(log N). Запись — O(N) в худшем случае (переписывает половину таблицы).
• Closure table — отдельная таблица всех пар (ancestor, descendant). Запрос — простой JOIN. Запись — много операций при переподчинении, но контролируемо.

В реальной жизни выбор между ними — это компромисс между скоростью чтения и скоростью записи.

3. Графы с миллионами рёбер и сложным анализом

PageRank, community detection, поиск кратчайшего пути между миллионами узлов — это задачи, для которых RDBMS не оптимизирована. Графовая БД имеет специализированные структуры данных (adjacency list в памяти, индексы по соседям).

PostgreSQL имеет расширение AGE (Apache Graph Extension) с Cypher-подобным языком — это компромисс: остаёшься в PostgreSQL, но получаешь графовый движок.

4. Когда задача решается одним JOIN

Не используй recursive CTE, если иерархия имеет фиксированную глубину. Если ты знаешь, что страны → города → улицы, и больше уровней не будет, — обычный 3-JOIN работает быстрее и читается проще.

Анти-паттерны, которых стоит избегать

• Recursive CTE без EXPLAIN на проде. Всегда смотри план: видишь ли ты ожидаемое число шагов, использует ли индексы JOIN внутри recursive term.
• Recursive CTE поверх таблицы без индекса на колонке, по которой идёт JOIN (manager_id, parent_id). Каждая итерация делает seq scan — взрыв на больших таблицах.
• Огромные ARRAY path на путях длиной 1000+. Массивы хорошо работают до сотен элементов; на тысячах — становятся узким местом сами.
• Recursive CTE для генерации серий, когда есть generate_series. Серии чисел или дат — это специализированная функция, она быстрее.

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

• Runaway recursion — рекурсия без останова. Защита: terminator по глубине, cycle detection через path, либо встроенный CYCLE clause (Postgres 14+).
• CYCLE col SET flag USING path — современный синтаксический сахар над ручной защитой. Регистрирует цикл и не раскручивает его дальше.
• SEARCH BREADTH FIRST/DEPTH FIRST BY ... SET ord — управляет порядком обхода. Кладёт «вес» в колонку, по которой можно сортировать.
• Recursive CTE — не подходит для: кратчайших путей в больших графах, частых breadcrumb-запросов на гигантских деревьях, графовых алгоритмов миллионных масштабов.
• Альтернативы для иерархий: materialized path, nested set, closure table — выбор по балансу чтение/запись.
• Перед prod-использованием — обязательно EXPLAIN ANALYZE и индексы на колонках JOIN внутри recursive term.