WITH RECURSIVE: структура и условие завершения

Генерация числового диапазона и структура WITH RECURSIVE

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

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

Якорный запрос (anchor SELECT) — нерекурсивный SELECT, который выполняется ровно один раз на старте и формирует начальный набор строк. 2.

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

Сформируем последовательность целых чисел от 1 до 5 без обращения к физическим таблицам базы:

WITH RECURSIVE seq(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1
    FROM seq
    WHERE n < 5
)
SELECT n FROM seq ORDER BY n ASC;

Результат запроса:

n
1
2
3
4
5

Механизм выполнения этого запроса в SQLite опирается на внутреннюю рабочую очередь:

• Шаг 1 (инициализация): движок выполняет якорную ветку SELECT 1 и помещает полученную строку (1) в очередь строк для обработки.
• Шаг 2 (первая итерация): из очереди извлекается одна строка (1) и вставляется в результирующую виртуальную таблицу seq. Рекурсивный SELECT выполняется только по этой извлечённой строке: условие WHERE 1 < 5 истинно, вычисляется выражение 1 + 1. Полученная строка (2) добавляется в конец очереди.
• Шаги 3–5: последовательно извлекаются строки (2), (3) и (4). Каждая извлекаемая строка переносится в результирующую таблицу seq, проверяется предикатом n < 5 и порождает строки (3), (4) и (5), которые дописываются в очередь.
• Шаг 6 (завершение): из очереди извлекается строка (5) и записывается в таблицу seq. Для неё проверяется предикат WHERE 5 < 5. Условие ложно: рекурсивный SELECT не возвращает строк, в очередь больше ничего не добавляется. Очередь пуста, рекурсия завершена.

Внешний ORDER BY n ASC здесь обязателен. Порядок обработки строк в очереди является внутренней деталью реализации движка и без явной сортировки во внешнем запросе не гарантирует клиенту детерминированный порядок вывода строк.

Условие остановки и предотвращение бесконечной рекурсии

В показанном числовом генераторе границу вычислений задаёт секция WHERE внутри рекурсивного SELECT. Естественное завершение такого генератора происходит при полном опустошении внутренней рабочей очереди строк: когда рекурсивный шаг для текущей извлечённой строки не возвращает новых записей и очередь пустеет, выполнение останавливается (в запросах с внутренним LIMIT движок может прервать рекурсию ещё раньше, не дожидаясь исчерпания очереди).

Распространённая ошибка при ограничении диапазона — неверно выбранный оператор сравнения (ошибка на единицу, или off-by-one). Изменим строгое неравенство n < 5 на нестрогое n <= 5:

WITH RECURSIVE seq(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1
    FROM seq
    WHERE n <= 5
)
SELECT n FROM seq ORDER BY n ASC;

Результат выполнения:

n
1
2
3
4
5
6

В выборку попало число 6. Причина кроется в моменте проверки: предикат WHERE проверяет текущее значение n, извлечённое из очереди, а выражение SELECT n + 1 вычисляет уже следующее число. Когда из очереди была извлечена строка со значением 5, условие 5 <= 5 вернуло TRUE. Движок выполнил сложение 5 + 1 и записал в результат число 6.

Общее правило генерации диапазона с шагом +step: если мы хотим получить числа включительно до end_val, предикат должен проверять либо текущий элемент строгим неравенством WHERE n < end_val (при шаге 1), либо следующее формируемое значение WHERE n + step <= end_val.

Если условие остановки вообще не может быть достигнуто, запрос уходит в бесконечную генерацию. Например, при шаге n + 2 от 1 с условием WHERE n != 10 нечётные числа никогда не совпадут с 10. В SQLite нет встроенного небольшого ограничения глубины для WITH RECURSIVE (параметры максимальной глубины вложенности триггеров к рекурсивным CTE не применяются). Запрос с недостижимым условием будет выполняться непрерывно, пока его принудительно не прервёт внешний таймаут среды или исчерпание системной памяти.

Генерация динамического календаря дат через date()

В уроке 22 для заполнения временных пропусков привлекалась готовая таблица calendar. Однако создавать физическую таблицу в базе данных не всегда возможно или оправдано. С помощью WITH RECURSIVE непрерывный опорный календарь (календарный хребет, или date spine) генерируется прямо внутри запроса.

Для расчёта дат в SQLite используется функция date(timestring, modifier). Прибавляя модификатор '+1 day', мы получаем следующий календарный день в текстовом формате YYYY-MM-DD (ISO-8601 в таймзоне UTC). Сгенерируем непрерывный недельный отрезок дат с 1 по 7 мая 2024 года включительно:

WITH RECURSIVE spine(cal_date) AS (
    SELECT '2024-05-01'
    UNION ALL
    SELECT date(cal_date, '+1 day')
    FROM spine
    WHERE cal_date < '2024-05-07'
)
SELECT cal_date FROM spine ORDER BY cal_date ASC;

