Elementy zakotwiczający i rekurencyjny

Gdy osoba prowadząca rozmowę pokaże Państwu schemat organizacyjny, zestawienie materiałowe lub drzewo kategorii i poprosi o wyświetlenie wszystkich potomków, sprawdza, czy sięgną Państwo po rekurencyjne CTE. Zwykłe złączenia mogą przechodzić tylko przez ustaloną liczbę poziomów, natomiast rekurencja obsługuje dowolną głębokość.

Charakterystyczne sformułowania w pytaniu to „na dowolną głębokość” lub „aż do samego dołu”. To jest właściwy sygnał. W tej lekcji poznają Państwo dwuetapową strukturę wspólną dla każdego rekurencyjnego CTE: człon kotwiczący i człon rekurencyjny.

Rekurencyjne CTE zawsze zawiera słowo kluczowe WITH RECURSIVE (Postgres, SQLite, MySQL 8+; SQL Server pomija RECURSIVE) oraz treść złożoną z dwóch zapytań połączonych przez UNION ALL:

• Człon kotwiczący — wiersze początkowe, wykonywany raz.
• Człon rekurencyjny — odwołuje się do nazwy CTE i jest wykonywany wielokrotnie.

Proszę zapamiętać ten szkielet; osoby prowadzące rozmowy kwalifikacyjne często proszą o napisanie go od zera.

Człon kotwiczący jest zwykłym zapytaniem, które nie odwołuje się do CTE. Tworzy wiersze zalążkowe — punkt startowy na poziomie zerowym. W przypadku schematu organizacyjnego jest to zwykle dyrektor generalny (wiersz, którego menedżer ma wartość NULL), a w przypadku szeregu liczb jest to pierwsza liczba.

Człon kotwiczący jest wykonywany dokładnie raz. Jego wynik staje się pierwszą partią wierszy przekazywaną do kroku rekurencyjnego.

Człon rekurencyjny odwołuje się do CTE po nazwie. W każdej iteracji łączy wiersze utworzone w poprzedniej iteracji z tabelą bazową, aby znaleźć kolejny poziom.

Nie widzi całego dotychczasowego CTE — widzi tylko wiersze dodane w bezpośrednio poprzednim kroku. To najważniejszy model mentalny, którego znajomość sprawdzają osoby prowadzące rozmowy.

Połącz człon kotwiczący i rekurencyjny za pomocą UNION ALL, a silnik będzie automatycznie wykonywać kolejne iteracje. Każde przejście dopisuje następny poziom, aż człon rekurencyjny zwróci zero wierszy; wtedy rekurencja się zatrzymuje.

Poniżej znajduje się kompletny, gotowy do uruchomienia przykład przechodzenia po schemacie organizacyjnym, który śledzi również depth.

Rekurencja zatrzymuje się, gdy człon rekurencyjny nie utworzy żadnych nowych wierszy. Nie trzeba jawnie stosować licznika pętli — złączenie naturalnie wyczerpuje się po dotarciu do liści drzewa.

W przykładzie schematu organizacyjnego, gdy dotrzemy do pracowników bez bezpośrednich podwładnych, złączenie w następnej iteracji nie znajdzie dzieci, zwróci pusty wynik, a silnik zakończy działanie. Zrozumienie tego samoczynnego kończenia jest klasycznym pytaniem dodatkowym.

Osoby prowadzące rozmowy często pytają, dlaczego używamy UNION ALL, a nie UNION. Są dwa powody:

• Wydajność — UNION usuwa duplikaty w każdej iteracji, co jest kosztowne.
• Poprawność — w drzewie zduplikowane wiersze zwykle nie mogą wystąpić, więc usuwanie duplikatów byłoby niepotrzebną pracą.

Po UNION należy sięgać tylko wtedy, gdy struktura jest grafem i świadomie chcą Państwo scalać powtarzające się węzły — jednak dla bezpieczeństwa cykli lepsze są jawne zabezpieczenia (omówione później).

Dwie dodatkowe kolumny znacznie zwiększają użyteczność wyników rekurencyjnych i są często wymagane podczas rozmów kwalifikacyjnych:

• depth — rozpocząć od wartości 1 w członie kotwiczącym i zwiększać o 1 w członie rekurencyjnym.
• path — gromadzić łańcuch identyfikatorów lub nazw, aby można było zobaczyć drogę od korzenia do węzła.

Budowanie path jako ciągu znaków służy również później do wykrywania cykli.

Subtelna pułapka: człon kotwiczący i człon rekurencyjny muszą zwracać taką samą liczbę kolumn o zgodnych typach. Jeśli tworzony jest ciąg znaków path, początkową wartość w członie kotwiczącym należy rzutować na typ o wystarczająco dużym rozmiarze, np. VARCHAR(1000), w przeciwnym razie silnik może obciąć wartość albo zgłosić błąd niezgodności typów w kolejnych iteracjach.

To dokładnie taki szczegół, który osoba prowadząca rozmowę może celowo wykorzystać, aby sprawdzić, czy rzeczywiście uruchamiali Państwo rekurencyjne CTE, a nie tylko czytali o nim.

Ten sam szkielet rozwiązuje problem zestawienia materiałowego: mając daną część, należy wyświetlić każdą część składową na dowolnej głębokości. Człon kotwiczący wybiera główny zespół, a człon rekurencyjny przechodzi po powiązaniach od parent_part do child_part.

Proszę zauważyć, że struktura jest identyczna jak w przypadku schematu organizacyjnego — zmieniają się tylko nazwy kolumn. Rozpoznanie, że jeden szkielet pasuje do wielu problemów, jest właściwą umiejętnością przydatną podczas rozmowy.

Szybka ściąga dotycząca różnych dialektów, którą doceniają osoby prowadzące rozmowy:

• PostgreSQL, SQLite, MySQL 8+: WITH RECURSIVE name AS (...).
• SQL Server: wystarczy WITH name AS (...) — słowo kluczowe RECURSIVE jest domyślne, a silnik wymusza domyślną wartość MAXRECURSION równą 100.
• Oracle: obsługuje zarówno rekurencyjne CTE, jak i starszą składnię CONNECT BY.

Powiedzenie „SQL Server nie używa słowa RECURSIVE” pokazuje rzeczywistą znajomość różnych rozwiązań.

Proszę sprawdzić, czy rozumieją Państwo dwuetapową strukturę.

Opanowali Państwo szkielet rekurencyjnego CTE:

• WITH RECURSIVE + człon kotwiczący + UNION ALL + człon rekurencyjny.
• Człon kotwiczący inicjuje poziom zerowy i jest wykonywany raz.
• Człon rekurencyjny łączy wynik poprzedniej iteracji z tabelą bazową i działa, dopóki nie zwróci żadnych wierszy.
• Należy używać UNION ALL, śledzić depth i path oraz zapewnić zgodność typów kolumn.

Następnie: zastosowanie tego szkieletu do przechodzenia po rzeczywistym schemacie organizacyjnym w dół i w górę.