Информатика · объяснение и практика

Рекурсивный CTE: начальные строки, шаг и условие остановки

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

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Таблицы, базы данных и SQL · Учебная карта

В маршруте Запросы, ограничения и устойчивое чтение · 10 тем

Главная мысль

Рекурсивный CTE строит результат из начального набора и повторного запроса к уже найденным строкам. Для дерева удобно двигаться от родителя к детям, сохраняя глубину. Остановку обеспечивает структура данных или явно заданное ограничение.

Какие строки запускают обход

Представим таблицу разделов с полями id и parent_id. У корневого раздела родителя нет, у остальных записан идентификатор вышестоящей темы. Чтобы собрать ветку выбранного раздела, сначала выбирают только его строку. Эта нерекурсивная часть называется начальной: без неё обходу неоткуда начать движение.

Рекурсивная часть соединяет текущий найденный раздел с таблицей по условию child.parent_id = current.id. Она выдаёт дочерние строки и увеличивает сохранённую глубину на единицу. Одно повторение не означает обработку всей таблицы: следующий шаг зависит от строк, которые действительно удалось получить ранее.

Прослеживаем небольшое дерево

Пусть у раздела 12 два подраздела: 18 и 21. У подраздела 18 есть дочерняя тема 25, у остальных детей нет. Начальный набор содержит 12 с глубиной ноль. Затем появляются 18 и 21 с глубиной один, после них — 25 с глубиной два.

Полученные уровни описывают расстояние от выбранного корня, а не гарантированный порядок строк на экране. Для вывода по уровням нужен внешний ORDER BY depth, id. Порядок обработки очереди и порядок окончательного результата являются разными вопросами; полагаться на случайный порядок плана запроса нельзя.

Пример

Ветка: 12 → 18 → 25 и 12 → 21. Результат с сортировкой по глубине: (12,0), (18,1), (21,1), (25,2).

Тема 25 лежит на два ребра ниже корня. Внешняя сортировка ставит её после обоих разделов первого уровня.

Где возникает бесконечное продолжение

В настоящих данных ошибочная ссылка может замкнуть цикл: один раздел оказывается предком самого себя. UNION ALL сохраняет повторные строки, поэтому обход такого графа способен продолжаться без полезного продвижения. Перед выполнением следует установить предел глубины или вести путь уже посещённых идентификаторов.

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

От чтения к действию

А теперь — вы

При обходе цикла строка содержит id и растущую depth. Почему замена UNION ALL на UNION может не остановить повторения?

Частые вопросы

CTE сохраняет отдельную таблицу навсегда?

Нет. Здесь именованный промежуточный набор существует в рамках одного SQL-выражения.

Почему UNION не всегда убирает цикл?

Он сравнивает целые строки. Один узел с разными значениями глубины образует разные строки.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться