Рекурсивные CTE
В Brew открыли админку меню и обнаружили, что категории давно стали деревом: «Напитки» делятся на «Кофе» и «Чай», «Кофе» — на «Эспрессо-напитки» и «Фильтр», а «Эспрессо-напитки» — это уже «Капучино» и «Латте». В таблице это всего одна колонка parent_id, ссылающаяся на собственный id. Маркетинг попросил выгрузить меню «как на витрине» — с отступами по уровню вложенности и полным путём от корня, чтобы вставить в баннер. Обычный JOIN тут бессилен: глубину дерева заранее никто не знает, а писать восемь самосоединений «на всякий случай» — не инженерное решение.
А через час прилетел второй инцидент. Логист собрал граф «куда везти партию дальше»: со склада — в цех, из цеха — в кафе. Кто-то по ошибке завёл строку, что из кафе остатки едут обратно на склад. Получилось кольцо Склад → Цех → Кафе → Склад, и первый же наивный рекурсивный запрос по этому графу повис: он бесконечно ходил по кругу, пока сервер не упёрся в лимит. Оба инцидента — про одну и ту же конструкцию, рекурсивный CTE, которую мы пообещали ещё в 04-06, когда впервые завели разговор о деревьях в реляционной модели. Пора её выдать.
Почему этот юнит — на psql, а не на sqlc
Весь курс по умолчанию держит sqlc в главной роли. Но здесь мы сознательно роняем инструмент, потому что урок — ровно про ту фичу, которую sqlc не умеет прочитать. Защита от циклов в SQL-стандарте оформлена секцией CYCLE: она дописывает к результату рекурсии «виртуальные» колонки is_cycle и path, которых нет ни в одной таблице схемы. sqlc v1.30.0 разбирает запрос статически, по DDL, не находит этих колонок и падает с column "is_cycle" does not exist. Менять урок под инструмент — значит выкинуть из урока его сердцевину. Поэтому мы выбираем фичу, а не инструмент, и ведём демо обычным psql-скриптом demo.sql. Это та же логика escape-hatch, что в 02-05 и 03-05: когда конструкция упирается в границы статического анализатора, побеждает конструкция.
WITH RECURSIVE: якорь плюс шаг
Рекурсивный CTE всегда состоит из двух частей, склеенных через UNION ALL. Первая — якорь: стартовые строки, с которых начинается обход. Для дерева это корни — категории без родителя (parent_id IS NULL). Вторая — рекурсивный шаг: он берёт уже найденные строки и присоединяет к ним детей. Postgres повторяет шаг снова и снова, пока тот не перестанет добавлять новые строки, — на дереве это естественно случается, когда обход доходит до листьев.
Важно, что на каждом уровне мы не просто спускаемся, а накапливаем контекст. В якоре заводим depth = 1 и путь, состоящий из одного своего узла; в шаге увеличиваем depth на единицу и дописываем текущий узел к пути родителя. Так к каждой строке прилипает и её глубина, и вся дорога от корня до неё — то самое, что просил маркетинг.
Вот это дерево целиком — те самые parent_id, разложенные по уровням. Обход идёт сверху вниз ровно в этом порядке (pre-order: родитель, затем всё его поддерево, затем сосед):
depth 1 Напитки
depth 2 ├─ Кофе
depth 3 │ ├─ Эспрессо-напитки
depth 4 │ │ ├─ Капучино
depth 4 │ │ └─ Латте
depth 3 │ └─ Фильтр
depth 2 └─ Чай
depth 3 └─ ЗелёныйЯкорь — это корень Напитки (родителя нет); каждый рекурсивный шаг спускается на уровень ниже, к детям уже найденных узлов. idpath — массив id вдоль ветки — и задаёт этот pre-order в выводе.
Что показывает наш код
Первая часть demo.sql — обход дерева категорий. Якорь выбирает корни и инициализирует три накопителя: depth, массив идентификаторов idpath и строковый путь namepath. Рекурсивный шаг джойнит таблицу саму на себя по c.parent_id = t.id и продолжает все три накопителя:
WITH RECURSIVE tree AS (
-- якорь: корни (нет родителя), глубина 1, путь = [свой id]
SELECT id, parent_id, name, 1 AS depth,
ARRAY[id] AS idpath,
name::text AS namepath
FROM category_tree_lab
WHERE parent_id IS NULL
UNION ALL
-- рекурсивный шаг: дети уже найденных узлов, глубина +1, путь дополняем
SELECT c.id, c.parent_id, c.name, t.depth + 1,
t.idpath || c.id,
t.namepath || ' > ' || c.name
FROM category_tree_lab c
JOIN tree t ON c.parent_id = t.id
)
SELECT depth,
repeat(' ', depth - 1) || name AS category,
namepath AS path
FROM tree
ORDER BY idpath; -- массив id → детерминированный pre-order, без зависимости от collationОтдельного разговора заслуживает ORDER BY idpath. Сам рекурсивный CTE ничего не обещает про порядок строк — без явной сортировки вывод мог бы перетасоваться от запуска к запуску. Хочется получить привычный pre-order: родитель, затем всё его поддерево, затем следующий сосед. Соблазнительно отсортировать по namepath — строковому пути с именами, — но тогда порядок «Кофе» и «Чай» начнёт зависеть от collation базы: в одной локали кириллица сравнивается так, в другой иначе, и вывод поплывёт. Поэтому сортируем по idpath — массиву числовых id. Массивы в Postgres сравниваются поэлементно, число с числом, мимо всякого collation. Результат — стабильный, воспроизводимый обход на любой инсталляции.
Вторая часть — тот же механизм, натравленный на циклический граф маршрутов. Здесь нас интересует не путь, а сам факт зацикливания, и его ловит SQL-стандартная секция CYCLE (Postgres понимает её с 14-й версии):
WITH RECURSIVE walk AS (
SELECT id, next_id, name, 1 AS step
FROM cyclic_routes_lab
WHERE id = 1
UNION ALL
SELECT r.id, r.next_id, r.name, w.step + 1
FROM cyclic_routes_lab r
JOIN walk w ON r.id = w.next_id
) CYCLE id SET is_cycle USING path -- помечаем повтор id и кладём пройденный путь в path
SELECT step, id, name, is_cycle, path
FROM walk
ORDER BY step;Читается это так: «следи за повтором значения id; как только рекурсия снова придёт в уже посещённый id, выставь флаг is_cycle в true, а в path веди список всех пройденных узлов». Колонки is_cycle и path Postgres материализует сам — их нет в cyclic_routes_lab, и именно их отсутствие в схеме спотыкает sqlc. Ключевое — поведение на повторе: обнаружив, что узел уже был в path, Postgres помечает строку и не делает по ней следующий рекурсивный шаг. Кольцо размыкается, рекурсия завершается сама.
Запуск
docker compose up -d
make lecture L=08-analytical-and-lateral/08-04-recursive-ctesT=run — цель по умолчанию: она прогоняет demo.sql через psql. Изнутри каталога юнита достаточно make run. Вывод детерминированный — он повторяется дословно при любом прогоне:
1) Обход дерева категорий сверху вниз (WITH RECURSIVE):
depth | category | path
-------+----------------------+----------------------------------------------
1 | Напитки | Напитки
2 | Кофе | Напитки > Кофе
3 | Эспрессо-напитки | Напитки > Кофе > Эспрессо-напитки
4 | Капучино | Напитки > Кофе > Эспрессо-напитки > Капучино
4 | Латте | Напитки > Кофе > Эспрессо-напитки > Латте
3 | Фильтр | Напитки > Кофе > Фильтр
2 | Чай | Напитки > Чай
3 | Зелёный | Напитки > Чай > Зелёный
2) Тот же обход по зациклённому графу, но с CYCLE — рекурсия сама тормозит:
step | id | name | is_cycle | path
------+----+-------+----------+-------------------
1 | 1 | Склад | f | {(1)}
2 | 2 | Цех | f | {(1),(2)}
3 | 3 | Кафе | f | {(1),(2),(3)}
4 | 1 | Склад | t | {(1),(2),(3),(1)}В первом блоке отступы repeat(' ', depth - 1) рисуют дерево, а path показывает полную дорогу от корня — ровно то, что уходит в баннер. Во втором обход прошёл Склад → Цех → Кафе и на четвёртом шаге снова пришёл в id = 1. Postgres увидел этот id в накопленном path, выставил is_cycle = t и положил в path замкнувшееся кольцо {(1),(2),(3),(1)}. На этой строке обход останавливается — вместо того чтобы крутиться по складу, цеху и кафе до бесконечности.
Заборчик
- Без явной защиты рекурсия по циклическому графу не завершается — это не теоретический риск, а тот самый повисший запрос из инцидента. До Postgres 14 секции
CYCLEне было, и цикл ловили руками: тащили через рекурсию массив пройденныхidи добавляли в шаг условие видаNOT c.id = ANY(path). Работало, но было многословно и легко ломалось при копировании.CYCLEговорит то же самое одной строкой; увидишь старый ручной вариант — знай, что он делает. - Глубокая рекурсия стоит памяти и времени: промежуточный результат живёт целиком, и на большом или плохо ветвящемся графе запрос съест заметный кусок ресурсов. В проде на таких данных ставят предел глубины (условие на
depthв рекурсивном шаге), чтобы запрос гарантированно завершился, даже если в графе притаилась аномалия. - Деревья, которые читают часто и помногу (навигация по каталогу, дерево комментариев, оргструктура), в проде обычно денормализуют: держат рядом материализованный путь, заводят тип
ltree, строят closure table. Тогда «дай всё поддерево» превращается в обычный индексированныйSELECTбез рекурсии на каждый чих. Рекурсивный обход хорош для разовых выгрузок и админских запросов, но как горячий путь под нагрузкой почти всегда проигрывает заранее посчитанной структуре. - Рамка: этот урок про выразительность
SQL— что дерево и граф укладываются в один запрос, — а не приглашение переносить бизнес-логику обхода в базу там, где ей место в коде.
Что забрать с собой
Рекурсивный CTE — это якорь плюс рекурсивный шаг, склеенные UNION ALL: якорь даёт старт (корни дерева), шаг присоединяет детей уже найденных узлов и повторяется, пока есть что добавлять. На каждом уровне мы накапливаем контекст — depth и path, — и именно накопление превращает плоскую таблицу с parent_id в дерево с отступами и полными путями. Детерминизм обхода обеспечивает сортировка по массиву id, а не по строке имени: массивы сравниваются поэлементно и не зависят от collation базы, поэтому pre-order стабилен на любой инсталляции.
Защита от зацикливания живёт в SQL-стандартной секции CYCLE id SET is_cycle USING path: на повторе id она выставляет флаг и обрывает рекурсию по этой ветке, так что обход циклического графа завершается сам, а не висит до лимита сервера. А escape-hatch здесь не каприз: sqlc не видит виртуальных колонок is_cycle/path и падает на статическом анализе — урок про фичу диктует инструмент.
Мы научились спускаться по дереву и графу в глубину. Дальше в 08-05 развернём ось на 90 градусов: LATERAL позволит для каждой строки слева выполнить отдельный подзапрос справа — «для каждого магазина дай три его последних заказа», — и это уже не про обход вглубь, а про коррелированное соединение вширь.