CTE ricorsive in SQLite: WITH RECURSIVE per alberi e serie

La ricorsione in SQL sembra strana, finché non la vedi

La maggior parte delle query restituisce righe da dati che esistono già. Una CTE ricorsiva è diversa: costruisce righe rimettendo in ingresso il proprio output, un passo alla volta, finché non c'è più niente di nuovo da aggiungere. È così che percorri un albero di profondità sconosciuta, o generi i numeri da 1 a 100 senza una tabella di numeri.

La struttura è sempre la stessa:

WITH RECURSIVE name(columns) AS (
    -- ancoraggio: le righe di partenza
    SELECT ...
    UNION ALL
    -- ricorsiva: righe derivate dal passo precedente
    SELECT ... FROM name WHERE ...
)
SELECT * FROM name;

Ancoraggio sopra, UNION ALL, query ricorsiva sotto. SQLite esegue l'ancoraggio una volta, poi continua a eseguire la parte ricorsiva, usando ogni volta le righe prodotte al giro precedente, finché non restituisce più righe nuove. A quel punto si ferma.

Contare da 1 a 10

La CTE ricorsiva più semplice genera una serie. Non servono tabelle:

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

Seguila passo per passo:

1. L'ancoraggio produce una riga: n = 1.
2. Il passo ricorsivo prende quella riga, calcola n + 1 = 2 e, dato che 2 < 10 è vero, tiene la riga.
3. L'iterazione successiva prende n = 2 e produce n = 3. E così via.
4. Quando n arriva a 10, 10 < 10 è falso, il passo ricorsivo non restituisce righe e SQLite si ferma.

WHERE n < 10 è la condizione di arresto. Senza, la query va avanti all'infinito.

Generare una serie di date

Stessa idea, utile nei report reali: riempire ogni giorno di un intervallo, anche quelli in cui non è successo niente:

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;

Di solito fai un LEFT JOIN di questa serie con una tabella di eventi per contare correttamente i giorni senza eventi. Un semplice GROUP BY date salta del tutto i giorni vuoti; la serie di date ti dà una riga per ogni giorno, comunque vada.

Percorrere un albero padre-figlio

Il caso d'uso classico. Ecco una tabella di dipendenti in cui ogni riga punta al proprio responsabile:

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;

L'ancoraggio sceglie la radice (la persona senza responsabile). Il passo ricorsivo unisce di nuovo la tabella dei dipendenti alla CTE, trovando tutti quelli il cui manager_id corrisponde a un id già presente nella CTE. Ogni iterazione scende di un livello. depth è solo un contatore che aggiungiamo per indentare l'output.

Funziona per alberi di qualsiasi profondità. Due livelli, dieci livelli: la query non cambia.

Trovare tutti gli antenati di una riga specifica

Inverti la direzione. Invece di scendere dalla radice, risali da un dipendente specifico per trovare l'intera catena dei suoi responsabili:

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;

L'ancoraggio è il dipendente di partenza. Ogni passo ricorsivo salta al genitore. SQLite si ferma quando arriva alla radice: manager_id IS NULL, quindi il join non trova niente.

Questo schema è utile per breadcrumb, commenti annidati, percorsi di categoria e ovunque tu debba "risalire fino in cima".

Condizioni di arresto e cicli infiniti

L'errore più comune è dimenticare la condizione di arresto o scriverne una che non scatta mai. Confronta:

-- Va avanti all'infinito:
WITH RECURSIVE bad(n) AS (
    SELECT 1
    UNION ALL
    SELECT n + 1 FROM bad
)
SELECT n FROM bad;

Non c'è nessuna clausola WHERE che prima o poi restituisca zero righe. SQLite proverà volentieri a contare fino all'infinito.

Due abitudini difensive:

1. Metti sempre nella parte ricorsiva una clausola WHERE che limiti la crescita.
2. Aggiungi LIMIT alla SELECT esterna come rete di sicurezza mentre sviluppi: se sbagli la condizione di arresto, la query termina comunque.

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

La CTE in sé è illimitata, ma LIMIT 5 ferma presto la query esterna. SQLite è abbastanza furbo da non continuare la ricorsione oltre quello che serve a LIMIT. Utile per esplorare; non sostituisce una vera condizione di arresto nel codice di produzione.

Cicli nei grafi

Gli alberi non possono avere cicli. I grafi in generale sì, e una CTE ricorsiva ingenua girerà all'infinito se i dati ne contengono uno. La soluzione è tenere traccia del percorso fatto finora e rifiutarsi di visitare di nuovo i nodi:

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 è una stringa di nodi già visitati separati da virgole. Prima di aggiungere un nuovo nodo, la clausola WHERE verifica che non sia già lì. Senza questa protezione, il ciclo 1 → 2 → 3 → 1 andrebbe avanti per sempre.

In SQL non esiste un "insieme dei visitati" integrato: te lo costruisci da solo, di solito come stringa o facendo un join con la CTE costruita fin lì.

CTE ricorsiva o self join

Se ti servono solo uno o due livelli di profondità, un self join è più semplice e più veloce:

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 dipendente, m.name AS responsabile
FROM employees e
LEFT JOIN employees m ON e.manager_id = m.id;

Così gestisci "chi è il responsabile diretto di ogni persona". Ma se ti serve "tutti quelli che fanno capo ad Ada, a qualsiasi profondità", cioè con una profondità sconosciuta, solo una CTE ricorsiva lo gestisce in modo pulito. Scegli lo strumento in base alla profondità che ti serve:

• Profondità fissa e piccola: self join, magari due o tre.
• Profondità sconosciuta o arbitraria: WITH RECURSIVE.

Modello mentale

Una CTE ricorsiva è un ciclo scritto in modo dichiarativo:

• L'ancoraggio è il valore iniziale del ciclo.
• La query ricorsiva è il corpo del ciclo: produce il gruppo successivo di righe a partire da quelle attuali.
• La condizione di arresto è il test di uscita del ciclo: quando restituisce zero righe, il ciclo finisce.
• UNION ALL accumula tutto nel risultato finale.

Una volta che questa corrispondenza ti è chiara, la sintassi smette di sembrarti strana. Stai scrivendo un ciclo for in SQL.

Prossimo passo: gli indici

Le CTE ricorsive percorrono molte righe, e il join dentro il passo ricorsivo viene eseguito a ogni iterazione. Se la colonna del join non è indicizzata, le prestazioni crollano in fretta. Gli indici sono il prossimo capitolo, e manager_id è proprio il tipo di colonna che ne trae vantaggio.