Обход графов в SQL

Три формы: дерево, DAG, граф

Прежде чем писать рекурсию, спроси себя: данные образуют дерево, DAG или общий граф? Ответ определяет, безопасен ли запрос по природе, нужен ли шаг дедупликации или он зависнет на реальных данных без явного тормоза. Один и тот же рекурсивный двигатель справляется с тремя структурами нарастающей опасности, все над edges(src, dst) (или manager_id, parent_id):

• дерево — у каждого узла один родитель (оргструктура, categories). Обход всегда завершается; риска циклов нет.
• DAG — направленный, без циклов, но у узла может быть много родителей (спецификация изделия: болт, используемый десятью сборками). Завершается, но один и тот же узел достигается многими путями, так что можешь посетить его многократно.
• общий граф — направленный, циклы возможны (графы зависимостей, подписки в соцсетях). Циклы значат, что ты обязан нести защиту от циклов, иначе обход не кончится никогда, ровно как в уроке 04.

Рабочая лошадка для всех трёх — накопление пути: неси массив посещённых узлов, и для обнаружения циклов, и для отчёта о реальном маршруте. Здесь «все детали внутри сборки 1, с путём, ведущим к каждой» над спецификацией изделия:

WITH RECURSIVE bom AS (
  -- якорь: прямые потомки сборки 1
  SELECT dst AS part, ARRAY[1, dst] AS path, 1 AS depth
  FROM edges
  WHERE src = 1

  UNION ALL

  -- рекурсивный терм: спускаемся, дописывая каждый узел в путь
  SELECT e.dst, b.path || e.dst, b.depth + 1
  FROM edges e
  JOIN bom b ON e.src = b.part
  WHERE NOT e.dst = ANY(b.path)        -- защита от цикла/повтора
    AND b.depth < 30                   -- ремень безопасности по глубине
)
SELECT part, path, depth FROM bom ORDER BY depth, part;

Достижимость, почти-кратчайшие пути и что SQL может выразить

Этот паттерн чисто отвечает на типичные продакшн-вопросы. Достижимость — «достижим ли B из A?» — это EXISTS по обходу. Транзитивное замыкание — «все узлы, достижимые из A» — это SELECT DISTINCT по обходу. Можно даже приблизить кратчайший путь, неся depth (число хопов) и беря минимум на пункт назначения, ведь цикл по рабочей таблице расширяется в ширину по уровням. Чего SQL-рекурсия не даёт дёшево — это настоящий взвешенный кратчайший путь (Дейкстра/A*): выразить его можно, но у движка нет очереди с приоритетом, так что он исследует куда больше путей, чем специализированный алгоритм, и цена жестока на реальных графах.

-- Расстояние в минимум хопов от узла 1 до каждого достижимого узла
WITH RECURSIVE walk AS (
  SELECT dst, 1 AS hops, ARRAY[1, dst] AS path FROM edges WHERE src = 1
  UNION ALL
  SELECT e.dst, w.hops + 1, w.path || e.dst
  FROM edges e JOIN walk w ON e.src = w.dst
  WHERE NOT e.dst = ANY(w.path)
)
SELECT dst, min(hops) AS shortest_hops
FROM walk GROUP BY dst ORDER BY dst;

Стена: взрыв путей и join на каждом хопе

Теперь сеньорская часть — почему это тормозит и какие числа. Две стоимости складываются. Первая: каждая итерация — это join всей рабочей таблицы против edges; без индекса на edges(src) каждый хоп — это sequential scan, и 6-хоповый обход по таблице на 10M рёбер — это шесть полных сканов. Всегда индексируй столбец join (src, или manager_id/parent_id). Вторая, и хуже, — взрыв путей: в плотном графе число различных путей растёт комбинаторно с глубиной, так что рабочая таблица может раздуться до куда большего числа строк, чем есть узлов — ты перечисляешь маршруты, а не узлы. Граф с парой тысяч узлов, но высоким ветвлением может породить миллионы промежуточных строк-путей, пробить work_mem (по умолчанию 4 МБ), слить на диск и превратить концептуально маленький обход в многогигабайтную сортировку.

Меры, по порядку: индексируй столбец join; агрессивно ограничивай глубину (большинству реальных вопросов нужно 3–6 хопов, не безграничность); если нужны лишь достижимые узлы, дедуплицируй рано через UNION (дедуп за проход) или перестрой так, чтобы отслеживать посещённые узлы, а не полные пути, чтобы рабочая таблица оставалась ограничена числом узлов, а не путей. С этим рекурсивные CTE комфортно тянут оргструктуры, деревья категорий и спецификации изделий примерно до нескольких миллионов рёбер при ограниченной глубине. Вместе эти три меры переносят узкое место с памяти и диска обратно на сетевую задержку — туда, где оно и должно быть для хорошо проиндексированного иерархического запроса. Пропусти хоть одну из них на плотном графе, и стена вернётся очень быстро.

За этим — миллионы рёбер с глубоким или безграничным обходом, частые запросы кратчайшего пути или центральности, или граф-форма как основная нагрузка — ты перерос инструмент. Реляционный движок соединяет множества; у него нет нативного индекса смежности, нет граф-осведомлённых операторов. Тянись к графовой базе (Neo4j и подобные) или к расширениям Postgres pgRouting/Apache AGE, добавляющим настоящие графовые алгоритмы. Продакшн-правило: рекурсивные CTE идеальны для эпизодических запросов иерархии и достижимости над умеренными графами, уже живущими в твоей реляционной схеме; они — неправильный дефолт для граф-центричного продукта.