Краткий ответ

В следующую итерацию передаются только строки, полученные на предыдущем шаге, то есть текущая рабочая выборка, или delta. Уже накопленный результат хранится отдельно и не подставляется целиком в рекурсивную часть на каждой итерации.

Это позволяет обрабатывать уровни графа последовательно и не пересчитывать все найденные строки заново. Рекурсия завершается, когда очередная итерация не производит новых строк.

Исторический контекст

Обычные SQL-запросы хорошо описывают операции над конечным набором данных, но не задают повторное применение операции к результату предыдущего шага. Для иерархий, графов, цепочек зависимостей иерархическую логику раньше часто приходилось реализовывать в прикладном коде или с помощью специфичных для СУБД механизмов.

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

Постановка проблемы

Если ошибочно считать, что на каждом шаге рекурсивная часть видит весь накопленный результат, можно неверно предсказать количество строк, уровни и достижимость узлов. Это особенно опасно при обходе графа, где одна и та же вершина может быть достижима несколькими путями.

Неверная модель также приводит к ошибочному ожиданию, что рекурсивная часть автоматически сравнивает новые строки со всеми ранее найденными строками или предотвращает циклы. На практике устранение дубликатов и защита от циклов зависят от конструкции запроса и возможностей конкретной СУБД.

Подробное решение

Логическая модель рекурсивного CTE состоит из двух частей:

якорная часть формирует начальную рабочую выборку;
рекурсивная часть получает строки текущей рабочей выборки и формирует следующую рабочую выборку.

Все полученные строки обычно добавляются в накопленный результат. Затем текущая рабочая выборка заменяется следующей, а рекурсивная часть выполняется снова. Поэтому строка, найденная на уровне 2, участвует непосредственно в построении уровня 3, но не является повторным входом на каждом последующем уровне.

WITH RECURSIVE walk(node, level) AS (
    VALUES (1, 0)
    UNION ALL
    SELECT e.child, w.level + 1
    FROM edges e
    JOIN walk w ON w.node = e.parent
)
SELECT *
FROM walk;

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

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

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

Ситуация из практики

В системе управления зависимостями нужно найти все компоненты, достижимые из выбранного компонента. В графе есть общий предок: два разных пути приводят к одному и тому же узлу.

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

Второй вариант — использовать устранение дубликатов или хранить путь посещённых узлов. Устранение дубликатов обычно уменьшает объём результата, но может скрыть различие между путями. Хранение пути лучше подходит, если нужно диагностировать циклы, однако требует дополнительных данных и может быть затратным для длинных цепочек.

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

Что кандидаты часто упускают

Обрабатывает ли рекурсивная часть накопленный результат?

Нет. В логической модели она получает строки текущей итерации. Накопленный результат используется для итогового результата и, в зависимости от конструкции, для устранения дубликатов, но не становится автоматически входом каждой итерации.
Гарантирует ли обработка по итерациям порядок строк в итоговом результате?

Нет. Итерационная модель объясняет, какие строки должны быть получены, но не гарантирует порядок их выдачи. Если порядок важен, его нужно задать явной сортировкой по уровню, пути или другому вычисленному признаку.
Предотвращает ли рабочая выборка сама по себе циклы?

Нет. При цикле новая итерация может снова породить уже встречавшиеся строки. Для защиты применяют устранение дубликатов там, где это семантически допустимо, явный контроль посещённых узлов, ограничение глубины или специальные средства конкретной СУБД. Выбор метода зависит от того, нужно ли сохранить все пути или только множество достижимых узлов.