В иерархии с неизвестной глубиной как получить всех потомков выбранного узла средствами SQL?

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

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

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

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

Рекурсивные табличные выражения добавили в SQL декларативный способ описывать повторное применение одного и того же соединения до достижения точки остановки.

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

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

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

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

Рекурсивный CTE выполняется итеративно:

1. Начальная часть формирует начальный набор строк — например, выбранного руководителя.
2. Рекурсивная часть использует уже найденные строки, чтобы найти следующий уровень.
3. Итерации продолжаются, пока рекурсивная часть возвращает новые строки.
4. Полученные строки объединяются в итоговый результат.

Минимальный пример для PostgreSQL:

WITH RECURSIVE hierarchy AS (
    SELECT employee_id, manager_id, 0 AS depth
    FROM employees
    WHERE employee_id = 10

    UNION ALL

    SELECT e.employee_id, e.manager_id, h.depth + 1
    FROM employees e
    JOIN hierarchy h ON e.manager_id = h.employee_id
)
SELECT employee_id, depth
FROM hierarchy;

Начальная часть выбирает сотрудника с идентификатором 10. Каждая следующая итерация находит сотрудников, чей руководитель уже присутствует в hierarchy.

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

Синтаксис различается между диалектами: например, PostgreSQL использует WITH RECURSIVE, а некоторые СУБД распознают рекурсивность без этого ключевого слова. Поэтому переносимость запроса нужно проверять отдельно.

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

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

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

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

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

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

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

2. Почему дерево в таблице не всегда является деревом с точки зрения рекурсивного запроса?

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

3. Чем отличается поиск потомков от поиска предков?

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