Dokumentacja SQLite z przykładami: Rekurencyjne CTE

Q: Czym jest rekurencyjne CTE w SQLite?

Rekurencyjne CTE to zapytanie WITH RECURSIVE, które buduje wynik, wielokrotnie odwołując się do samego siebie. Ma dwie części połączone przez UNION ALL: zapytanie startowe (anchor), które tworzy początkowe wiersze, i zapytanie rekurencyjne, które tworzy kolejne wiersze z poprzedniego kroku. SQLite uruchamia część rekurencyjną, dopóki nie przestanie zwracać nowych wierszy.

Q: Kiedy używać WITH RECURSIVE w SQLite?

Sięgnij po nie, gdy musisz przejść drzewo lub graf (pracownicy i kierownicy, kategorie i podkategorie, komentarze w wątkach) albo wygenerować ciąg (każda data w zakresie, liczby od 1 do 100). Zwykłe złączenia radzą sobie z jednym lub dwoma poziomami, a rekurencyjne CTE obsługuje dowolną głębokość bez znajomości jej z góry.

Q: Jak uniknąć nieskończonej pętli w rekurencyjnym CTE w SQLite?

Upewnij się, że zapytanie rekurencyjne ma warunek zatrzymania: klauzulę WHERE, która w końcu zwróci zero wierszy, albo licznik z górnym limitem. W grafach z cyklami zapisuj odwiedzoną ścieżkę w kolumnie i wykluczaj wiersze, które już w niej są. Jako siatkę bezpieczeństwa dodaj LIMIT do zewnętrznego zapytania, żeby niekontrolowana rekurencja nie zapełniła pamięci.

Rekurencja w SQL brzmi dziwnie, dopóki jej nie zobaczysz

Większość zapytań zwraca wiersze z danych, które już istnieją. Rekurencyjne CTE działa inaczej: buduje wiersze, podając własny wynik z powrotem jako wejście, krok po kroku, aż nie będzie już nic nowego do dodania. Tak przechodzi się drzewo o nieznanej głębokości albo generuje liczby od 1 do 100 bez tabeli z liczbami.

Kształt jest zawsze taki sam:

WITH RECURSIVE name(columns) AS (
    -- zapytanie startowe: początkowe wiersze
    SELECT ...
    UNION ALL
    -- rekurencja: wiersze wyprowadzone z poprzedniego kroku
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

Zapytanie startowe na górze, UNION ALL, zapytanie rekurencyjne pod spodem. SQLite uruchamia zapytanie startowe raz, a potem wciąż uruchamia część rekurencyjną, za każdym razem na wierszach z poprzedniej rundy, dopóki nie przestanie zwracać nowych wierszy. Wtedy się zatrzymuje.

Liczenie od 1 do 10

Najprostsze rekurencyjne CTE generuje ciąg. Żadne tabele nie są potrzebne:

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter WHERE n < 10
)
SELECT n FROM counter;

Prześledźmy to:

Zapytanie startowe tworzy jeden wiersz: n = 1.
Krok rekurencyjny bierze ten wiersz, oblicza n + 1 = 2, a 2 < 10 jest prawdą, więc wiersz zostaje.
Następna iteracja bierze n = 2 i tworzy n = 3. I tak dalej.
Gdy n dochodzi do 10, 10 < 10 jest fałszem, krok rekurencyjny nie zwraca żadnych wierszy i SQLite się zatrzymuje.

WHERE n < 10 to warunek zatrzymania. Bez niego zapytanie działa w nieskończoność.

Generowanie serii dat

Ten sam pomysł, przydatny w prawdziwych raportach: uzupełnij każdy dzień w zakresie, także dni, w których nic się nie działo:

WITH RECURSIVE days(d) AS (
    SELECT date('2024-01-01')
    UNION ALL
    SELECT date(d, '+1 day') FROM days WHERE d < '2024-01-07'
)
SELECT d FROM days;

Zwykle robi się LEFT JOIN takiej serii z tabelą zdarzeń, żeby poprawnie policzyć dni bez zdarzeń. Zwykłe GROUP BY date całkowicie pomija puste dni, a seria dat daje wiersz dla każdego dnia bez wyjątku.

