Рекурсивный запрос в SQL: WITH RECURSIVE на примерах

Короткий ответ: якорь, шаг, остановка

Рекурсивный CTE состоит из якоря — исходной строки — и рекурсивной части после UNION ALL. Рекурсивная часть читает предыдущий результат CTE, прибавляет один шаг и возвращает новые строки. WHERE depth < 3 ограничивает число переходов, а массив уже посещённых аэропортов запрещает повторить аэропорт в одном пути.

Для сети сначала берём DISTINCT departure_airport, arrival_airport, иначе каждый рейс одного направления станет отдельным ребром. Из 33 121 рейса получается 618 уникальных направлений. В уроке курса разбираются другие исходные города и задания; здесь изучаем достижимость из LED и цену ошибочного числа путей.

Из таблицы рейсов в направленный граф

Ребро src → dst означает, что в учебной базе существует хотя бы один рейс из аэропорта src в dst. Это топологическая модель, а не готовый маршрут пассажира: мы пока не проверяем даты, расписание стыковок, наличие мест и билет. Поэтому фраза «достижимо за три перелёта» в этой статье означает связь в сети направлений, а не продаваемый билет.

Направление важно. Рейс LED → SVO не доказывает обратный рейс SVO → LED, пока он отдельно не найден. Город и аэропорт тоже разные уровни: Петербург представлен кодом LED, Москва несколькими аэропортами. Если вопрос задан по городам, нужна отдельная нормализация через airports; в текущем запросе узел — аэропорт.

Как выполняется рекурсия

Якорь кладёт в рабочую таблицу LED, глубину 0 и путь из одного кода. На первой итерации соединение с edges находит направления из LED, выдаёт 24 строки глубины 1. На следующей оно работает уже с ними и выдаёт 217 простых путей глубины 2. На третьей — 1 805 путей глубины 3. Затем условие depth < 3 не разрешает ещё один переход и рекурсия заканчивается.

Рабочая таблица итерации — не весь накопленный ответ: рекурсивная часть получает строки предыдущего шага, а выход собирает строки всех шагов. Это объясняет, почему ограничение в рекурсивной части экономит работу. Фильтр глубины снаружи менял бы только вывод и не предотвращал построение лишних уровней.

В pandas для такого обхода понадобился бы цикл «уровень за уровнем» с повторным merge и собственным контролем посещённых узлов. Короткого аналога WITH RECURSIVE у DataFrame нет; здесь SQL-запрос яснее отдельного длинного Python-листинга.

Запрос: минимальное число перелётов до аэропорта

Сам CTE хранит пути, но вопрос читателя — число аэропортов по минимальной глубине. Поэтому после обхода группируем по airport, берём min(depth) и только затем считаем категории. Получаем один исходный аэропорт, 24 прямых, 72 впервые появившихся после второго перелёта и 7 — после третьего. Всего в графе 104 аэропорта и на этой глубине достигнуты все 104, включая исходный LED.

Массив path нужен для запрета цикла в конкретной ветке, а не для вычисления минимального пути. AS MATERIALIZED у edges задаёт вычисление набора уникальных направлений один раз. Это поддерживается PostgreSQL 14 и текущим DuckDB; при проверке на этих Parquet без материализации DuckDB выдавал неполный результат с разным числом уровней, поэтому в опубликованном запросе набор рёбер зафиксирован.

WITH RECURSIVE edges AS MATERIALIZED (
  SELECT DISTINCT departure_airport AS src, arrival_airport AS dst
  FROM flights
), reach(airport, depth, path) AS (
  SELECT 'LED'::varchar, 0, ARRAY['LED'::varchar]
  UNION ALL
  SELECT e.dst, r.depth + 1, array_append(r.path, e.dst)
  FROM reach r JOIN edges e ON e.src = r.airport
  WHERE r.depth < 3 AND NOT (e.dst = ANY(r.path))
), shortest AS (
  SELECT airport, min(depth) AS hops
  FROM reach GROUP BY airport
)
SELECT hops, count(*) AS airports
FROM shortest GROUP BY hops ORDER BY hops;

Путь и аэропорт — два разных результата

На глубине 2 рекурсия хранит 217 путей, но разные конечные аэропорты среди них — 92: к одному месту можно прийти через несколько промежуточных пунктов. Из 92 лишь 72 впервые появляются на глубине 2; остальные уже доступны напрямую. На глубине 3 путей 1 805, конечных аэропортов 102, а впервые достижимых — только 7.

Поэтому вывод count(*) = 1 805 с подписью «1 805 аэропортов» неверен, хотя SQL выполняется. Для уникальных аэропортов используйте count(DISTINCT airport), а для минимальной глубины — отдельный GROUP BY airport с min(depth). Если нужны маршруты, наоборот, сохраняйте путь и не схлопывайте его в аэропорт.

