Як обходити дерева й графи рекурсивним 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: виявлення циклів