Рекурсивные запросы

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

История и развитие

Концепция рекурсии в запросах возникла из потребности эффективно работать с иерархическими данными в реляционных базах данных, которые изначально не были оптимизированы для таких структур. В 1980-х годах, с ростом популярности реляционных СУБД, разработчики столкнулись с проблемой: для обхода дерева (например, подчинённых в организации) приходилось писать хранимые процедуры или использовать несколько последовательных запросов, что было громоздко и неэффективно.

Первые реализации рекурсивных запросов появились в коммерческих СУБД в начале 1990-х годов. Например, IBM DB2 ввела поддержку рекурсивных CTE в версии 2.0 (1993 год). Стандарт SQL:1999 (ISO/IEC 9075-2:1999) официально включил рекурсивные запросы в спецификацию языка SQL, определив синтаксис WITH RECURSIVE. Однако многие крупные СУБД (включая MySQL) внедрили эту возможность лишь в 2010-х годах. MySQL добавил поддержку рекурсивных CTE в версии 8.0 (2018 год), а PostgreSQL — значительно раньше, начиная с версии 8.4 (2009 год). В настоящее время рекурсивные запросы поддерживаются всеми основными реляционными СУБД: Oracle Database (с версии 11gR2 через CONNECT BY или WITH RECURSIVE), Microsoft SQL Server (с версии 2005), SQLite (с версии 3.8.3, 2014 год) и другими.

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

Рекурсивный запрос в SQL состоит из двух частей, объединённых оператором UNION ALL или UNION:

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

Синтаксис общего вида:

``sql WITH RECURSIVE cte_name (column_list) AS ( -- Базовый член SELECT ... UNION ALL -- Рекурсивный член SELECT ... FROM cte_name WHERE ... ) SELECT * FROM cte_name; ``

Пример: Поиск всех подчинённых сотрудника в иерархии «руководитель — подчинённый».

Таблица employees:

id	name	manager_id
1	Иванов	NULL
2	Петров	1
3	Сидоров	2
4	Кузнецов	1

Запрос для поиска всех подчинённых Иванова (id=1):

``sql WITH RECURSIVE subordinates AS ( SELECT id, name, manager_id FROM employees WHERE id = 1 -- Базовый член: сам Иванов UNION ALL SELECT e.id, e.name, e.manager_id FROM employees e INNER JOIN subordinates s ON e.manager_id = s.id -- Рекурсивный член: подчинённые ) SELECT * FROM subordinates; ``

Результат: Иванов, Петров, Сидоров, Кузнецов.

Виды рекурсивных запросов

Рекурсивные запросы классифицируются по типу обрабатываемых данных и способу завершения рекурсии:

Иерархические запросы — обработка древовидных структур с одним родителем (например, организационная структура, категории товаров). Характеризуются направлением обхода: сверху вниз (от корня к листьям) или снизу вверх (от листьев к корню).
Графовые запросы — поиск путей в графах с возможными циклами (например, социальные сети, маршруты в транспортной сети). Для предотвращения бесконечной рекурсии при наличии циклов требуется дополнительная проверка (например, хранение уже посещённых узлов в массиве).
Рекурсивные агрегатные запросы — вычисление накопительных сумм или других агрегатов, где каждый шаг зависит от предыдущего (например, расчёт факториала, последовательности Фибоначчи, накопленного итога).

Применение

Рекурсивные запросы широко используются в различных областях:

Управление персоналом: построение организационных иерархий, поиск всех подчинённых или всех руководителей сотрудника.
Электронная коммерция: работа с многоуровневыми каталогами товаров (например, «Электроника» → «Компьютеры» → «Ноутбуки»).
Социальные сети: поиск друзей друзей (на глубину N), рекомендация контактов.
Логистика и транспорт: поиск кратчайшего пути в графе дорог (алгоритм Дейкстры может быть реализован через рекурсивные запросы, хотя обычно это неоптимально).
Генеалогия: построение родословных деревьев.
Обработка естественного языка: разбор синтаксических деревьев предложений.
Финансы: расчёт сложных процентов, амортизации, накопленных итогов.

