Исполняемые доки SQLite: Рекурсивные CTE

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

Это запрос с WITH RECURSIVE, который собирает результат, ссылаясь сам на себя. Состоит из двух частей, склеенных через UNION ALL: якорный запрос (anchor) задаёт стартовые строки, а рекурсивный — добавляет новые на основе предыдущего шага. SQLite повторяет рекурсивную часть до тех пор, пока она не перестанет возвращать новые строки.

Q: Когда стоит использовать WITH RECURSIVE в SQLite?

Когда нужно пройти по дереву или графу — сотрудники и руководители, категории и подкатегории, ветки комментариев — либо сгенерировать последовательность: все даты в диапазоне, числа от 1 до 100. Обычные JOIN спасают, если глубина 1-2 уровня. А вот когда глубина заранее неизвестна, без рекурсивного CTE не обойтись.

Q: Как избежать бесконечного цикла в рекурсивном CTE?

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

Рекурсия в SQL звучит странно — пока ты её не увидишь

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

Структура у такого запроса всегда одна и та же:

WITH RECURSIVE name(columns) AS (
    -- якорь: начальные строки
    SELECT ...
    UNION ALL
    -- рекурсия: строки, полученные из предыдущего шага
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

Сверху — якорный запрос, посередине — UNION ALL, снизу — рекурсивная часть. SQLite один раз выполняет якорь, а затем гоняет рекурсивную часть по кругу: каждая новая итерация работает со строками, полученными на предыдущем шаге. Как только новых строк не появляется — рекурсия останавливается.

Считаем от 1 до 10

Самый простой пример рекурсивного CTE — сгенерировать числовой ряд. Никаких таблиц для этого не нужно:

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10
)
SELECT n FROM counter;

Разберём по шагам:

Якорная часть выдаёт одну строку: n = 1.
Рекурсивный шаг берёт эту строку, считает n + 1 = 2, проверяет условие 2 < 10 — оно истинно, значит строка остаётся.
На следующей итерации из n = 2 получаем n = 3. И так далее.
Когда n доходит до 10, условие 10 < 10 ложно, рекурсивный шаг не возвращает ни одной строки, и SQLite останавливается.

Условие WHERE n < 10 — это и есть условие остановки. Без него запрос превратится в бесконечный цикл.

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

Та же логика, но с реальной пользой — заполнить все дни в заданном диапазоне, включая те, по которым ничего не произошло:

WITH RECURSIVE days(d) AS (
    SELECT date('2024-01-01')
    UNION ALL
    SELECT date(d, '+1 day') FROM days WHERE d < '2024-01-07'
)
SELECT d FROM days;

Обычно такую серию дат потом делают через LEFT JOIN с таблицей событий — чтобы корректно посчитать дни, в которых событий не было. Простой GROUP BY date просто пропустит пустые дни, а серия дат даёт строку на каждый день, есть события или нет.

Обход дерева «родитель — потомок»

Классический случай для рекурсивного CTE. Возьмём таблицу сотрудников, где каждая строка ссылается на своего руководителя:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE org(id, name, manager_id, depth) AS (
    SELECT id, name, manager_id, 0
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, org.depth + 1
    FROM employees e
    JOIN org ON e.manager_id = org.id
)
SELECT printf('%.*c%s', depth * 2, ' ', name) AS tree
FROM org;

Якорь выбирает корень — сотрудника без руководителя. Рекурсивная часть джойнит таблицу employees обратно с самим CTE и находит всех, чей manager_id уже есть в id нашего CTE. Каждая итерация — это шаг на уровень глубже. Поле depth — это просто счётчик, чтобы делать отступы при выводе.

Такой иерархический запрос работает с деревьями любой глубины. Хоть два уровня, хоть десять — сам запрос остаётся прежним.

Как найти всех предков конкретной строки

Развернём направление обхода. Теперь идём не сверху вниз от корня, а снизу вверх — от конкретного сотрудника по всей цепочке его руководителей:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE chain(id, name, manager_id) AS (
    SELECT id, name, manager_id
    FROM employees
    WHERE name = 'Diego'
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN chain ON chain.manager_id = e.id
)
SELECT name FROM chain;

Якорь — это сотрудник, с которого мы стартуем. Каждый рекурсивный шаг поднимается к руководителю. SQLite останавливается, когда добирается до корня: manager_id IS NULL, и join перестаёт что-либо находить.

