Алгоритмы обхода графа традиционно были доменом языков приложений, таких как Python или Java, использующих библиотеки, такие как NetworkX или JGraphT. Однако с появлением рекурсивных общих таблиц выражений (CTE) в стандарте SQL:1999, SQL приобрел тьюринг-полные возможности для иерархических и рекурсивных запросов. Эта эволюция преобразовала ANSI SQL из простого языка извлечения данных в платформу, способную решать сложные вычислительные задачи геометрии и теории графов непосредственно на уровне базы данных, минимизируя движение данных и используя оптимизацию на основе множеств.
Определение кратчайшего пути в неориентированном графе требует нахождения минимального количества ребер между исходным узлом и целевым узлом. В отличие от структур деревьев, графы содержат циклы, что требует обнаружения циклов для предотвращения бесконечной рекурсии. Проблема заключается в имплементации логики поиска в ширину (BFS) — обычно процедурной и основанной на очередях — в декларативной, основанной на множестве парадигме без явных конструкций циклов или изменяемых переменных, с строгим соблюдением синтаксиса ANSI SQL, который запрещает проприетарные расширения, такие как CONNECT BY от Oracle или процедурные опции от SQL Server.
Решение использует рекурсивную CTE для имитации уровня за уровнем поиска BFS. Начальный член инициализирует поиск из исходного узла. Рекурсивный член присоединяется к таблице ребер для поиска смежных узлов, увеличивая счетчик длины пути. Критически важно, что ведется отслеживание посещенных путей, чтобы обнаруживать циклы и предотвращать повторный визит узлов. Рекурсия завершается, когда целевой узел достигнут или новые узлы не обнаружены. Стандарт ANSI SQL поддерживает явное обнаружение циклов с помощью оператора CYCLE или ручного отслеживания внутри CTE.
WITH RECURSIVE path_finder ( current_node, path_length, visited_path ) AS ( -- Якорь: начать с источника SELECT source_node, 0, CAST(source_node AS VARCHAR(1000)) FROM edges WHERE source_node = 'A' UNION ALL -- Рекурсивный: исследование соседей SELECT e.target_node, pf.path_length + 1, CAST(pf.visited_path || '->' || e.target_node AS VARCHAR(1000)) FROM path_finder pf JOIN edges e ON pf.current_node = e.source_node WHERE POSITION(e.target_node IN pf.visited_path) = 0 AND pf.path_length < 100 -- Ограничение безопасности ) SELECT path_length, visited_path FROM path_finder WHERE current_node = 'Z' ORDER BY path_length FETCH FIRST 1 ROW ONLY;
Логистическая компания управляла навигационной системой для своих складских роботов через реляционную базу данных, отслеживающую разрешенные маршруты между складами как ориентированные ребра. Операционная команда нуждалась в запросе в реальном времени, чтобы определить оптимальный (кратчайший) маршрут для роботов между любыми двумя складами с целью минимизации потребления батареи. Ограничение было строгим: решение должно было работать на их существующем кластере PostgreSQL, используя исключительно ANSI SQL, без развертывания внешних микросервисов или графовых баз данных, таких как Neo4j, из-за требований к задержке и архитектурной простоты.
Решение 1: Обработка BFS на уровне приложения с помощью Python
Команда рассмотрела возможность экспорта данных рёбер в сервис на Python с использованием NetworkX для вычисления кратчайших путей. Хотя это предлагало богатые алгоритмические библиотеки и простую реализацию, это привело бы к значительной сетевой задержке между базой данных и сервером приложения. Это также нарушило бы принцип единого источника правды, требуя репликации данных и создавая потенциальную точку сбоя при сетевых разделениях.
Решение 2: Хранимая процедура с процедурным SQL
Они оценили написание хранимой процедуры с использованием PL/pgSQL (процедурного языка PostgreSQL), чтобы реализовать очередь на основе BFS с изменяемыми переменными и циклами. Это устранило сетевую задержку, но жертвовало портативностью и нарушало требования стандарта ANSI SQL, завязывая их на синтаксис, специфичный для PostgreSQL. Этот подход также требовал сложного обработки исключений для частных случаев в обходе графа.
Решение 3: Чистый ANSI SQL с рекурсивной CTE
Выбранный подход использовал рекурсивную CTE, реализующую ограниченный по уровням BFS с отслеживанием путей. Это выполнялось полностью внутри движка SQL, используя возможность оптимизатора запросов параллелизировать объединения. Этот подход обеспечивал строгую совместимость с ANSI, обеспечивая портативность базы данных, устраняя сетевые накладные расходы и использовав оптимизацию на основе множеств.
Команда выбрала Решение 3, потому что оно соответствовало строгим архитектурным ограничениям работы в существующем класте базы данных, сохраняя при этом независимость от поставщика. Подход с ANSI SQL устранил необходимость в дополнительной инфраструктуре и достиг производительности запросов менее 1 миллисекунды на графах с 10,000+ ребер. Решение могло быть встроено непосредственно в вызовы JDBC API по диспетчеризации роботов без промежуточных слоев.
Реализация успешно вычислила кратчайшие пути для 500+ параллельных запросов от роботов в секунду со средним временем отклика менее 5 ммс. Логистическая компания впоследствии мигрировала свою базу данных с PostgreSQL на EnterpriseDB без изменения логики запросов, что подтвердило преимущества портативности. Решение стало образцом для других графовых запросов в организации, включая обнаружение циклической зависимости в сетях поставок.
Как предотвратить бесконечную рекурсию в циклическом графе, когда версия SQL стандарта не поддерживает оператор CYCLE?
Кандидаты часто упускают из виду, что более старые реализации ANSI SQL могут не иметь операторов SEARCH и CYCLE. Решение заключается в ручном обнаружении циклов, поддерживая строку с разделителем или массив посещенных узлов внутри рекурсивной CTE. Прежде чем добавить новый узел, запрос должен проверить, что перспективный узел уже не существует в накопленной строке пути, используя строковые функции, такие как POSITION. Это требует тщательной обработки символов-разделителей, чтобы предотвратить ложные положительные, такие как узел '11', обнаруживаемый внутри '111' без надлежащих разделителей. Кроме того, кандидаты часто забывают включить ограничитель глубины как меру предосторожности против бесконтрольной рекурсии в глубоко связанных графах.
Почему подход рекурсивной CTE к кратчайшему пути потенциально может возвращать неоптимальные результаты, если он написан как простое рекурсивное соединение без упорядочивания уровней?
Многие кандидаты реализуют рекурсивный шаг как простое соединение, не понимая, что рекурсивные CTE ANSI SQL по умолчанию выполняют поиск в глубину (DFS), если не ограничены иначе, а не поиск в ширину (BFS). В задачах кратчайшего пути для неориентированных графов BFS гарантирует, что первое найденное решение является оптимальным, тогда как DFS может сначала найти более длинный путь. Критическая деталь, которая упущена, заключается в том, что без ограничения глубины рекурсии или использования счетчика уровня, чтобы остановиться на первом совпадении, запрос может исследовать экпоненциально растущие пути неоправданно.
Как вы справляетесь с ухудшением производительности, когда тот же узел доступен через несколько путей одинаковой длины в рекурсивной CTE?
Кандидаты часто упускают концепцию устранения избыточных путей в SQL. Без надлежащей обработки рекурсивная CTE генерирует отдельные строки для каждого возможного пути к промежуточным узлам, что приводит к экспоненциальному росту наборов результатов. Решение требует использования оконной функции, такой как ROW_NUMBER(), разделенной по узлу, упорядоченной по длине пути, чтобы сохранять только кратчайший путь к каждому промежуточному узлу на каждой итерации. Эта оптимизация предотвращает раздувание промежуточного набора результатов, отвергая более длинные пути к уже посещенным узлам сразу, а не на этапе окончательного выбора.