re:re:actable
Урок 043 минуты чтения

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

На этой странице
Кратко

Рекурсивный CTE (WITH RECURSIVE) повторно выполняет запрос, подставляя в него результат предыдущего шага. Он состоит из якоря (начальные строки) и рекурсивной части, которая ссылается на сам CTE, соединённых через UNION ALL (или UNION, который убирает дубли и помогает против циклов). Итерации продолжаются, пока рекурсивная часть не вернёт пустой набор. Применения: деревья и иерархии произвольной глубины (категории, комментарии, оргструктура), обход графов, генерация последовательностей. Обязательно предусматривают защиту от циклов — ограничение глубины, путь посещённых узлов или CYCLE (PostgreSQL 14+).

Вопрос

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

Структура

WITH RECURSIVE cte AS (
  -- якорь
  SELECT ...
  UNION ALL
  -- рекурсивная часть, ссылается на cte
  SELECT ... FROM table JOIN cte ON ...
)
SELECT * FROM cte;

Дерево категорий вниз

CREATE TABLE categories (
  id bigint PRIMARY KEY,
  parent_id bigint REFERENCES categories (id),
  name text NOT NULL
);
 
-- все подкатегории «Электроники» с уровнем и путём
WITH RECURSIVE tree AS (
  SELECT id, parent_id, name, 1 AS depth, name::text AS path
  FROM categories
  WHERE id = 1
 
  UNION ALL
 
  SELECT c.id, c.parent_id, c.name, t.depth + 1, t.path || ' / ' || c.name
  FROM categories c
  JOIN tree t ON c.parent_id = t.id
)
SELECT * FROM tree ORDER BY path;
1 | NULL | Электроника                  | 1 | Электроника
2 | 1    | Ноутбуки                     | 2 | Электроника / Ноутбуки
5 | 2    | Игровые                      | 3 | Электроника / Ноутбуки / Игровые

Путь вверх — хлебные крошки

WITH RECURSIVE breadcrumbs AS (
  SELECT id, parent_id, name, 0 AS lvl FROM categories WHERE id = 5
  UNION ALL
  SELECT c.id, c.parent_id, c.name, b.lvl + 1
  FROM categories c
  JOIN breadcrumbs b ON c.id = b.parent_id
)
SELECT name FROM breadcrumbs ORDER BY lvl DESC;
-- Электроника → Ноутбуки → Игровые

Защита от циклов

-- ограничение глубины
... WHERE t.depth < 20
 
-- PostgreSQL 14+: встроенная проверка
WITH RECURSIVE graph AS (
  SELECT id, parent_id FROM nodes WHERE id = 1
  UNION ALL
  SELECT n.id, n.parent_id FROM nodes n JOIN graph g ON n.parent_id = g.id
) CYCLE id SET is_cycle USING path
SELECT * FROM graph WHERE NOT is_cycle;

Без защиты цикл в данных (A → B → A) приведёт к бесконечному запросу.

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

WITH RECURSIVE n AS (
  SELECT 1 AS i
  UNION ALL
  SELECT i + 1 FROM n WHERE i < 10
)
SELECT i FROM n;
-- в PostgreSQL проще: SELECT generate_series(1, 10)

Альтернативы для деревьев

МодельПлюсыМинусы
Adjacency list (parent_id) + рекурсияПростые вставки и перемещенияРекурсия при чтении
Materialized path ('1/2/5', тип ltree)Быстрый поиск поддерева по префиксуПеремещение = обновление путей
Closure table (все пары предок–потомок)Быстрые запросы любой глубиныМного строк, сложнее вставки

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

  • Рекурсия без условия остановки или защиты от циклов.
  • UNION ALL в графе с несколькими путями к узлу — экспоненциальный рост строк.
  • Нет индекса по parent_id — каждая итерация сканирует таблицу.
  • Загружать дерево по уровням из приложения (N+1) вместо одного рекурсивного запроса.

Что важно помнить

  • Якорь + рекурсивная часть + UNION ALL.
  • Остановка — когда новая итерация пуста.
  • Глубина, путь или CYCLE защищают от бесконечной рекурсии.

Мини-шпаргалка

  • WITH RECURSIVE t AS (anchor UNION ALL step JOIN t).
  • depth + 1, path || ' / ' || name.
  • CYCLE id SET is_cycle USING path (PG 14+).
  • Индекс по parent_id.

Документация

PostgreSQL: Recursive Queries, PostgreSQL: ltree.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам