Algorytmy przeszukiwania grafów tradycyjnie były dziedziną języków aplikacyjnych, takich jak Python czy Java, wykorzystując biblioteki takie jak NetworkX czy JGraphT. Jednak z nadejściem rekurencyjnych CTE w standardzie SQL:1999, SQL zyskało możliwości Turinga do hierarchicznych i rekurencyjnych zapytań. Ta ewolucja przekształciła ANSI SQL z zaledwie języka do pobierania danych w platformę zdolną do rozwiązywania skomplikowanych problemów związanych z geometrią obliczeniową i teorią grafów bezpośrednio w warstwie bazy danych, minimalizując ruch danych i wykorzystując optymalizację opartą na zbiorach.
Określenie najkrótszej ścieżki w nieskierowanym grafie wymaga znalezienia minimalnej liczby krawędzi między węzłem źródłowym a węzłem docelowym. W przeciwieństwie do struktur drzewiastych, grafy zawierają cykle, co wymaga detekcji cykli, aby zapobiec nieskończonej rekurencji. Wyzwanie polega na wdrożeniu logiki przeszukiwania wszerz (BFS) — zazwyczaj proceduralnej i opartej na kolejkach — w deklaratywnej, opartej na zbiorach paradygmatycznej bez wyraźnych konstrukcji pętli lub zmiennych mutowalnych, przy ściśle przestrzeganiu składni ANSI SQL, która zabrania rozszerzeń własnościowych, takich jak CONNECT BY Oracle lub możliwości proceduralnych SQL Servera.
Rozwiązanie wykorzystuje rekurencyjne CTE do symulacji poziomowego przeszukiwania BFS. Część wstępna inicjuje wyszukiwanie z węzła źródłowego. Część rekurencyjna łączy się z tabelą krawędzi w celu odkrycia sąsiadujących węzłów, zwiększając licznik długości ścieżki. Kluczowe jest utrzymanie ciągu znaków śledzącego odwiedzone ścieżki, aby wykrywać cykle i zapobiegać ponownemu odwiedzaniu węzłów. Rekursja kończy się, gdy cel zostanie osiągnięty lub nie odkryto nowych węzłów. Standard ANSI SQL wspiera explicite detekcję cykli za pomocą klauzuli CYCLE lub ręcznego śledzenia w obrębie CTE.
WITH RECURSIVE path_finder ( current_node, path_length, visited_path ) AS ( -- Początkowa: start z węzła źródłowego SELECT source_node, 0, CAST(source_node AS VARCHAR(1000)) FROM edges WHERE source_node = 'A' UNION ALL -- Rekurencyjna: eksploruj sąsiadów 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 -- Limit bezpieczeństwa ) SELECT path_length, visited_path FROM path_finder WHERE current_node = 'Z' ORDER BY path_length FETCH FIRST 1 ROW ONLY;
Firma logistyczna zarządzała systemem nawigacji robotów w magazynie poprzez bazę danych relacyjną, śledząc dozwolone trasy między regałami magazynowymi jako skierowane krawędzie. Zespół operacyjny potrzebował zapytania w czasie rzeczywistym, aby określić optymalną (najkrótszą) trasę dla robotów między dowolnymi dwoma regałami, aby zminimalizować zużycie energii. Wymaganie było ściśle określone: rozwiązanie musiało działać na ich istniejącym klastrze PostgreSQL, używając ściśle ANSI SQL bez wdrażania zewnętrznych mikroserwisów czy baz danych grafowych, takich jak Neo4j, z uwagi na wymagania dotyczące opóźnienia i mandaty architektoniczne dotyczące prostoty.
Rozwiązanie 1: BFS na warstwie aplikacji z Pythonem
Zespół rozważał eksport danych krawędzi do serwisu Python z użyciem NetworkX, aby obliczyć najkrótsze ścieżki. Choć dawało to bogate biblioteki algorytmiczne i prostą implementację, wprowadzało znaczne opóźnienie sieciowe między bazą danych a serwerem aplikacji. Naruszało to również zasadę pojedynczego źródła prawdy, wymagając replikacji danych i tworząc potencjalny punkt awarii podczas partycji sieci.
Rozwiązanie 2: Procedura składowana z proceduralnym SQL
Ocenili napisanie procedury składowanej z użyciem PL/pgSQL (proceduralnego języka PostgreSQL), aby wdrożyć przeszukiwanie wszerz BFS z użyciem zmiennych mutowalnych i pętli. To wyeliminowało opóźnienia w sieci, ale poświęciło przenośność i naruszyło wymagania standardu ANSI SQL, blokując ich w specyficznej składni PostgreSQL. To podejście wymagało również złożonego obsługiwanie wyjątków dla przypadków krawędziowych w przeszukiwaniu grafów.
Rozwiązanie 3: CTE rekurencyjne czystego ANSI SQL
Wybrane podejście wykorzystało rekurencyjne CTE, implementując BFS z ograniczeniem do poziomu i śledzeniem ścieżek. To działało całkowicie w czasie działania silnika SQL, wykorzystując zdolność optymalizatora zapytań do równoległego łączenia. To podejście zapewniło ścisłą zgodność z ANSI dla przenośności bazy danych, wyeliminowało przeciążenie sieci i wykorzystało optymalizacje wydajności oparte na zbiorach.
Zespół wybrał Rozwiązanie 3, ponieważ spełniało ściśle architektoniczne wymagania dotyczące działania w istniejącym klastrze bazy danych przy zachowaniu niezależności od dostawców. Podejście ANSI SQL wyeliminowało potrzebę dodatkowej infrastruktury i osiągnęło odzyskiwanie zapytań poniżej 5 ms w grafach z ponad 10 000 krawędziami. Rozwiązanie umożliwiło bezpośrednie osadzenie zapytania w wywołaniach JDBC API do wysyłania robotów bez pośrednich warstw.
Implementacja skutecznie obliczała najkrótsze ścieżki dla ponad 500 równoczesnych żądań robotów na sekundę, z średnim czasem odpowiedzi poniżej 5 ms. Firma logistyczna później przeniosła swoją bazę danych z PostgreSQL do EnterpriseDB bez modyfikacji logiki zapytań, co potwierdzało korzyści związane z przenośnością. Rozwiązanie stało się przykładem dla innych zapytań opartych na grafach w organizacji, w tym wykrywania cyklicznych zależności w sieciach łańcucha dostaw.
Jak zapobiec nieskończonej rekurencji w grafie cyklicznym, gdy wersja standardu SQL nie obsługuje klauzuli CYCLE?
Kandydaci często nie zauważają, że starsze implementacje ANSI SQL mogą nie mieć klauzul SEARCH i CYCLE. Rozwiązaniem jest ręczna detekcja cykli poprzez utrzymywanie ciągu z limitatorami lub tablicy odwiedzonych węzłów w obrębie rekurencyjnego CTE. Przed dodaniem nowego węzła zapytanie musi zweryfikować, czy potencjalny węzeł nie istnieje już w skumulowanym ciągu ścieżki, korzystając z funkcji ciągowych, takich jak POSITION. Wymaga to starannego traktowania znaków limitujących, aby zapobiec fałszywym pozytywom, takim jak wykrywanie węzła '11' w '111' bez odpowiednich separatorów. Dodatkowo, kandydaci często zapominają o włączeniu limitera głębokości jako zabezpieczenia przed nieskończoną rekurencją w głęboko połączonych grafach.
Dlaczego podejście rekurencyjnego CTE do najkrótszej ścieżki może potencjalnie zwrócić suboptymalne wyniki, jeśli jest napisane jako proste łączenie rekurencyjne bez porządkowania poziomów?
Wielu kandydatów wdraża krok rekurencyjny jako proste łączenie, nie rozumiejąc, że rekurencyjne CTE ANSI SQL domyślnie wykonują przeszukiwanie w głąb (DFS) chyba że inaczej ograniczone, a nie przeszukiwanie wszerz (BFS). W problemach z najkrótszą ścieżką w nieskierowanych grafach, BFS gwarantuje, że pierwsze znalezione rozwiązanie jest optymalne, podczas gdy DFS może najpierw znaleźć dłuższą ścieżkę. Kluczowy szczegół, który umyka, polega na tym, że bez ograniczenia głębokości rekurencji lub użycia licznika poziomu, zapytanie może niepotrzebnie eksplorować eksponencjalnie rosnące ścieżki.
Jak radzisz sobie z degradacją wydajności, gdy ten sam węzeł jest osiągalny przez wiele ścieżek o równej długości w rekurencyjnym CTE?
Kandydaci często umykają koncepcji eliminacji redundantnych ścieżek w SQL. Bez odpowiedniego traktowania, rekurencyjne CTE generuje oddzielne wiersze dla każdej możliwej ścieżki do węzłów pośrednich, co powoduje eksponencjalny wzrost zestawów wyników. Rozwiązanie wymaga użycia funkcji okna, takiej jak ROW_NUMBER(), podzielonej według węzła, uporządkowanej według długości ścieżki, aby utrzymać tylko najkrótszą ścieżkę do każdego węzła pośredniego na każdym etapie. Ta optymalizacja zapobiega eksplozji zestawu wyników pośrednich poprzez odrzucenie dłuższych ścieżek do już odwiedzonych węzłów natychmiast, a nie na etapie ostatecznego wyboru.