Ловушка 1: экземпляры рейса принимают за направления

Неправильно рекурсивно соединять исходную flights без слоя DISTINCT. Только из LED есть 1 900 экземпляров рейса, но прямых аэропортов всего 24. На первом шаге получится 1 900 строк вместо 24; на следующих повторяющиеся рейсы перемножатся и займут память, хотя новых узлов не добавят.

Исправление — заранее выбрать зерно ребра. Если важен факт существования маршрута, это пара аэропортов. Если нужна конкретная стыковка по расписанию, ребро уже обязано включать время и flight_id, а такой граф требует другого условия перехода. Не удаляйте дубли механически там, где рейсы действительно различаются для вопроса.

Ловушка 2: циклы возвращают нас назад

Неправильно писать UNION ALL с ограничением глубины, но без проверки посещённых узлов, если требуются простые пути. Уже на глубине 2 из LED получается 241 путь вместо 217; на глубине 3 — 2 652 вместо 1 805. Часть лишних строк идёт по циклам вроде LED → X → LED.

Исправление — хранить path и требовать NOT (e.dst = ANY(r.path)) при каждом переходе. Даже с защитой от циклов число простых путей растёт: на глубине 4 их 15 974. Ограничение глубины всё равно необходимо. Для допуска повторов при иных задачах определите максимальную длину и объясните, почему цикл осмыслен.

Ловушка 3: `UNION` считают полной защитой от циклов

Замена UNION ALL на UNION удаляет только идентичные строки CTE. Если строка содержит airport, depth и path, два визита в тот же аэропорт с разными путями не совпадают. Даже без массива путь к одному аэропорту на глубине 2 может появиться много раз. На нашей сети 217 простых путей этой глубины заканчиваются лишь в 92 аэропортах.

Исправление зависит от цели. Для обхода без повторения узла в конкретном пути нужна проверка массива. Для множества достижимых узлов можно хранить только узел и применять дедупликацию посещённых на каждом шаге, но тогда теряется информация о маршрутах. UNION полезен, когда идентичность строки действительно совпадает с вашей сущностью, а не потому, что он выглядит безопаснее.

Ловушка 4: число пересадок путают с числом перелётов

Неправильно отвечать на вопрос «не больше двух пересадок» условием depth <= 2: это допускает только два перелёта и максимум одну пересадку. В нашей сети тогда, исключая исходный LED, доступно 96 аэропортов: 24 прямых и 72 новых через один промежуточный. При двух пересадках нужен depth <= 3; достижимы 103 остальных аэропорта.

Исправление — подписать единицу у каждой колонки: hops здесь число рёбер, то есть перелётов, а пересадки для пути с хотя бы одним перелётом равны hops - 1. В ответе по глубине 0 исходный аэропорт не считается поездкой. Такая явная подпись помогает не ошибиться на граничном условии.

Ловушка 5: фильтр глубины ставят снаружи

Неправильно убрать r.depth < 3 из рекурсивной части и добавить WHERE depth <= 3 только в финальном SELECT. Снаружи база уже должна построить рекурсивный результат, прежде чем его отфильтровать; при циклическом графе без иной остановки запрос может не завершиться. Нельзя назвать это просто «лишними семью строками»: работа способна расти без предела.

Даже при защите от циклов лишний четвёртый шаг стоит дорого: для LED он добавляет 15 974 пути после 1 805 путей третьего шага. Исправление — ограничение в WHERE рекурсивной части, а внешний фильтр оставить только для оформления ответа. Для расследования производительности считайте строки по каждой итерации, как в таблице выше.

Ловушка 6: вывод считают упорядоченным обходом

Неправильно полагаться на видимый порядок строк рекурсивного CTE и объявлять его порядком кратчайших маршрутов. Запрос не обещает порядок без внешнего ORDER BY. Если вы строите отчёт, сортируйте по hops, аэропорту и, при необходимости, пути. После GROUP BY порядок тем более не сохраняется.

На нашем ответе категории 0/1/2/3 идут в таком порядке только потому, что в последнем SELECT стоит ORDER BY hops. Для ранжирования нескольких маршрутов к одному аэропорту дополнительно потребуется правило: меньше перелётов, затем продолжительность, затем стабильный ключ. Рекурсия перечисляет кандидатов, а не выбирает лучший билет.

Синтетическая иерархия: тот же алгоритм

В дереве сотрудников якорь — руководитель, рекурсивный шаг — строки, у которых manager_id равен текущему employee_id. Глубина означает расстояние от руководителя. На синтетической структуре директор → два менеджера → три аналитика уровни содержат 1, 2 и 3 человека. В отличие от маршрутного графа, корректное дерево не должно содержать цикл; его обнаружение — проверка качества кадрового источника.