Ограничения и особенности

Производительность: рекурсивные запросы могут быть медленными на больших наборах данных, так как каждая итерация требует отдельного сканирования таблицы. Оптимизаторы СУБД не всегда могут эффективно построить план выполнения.
Глубина рекурсии: большинство СУБД устанавливают максимальную глубину рекурсии (например, по умолчанию 100 в PostgreSQL, 1000 в MySQL). При превышении запрос завершается с ошибкой. Параметр можно изменить (например, SET max_recursive_iterations = 1000; в MySQL).
Циклы: при наличии циклов в данных (например, A подчиняется B, а B подчиняется A) рекурсивный запрос без защиты от зацикливания войдёт в бесконечный цикл. Для предотвращения этого используют проверку на уже посещённые узлы (обычно через массив или строку с идентификаторами).
Порядок обхода: стандартный SQL не гарантирует порядок обхода дерева (в глубину или в ширину). Для конкретного порядка требуется явное указание (например, ORDER BY с уровнем вложенности).
Отсутствие поддержки в некоторых СУБД: хотя рекурсивные запросы стали стандартом, некоторые старые версии СУБД (например, MySQL до 8.0) их не поддерживали, что вынуждало разработчиков использовать хранимые процедуры или внешние скрипты.

Критика и альтернативы

Рекурсивные запросы критикуются за сложность отладки и низкую производительность на глубоких иерархиях. Альтернативными подходами являются:

Хранимые процедуры — позволяют реализовать рекурсию с явным управлением итерациями, но требуют больше кода и менее декларативны.
Вложенные множества (Nested Sets) — модель хранения иерархических данных, где каждому узлу присваиваются левый и правый ключи, что позволяет выбирать поддеревья одним запросом без рекурсии. Однако этот подход сложен в обслуживании при частых вставках и удалениях.
Материализованные пути (Materialized Paths) — хранение полного пути от корня к узлу в строковом поле (например, 1/2/3/). Поиск подчинённых выполняется через LIKE, что может быть медленным на больших данных.
Графовые базы данных (например, Neo4j) — специализированные СУБД, которые обрабатывают иерархии и графы на порядок эффективнее реляционных с рекурсивными запросами.
Внешние языки программирования — выполнение рекурсивной логики на стороне приложения (Python, Java) с использованием нескольких SQL-запросов.

Интересные факты

В стандарте SQL:1999 рекурсивные запросы назывались «рекурсивными обобщёнными табличными выражениями» (Recursive Common Table Expressions).
В Oracle Database исторически использовался собственный синтаксис CONNECT BY PRIOR для иерархических запросов, который появился раньше стандарта SQL:1999. Начиная с Oracle 11gR2, поддерживается и стандартный WITH RECURSIVE.
Рекурсивные запросы можно использовать для генерации последовательностей чисел (например, для заполнения календаря датами) без создания физической таблицы.
В PostgreSQL рекурсивные запросы могут быть использованы для реализации алгоритма обхода графа в ширину (BFS) при правильном порядке добавления строк.

Источники

ISO/IEC 9075-2:1999, Information technology — Database languages — SQL — Part 2: Foundation (SQL/Foundation).
PostgreSQL Documentation, Chapter 7.8: WITH Queries (Common Table Expressions).
MySQL 8.0 Reference Manual, Section 13.2.15: WITH (Common Table Expressions).
Microsoft SQL Server Documentation, WITH common_table_expression (Transact-SQL).
C. J. Date, «An Introduction to Database Systems», 8th Edition, Addison-Wesley, 2004.
Joe Celko, «Joe Celko’s SQL for Smarties: Advanced SQL Programming», 5th Edition, Morgan Kaufmann, 2014.

BFOmetr — база данных и аналитика по компаниям России.

На главную BFOmetr →