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

UNION удаляет дубликаты строк между итерациями рекурсии, поэтому узел, достигнутый несколькими путями, обычно появляется один раз. UNION ALL сохраняет каждое такое достижение, из-за чего результат может содержать повторения, а при наличии циклов рекурсия может не завершиться без дополнительного ограничения.

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

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

Различие между UNION и UNION ALL переносит в рекурсивный запрос обычную разницу между множественной и мультимножественной семантикой: первый вариант устраняет повторы, второй сохраняет их.

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

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

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

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

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

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

WITH RECURSIVE
edges(from_node, to_node) AS (
    VALUES (1, 2), (1, 3), (2, 4), (3, 4)
),
reach(node) AS (
    VALUES (1)
    UNION
    SELECT e.to_node
    FROM edges e
    JOIN reach r ON r.node = e.from_node
)
SELECT node FROM reach;

В примере узел 4 достижим двумя путями, но с UNION возвращается один раз. Если заменить его на UNION ALL, узел 4 появится дважды.

Ключевая тонкость: удаляются дубликаты всей строки рекурсивного CTE, а не только идентификатора узла. Если CTE хранит глубину или полный путь, строки с одним узлом, но разными глубиной или путём, дубликатами не считаются. Поэтому UNION сам по себе не является универсальным обнаружением циклов.

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

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

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

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

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

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

Достаточно ли UNION для предотвращения любого цикла?

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

Почему UNION может изменить не только количество строк, но и смысл результата?

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

Можно ли заменить UNION ALL на UNION после добавления идентификатора узла в результат?

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