Rekurencyjne Common Table Expression (CTE) w SQL umożliwia przeszukiwanie danych hierarchicznych za pomocą zapytania samoreferencyjnego, które działa w sposób oparty na zbiorach. Struktura składa się z członka głównego (przypadek bazowy, zwykle węzły korzenia, gdzie manager_id IS NULL) oraz członka rekurencyjnego (część iteracyjna, która łączy CTE z samym sobą na podstawie relacji rodzic-dziecko). Silnik bazy danych wielokrotnie wykonuje człon rekurencyjny, aż nie zostaną zwrócone nowe wiersze, budując zestaw wyników stopniowo, bez jawnych konstrukcji iteracyjnych.
To podejście wykorzystuje deklaratywną naturę SQL, pozwalając optymalizatorowi wybierać efektywne algorytmy łączenia (zwykle łączenia haszowe lub scalające) zamiast przetwarzania wiersz po wierszu, które jest charakterystyczne dla CURSOR lub pętli WHILE. Składnia używa WITH RECURSIVE w PostgreSQL i MySQL, lub po prostu WITH w SQL Server (gdzie rekurencja jest implicitna), a następnie nazwy CTE i listy kolumn.
Międzynarodowa korporacja z 12 000 pracowników potrzebowała generować pełne łańcuchy raportowe dla audytów zgodności z SOX. Istniejący system wykorzystywał T-SQL CURSOR, który iterował przez każdego pracownika, rekurencyjnie wywoływał funkcję skalarną, aby znaleźć ich menedżera, i budował hierarchię wiersz po wierszu. Proces ten trwał 47 minut, blokował tabelę Employees, uniemożliwiając aktualizacje HR w godzinach pracy, i często kończył się błędami przepełnienia stosu podczas przetwarzania głębokich hierarchii przekraczających 100 poziomów (co było powszechne w macierzowej strukturze działu inżynieryjnego).
Rozwiązanie A: Optymalizowany CURSOR z tabelami tymczasowymi. Zespół rozważał przepisanie kursora w celu najpierw zapisywania wyników w tabeli tymczasowej, a następnie masowego wstawiania na końcu. To zmniejszyłoby czas blokowania z 47 minut do około 40 minut. Zaletami były: minimalne zmiany w kodzie, znany wzór dla zespołu legacy. Wady: nadal przetwarzanie wiersz po wierszu, nadal podatne na głębokie przepełnienia stosu rekurencji, jedynie łagodzi, a nie rozwiązuje problemu wydajności.
Rozwiązanie B: Typ danych HierarchyID. Migracja tabeli do użycia natywnego typu HierarchyID w SQL Server, który przechowuje pozycje drzewiaste jako zakodowane ścieżki zoptymalizowane do przeszukiwania. Zaletami były: O(1) pobieranie poddrzew, wbudowane metody takie jak GetAncestor() i GetDescendant(), niezwykle szybkie dla obciążenia opartego na odczycie. Wady: wymaga ogromnej migracji schematu (12 000 wierszy plus dane historyczne), trudne do utrzymania podczas reorganizacji (aktualizacja menedżera wymaga przeliczenia wszystkich ścieżek potomków), uzależnienie od dostawcy SQL Server, podczas gdy firma rozważała migrację do PostgreSQL.
Rozwiązanie C: Rekurencyjne CTE z detekcją cykli. Wdrożenie rekurencyjnego CTE, które łączy tabelę pracowników z samą sobą na podstawie manager_id, używając tablicy ścieżek w celu śledzenia odwiedzonych węzłów w celu zapobieżenia nieskończonym pętlom w przypadku odniesień cyklicznych (co zdarzyło się dwukrotnie z powodu błędów wprowadzania danych). Zaletami były: czysty standard ANSI SQL (przenośny do PostgreSQL podczas migracji), wykonanie oparte na zbiorach skróciło czas trwania do 4 minut 12 sekund, brak blokad tabel podczas wykonania (korzysta z izolacji migawkowej), obsługuje dowolną głębokość bez przepełnienia stosu, automatycznie wykrywa problemy z jakością danych (cykle).
Zespół wybrał Rozwiązanie C. Implementacja używała rekurencyjnego CTE z kolumną path, akumulującą identyfikatory pracowników za pomocą agregacji tablic w PostgreSQL (lub konkatenacji ciągów w SQL Server), z klauzulą WHERE, sprawdzającą, że nowy manager_id nie istnieje w skumulowanej ścieżce. Rezultatem była poprawa wydajności o 91%, eliminacja blokad produkcyjnych oraz wczesne wykrywanie cyklicznych relacji raportowania, które wcześniej powodowały awarie aplikacji.
Dlaczego rekurencyjny CTE kończy działanie, a co się stanie, jeśli dane zawierają odniesienie cykliczne?
Kandydaci często wierzą, że rekurencyjne CTE mają wbudowaną detekcję cykli, ale standardowa rekurencja SQL kończy się tylko wtedy, gdy człon rekurencyjny zwraca zero nowych wierszy. Jeśli Pracownik A raportuje do B, B do C, a C z powrotem do A, CTE działa w nieskończoność (lub do osiągnięcia limitów implementacji, takich jak domyślne 100 poziomów rekurencji w SQL Server). Rozwiązanie wymaga ręcznej detekcji cykli, akumulując odwiedzone identyfikatory węzłów w kolumnie ścieżki (używając tablic lub łańcuchów oddzielonych) i filtrując WHERE new_id != ALL(path_array). Nowoczesne PostgreSQL (14+) i SQL Server (2022+) wspierają standardową klauzulę SQL:1999 CYCLE: WITH RECURSIVE cte AS (...) CYCLE id SET is_cycle USING path, która automatycznie to obsługuje.
Jak plan wykonania różni się między rekurencyjnym CTE a podejściem opartym na kursorze i dlaczego ma to znaczenie dla współbieżności?
Młodsi kandydaci często twierdzą, że CTE są "szybsze" bez zrozumienia modelu wykonania. CURSOR w SQL Server lub PostgreSQL zmusza silnik do zmaterializowania zestawu wynikowego i iteracji wiersz po wierszu, zazwyczaj używając typu kursora Keyset lub Static, który wymaga blokad lub zasobów tempdb na czas iteracji. To tworzy Shared Locks (lub Update Locks) na podstawowych tabelach przez cały czas trwania 47-minutowego przykładu. Przeciwnie, rekurencyjny CTE jest pojedynczym zapytaniem SELECT. W ramach Read Committed Snapshot Isolation (RCSI) lub Snapshot Isolation odczytuje spójną perspektywę danych w czasie, nie trzymając żadnych blokad, wykorzystując zamiast tego sklep wersji. Optymalizator zazwyczaj wybiera Nested Loop Joins dla członu rekurencyjnego z operacjami Index Seek na indeksie rodzic-dziecko, co sprawia, że działa to w czasie O(n log n), a nie O(n²) dla podejść kursorowych.
Jaka jest różnica między rekurencyjnym CTE a modelem Nested Sets dla danych hierarchicznych i kiedy wybrałbyś jedno nad drugim?
Kandydaci często mylą metody przeszukiwania z modelami przechowywania. Rekurencyjny CTE to technika przeszukiwania w czasie zapytania, która działa na Adjacency Lists (klucze obce parent_id). Nested Sets Model (lewe/prawe wartości) to wzór projektowania przechowywania, który wstępnie oblicza ścieżki przeszukiwania drzewa. W przypadku obciążeń ciężkich na zapisie (częste zmiany menedżerów), rekurencyjne CTE na listach są lepsze, ponieważ aktualizacja pojedynczego parent_id to O(1), podczas gdy zagnieżdżone zestawy wymagają O(n) aktualizacji wszystkich prawych wartości na prawo od przeniesionego węzła. Dla obciążeń intensywnie odczytujących, statycznych hierarchii (organigramy zmieniające się co miesiąc), zagnieżdżone zestawy zapewniają O(1) pobieranie poddrzew (WHERE left BETWEEN parent.left AND parent.right) w porównaniu do O(n) dla rekurencyjnych CTE. Hybrydowe podejście wykorzystuje Closure Tables (oddzielna tabela przechowująca wszystkie pary przodków-potomków), co oferuje O(1) zarówno dla przeszukiwania, jak i znajdowania wszystkich dzieci, kosztem O(n²) przechowywania i bardziej skomplikowanego utrzymania. Wybór zależy od stosunku odczytów do zapisów: używaj rekurencyjnych CTE, gdy zapisy > 5% operacji; używaj zagnieżdżonych zestawów lub tabel zamknięcia dla przeważnie statycznych drzew.