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

Урок 6.5 · Время чтения: ~9 мин · Задачи для практики ↓

Рекурсивный CTE в SQL - это обобщённое табличное выражение, которое ссылается само на себя, поэтому один запрос может обойти иерархию любой глубины: оргструктуру, дерево категорий, ветку комментариев. В этом уроке вы изучите синтаксис WITH RECURSIVE, узнаете, как якорная и рекурсивная части работают вместе, как найти всех подчинённых или всех руководителей сотрудника, как построить путь по дереву и как остановить бесконечную рекурсию.

В предыдущем уроке CTE был именованным шагом запроса, который выполнялся один раз. Иерархическим данным нужно больше. Если в каждой строке сотрудника хранится id его руководителя, один JOIN находит прямых подчинённых, второй JOIN - следующий уровень и так далее, но заранее неизвестно, сколько уровней в иерархии. Рекурсивный CTE повторяет соединение за вас, пока находятся новые строки.

Примеры используют синтаксис MySQL 8.0 и также работают в MariaDB 10.2+. Учебные базы данных на SQLtest доступны только для чтения, поэтому запускайте примеры в песочнице на базе без учебных данных: каждый пример создаёт собственную таблицу.

Как работает рекурсивный CTE

Рекурсивный CTE состоит из двух частей, соединённых UNION ALL:

WITH RECURSIVE cte_name AS (
    -- Якорная часть: начальные строки
    SELECT ...
    FROM table_name
    WHERE start_condition

    UNION ALL

    -- Рекурсивная часть: следующий уровень, найденный по предыдущему
    SELECT ...
    FROM table_name
    INNER JOIN cte_name ON join_condition
)
SELECT * FROM cte_name;

• WITH RECURSIVE сообщает базе данных, что CTE ссылается сам на себя.
• Якорная часть (anchor member) выполняется один раз и возвращает начальные строки, например главного руководителя.
• Рекурсивная часть (recursive member) ссылается на CTE по имени. При каждом выполнении она видит только строки, полученные на предыдущей итерации.
• Рекурсия останавливается, когда итерация не возвращает ни одной строки. Строки всех итераций вместе образуют результат.

Простейший пример: последовательность чисел

WITH RECURSIVE numbers AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1
    FROM numbers
    WHERE n < 5
)
SELECT n FROM numbers;

Результат: 5 строк с числами 1, 2, 3, 4, 5.

Якорная часть возвращает 1. Первая итерация читает 1 и возвращает 2, следующая - 3 и так далее. Когда предыдущая итерация вернула 5, условие n < 5 ложно, рекурсивная часть ничего не возвращает, и запрос завершается. Условие в WHERE - это условие завершения: без него рекурсия никогда бы не остановилась.

Учебные данные: оргструктура

Иерархию в таблице обычно хранят как список смежности (adjacency list): в каждой строке есть ссылка на родителя в той же таблице. Здесь manager_id указывает на другого сотрудника, а у генерального директора руководителя нет:

CREATE TABLE employee (
    employee_id INT PRIMARY KEY,
    employee_name VARCHAR(100) NOT NULL,
    manager_id INT,
    title VARCHAR(100)
);

INSERT INTO employee VALUES
    (1, 'Alice Johnson', NULL, 'CEO'),
    (2, 'Bob Smith', 1, 'VP of Engineering'),
    (3, 'Carol White', 1, 'VP of Sales'),
    (4, 'David Brown', 2, 'Engineering Manager'),
    (5, 'Eve Davis', 2, 'Engineering Manager'),
    (6, 'Frank Miller', 3, 'Sales Manager'),
    (7, 'Grace Wilson', 4, 'Senior Developer'),
    (8, 'Henry Moore', 4, 'Developer'),
    (9, 'Ivy Taylor', 5, 'Developer'),
    (10, 'Jack Anderson', 6, 'Sales Representative');

Поиск всех подчинённых

