Рекурсивные запросы в PostgreSQL: Иерархии, графы и не только

Рекурсивные запросы — мощный инструмент PostgreSQL для работы с иерархическими структурами и графами. Они позволяют обрабатывать данные, где элементы связаны друг с другом через родительско-дочерние отношения, например, организационные структуры, деревья категорий или пути в социальных сетях. В этой статье мы разберем, как работают рекурсивные CTE (Common Table Expressions), их синтаксис, примеры использования и подводные камни.

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

Рекурсивный CTE (Common Table Expression) — это временный результат запроса, который может ссылаться на самого себя. Он состоит из двух частей:

1. Нерекурсивный член (Anchor Member) — начальный запрос, возвращающий базовый набор данных.
2. Рекурсивный член (Recursive Member) — часть, которая ссылается на CTE и расширяет результат до достижения условия остановки.

Синтаксис:

WITH RECURSIVE cte_name AS (
    -- Нерекурсивный член
    SELECT ... FROM ...
    UNION ALL
    -- Рекурсивный член
    SELECT ... FROM cte_name JOIN ...
)
SELECT * FROM cte_name;

Пример 1: Иерархия сотрудников

Представим таблицу employees, где каждый сотрудник может иметь менеджера:

CREATE TABLE employees (
    id INT PRIMARY KEY,
    name VARCHAR(50),
    manager_id INT REFERENCES employees(id)
);

Задача: Найти всех подчиненных сотрудника с id = 1, включая косвенных.

Решение:

WITH RECURSIVE subordinates AS (
    -- Anchor Member: начальный сотрудник (менеджер)
    SELECT id, name, manager_id, 1 AS depth
    FROM employees
    WHERE id = 1
    UNION ALL
    -- Recursive Member: подчиненные на каждом уровне
    SELECT e.id, e.name, e.manager_id, s.depth + 1
    FROM employees e
    INNER JOIN subordinates s ON e.manager_id = s.id
)
SELECT * FROM subordinates;

Результат будет включать все уровни подчинения с указанием глубины (depth).

Как это работает?

1. Шаг 1: Выполняется нерекурсивный член. Результат — начальная строка (сотрудник с id = 1).
2. Шаг 2: Рекурсивный член объединяется с текущим результатом CTE. На каждой итерации добавляются подчиненные предыдущего уровня.
3. Шаг 3: Процесс повторяется, пока рекурсивный член не вернет пустой набор.

Пример 2: Вычисление факториала

Рекурсивные запросы можно использовать и для математических вычислений. Например, факториал числа 5:

WITH RECURSIVE factorial(n, result) AS (
    SELECT 5, 1 -- Начальное значение: 5! = 5 * 4 * ... * 1
    UNION ALL
    SELECT n - 1, result * n
    FROM factorial
    WHERE n > 1
)
SELECT result FROM factorial WHERE n = 1;

Результат: 120.

Осторожно: Бесконечные циклы!

Если иерархия содержит циклы (например, сотрудник A подчиняется B, а B подчиняется A), запрос может зациклиться. Чтобы избежать этого:

• Используйте массив для отслеживания посещенных узлов.
• Ограничьте глубину рекурсии.

Пример с проверкой циклов:

WITH RECURSIVE hierarchy AS (
    SELECT id, name, manager_id, ARRAY[id] AS path
    FROM employees
    WHERE id = 1
    UNION ALL
    SELECT e.id, e.name, e.manager_id, h.path || e.id
    FROM employees e
    JOIN hierarchy h ON e.manager_id = h.id
    WHERE NOT e.id = ANY(h.path) -- Предотвращение циклов
)
SELECT * FROM hierarchy;

Оптимизация и ограничения

• Производительность: Рекурсивные запросы могут быть медленными на больших данных. Для деревьев используйте специализированные подходы (например, Nested Sets).
• Глубина рекурсии: PostgreSQL ограничивает глубину рекурсии параметром max_recursive_iterations (по умолчанию 100000). При необходимости его можно изменить.

Заключение

Рекурсивные CTE в PostgreSQL — гибкий инструмент для обработки иерархий и графов. Они позволяют:

• Строить древовидные структуры.
• Находить пути в графах.
• Решать задачи, требующие итеративных вычислений.

Однако важно помнить о возможных циклах и оптимизировать запросы для больших наборов данных. Используйте рекурсию там, где она действительно упрощает логику, но не забывайте о альтернативах, таких как материализованные пути или расширение ltree.