Рекурсивное CTE¶

Рекурсивное CTE (Common Table Expression, обобщённое табличное выражение) — это синтаксическая конструкция в языке SQL, позволяющая выполнять рекурсивные запросы к иерархическим или графовым данным, хранящимся в реляционных базах данных. Рекурсивное CTE представляет собой временный набор результатов, который ссылается сам на себя в процессе выполнения, что даёт возможность обрабатывать структуры с неизвестной или переменной глубиной вложенности, такие как организационные иерархии, деревья категорий, графы зависимостей или маршруты в транспортных сетях.

¶История и стандартизация

Рекурсивные CTE были введены в стандарт SQL:1999 как часть расширения возможностей работы с иерархическими данными. До этого рекурсивные запросы в реляционных базах данных реализовывались с помощью хранимых процедур, курсоров или временных таблиц, что было громоздко и неэффективно. Первыми крупными СУБД, поддержавшими рекурсивные CTE, стали IBM DB2 (версия 7, 2000 год) и Oracle Database (с версии 11g Release 2, 2009 год, через конструкцию WITH ... CONNECT BY). Впоследствии поддержка была добавлена в PostgreSQL (с версии 8.4, 2009 год), Microsoft SQL Server (с версии 2005), SQLite (с версии 3.8.3, 2014 год) и MySQL (с версии 8.0, 2018 год). Стандарт SQL:2003 уточнил синтаксис, а SQL:2016 закрепил рекурсивные CTE как обязательную часть языка.

¶Синтаксис и структура

Рекурсивное CTE в SQL определяется с помощью ключевого слова WITH RECURSIVE. Базовая структура включает два основных компонента, объединённых оператором UNION ALL (реже UNION):

1. Якорный элемент (anchor member) — нерекурсивный запрос, который возвращает начальный набор строк (базовый случай рекурсии). Этот запрос выполняется один раз и формирует начальное состояние итерации.
2. Рекурсивный элемент (recursive member) — запрос, который ссылается на имя самого CTE. Он выполняется многократно, каждый раз используя результат предыдущей итерации в качестве входных данных. Рекурсия прекращается, когда рекурсивный элемент возвращает пустой набор строк (не добавляет новых записей).

Общий синтаксис: ``sql WITH RECURSIVE cte_name (column1, column2, ...) AS ( -- Якорный элемент SELECT ... FROM ... WHERE ... UNION ALL -- Рекурсивный элемент SELECT ... FROM cte_name JOIN ... ON ... WHERE ... ) SELECT * FROM cte_name; ``

¶Ограничения и управление глубиной

Для предотвращения бесконечных циклов в большинстве СУБД существует ограничение на максимальное количество итераций (глубину рекурсии). В PostgreSQL и SQLite это значение по умолчанию равно 1000, в Microsoft SQL Server — 100 (задаётся через OPTION (MAXRECURSION N)), в MySQL — 255 (настраивается через системную переменную cte_max_recursion_depth). При превышении лимита запрос завершается с ошибкой. Также рекурсия может быть ограничена явным условием в рекурсивном элементе (например, WHERE depth < 10).

¶Принцип работы

Выполнение рекурсивного CTE можно представить как итеративный процесс:

1. Выполняется якорный запрос, его результат помещается в рабочий набор (work table) и в итоговый набор (final result set).
2. Выполняется рекурсивный запрос, который использует текущий рабочий набор как исходные данные. Результат этого запроса становится новым рабочим набором.
3. Новые строки добавляются в итоговый набор.
4. Шаги 2–3 повторяются до тех пор, пока рекурсивный запрос не вернёт пустой набор (или не будет достигнут лимит глубины).
5. После завершения рекурсии возвращается итоговый набор, содержащий все строки, полученные на всех итерациях.

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

¶Применение

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

¶Организационные иерархии

Наиболее типичный пример — получение всех подчинённых сотрудника в компании, включая подчинённых его подчинённых (рекурсия вниз по дереву). Например, для таблицы employees с колонками id, name и manager_id можно построить иерархию, начиная с заданного руководителя.

¶Деревья категорий и меню

В интернет-магазинах и системах управления контентом часто используется модель «вложенных множеств» или «родитель-потомок» для категорий товаров. Рекурсивное CTE позволяет получить полный путь к категории (например, «Электроника → Компьютеры → Ноутбуки») или список всех подкатегорий верхнего уровня.

¶Графы и маршруты

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

¶Генерация последовательностей

Рекурсивные CTE могут применяться для генерации числовых или временных рядов без использования внешних таблиц. Например, создание списка дат от 2024-01-01 до 2024-01-31: ``sql WITH RECURSIVE dates (d) AS ( SELECT DATE('2024-01-01') UNION ALL SELECT DATE(d, '+1 day') FROM dates WHERE d < '2024-01-31' ) SELECT * FROM dates; ``

¶Обработка древовидных структур с агрегацией

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

¶Особенности реализации в различных СУБД

• PostgreSQL — поддерживает рекурсивные CTE в полном объёме, включая использование UNION (для устранения дубликатов) и UNION ALL. Позволяет использовать массивы и другие сложные типы данных в рекурсивных запросах.
• Microsoft SQL Server — использует синтаксис WITH cte_name AS (...), где рекурсивность определяется наличием ссылки на CTE внутри запроса. Поддерживает MAXRECURSION и OPTION.
• MySQL — добавил поддержку в версии 8.0. Синтаксис аналогичен стандарту. Ограничение глубины задаётся через cte_max_recursion_depth.
• SQLite — поддерживает рекурсивные CTE, но с некоторыми ограничениями (например, не поддерживает UNION без ALL в рекурсивной части).
• Oracle Database — исторически использовал CONNECT BY для иерархических запросов, но с версии 11g Release 2 поддерживает и стандартный синтаксис WITH RECURSIVE.

¶Производительность и ограничения

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

• глубина рекурсии (количество итераций);
• объём данных на каждой итерации;
• наличие индексов на ключевых колонках (например, manager_id или parent_id);
• сложность рекурсивного запроса (количество соединений, фильтров, агрегаций).

Для графов с циклами стандартное рекурсивное CTE может войти в бесконечный цикл. Для предотвращения этого необходимо явно отслеживать посещённые вершины, например, накапливая путь в виде массива или строки и проверяя, что текущая вершина ещё не встречалась. В некоторых СУБД (например, PostgreSQL) это можно сделать с помощью CYCLE-клаузы (стандарт SQL:2016), которая автоматически обнаруживает циклы.

¶Сравнение с альтернативными подходами

До появления рекурсивных CTE для работы с иерархиями использовались:

• Хранимые процедуры с курсорами — требовали написания сложного императивного кода, были медленными и плохо поддерживались.
• Вложенные запросы — неэффективны при неизвестной глубине.
• Модель «вложенных множеств» (Nested Sets) — позволяла получать иерархию одним запросом, но требовала трудоёмкого обновления при добавлении/удалении узлов.
• Материализованные пути (Materialized Path) — хранили полный путь в виде строки, что упрощало запросы, но усложняло изменение структуры.

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

¶Источники

• Международный стандарт ISO/IEC 9075-2:2016 (SQL/Foundation).
• Документация PostgreSQL: «WITH Queries (Common Table Expressions)».
• Документация Microsoft SQL Server: «WITH common_table_expression (Transact-SQL)».
• Документация MySQL: «WITH (Common Table Expressions)».
• Документация SQLite: «WITH clause».
• Документация Oracle Database: «Hierarchical Queries».