Этот паттерн пригождается для хлебных крошек, древовидных комментариев, путей по категориям — словом, везде, где нужно «пройти вверх до самой вершины».

Условия остановки и бесконечный цикл в рекурсивном CTE

Самая частая ошибка — забыть условие остановки или написать такое, которое никогда не сработает. Сравните:

-- Выполняется бесконечно:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

Здесь нет ни одного WHERE, который когда-нибудь вернул бы пустой результат. SQLite с радостью будет считать до бесконечности.

Две привычки, которые спасают:

Всегда добавляйте в рекурсивную часть WHERE, ограничивающий рост.
На время отладки подстраховывайтесь LIMIT во внешнем SELECT — если вы ошиблись с условием выхода, запрос хотя бы завершится.

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter
)
SELECT n FROM counter LIMIT 5;

Сам CTE здесь не имеет границ, но LIMIT 5 во внешнем запросе останавливает выборку раньше времени. SQLite достаточно умён, чтобы не уходить в рекурсию глубже, чем требует LIMIT. Удобно для экспериментов, но в продакшене так делать не стоит — нужно нормальное условие остановки.

Циклы в графах

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

CREATE TABLE edges (a INTEGER, b INTEGER);
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (3, 4);

WITH RECURSIVE walk(node, path) AS (
    SELECT 1, ',1,'
    UNION ALL
    SELECT e.b, path || e.b || ','
    FROM edges e
    JOIN walk ON e.a = walk.node
    WHERE instr(path, ',' || e.b || ',') = 0
)
SELECT node, path FROM walk;

path — это строка с разделителями-запятыми, в которой перечислены уже пройденные узлы. Перед добавлением нового узла условие WHERE проверяет, что его там ещё нет. Без этой защиты цикл 1 → 2 → 3 → 1 крутился бы бесконечно.

В SQL нет встроенного «множества посещённых» — его приходится собирать самому, обычно в виде строки или через джойн с уже накопленной частью CTE.

Рекурсивный CTE против self join

Если нужно спуститься всего на один-два уровня, self join проще и быстрее:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

SELECT e.name AS employee, m.name AS manager
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

Этот вариант покрывает задачу «кто непосредственный руководитель каждого сотрудника». А вот если нужно вытащить «всех, кто подчиняется Аде по цепочке, на любой глубине» — а глубина заранее неизвестна, — то по-человечески это решается только через рекурсивный CTE. Выбирайте инструмент под нужную глубину:

Фиксированная и небольшая глубина: self join, ну максимум два-три.
Неизвестная или произвольная глубина: WITH RECURSIVE.

Как это устроено в голове

Рекурсивный CTE в SQLite — это, по сути, цикл, только записанный декларативно:

Якорный запрос — стартовое значение цикла.
Рекурсивная часть — тело цикла: из текущих строк получаем следующую порцию.
Условие остановки — выход из цикла: как только запрос возвращает ноль строк, всё, приехали.
UNION ALL копит результат и собирает его в финальную выборку.

Когда эта картинка щёлкнет в голове, синтаксис перестаёт казаться странным. Вы просто пишете for-цикл на SQL.

Что дальше: индексы

Рекурсивный CTE прошивает кучу строк, и join внутри рекурсивного шага выполняется на каждой итерации. Если по колонке join нет индекса — производительность улетает в пол моментально. Про индексы поговорим в следующей главе, и manager_id — как раз тот случай, когда индекс реально окупается.

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

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

Это запрос с WITH RECURSIVE, который собирает результат, ссылаясь сам на себя. Состоит из двух частей, склеенных через UNION ALL: якорный запрос (anchor) задаёт стартовые строки, а рекурсивный — добавляет новые на основе предыдущего шага. SQLite повторяет рекурсивную часть до тех пор, пока она не перестанет возвращать новые строки.

Когда стоит использовать WITH RECURSIVE в SQLite?

Когда нужно пройти по дереву или графу — сотрудники и руководители, категории и подкатегории, ветки комментариев — либо сгенерировать последовательность: все даты в диапазоне, числа от 1 до 100. Обычные JOIN спасают, если глубина 1-2 уровня. А вот когда глубина заранее неизвестна, без рекурсивного CTE не обойтись.

Как избежать бесконечного цикла в рекурсивном CTE?

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

Связанные концепции

Рекурсивные CTE в SQLite: WITH RECURSIVE на примерах