Результат запроса:

cal_date
2024-05-01
2024-05-02
2024-05-03
2024-05-04
2024-05-05
2024-05-06
2024-05-07

Логика остановки здесь повторяет числовую последовательность: предикат WHERE cal_date < '2024-05-07' проверяет дату текущей строки. Когда обрабатывается '2024-05-06', условие истинно, и функция date('2024-05-06', '+1 day') формирует границу '2024-05-07'. Для строки '2024-05-07' условие '2024-05-07' < '2024-05-07' ложно, и генерация завершается ровно на 7 мая.

Шаблон генерации динамического календаря дат имеет вид:

WITH RECURSIVE calendar_spine(cal_date) AS (
    SELECT 'YYYY-MM-DD' AS cal_date
    UNION ALL
    SELECT date(cal_date, '+1 day')
    FROM calendar_spine
    WHERE cal_date < 'YYYY-MM-DD'
)
SELECT cal_date FROM calendar_spine;

Такой CTE возвращает набор строк, полностью эквивалентный выборке из постоянного справочника дат, но формируется на лету под конкретный интересующий диапазон анализа.

Восстановление пропусков: LEFT JOIN календаря с фактами платежей

Подготовим таблицу платежей payments с пропусками по дням и статическую таблицу static_calendar для проверки идентичности данных:

DROP TABLE IF EXISTS payments;
CREATE TABLE payments (
    payment_id INTEGER PRIMARY KEY,
    payment_date TEXT NOT NULL,
    amount INTEGER NOT NULL
);

INSERT INTO payments (payment_id, payment_date, amount) VALUES
(1, '2024-05-01', 150),
(2, '2024-05-01', 250),
(3, '2024-05-04', 500),
(4, '2024-05-06', 100);

DROP TABLE IF EXISTS static_calendar;
CREATE TABLE static_calendar (
    cal_date TEXT PRIMARY KEY
);

INSERT INTO static_calendar (cal_date) VALUES
('2024-05-01'),
('2024-05-02'),
('2024-05-03'),
('2024-05-04'),
('2024-05-05'),
('2024-05-06'),
('2024-05-07');

В таблице payments присутствуют платежи только за три дня: 1, 4 и 6 мая. Дни 2, 3, 5 и 7 мая пропущены. Если сгруппировать таблицу payments напрямую, в отчёте останется 3 строки, а пропущенные дни выпадут из динамики.

Сначала проверим, что сгенерированный нами CTE spine не содержит дат за пределами static_calendar. Оператор EXCEPT возвращает строки левого запроса, которых нет в правом:

WITH RECURSIVE spine(cal_date) AS (
    SELECT '2024-05-01'
    UNION ALL
    SELECT date(cal_date, '+1 day')
    FROM spine
    WHERE cal_date < '2024-05-07'
)
SELECT cal_date FROM spine
EXCEPT
SELECT cal_date FROM static_calendar;

Запрос возвращает пустой набор. Пустая разность доказывает включение: в CTE spine нет ни одной даты, которой не было бы в static_calendar. Полное равенство двух наборов гарантирует симметричная проверка (в обратную сторону разность static_calendar EXCEPT spine на этих данных также пуста).

Теперь построим аналитический отчёт с непрерывной подневной гранулярностью. Соединяем spine через LEFT JOIN с фактами платежей и суммируем суммы:

WITH RECURSIVE spine(cal_date) AS (
    SELECT '2024-05-01'
    UNION ALL
    SELECT date(cal_date, '+1 day')
    FROM spine
    WHERE cal_date < '2024-05-07'
)
SELECT
    s.cal_date,
    COALESCE(SUM(p.amount), 0) AS total_amount
FROM spine s
LEFT JOIN payments p ON s.cal_date = p.payment_date
GROUP BY s.cal_date
ORDER BY s.cal_date ASC;

Результат запроса:

cal_date	total_amount
2024-05-01	400
2024-05-02	0
2024-05-03	0
2024-05-04	500
2024-05-05	0
2024-05-06	100
2024-05-07	0

В итоговой таблице ровно 7 строк — по одной строке на каждый день недели. На дату 2024-05-01 сгруппировались два платежа (150 и 250), дав в сумме 400. Для дней 2024-05-02, 2024-05-03, 2024-05-05 и 2024-05-07 совпадений в таблице payments не нашлось: правая сторона вернула NULL, агрегат SUM(p.amount) вернул NULL, а функция COALESCE заменила его на 0.

Если бы вместо SUM(p.amount) был ошибочно применён COUNT(*), дни без платежей получили бы значение 1 (так как строка календаря существует). А если бы в запрос была добавлена фильтрация WHERE p.amount > 0, она отсекла бы NULL-строки и уничтожила результат LEFT JOIN, вернув выборку к исходным 3 дням.