Структура запроса при этом не меняется: якорь, UNION ALL, соединение с текущим уровнем, условие остановки и внешний порядок. Но смысл пути другой. В маршрутах узел может иметь несколько дорог; в дереве у сотрудника обычно один родитель на дату. Если источники допускают временную историю руководителей, сначала выберите запись на дату, а уже потом запускайте рекурсию.

В других СУБД

PostgreSQL 14 поддерживает WITH RECURSIVE, массивы и CYCLE для декларативной отметки циклов; показанный запрос с массивом выполнен в PostgreSQL 14. В текущем DuckDB этот же вариант с ARRAY, array_append и ANY(path) тоже выполнен, но декларативный синтаксис CYCLE не стоит переносить туда без отдельной проверки. При работе с Parquet-представлениями AS MATERIALIZED делает набор рёбер устойчивым и вычисляется один раз.

Иерархии и графы часто описывают одинаковым рекурсивным CTE, но ограничения различаются. В дереве обычно важен потомок, в сети — маршрут и цена каждого пути. Основы обычного WITH без рекурсии — в разборе CTE по шагам.

От достижимости к расписанию: где меняется задача

Направление LED → X и направление X → Y в таблице могут существовать, но это не означает, что есть выполнимая пересадка. Первый самолёт может прилететь позже вылета второго, рейсы могут летать в разные даты, а между аэропортами одного города может потребоваться наземный переезд. Топологический обход здесь намеренно отвечает только на вопрос сети. Если продукт обещает продаваемый маршрут, рекурсивная строка должна нести время прибытия, а переход проверять минимальный и максимальный интервал ожидания.

Такой переход меняет зерно ребра. DISTINCT departure_airport, arrival_airport больше не годится: два рейса одного направления в разное время становятся разными возможностями пересадки. Размер графа возвращается от 618 направлений к десяткам тысяч рейсов, и число путей растёт намного быстрее. До написания запроса надо установить бизнес-ограничения: максимум перелётов, окно времени, допускаемые аэропорты и повтор одного узла. Без ограничений красивый рекурсивный CTE станет машиной перебора бессмысленных цепочек.

Если пользователь просит только «есть ли путь до Y», перечислять все пути иногда избыточно: достаточно доказать достижимость и остановиться на нужной глубине. Если нужны все альтернативы, нельзя преждевременно схлопывать их по конечному аэропорту. Если нужен лучший билет, к условиям добавляются цена и время, а оптимизация уже не сводится к простому min(depth). Один и тот же каркас рекурсии обслуживает разные задачи, но ответ определяет состояние, которое переносится между итерациями.

Контроль размера промежуточных уровней

Практическая проверка рекурсивного запроса — таблица числа строк по depth до финального схлопывания. Для LED здесь 1, 24, 217, 1 805. Следующий шаг дал бы 15 974 простых путей, хотя новых аэропортов после трёх шагов уже не осталось. Это прямой сигнал, что продление поиска ради той же метрики бессмысленно. Считать только финальные 104 аэропорта опасно: промежуточный набор может быть огромным при маленьком ответе.

Если число путей неожиданно растёт, по очереди проверьте уникальность рёбер, циклы, повторение аэропорта и глубину. Первая ошибка даёт 1 900 строк уже на прямых рейсах LED вместо 24; вторая расширяет глубину 3 с 1 805 до 2 652; отсутствие предела глубины может совсем не остановиться. Исправления различаются, поэтому не прячьте проблему за SELECT DISTINCT airport в самом конце. Он уменьшит вывод, но не предотвратит построение тяжёлых уровней.

На большой базе подготовленный слой рёбер полезно материализовать или индексировать по src, если такое требуется планом и частотой запроса. Здесь AS MATERIALIZED фиксирует 618 уникальных направлений в рамках одного запроса. Но производительная техника вторична: если вопрос должен учитывать расписание, материализация грубых направлений дала бы быстрый, но предметно неверный ответ.

Частые вопросы

**Зачем нужен WITH RECURSIVE?** Чтобы повторять один переход, пока появляются новые строки и выполнено условие продолжения: например, от аэропорта к соседним аэропортам или от руководителя к подчинённым.

**Чем UNION отличается от UNION ALL в рекурсии?** Первый убирает одинаковые строки, второй сохраняет их. Если в строке хранится весь путь, UNION не удалит разные пути к одному узлу.

Как остановить бесконечную рекурсию? Поставьте лимит глубины внутри рекурсивной части и, если граф содержит циклы, храните посещённые узлы либо используйте проверенную поддержку CYCLE в PostgreSQL 14.

Почему путей больше, чем аэропортов? К одному аэропорту ведут разные цепочки. Считайте DISTINCT airport для узлов и count(*) для путей, не смешивая единицы.

Можно ли по сети направлений выбрать реальный билет? Нет: нужны время пересадки, расписание, места и ограничения тарифа. Граф направлений отвечает лишь на вопрос топологической достижимости.