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

Порядок строк рекурсивного CTE сам по себе не гарантирован. Чтобы воспроизвести порядок обхода, нужно сформировать для каждой строки явный ключ сортировки — например, путь от корневого узла — и выполнить внешний ORDER BY по этому ключу.

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

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

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

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

При обходе дерева или графа разработчик может увидеть строки сначала для корня, затем для его потомков и принять это за гарантированное поведение. После изменения плана, версии СУБД, индексов или объёма данных порядок способен измениться без изменения логики запроса.

Сортировка только по уровню недостаточна: она группирует узлы по глубине, но не определяет порядок узлов внутри одного уровня. Сортировка по идентификатору также не обязательно отражает путь обхода.

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

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

Пример для PostgreSQL:

WITH RECURSIVE tree(node, parent, path) AS (
    SELECT 1, NULL, ARRAY[1]
    UNION ALL
    SELECT e.child, e.parent, t.path || e.child
    FROM edges e
    JOIN tree t ON e.parent = t.node
)
SELECT node, path
FROM tree
ORDER BY path;

Здесь path содержит последовательность узлов от корня до текущей строки. Внешний ORDER BY path является частью результата запроса, поэтому порядок становится проверяемым контрактом, а не побочным эффектом плана.

Тип ключа зависит от СУБД: это может быть массив, строковый путь или другой сопоставимый тип. Для строковых путей требуется аккуратно кодировать элементы, иначе значения 2 и 10 могут сортироваться не в числовом порядке.

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

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

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

Рассматривались три варианта. Полагаться на порядок рекурсивного CTE было просто, но ненадёжно. Сортировка по глубине давала группировку по уровням, однако смешивала соседние ветви. Сортировка по идентификаторам была стабильной, но не отражала структуру дерева.

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

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

Достаточно ли сортировать итог по глубине, чтобы получить обход в ширину?

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

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

Гарантирует ли порядок строк в рекурсивной части порядок итогового результата?

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

Гарантия появляется только при явном ORDER BY в запросе, который возвращает результат клиенту. Сортировка внутри производной таблицы или промежуточного CTE без внешней сортировки сама по себе такой гарантии не создаёт.

Что нужно учитывать, если один узел достижим по нескольким путям?

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

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