До сих пор все операции, которые мы изучали — селекция, проекция, JOIN, агрегация, оконные функции — имели общее свойство: число шагов запроса известно заранее. Ты пишешь запрос, оптимизатор строит план, и план — это конечный конвейер из понятных кирпичей. JOIN таблиц A и B — это один проход (с точки зрения алгебры). JOIN трёх таблиц — это два. Чтобы сделать пять — пишешь пять JOIN в коде.
Но что, если число шагов зависит от данных? Например: «найди всех, кто подчиняется Анне Громовой — на любой глубине». Один уровень — JOIN. Два уровня — два JOIN. Десять — десять. А если глубина дерева заранее неизвестна, и в одной ветке она 3, а в другой 7?
Здесь обычный SQL ломается. И здесь начинается рекурсия.
Где обычный JOIN перестаёт работать
Давай посмотрим на нашу таблицу employees — там 16 сотрудников, организованных в дерево через manager_id.
Посмотрим на иерархию сотрудников. id 1 — CEO Анна, корень дерева.
Анна (id=1) — корень, manager_id IS NULL. У неё в подчинении Борис (CTO) и Виктор (CFO). У Бориса — Галина и Дмитрий. У Галины — Елена, Феликс и Гриша. И так далее. Дерево имеет разную глубину в разных ветках.
Попробуем найти прямых подчинённых Анны — это легко:
Прямые подчинённые CEO — один JOIN, один уровень:
Два уровня вниз — уже два self-join:
Внуки Анны (подчинённые её подчинённых) — два JOIN:
А теперь представь, что тебя просят: «найди всех подчинённых Анны, на любой глубине». Сколько JOIN написать? Три? Пять? Двадцать?
Каждый уровень дерева — отдельный JOIN. Если глубина неизвестна, количество JOIN-ов нельзя зафиксировать в тексте запроса.
Можно, конечно, нагенерировать запрос с 50 JOIN-ами «на всякий случай». Это работает в учебнике, но в реальности убивает оптимизатор и всё равно ломается, если кто-то превысит 50 уровней. Нужен механизм, который сам останавливается, когда данные закончились.
Три класса задач, требующих рекурсии
-
Иерархии произвольной глубины. Сотрудники и менеджеры, категории и подкатегории товаров, треды комментариев, дерево файловой системы, BOM (bill of materials) в производстве.
-
Графы и обходы. Транспортная сеть, социальный граф, ссылки между документами, зависимости пакетов в npm. Задача — обойти весь связный компонент или найти путь от A до B.
-
Итеративные вычисления. Числа Фибоначчи, факториал, генерация серии дат «от X до Y», построение временных интервалов. Тут рекурсия используется как замена императивному циклу.
В первых двух случаях рекурсия необходима — другого способа корректно решить задачу в чистом SQL нет (без процедурного расширения вроде PL/pgSQL). В третьем — это удобный приём, который иногда заменяет генератор generate_series.
Категории товаров — тот же сюжет
Тот же шаблон встречается с категориями. В нашей вселенной categories тоже дерево: «Электроника» содержит «Ноутбуки», «Смартфоны», «Аксессуары». «Книги» содержит «Художественную литературу» и «Техническую». Каждая запись хранит parent_id.
Дерево категорий — двух уровней пока хватает, но в реальном e-commerce их может быть 5–7:
Если завтра «Ноутбуки» разделят на «Игровые», «Рабочие», «Ультрабуки», а у тех ещё подкатегории — запрос «выведи все товары категории Электроника и её потомков» уже не написать через фиксированный список JOIN. Нужен механизм, способный обходить дерево столько уровней, сколько потребуется.
Семантика: фикс-точка
Идея рекурсивного запроса в SQL формализуется так: мы определяем отношение, которое равно объединению двух частей:
- Anchor (база рекурсии) — стартовое множество кортежей.
- Recursive term — правило, которое из текущего отношения порождает новые кортежи.
И мы говорим: «бери текущее отношение, применяй правило, добавляй то, что получилось, повторяй, пока ничего нового не добавляется». Точка, в которой результат перестаёт расти, называется
На каждом шаге берём результат предыдущего шага и применяем к нему правило. Останавливаемся, когда правило ничего нового не даёт.
Это, по сути, императивный цикл, замаскированный под декларативное определение отношения. Но за этим маскарадом стоит математика: при разумных ограничениях (правило монотонно, данные конечны) фикс-точка существует и достижима за конечное число шагов.
Почему именно SQL-расширение, а не цикл в приложении
Можно ведь написать обход дерева в Python: вытащил корень → запросил детей → запросил детей детей → так до конца. Зачем тащить рекурсию внутрь базы?
Три причины:
- Один round-trip вместо N. При обходе дерева глубиной 10 на стороне приложения — это 10 запросов к базе, 10 сетевых обращений. Один рекурсивный запрос — один round-trip.
- Согласованность. Внутри одного запроса данные не меняются. Между десятью отдельными запросами кто-то может вставить, удалить, переподчинить — и ты соберёшь невалидную картинку.
- Оптимизатор может всё. Когда вся логика в SQL, планировщик видит её целиком, может выбрать индексы, переписать предикаты, оценить стоимость. Императивный цикл — это чёрный ящик для базы.
Что дальше
Мы согласились, что задача существует. В следующем уроке разберём синтаксис: как именно WITH RECURSIVE записывает «начало + правило шага» в SQL, что такое anchor и recursive term, чем UNION отличается от UNION ALL в рекурсивном CTE, и как PostgreSQL пошагово вычисляет фикс-точку.
Чек-лист урока
- Обычный SQL обрабатывает фиксированное число шагов. JOIN-ы прописываются явно в тексте запроса.
- Иерархии произвольной глубины, обходы графов, итеративные вычисления требуют переменного числа шагов.
- Рекурсия в SQL формализуется через фикс-точку: anchor + recursive term, повторяемые до стабилизации.
- Решение задачи внутри SQL вместо цикла в приложении даёт один round-trip, согласованный снимок и видимость для оптимизатора.