Recursive CTE на собеседовании Data Engineer

Зачем спрашивают на собесе DE

Recursive CTE — мощный инструмент в SQL для работы с иерархиями, графами, генерацией последовательностей. На собесе DE дадут одну из трёх классических задач: «найти всех подчинённых менеджера», «заполнить пропуски в датах», «найти связанные транзакции». Без recursive CTE это сделать тяжело или невозможно.

Главная боль без recursive CTE — DE пишет циклы в Python для иерархии 50k сотрудников, тратит час на full scan. Один recursive CTE — секунды.

Базовый синтаксис

WITH RECURSIVE cte_name AS (
    -- anchor (база)
    SELECT ...
    UNION ALL
    -- recursive (рекурсия — ссылается на сам CTE)
    SELECT ...
    FROM cte_name
    WHERE <условие остановки>
)
SELECT * FROM cte_name;

Логика:

1. Выполнить anchor — стартовый набор строк
2. Выполнить recursive часть, ссылаясь на текущий накопленный CTE
3. Объединить результат через UNION ALL
4. Повторять, пока recursive часть возвращает строки
5. Финальный SELECT работает с полным накопленным набором

UNION ALL (не UNION) — без дедупликации, порядок важен.

Иерархия: организационная структура

Таблица employees(id, name, manager_id). Найти всех подчинённых менеджера 1:

WITH RECURSIVE subordinates AS (
    -- anchor: прямые подчинённые
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE manager_id = 1

    UNION ALL

    -- recursive: подчинённые подчинённых
    SELECT e.id, e.name, e.manager_id, s.depth + 1
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates ORDER BY depth, id;

depth — глубина в иерархии, полезна для отладки и форматирования.

Обратный обход — найти всех руководителей сотрудника:

WITH RECURSIVE managers AS (
    SELECT id, name, manager_id, 1 AS lvl
    FROM employees WHERE id = 42
    UNION ALL
    SELECT e.id, e.name, e.manager_id, m.lvl + 1
    FROM employees e
    JOIN managers m ON e.id = m.manager_id
)
SELECT * FROM managers WHERE id <> 42;

Генерация дат

В Postgres / GP есть generate_series, в ClickHouse — arrayJoin. Если их нет (старые БД, специфические движки) — recursive CTE:

WITH RECURSIVE date_series AS (
    SELECT DATE '2026-01-01' AS d
    UNION ALL
    SELECT d + INTERVAL '1 day'
    FROM date_series
    WHERE d < DATE '2026-12-31'
)
SELECT d FROM date_series;

Полезно для left-join'а с фактами, чтобы заполнить пропуски (не было заказов в день — нулевая строка):

WITH RECURSIVE date_series AS (...)
SELECT
    d.d AS event_date,
    COALESCE(SUM(o.amount), 0) AS revenue
FROM date_series d
LEFT JOIN orders o ON DATE(o.created_at) = d.d
GROUP BY 1;

Графы и BFS

Таблица edges(from_id, to_id). Найти все вершины, достижимые из node 1 (BFS):

WITH RECURSIVE reachable AS (
    SELECT 1 AS node, 0 AS depth
    UNION ALL
    SELECT e.to_id, r.depth + 1
    FROM edges e
    JOIN reachable r ON e.from_id = r.node
)
SELECT DISTINCT node FROM reachable;

Грабля: циклы в графе → recursive выполнится бесконечно (или до лимита). Защита:

WITH RECURSIVE reachable AS (
    SELECT 1 AS node, 0 AS depth, ARRAY[1] AS path
    UNION ALL
    SELECT e.to_id, r.depth + 1, r.path || e.to_id
    FROM edges e
    JOIN reachable r ON e.from_id = r.node
    WHERE NOT (e.to_id = ANY(r.path))   -- не возвращаемся в посещённые
      AND r.depth < 10                   -- лимит глубины
)
SELECT DISTINCT node FROM reachable;

Или использовать SET-based check:

... WHERE e.to_id NOT IN (SELECT node FROM reachable)

Производительность и грабли

Recursive CTE не материализуется по умолчанию — каждая итерация делает запрос. На больших данных может быть медленным.

Memory: recursive часть накапливает результаты. На иерархиях 1М+ — OOM.

Postgres-specific: в Postgres CTE раньше всегда были optimization fence (материализовались). С 12+ — обычно inline. Recursive CTE — всегда отдельный nested loop, не inline.

Альтернативы:

• generate_series — для дат и чисел
• Loop в plpgsql — иногда быстрее на сложной логике
• Граф-БД (Neo4j) — для графовых задач большого размера
• Closure table — предвычисленная таблица всех путей

Частые ошибки

Без RECURSIVE. Postgres по стандарту требует WITH RECURSIVE. Без него — синтаксическая ошибка. MySQL 8+ — WITH RECURSIVE. SQL Server — WITH (без RECURSIVE), но обязателен UNION ALL.

UNION вместо UNION ALL. UNION дедуплицирует, может скрыть ошибки и сделать запрос медленным.

Без условия остановки. SELECT * FROM cte без WHERE в recursive части — бесконечная рекурсия. Postgres имеет max_recursion_depth (по умолчанию infinite), может зависнуть.

Цикл в графе. Без защиты от посещённых узлов — бесконечная рекурсия.

Использовать на 10М+ строк. Recursive CTE плохо масштабируется. Закрытая таблица (closure table) или специализированный движок.

Ожидать порядок в результате. Recursive CTE порядок не гарантирует. ORDER BY на финале или используй depth.

Modify CTE source mid-recursion. Изменения в исходной таблице во время выполнения CTE — undefined behavior.

Связанные темы

• Оконные функции на собесе DE
• Как написать рекурсивный CTE
• SQL для Data Engineer: собеседование
• Подготовка к собесу Data Engineer
• Greenplum на собесе DE

FAQ

Recursive CTE работает в ClickHouse?

С ограничениями (CH 22.x+). Для иерархий ClickHouse рекомендует другие подходы: денормализованные пути, dictionary с иерархией, или загружать готовые closure tables.

Что такое closure table?

Предвычисленная таблица (ancestor_id, descendant_id, depth). Заменяет recursive CTE на простой JOIN. Хороша на read-heavy с редкими изменениями иерархии.

Можно ли использовать recursive CTE для генерации тестовых данных?

Да. WITH RECURSIVE n AS (SELECT 1 AS i UNION ALL SELECT i+1 FROM n WHERE i<10000) SELECT i FROM n — генерит 10k строк. Удобно для бенчмарков.

Как остановить рекурсию по нестандартному условию?

Любой WHERE в recursive части. Можно по depth, по значению, по NOT IN previous, по комбинации.

Recursive CTE в Spark SQL?

Spark поддерживает с версии 3.4 (через spark.sql.legacy.allowRecursionInWith). Но recursive CTE в Spark — не стандарт; для иерархий обычно используют graphframes или итеративные join.

Это официальная информация?

Нет. Статья основана на стандарте SQL:1999, документации Postgres / GP / SQL Server / MySQL.

Тренируйте SQL — откройте тренажёр с 1500+ вопросами для собесов.