Кто подчиняется Bob Smith напрямую или через других руководителей? Якорная часть выбирает Bob, рекурсивная - сотрудников, чей руководитель находится на предыдущем уровне:

WITH RECURSIVE subordinates AS (
    SELECT employee_id, employee_name, title, 0 AS level
    FROM employee
    WHERE employee_name = 'Bob Smith'

    UNION ALL

    SELECT e.employee_id, e.employee_name, e.title, s.level + 1
    FROM employee AS e
    INNER JOIN subordinates AS s ON e.manager_id = s.employee_id
)
SELECT employee_id, employee_name, title, level
FROM subordinates
ORDER BY level, employee_name;

Результат: 6 строк: Bob Smith на уровне 0, David Brown и Eve Davis на уровне 1, Grace Wilson, Henry Moore и Ivy Taylor на уровне 2.

Столбец level считает итерации: в якорной части он равен 0 и увеличивается на единицу с каждым шагом вниз. Чтобы исключить самого Bob, добавьте WHERE level > 0 в итоговый запрос.

Всё дерево с путём

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

WITH RECURSIVE org_chart AS (
    SELECT
        employee_id,
        employee_name,
        title,
        0 AS level,
        CAST(employee_name AS CHAR(500)) AS path
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT
        e.employee_id,
        e.employee_name,
        e.title,
        oc.level + 1,
        CONCAT(oc.path, ' > ', e.employee_name)
    FROM employee AS e
    INNER JOIN org_chart AS oc ON e.manager_id = oc.employee_id
)
SELECT
    CONCAT(REPEAT('- ', level), employee_name) AS hierarchy,
    title,
    path
FROM org_chart
ORDER BY path;

Результат: все 10 сотрудников в порядке дерева, у каждого - цепочка руководителей над ним.

Здесь важны две детали:

• Сортировка по пути ставит каждого сотрудника сразу после его руководителя, поэтому результат читается как дерево.
• CAST(... AS CHAR(500)) в якорной части. Типы столбцов рекурсивного CTE берутся из якорной части. Без приведения path получил бы тип employee_name, VARCHAR(100), и как только путь стал бы длиннее 100 символов, MySQL остановился бы с ошибкой «Data too long for column 'path'». Делайте текстовые столбцы, которые растут в рекурсии, достаточно широкими уже в якорной части.

Обход вверх: все руководители сотрудника

Тот же приём работает и в обратную сторону. Чтобы найти цепочку руководителей над Ivy Taylor, начните с неё и соединяйте каждую строку с её родителем: условие соединения меняется местами.

WITH RECURSIVE managers AS (
    SELECT employee_id, employee_name, manager_id, 0 AS steps_up
    FROM employee
    WHERE employee_name = 'Ivy Taylor'

    UNION ALL

    SELECT e.employee_id, e.employee_name, e.manager_id, m.steps_up + 1
    FROM employee AS e
    INNER JOIN managers AS m ON e.employee_id = m.manager_id
)
SELECT employee_name, steps_up
FROM managers
ORDER BY steps_up;

Результат: 4 строки: Ivy Taylor (0), Eve Davis (1), Bob Smith (2), Alice Johnson (3).

Рекурсия останавливается на Alice Johnson: её manager_id равен NULL, и соединение ничего не находит.

Как остановить бесконечную рекурсию

Рекурсивный CTE завершается, когда итерация не возвращает строк. Это правило нарушают две ситуации: отсутствие условия завершения, как в последовательности чисел без WHERE, и циклы в данных, например когда по ошибке A - руководитель B, а B - руководитель A. Тогда одни и те же строки находятся снова и снова.

Ограничение глубины

Добавьте в рекурсивную часть условие на уровень:

WITH RECURSIVE subordinates AS (
    SELECT employee_id, employee_name, 0 AS level
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.employee_id, e.employee_name, s.level + 1
    FROM employee AS e
    INNER JOIN subordinates AS s ON e.manager_id = s.employee_id
    WHERE s.level < 2
)
SELECT employee_name, level
FROM subordinates;