Przechodzenie drzewa rodzic-dziecko

Klasyczne zastosowanie. Oto tabela pracowników, w której każdy wiersz wskazuje swojego kierownika:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE org(id, name, manager_id, depth) AS (
    SELECT id, name, manager_id, 0
    FROM employees
    WHERE manager_id IS NULL
    UNION ALL
    SELECT e.id, e.name, e.manager_id, org.depth + 1
    FROM employees e
    JOIN org ON e.manager_id = org.id
)
SELECT printf('%.*c%s', depth * 2, ' ', name) AS tree
FROM org;

Zapytanie startowe wybiera korzeń (osobę bez kierownika). Krok rekurencyjny złącza tabelę pracowników z CTE i znajduje wszystkich, których manager_id pasuje do id już obecnego w CTE. Każda iteracja schodzi o poziom głębiej. depth to tylko licznik, który dodajemy, by wciąć wynik.

To działa dla drzew o dowolnej głębokości. Dwa poziomy czy dziesięć, zapytanie się nie zmienia.

Znajdowanie wszystkich przodków konkretnego wiersza

Odwróć kierunek. Zamiast schodzić od korzenia, idź w górę od konkretnego pracownika, żeby znaleźć cały łańcuch jego przełożonych:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

WITH RECURSIVE chain(id, name, manager_id) AS (
    SELECT id, name, manager_id
    FROM employees
    WHERE name = 'Diego'
    UNION ALL
    SELECT e.id, e.name, e.manager_id
    FROM employees e
    JOIN chain ON chain.manager_id = e.id
)
SELECT name FROM chain;

Zapytanie startowe to pracownik, od którego zaczynasz. Każdy krok rekurencyjny przeskakuje do rodzica. SQLite zatrzymuje się, gdy dojdzie do korzenia: manager_id IS NULL, więc złączenie nic nie znajduje.

Ten wzorzec przydaje się do okruszków nawigacji (breadcrumbs), komentarzy w wątkach, ścieżek kategorii i wszędzie tam, gdzie trzeba "dojść na samą górę".

Warunki zatrzymania i nieskończone pętle

Najczęstszy błąd to zapomniany warunek zatrzymania albo taki, który nigdy nie zadziała. Porównaj:

-- Działa w nieskończoność:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

Nie ma tu klauzuli WHERE, która kiedykolwiek zwróciłaby zero wierszy. SQLite chętnie spróbuje doliczyć do nieskończoności.

Dwa nawyki obronne:

Zawsze miej w części rekurencyjnej klauzulę WHERE, która ogranicza wzrost.
W trakcie pracy dodawaj LIMIT do zewnętrznego SELECT jako siatkę bezpieczeństwa: jeśli pomylisz się co do warunku zatrzymania, zapytanie i tak się zakończy.

WITH RECURSIVE counter(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM counter
)
SELECT n FROM counter LIMIT 5;

Samo CTE nie ma ograniczenia, ale LIMIT 5 wcześnie zatrzymuje zewnętrzne zapytanie. SQLite jest na tyle sprytny, że nie kontynuuje rekurencji ponad to, czego potrzebuje LIMIT. Przydatne przy eksperymentach, ale w kodzie produkcyjnym nie zastępuje prawdziwego warunku zatrzymania.

Cykle w grafach

Drzewa nie mogą mieć cykli. Ogólne grafy mogą, a naiwne rekurencyjne CTE zapętli się na zawsze, jeśli w danych jest cykl. Rozwiązanie: śledź przebytą do tej pory ścieżkę i nie odwiedzaj węzłów ponownie:

CREATE TABLE edges (a INTEGER, b INTEGER);
INSERT INTO edges VALUES (1, 2), (2, 3), (3, 1), (3, 4);

WITH RECURSIVE walk(node, path) AS (
    SELECT 1, ',1,'
    UNION ALL
    SELECT e.b, path || e.b || ','
    FROM edges e
    JOIN walk ON e.a = walk.node
    WHERE instr(path, ',' || e.b || ',') = 0
)
SELECT node, path FROM walk;

