Дерево — это граф без циклов. С деревьями recursive CTE работает изящно: working table сама исчерпывается на листьях, и рекурсия останавливается. Но как только в данных появляется цикл — A ссылается на B, B на C, C обратно на A — рекурсия превращается в бесконечный цикл и съедает всю память.

В этом уроке: как выглядит граф в SQL-таблицах, что ломается без cycle detection и как его правильно прикрутить.

Граф в одной таблице

Граф представляется таблицей рёбер: каждая запись — это связь «из A в B». Возьмём маленький пример: воображаемая сеть городов с прямыми авиарейсами.

В графе циклы — это норма. Транспортная сеть, friend-of-friend в социалке, граф зависимостей в монорепо — везде встречаются обратные рёбра.

Что произойдёт без cycle detection

Допустим, мы хотим найти все города, достижимые из Москвы. Напишем наивный recursive CTE:

Без WHERE r.depth < 6 recursive term будет крутиться вечно: Москва → Дубай → Москва → Дубай → … Working table никогда не пустеет.

Терминатор по глубине помогает, но он не различает уникальные города и повторы. В результате ты видишь «Дубай» на глубинах 1, 3, 5… — это один город, но запрос возвращает его много раз с разными depth. Для задачи «какие города достижимы» это неудобно: нужен DISTINCT сверху, или — лучше — встроенная защита от циклов.

Решение: тащить путь и проверять на вхождение

Классическая техника cycle detection в recursive CTE — тащить путь в виде массива, и в recursive term проверять, что новый узел в этот путь ещё не входит.

Условие f.dst <> ALL(r.path) — это «новый город не равен ни одному из уже посещённых в этом пути». PostgreSQL вычисляет это эффективно через линейный скан массива.

Каждая строка результата recursive CTE — это один путь, ведущий в свою конечную точку. Один город может попасть в результат много раз — через разные пути. Финальный GROUP BY city свёртывает это в «уникальные достижимые города».

Поиск всех путей от A до B

Часто нужно не «куда вообще можно добраться», а «все пути из A в B, до какой-то глубины». Это та же конструкция, но фильтр на финальном шаге:

Здесь видим все маршруты из Москвы в Токио, отсортированные по общему времени. Один маршрут идёт через Стамбул и Бангкок, другой — через Дубай и Бангкок, и так далее. Каждый — без повторных посещений городов.

Кратчайший путь — не задача рекурсивного CTE

Технически, в нашем последнем запросе мы получили все пути, отсортировали по total_hours и можем взять LIMIT 1 — вот тебе и «кратчайший». Но это работает только потому, что граф маленький.

На реальных графах (тысячи рёбер) перебор всех путей с защитой от циклов взрывается комбинаторно. Это NP-сложный поиск в общем случае.

Алгоритм Дейкстры или A*, которые решают задачу за O((V+E)·log V), нельзя записать прямой recursive CTE: они требуют приоритетной очереди и подбора минимального следующего шага. SQL такого не умеет — нужны процедурные надстройки (PL/pgSQL функция) или специализированная графовая БД (Neo4j, Memgraph).

Для recursive CTE подходят: достижимость, обход всего связного компонента, поиск всех путей до ограниченной глубины. Кратчайший путь — только на маленьких графах через «перебрать всё и взять минимум».

Bidirectional поиск: «друзья друзей»

Ещё один типичный сценарий — обход в неориентированном графе, где ребро (A,B) можно пройти и из A в B, и из B в A. В SQL это записывается как UNION ALL двух направлений или хитрый JOIN.

Здесь рёбра «симметричны»: если есть (1, 2), можно из 1 попасть в 2 и из 2 в 1. Поэтому в JOIN мы пишем f.a = fr.person OR f.b = fr.person, а нового соседа выбираем как «противоположный конец ребра».

Detection vs prevention

Есть два способа защититься от циклов:

1. Prevention — то, что мы делали выше: тащим путь, в recursive term проверяем dst <> ALL(path). Цикл просто не возникает: новый узел не добавляется, если он уже в пути.
2. Detection — тащим флаг is_cycle, ставим его в TRUE, если узел уже видели. Цикл возникает, но мы его регистрируем и обрабатываем.

PostgreSQL 14+ для второго подхода добавил специальный синтаксис CYCLE ... SET ... USING ... — это сахар над теми же массивами. О нём в уроке 6.

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

• Граф в SQL — это таблица рёбер (src, dst, [weight]).
• Наивная рекурсия по графу с циклами не сходится — нужен либо терминатор по глубине, либо cycle detection.
• Классическая техника — тащить путь как ARRAY и в recursive term проверять next_node <> ALL(path).
• Поиск всех путей и достижимость — задачи recursive CTE. Кратчайший путь на больших графах — нет (используй процедурный код или графовую БД).
• В неориентированном графе ребро (a, b) проходимо в обе стороны — JOIN пишется через OR и CASE.