Модуль: Подзапросы и CTE


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


CTE, которое ссылается само на себя

Иногда данные устроены как дерево: у сотрудника есть начальник, у начальника — свой начальник. Одним JOIN можно подняться только на один уровень, а глубина дерева заранее неизвестна.

Рекурсивное CTE — общее табличное выражение, которое обращается к самому себе. Оно состоит из двух частей, соединённых UNION ALL:

  1. Начальная часть — обычный SELECT, который даёт первые строки.
  2. Рекурсивная часть — SELECT, который берёт строки предыдущего шага и строит из них новые. Он ссылается на само CTE.

Рекурсивная часть повторяется, пока на очередном шаге не получится ни одной новой строки. Пишется WITH RECURSIVE.

SQLite поймёт рекурсивное CTE и без слова RECURSIVE, но в PostgreSQL и MySQL оно обязательно — пишите его всегда.

Части обычно соединяют через UNION ALL. Можно и через UNION: тогда уже полученные строки повторно не добавляются.


Простейший пример: числа от 1 до 5

WITH RECURSIVE nums(n) AS (
    SELECT 1                 -- начальная часть
    UNION ALL
    SELECT n + 1 FROM nums   -- рекурсивная часть
    WHERE n < 5
)
SELECT n FROM nums;

Результат:

n
1
2
3
4
5

Как это выполняется:

ШагЧто вычисляетсяНовые строки
0начальная часть SELECT 11
1из строки 1: 1 + 1, условие 1 < 5 выполнено2
2из строки 2: 2 + 13
3из строки 3: 3 + 14
4из строки 4: 4 + 15
5из строки 5: условие 5 < 5 не выполнено— (остановка)

Рекурсия — это старт, шаг и условие остановки.

Без WHERE n < 5 новые строки появлялись бы бесконечно, и запрос не завершился бы.

Иногда пишут LIMIT в основном запросе: SELECT n FROM nums LIMIT 3. Такой запрос остановится, но только если в основном запросе нет сортировки, группировки и агрегатов.

Запрос SELECT n FROM nums ORDER BY n LIMIT 3 без условия остановки зависнет: чтобы отсортировать строки, SQLite сначала попытается получить их все.

В SQLite LIMIT можно написать и внутри рекурсивной части — тогда он ограничит число строк CTE. Но надёжнее всего — условие остановки в WHERE.


Дерево подчинения

В таблице staff у каждого сотрудника указан начальник (boss_id). Выведем всех сотрудников школы с уровнем: директор — 1, завучи — 2 и так далее.

WITH RECURSIVE tree(id, name, position, lvl) AS (
    SELECT id, name, position, 1
    FROM staff
    WHERE boss_id IS NULL                -- начинаем с директора
    UNION ALL
    SELECT s.id, s.name, s.position, t.lvl + 1
    FROM staff s
    JOIN tree t ON s.boss_id = t.id      -- подчинённые тех, кто уже найден
)
SELECT lvl, name, position
FROM tree
ORDER BY lvl, name;

Результат:

lvlnameposition
1Ольга Николаевнадиректор
2Ирина Павловназавуч
2Сергей Петровичзавуч
3Анна Викторовнаучитель математики
3Мария Сергеевнаучитель русского языка
3Наталья Ивановнаучитель истории
3Павел Андреевичучитель информатики
4Дмитрий Олеговичлаборант

На каждом шаге рекурсивная часть находит сотрудников, чей начальник (s.boss_id) был найден на предыдущем шаге (t.id).

Когда подчинённых больше нет, новых строк не появляется, и запрос завершается сам. Это верно, пока в данных нет цикла: если А начальник Б, а Б начальник А, запрос с UNION ALL не завершится.

Чтобы идти по дереву вверх, от сотрудника к начальникам, соединение разворачивают: ищут сотрудника, чей id равен boss_id строки предыдущего шага.

Коротко

  • WITH RECURSIVE имя AS (начальная часть UNION ALL рекурсивная часть).
  • Рекурсивная часть ссылается на само CTE и повторяется, пока появляются новые строки.
  • Рекурсия нужна для деревьев и цепочек неизвестной глубины и для последовательностей чисел.