Prima di tutto, cerchiamo di semplificare e chiarire la descrizione dell'algoritmo fornita nella pagina di manuale. Per semplificare considera solo union all in with recursive per ora (e union dopo):
WITH RECURSIVE pseudo-entity-name(column-names) AS (
Initial-SELECT
UNION ALL
Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name
Per chiarirlo, descriviamo il processo di esecuzione della query in pseudo codice:
working-recordset = result of Initial-SELECT
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
O anche più breve:il motore di database esegue la selezione iniziale, prendendo le righe dei risultati come set di lavoro. Quindi esegue ripetutamente la selezione ricorsiva sul working set, sostituendo ogni volta il contenuto del working set con il risultato della query ottenuto. Questo processo termina quando l'insieme vuoto viene restituito dalla selezione ricorsiva. E tutte le righe dei risultati fornite prima dalla selezione iniziale e poi dalla selezione ricorsiva vengono raccolte e inviate alla selezione esterna, il cui risultato diventa il risultato complessivo della query.
Questa query sta calcolando fattoriale di 3:
WITH RECURSIVE factorial(F,n) AS (
SELECT 1 F, 3 n
UNION ALL
SELECT F*n F, n-1 n from factorial where n>1
)
SELECT F from factorial where n=1
Selezione iniziale SELECT 1 F, 3 n ci fornisce i valori iniziali:3 per argomento e 1 per valore funzione.
Selezione ricorsiva SELECT F*n F, n-1 n from factorial where n>1 afferma che ogni volta che dobbiamo moltiplicare il valore dell'ultima funzione per il valore dell'ultimo argomento e decrementare il valore dell'argomento.
Il motore di database lo esegue in questo modo:
Per prima cosa esegue initail select, che fornisce lo stato iniziale del recordset di lavoro:
F | n
--+--
1 | 3
Quindi trasforma il recordset di lavoro con una query ricorsiva e ottiene il suo secondo stato:
F | n
--+--
3 | 2
Poi terzo stato:
F | n
--+--
6 | 1
Nel terzo stato non c'è riga che segue n>1 condizione nella selezione ricorsiva, quindi il working set è il loop esce.
Il recordset esterno ora contiene tutte le righe, restituite dalla selezione iniziale e ricorsiva:
F | n
--+--
1 | 3
3 | 2
6 | 1
La selezione esterna filtra tutti i risultati intermedi dal recordset esterno, mostrando solo il valore fattoriale finale che diventa il risultato complessivo della query:
F
--
6
E ora consideriamo la tabella forest(id,parent_id,name) :
id | parent_id | name
---+-----------+-----------------
1 | | item 1
2 | 1 | subitem 1.1
3 | 1 | subitem 1.2
4 | 1 | subitem 1.3
5 | 3 | subsubitem 1.2.1
6 | | item 2
7 | 6 | subitem 2.1
8 | | item 3
'Espansione albero completo ' qui significa ordinare gli elementi dell'albero in base all'ordine di profondità leggibile dall'uomo durante il calcolo dei loro livelli e (forse) percorsi. Entrambe le attività (di ordinamento corretto e calcolo del livello o del percorso) non sono risolvibili in uno (o anche in qualsiasi numero costante di) SELECT senza utilizzare la clausola WITH RECURSIVE (o la clausola Oracle CONNECT BY, che non è supportata da PostgreSQL). Ma questa query ricorsiva fa il lavoro (beh, lo fa quasi, vedi la nota sotto):
WITH RECURSIVE fulltree(id,parent_id,level,name,path) AS (
SELECT id, parent_id, 1 as level, name, name||'' as path from forest where parent_id is null
UNION ALL
SELECT t.id, t.parent_id, ft.level+1 as level, t.name, ft.path||' / '||t.name as path
from forest t, fulltree ft where t.parent_id = ft.id
)
SELECT * from fulltree order by path
Il motore di database lo esegue in questo modo:
In primo luogo, esegue initail select, che fornisce tutti gli elementi di livello più alto (radici) da forest tabella:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
8 | | 1 | item 3 | item 3
6 | | 1 | item 2 | item 2
Quindi, esegue la selezione ricorsiva, che fornisce tutti gli elementi di 2° livello da forest tabella:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
Quindi, esegue nuovamente la selezione ricorsiva, recuperando elementi di livello 3D:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
E ora esegue di nuovo la selezione ricorsiva, cercando di recuperare oggetti di 4° livello, ma non ce ne sono, quindi il ciclo si chiude.
Il SELECT esterno imposta l'ordine delle righe leggibile corretto, ordinando in base alla colonna del percorso:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
2 | 1 | 2 | subitem 1.1 | item 1 / subitem 1.1
3 | 1 | 2 | subitem 1.2 | item 1 / subitem 1.2
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
4 | 1 | 2 | subitem 1.3 | item 1 / subitem 1.3
6 | | 1 | item 2 | item 2
7 | 6 | 2 | subitem 2.1 | item 2 / subitem 2.1
8 | | 1 | item 3 | item 3
NOTA :L'ordine delle righe risultante rimarrà corretto solo finché non ci sono caratteri di punteggiatura che precedono il / nei nomi degli elementi. Se rinominiamo Item 2 in Item 1 * , interromperà l'ordine delle righe, che si trova tra Item 1 e i suoi discendenti.
Una soluzione più stabile è usare il carattere di tabulazione (E'\t' ) come separatore di percorso nella query (che può essere sostituito da un separatore di percorso più leggibile in seguito:nella selezione esterna, prima della visualizzazione in umano o ecc.). I percorsi separati da tabulazioni manterranno l'ordine corretto finché non ci saranno tabulazioni o caratteri di controllo nei nomi degli elementi, che possono essere facilmente controllati ed esclusi senza perdita di usabilità.
È molto semplice modificare l'ultima query per espandere qualsiasi sottoalbero arbitrario:devi solo sostituire la condizione parent_id is null con perent_id=1 (Per esempio). Tieni presente che questa variante di query restituirà tutti i livelli e percorsi relativi a Item 1 .
E ora sugli errori tipici . L'errore tipico più notevole, specifico delle query ricorsive, è la definizione di condizioni di arresto errato nella selezione ricorsiva, che si traduce in un ciclo infinito.
Ad esempio, se omettiamo where n>1 condizione nel campione fattoriale sopra, l'esecuzione di select ricorsiva non darà mai un set vuoto (perché non abbiamo alcuna condizione per filtrare la singola riga) e il ciclo continuerà all'infinito.
Questo è il motivo più probabile per cui alcune delle tue query si bloccano (l'altro motivo non specifico ma ancora possibile è select molto inefficace, che viene eseguito in un tempo limitato ma molto lungo).
Non ci sono molte linee guida per le query specifiche RICORSIVE per citare, per quanto ne so. Ma vorrei suggerire (piuttosto ovvio) una procedura ricorsiva di creazione di query passo dopo passo.
-
Crea ed esegui il debug separatamente della tua selezione iniziale.
-
Avvolgilo con l'impalcatura WITH RECURSIVE costrutto
e inizia a creare e a eseguire il debug della tua selezione ricorsiva.
Il costrutto di scuffold consigliato è questo:
WITH RECURSIVE rec( <Your column names> ) AS (
<Your ready and working initial SELECT>
UNION ALL
<Recursive SELECT that you are debugging now>
)
SELECT * from rec limit 1000
Questa selezione esterna più semplice produrrà l'intero recordset esterno, che, come sappiamo, contiene tutte le righe di output dalla selezione iniziale e ogni esecuzione di selezione ricorsiva in un ciclo nel loro ordine di output originale, proprio come negli esempi sopra! Il limit 1000 parte impedirà l'impiccagione, sostituendola con un output sovradimensionato in cui potrai vedere il punto di sosta mancato.
- Dopo il debug della selezione iniziale e ricorsiva, compila ed esegui il debug della selezione esterna.
E ora l'ultima cosa da menzionare:la differenza nell'utilizzo di union invece di union all in with recursive clausola. Introduce il vincolo di unicità della riga che si traduce in due righe extra nel nostro pseudocodice di esecuzione:
working-recordset = result of Initial-SELECT
discard duplicate rows from working-recordset /*union-specific*/
append working-recordset to empty outer-recordset
while( working-recordset is not empty ) begin
new working-recordset = result of Recursive-SELECT
taking previous working-recordset as pseudo-entity-name
discard duplicate rows and rows that have duplicates in outer-recordset
from working-recordset /*union-specific*/
append working-recordset to outer-recordset
end
overall-result = result of Outer-SELECT
taking outer-recordset as pseudo-entity-name