path to tekst z już odwiedzonymi węzłami rozdzielonymi przecinkami. Przed dodaniem nowego węzła klauzula WHERE sprawdza, czy go tam nie ma. Bez tego zabezpieczenia cykl 1 → 2 → 3 → 1 kręciłby się w nieskończoność.

SQL nie ma wbudowanego "zbioru odwiedzonych": budujesz go sam, zwykle jako tekst albo przez złączenie z dotychczasowym CTE.

Rekurencyjne CTE a self join

Jeśli potrzebujesz tylko jednego lub dwóch poziomów, self join jest prostszy i szybszy:

CREATE TABLE employees (
    id INTEGER PRIMARY KEY,
    name TEXT NOT NULL,
    manager_id INTEGER REFERENCES employees(id)
);

INSERT INTO employees VALUES
    (1, 'Ada',    NULL),
    (2, 'Boris',  1),
    (3, 'Carla',  1),
    (4, 'Diego',  2),
    (5, 'Elena',  2),
    (6, 'Farouk', 3);

SELECT e.name AS pracownik, m.name AS kierownik
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

To odpowiada na pytanie "kto jest bezpośrednim kierownikiem każdej osoby". Ale jeśli potrzebujesz "wszystkich, którzy podlegają Adzie, bez względu na głębokość", a głębokość jest nieznana, czysto poradzi sobie z tym tylko rekurencyjne CTE. Dobierz narzędzie do potrzebnej głębokości:

Stała, niewielka głębokość: self join, może dwa lub trzy.
Nieznana lub dowolna głębokość: WITH RECURSIVE.

Model myślowy

Rekurencyjne CTE to pętla zapisana deklaratywnie:

Zapytanie startowe to wartość początkowa pętli.
Zapytanie rekurencyjne to ciało pętli: tworzy następną porcję wierszy z bieżących.
Warunek zatrzymania to test wyjścia z pętli: gdy zwraca zero wierszy, pętla się kończy.
UNION ALL gromadzi wszystko w końcowym wyniku.

Gdy to sobie poukładasz w głowie, składnia przestaje wydawać się dziwna. Piszesz pętlę for w SQL.

Dalej: indeksy

Rekurencyjne CTE przechodzą przez wiele wierszy, a złączenie w kroku rekurencyjnym wykonuje się w każdej iteracji. Jeśli kolumna złączenia nie ma indeksu, wydajność szybko leci w dół. Indeksy to następny rozdział, a manager_id to dokładnie taka kolumna, której indeks się przyda.

Najczęściej zadawane pytania

Czym jest rekurencyjne CTE w SQLite?

Rekurencyjne CTE to zapytanie WITH RECURSIVE, które buduje wynik, wielokrotnie odwołując się do samego siebie. Ma dwie części połączone przez UNION ALL: zapytanie startowe (anchor), które tworzy początkowe wiersze, i zapytanie rekurencyjne, które tworzy kolejne wiersze z poprzedniego kroku. SQLite uruchamia część rekurencyjną, dopóki nie przestanie zwracać nowych wierszy.

Kiedy używać WITH RECURSIVE w SQLite?

Sięgnij po nie, gdy musisz przejść drzewo lub graf (pracownicy i kierownicy, kategorie i podkategorie, komentarze w wątkach) albo wygenerować ciąg (każda data w zakresie, liczby od 1 do 100). Zwykłe złączenia radzą sobie z jednym lub dwoma poziomami, a rekurencyjne CTE obsługuje dowolną głębokość bez znajomości jej z góry.

Jak uniknąć nieskończonej pętli w rekurencyjnym CTE w SQLite?

Upewnij się, że zapytanie rekurencyjne ma warunek zatrzymania: klauzulę WHERE, która w końcu zwróci zero wierszy, albo licznik z górnym limitem. W grafach z cyklami zapisuj odwiedzoną ścieżkę w kolumnie i wykluczaj wiersze, które już w niej są. Jako siatkę bezpieczeństwa dodaj LIMIT do zewnętrznego zapytania, żeby niekontrolowana rekurencja nie zapełniła pamięci.

Powiązane zagadnienia