Результат: 6 строк: генеральный директор, два вице-президента и три менеджера; уровни ниже 2 не раскрываются.

В MySQL есть и встроенный предохранитель - переменная cte_max_recursion_depth (по умолчанию 1000). Запрос, которому нужно больше итераций, завершается ошибкой «Recursive query aborted after 1001 iterations». Для действительно глубокой рекурсии увеличьте лимит: SET SESSION cte_max_recursion_depth = 10000;. MariaDB ведёт себя иначе: достигнув max_recursive_iterations, она останавливается без ошибки и возвращает строки, найденные к этому моменту, поэтому неполный результат легко не заметить.

Пропуск уже посещённых строк

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

WITH RECURSIVE org_chart AS (
    SELECT employee_id, employee_name, CAST(employee_id AS CHAR(500)) AS visited
    FROM employee
    WHERE manager_id IS NULL

    UNION ALL

    SELECT e.employee_id, e.employee_name, CONCAT(oc.visited, ',', e.employee_id)
    FROM employee AS e
    INNER JOIN org_chart AS oc ON e.manager_id = oc.employee_id
    WHERE FIND_IN_SET(e.employee_id, oc.visited) = 0
)
SELECT employee_name, visited
FROM org_chart;

Результат: 10 строк; например, у Ivy Taylor visited = 1,2,5,9.

FIND_IN_SET() возвращает позицию значения в списке через запятую или 0, если значения в списке нет. В PostgreSQL 14+ для этого есть встроенное предложение CYCLE.

Правила и различия СУБД

• Рекурсивная часть должна ссылаться на CTE ровно один раз, во FROM или JOIN, а не в подзапросе.
• В MySQL рекурсивная часть не может содержать агрегатные и оконные функции, GROUP BY, ORDER BY и DISTINCT. Агрегируйте в итоговом запросе.
• UNION ALL сохраняет все строки, и обычно используют его. UNION удаляет повторяющиеся строки и попутно останавливает цикл, если повторяющиеся строки полностью совпадают.

Для скорости проиндексируйте столбец, по которому идёт рекурсивное соединение, например manager_id.

Ключевые выводы:

• Рекурсивный CTE ссылается сам на себя и обходит иерархию любой глубины с помощью WITH RECURSIVE.
• Якорная часть возвращает начальные строки, рекурсивная находит следующий уровень по предыдущему; рекурсия останавливается, когда итерация не вернула строк.
• Соединение e.manager_id = cte.employee_id идёт вниз по дереву, e.employee_id = cte.manager_id - вверх.
• Счётчик level и столбец path показывают положение каждой строки; растущие текстовые столбцы приводите к нужному типу в якорной части.
• Защищайте запросы ограничением глубины или списком посещённых id; MySQL останавливается после cte_max_recursion_depth итераций.

Часто задаваемые вопросы

Что такое рекурсивный CTE в SQL?

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

Как остановить бесконечную рекурсию в рекурсивном CTE?

Добавьте в рекурсивную часть условие завершения, например WHERE level < 10, и защититесь от циклов в данных, отслеживая посещённые id. Кроме того, MySQL прерывает запрос после cte_max_recursion_depth итераций (по умолчанию 1000), SQL Server - после MAXRECURSION (по умолчанию 100), а MariaDB молча останавливается после max_recursive_iterations.

Поддерживает ли MySQL рекурсивные CTE?

Да, начиная с MySQL 8.0 и MariaDB 10.2, с синтаксисом WITH RECURSIVE. В старых версиях MySQL CTE нет; иерархии там обходили хранимыми процедурами или фиксированным числом самосоединений.

Почему рекурсивный CTE падает с ошибкой «Data too long for column»?

Столбцы рекурсивного CTE получают типы из якорной части. Если рекурсивная часть строит более длинную строку, например путь, она перестаёт помещаться. Приведите столбец в якорной части к более широкому типу, например CAST(name AS CHAR(500)).