Увійти Реєстрація
Вакансії
Вакансії Laravel Компанії Статистика
Підготовка
Як підготуватися Співбесіди Тестування Документація
Блог
Всі статті Серії
Екосистема
Пакети Ресурси Проєкти Інструменти Події Відео
Інше
Про нас Реклама

Як обходити дерева й графи рекурсивним CTE і не потрапити в нескінченний цикл?

WITH RECURSIVE складається з двох частин, об'єднаних UNION ALL:

  • початкова - стартові рядки;
  • рекурсивна - посилається на сам CTE і додає наступний рівень, доки не поверне порожній результат.

Усі підкатегорії категорії з глибиною:

WITH RECURSIVE tree AS (
    SELECT id, parent_id, name, 1 AS depth
    FROM categories
    WHERE id = 10

    UNION ALL

    SELECT c.id, c.parent_id, c.name, t.depth + 1
    FROM categories c
    JOIN tree t ON c.parent_id = t.id
)
SELECT * FROM tree;

Шлях від вузла до кореня (хлібні крихти) - те саме в зворотному напрямку: JOIN tree t ON c.id = t.parent_id.

Проблема циклів. У дереві циклів немає, але в графі (рекомендації, залежності, «хто кого запросив») чи в зіпсованих даних (категорія стала батьком свого предка) рекурсія ніколи не завершиться - запит працюватиме до вичерпання пам'яті чи тайм-ауту.

PostgreSQL 14+: CYCLE - вбудоване виявлення циклів:

WITH RECURSIVE graph AS (
    SELECT id, parent_id FROM categories WHERE id = 10
    UNION ALL
    SELECT c.id, c.parent_id FROM categories c JOIN graph g ON c.parent_id = g.id
) CYCLE id SET is_cycle USING path
SELECT * FROM graph WHERE NOT is_cycle;

PostgreSQL сам відстежує шлях і зупиняє гілку, що повертається до вже відвіданого вузла.

SEARCH задає порядок обходу:

) SEARCH DEPTH FIRST BY id SET ordercol
SELECT * FROM tree ORDER BY ordercol;

DEPTH FIRST дає порядок, у якому зручно виводити дерево з відступами; BREADTH FIRST - рівень за рівнем.

До PG 14 - вручну: накопичувати масив відвіданих id і перевіряти NOT c.id = ANY(path).

Додаткові запобіжники:

  • обмеження глибини (WHERE t.depth < 20) - навіть з CYCLE захищає від неочікувано глибоких структур;
  • statement_timeout для таких запитів;
  • UNION замість UNION ALL прибирає дублікати рядків і теж обриває прості цикли, але дорожчий і не завжди достатній.

Продуктивність: індекс на parent_id обов'язковий - кожен рівень рекурсії шукає дітей за ним.

Альтернативи рекурсії для дерев, які часто читають і рідко змінюють: матеріалізований шлях (ltree), closure table, nested sets - вони дають піддерево одним простим запитом.

У Laravel рекурсивні CTE пишуть сирим SQL або через пакет staudenmeir/laravel-adjacency-list, що додає зв'язки descendants() і ancestors() на основі WITH RECURSIVE.

Докладніше в документації: WITH: виявлення циклів

Схожі питання