Рекурсивные CTE в PostgreSQL: иерархии, деревья и графы

Рекурсивные CTE позволяют обходить иерархические данные — деревья категорий, оргструктуры, файловые системы, граф социальных связей. Это мощный инструмент, заменяющий хранимые процедуры или многоуровневые JOIN.

Синтаксис WITH RECURSIVE

WITH RECURSIVE cte_name AS (
    -- Базовая часть: начальные строки (не рекурсивна)
    SELECT ...

    UNION ALL

    -- Рекурсивная часть: ссылается на cte_name
    SELECT ...
    FROM cte_name
    JOIN ... ON ...
)
SELECT * FROM cte_name;

Выполнение:

1. Запускается базовая часть → первый набор строк
2. К результату применяется рекурсивная часть → новые строки
3. Шаг 2 повторяется пока не вернётся ноль строк
4. Все строки объединяются в результат

Пример 1: Дерево категорий

-- Таблица categories
-- id | name          | parent_id
-- 1  | Электроника   | NULL
-- 2  | Смартфоны     | 1
-- 3  | Ноутбуки      | 1
-- 4  | iPhone        | 2
-- 5  | Android       | 2

WITH RECURSIVE category_tree AS (
    -- Базовая часть: корневые категории (без родителя)
    SELECT id, name, parent_id, 1 AS level, name::TEXT AS path
    FROM categories
    WHERE parent_id IS NULL

    UNION ALL

    -- Рекурсивная часть: дочерние категории
    SELECT c.id, c.name, c.parent_id, ct.level + 1, ct.path || ' > ' || c.name
    FROM categories c
    JOIN category_tree ct ON c.parent_id = ct.id
)
SELECT id, level, path, name
FROM category_tree
ORDER BY path;

Результат:

id | level | path                              | name
1  | 1     | Электроника                       | Электроника
3  | 2     | Электроника > Ноутбуки            | Ноутбуки
2  | 2     | Электроника > Смартфоны           | Смартфоны
4  | 3     | Электроника > Смартфоны > iPhone  | iPhone
5  | 3     | Электроника > Смартфоны > Android | Android

Пример 2: Оргструктура — найти всех подчинённых

-- employees: id | name | manager_id
-- Найти всех подчинённых менеджера с id = 5

WITH RECURSIVE subordinates AS (
    -- Базовая часть: сам менеджер
    SELECT id, name, manager_id, 0 AS depth
    FROM employees
    WHERE id = 5

    UNION ALL

    -- Рекурсивная часть: их подчинённые
    SELECT e.id, e.name, e.manager_id, s.depth + 1
    FROM employees e
    JOIN subordinates s ON e.manager_id = s.id
)
SELECT id, name, depth
FROM subordinates
WHERE id <> 5  -- исключить самого менеджера
ORDER BY depth, name;

Пример 3: Путь до корня (bottom-up)

-- Найти цепочку категорий от конкретной до корня
WITH RECURSIVE path_to_root AS (
    -- Начинаем с листовой категории
    SELECT id, name, parent_id, 1 AS level
    FROM categories
    WHERE id = 4  -- iPhone

    UNION ALL

    -- Поднимаемся к родителю
    SELECT c.id, c.name, c.parent_id, p.level + 1
    FROM categories c
    JOIN path_to_root p ON c.id = p.parent_id
)
SELECT id, name, level
FROM path_to_root
ORDER BY level DESC;
-- Результат: Электроника → Смартфоны → iPhone

Пример 4: Числовые последовательности

Рекурсивные CTE полезны для генерации рядов:

-- Сгенерировать числа от 1 до 10
WITH RECURSIVE nums AS (
    SELECT 1 AS n
    UNION ALL
    SELECT n + 1 FROM nums WHERE n < 10
)
SELECT n FROM nums;

-- Fibonacci
WITH RECURSIVE fib AS (
    SELECT 0 AS a, 1 AS b
    UNION ALL
    SELECT b, a + b FROM fib WHERE b < 1000
)
SELECT a AS fibonacci FROM fib;

Для последовательностей дат PostgreSQL имеет generate_series() — используйте её вместо рекурсии.

Пример 5: Граф — найти все маршруты

-- Таблица flights: from_city | to_city | price
-- Найти все маршруты из Москвы в любой город (с пересадками)

WITH RECURSIVE routes AS (
    -- Прямые рейсы из Москвы
    SELECT from_city, to_city, price, ARRAY[from_city, to_city] AS visited, 1 AS stops
    FROM flights
    WHERE from_city = 'Москва'

    UNION ALL

    -- Добавляем пересадку
    SELECT r.from_city, f.to_city, r.price + f.price,
           r.visited || f.to_city, r.stops + 1
    FROM routes r
    JOIN flights f ON f.from_city = r.to_city
    WHERE f.to_city <> ALL(r.visited)  -- защита от циклов
      AND r.stops < 3                   -- ограничение глубины
)
SELECT from_city, to_city, price, visited AS path, stops
FROM routes
WHERE to_city = 'Владивосток'
ORDER BY price;

Защита от бесконечной рекурсии

Всегда ограничивайте глубину или используйте защиту от циклов:

-- Ограничение уровня
WHERE level < 10

-- Массив посещённых узлов (граф с циклами)
WHERE target_id <> ALL(visited_nodes)

-- Глобальная защита PostgreSQL
SET max_recursive_cte_iterations = 1000;

Без ограничений рекурсия будет выполняться до max_recursive_cte_iterations (дефолт: без лимита — ваш запрос зависнет).

Оптимизация рекурсивных CTE

-- Плохо: рекурсия по всей таблице с огромным фильтром в конце
WITH RECURSIVE tree AS (...)
SELECT * FROM tree WHERE level = 5;

-- Лучше: фильтруй как можно раньше внутри рекурсии
WITH RECURSIVE tree AS (
    SELECT ... WHERE category_type = 'active'  -- фильтр в базовой части
    UNION ALL
    SELECT ... WHERE level < 10                 -- ограничение в рекурсивной
)
SELECT * FROM tree;

Рекурсивные CTE в PostgreSQL материализуются — PostgreSQL не встраивает их план в основной запрос. Это значит, что индексы на полях WHERE в основном SELECT не помогут.

Когда рекурсивный CTE лучше альтернатив

Расширение ltree (PostgreSQL) — специализированное решение для иерархических данных с мощными индексами. Рекурсивный CTE — универсальный инструмент.

Итог

Рекурсивные CTE — единственный стандартный способ в SQL обходить данные переменной глубины. Ключевые моменты:

• Базовая часть (якорь) выполняется один раз
• Рекурсивная часть выполняется пока возвращает строки
• Всегда ограничивайте глубину или защищайтесь от циклов
• Используйте level, path, visited для отслеживания прогресса
• Для больших иерархий (миллионы узлов) рассмотрите ltree или Closure Table