Laten we allereerst proberen de algoritmebeschrijving op de handleidingpagina te vereenvoudigen en te verduidelijken. Om het te vereenvoudigen, overweeg alleen union all in with recursive clausule voor nu (en union later):
WITH RECURSIVE pseudo-entity-name(column-names) AS (
Initial-SELECT
UNION ALL
Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name
Laten we, om het te verduidelijken, het uitvoeringsproces van de query in pseudocode beschrijven:
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
Of zelfs korter:de database-engine voert de eerste selectie uit en neemt de resultaatrijen als werkset. Vervolgens voert het herhaaldelijk recursieve selectie uit op de werkset, waarbij elke keer de inhoud van de werkset wordt vervangen door het verkregen queryresultaat. Dit proces eindigt wanneer een lege set wordt geretourneerd door recursieve selectie. En alle resultaatrijen die eerst door initiële selectie en vervolgens door recursieve selectie worden gegeven, worden verzameld en naar de buitenste selectie gevoerd, welk resultaat het algemene zoekresultaat wordt.
Deze zoekopdracht berekent faculteit van 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
Eerste selectie SELECT 1 F, 3 n geeft ons beginwaarden:3 voor argument en 1 voor functiewaarde.
Recursieve selectie SELECT F*n F, n-1 n from factorial where n>1 stelt dat elke keer dat we de waarde van de laatste functie moeten vermenigvuldigen met de waarde van het laatste argument en de waarde van het argument moeten verlagen.
Database-engine voert het als volgt uit:
Allereerst voert het initail select uit, wat de initiële status van de werkende recordset geeft:
F | n
--+--
1 | 3
Vervolgens transformeert het een werkende recordset met recursieve query en verkrijgt het zijn tweede status:
F | n
--+--
3 | 2
Dan derde staat:
F | n
--+--
6 | 1
In de derde staat is er geen rij die volgt op n>1 voorwaarde in recursieve selectie, dus werkset is loop-uitgangen.
Buitenste recordset bevat nu alle rijen, geretourneerd door initiële en recursieve selectie:
F | n
--+--
1 | 3
3 | 2
6 | 1
Outer select filtert alle tussenresultaten uit de buitenste recordset, waarbij alleen de uiteindelijke factoriële waarde wordt weergegeven die het algemene queryresultaat wordt:
F
--
6
En laten we nu eens kijken naar tabel 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
'Volledige boomstructuur uitvouwen ' betekent hier het sorteren van boomitems in voor mensen leesbare diepte-eerste volgorde terwijl ze hun niveaus en (misschien) paden berekenen. Beide taken (van correct sorteren en berekenen van niveau of pad) zijn niet oplosbaar in één (of zelfs een constant aantal) SELECT zonder de WITH RECURSIVE-clausule (of Oracle CONNECT BY-clausule, die niet wordt ondersteund door PostgreSQL). Maar deze recursieve query doet het werk (nou ja, bijna, zie de opmerking hieronder):
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
Database-engine voert het als volgt uit:
Ten eerste voert het initail select uit, wat alle items op het hoogste niveau (roots) van forest geeft. tafel:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
8 | | 1 | item 3 | item 3
6 | | 1 | item 2 | item 2
Vervolgens voert het recursieve selectie uit, die alle items van het 2e niveau uit forest geeft tafel:
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
Daarna voert het recursieve selectie opnieuw uit, waarbij items op 3D-niveau worden opgehaald:
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
En nu voert het recursieve selectie opnieuw uit, in een poging om items van het 4e niveau op te halen, maar er zijn er geen, dus de lus wordt afgesloten.
De buitenste SELECT stelt de juiste door mensen leesbare rijvolgorde in, sorterend op padkolom:
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
OPMERKING :de resulterende rijvolgorde blijft alleen correct als er geen leestekens zijn die voorafgaan aan / in de itemnamen. Als we Item 2 hernoemen in Item 1 * , het zal de rijvolgorde doorbreken, tussen Item 1 en zijn nakomelingen.
Een stabielere oplossing is het gebruik van tabtekens (E'\t' ) als padscheidingsteken in query (dat later kan worden vervangen door een beter leesbaar padscheidingsteken:in buitenste selectie, voordat het wordt weergegeven aan mensen of enz.). Door tabs gescheiden paden behouden de juiste volgorde totdat er tabs of controletekens in de itemnamen staan - wat gemakkelijk kan worden gecontroleerd en uitgesloten zonder verlies van bruikbaarheid.
Het is heel eenvoudig om de laatste zoekopdracht te wijzigen om een willekeurige substructuur uit te breiden - u hoeft alleen de voorwaarde parent_id is null te vervangen met perent_id=1 (bijvoorbeeld). Merk op dat deze zoekvariant alle niveaus en paden retourneert ten opzichte van Item 1 .
En nu over typische fouten . De meest opvallende typische fout die specifiek is voor recursieve zoekopdrachten, is het definiëren van slechte stopcondities in recursieve selectie, wat resulteert in oneindige looping.
Als we bijvoorbeeld where n>1 . weglaten voorwaarde in factoriële steekproef hierboven, zal de uitvoering van recursieve selectie nooit een lege set opleveren (omdat we geen voorwaarde hebben om een enkele rij uit te filteren) en zal het herhalen oneindig doorgaan.
Dat is de meest waarschijnlijke reden waarom sommige van uw zoekopdrachten vastlopen (de andere niet-specifieke maar nog steeds mogelijke reden is een zeer ineffectieve selectie, die in een eindige maar zeer lange tijd wordt uitgevoerd).
Er zijn niet veel RECURSIVE-specifieke zoekopdrachten voor richtlijnen te noemen, voor zover ik weet. Maar ik zou graag een (vrij voor de hand liggende) stapsgewijze recursieve procedure voor het maken van query's willen voorstellen.
-
Bouw en debug uw eerste selectie afzonderlijk.
-
Wikkel het in met steigers MET RECURSIEVE constructie
en begin met het bouwen en debuggen van uw recursieve selectie.
De aanbevolen scuffolding-constructie is als volgt:
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
Deze eenvoudigste buitenste selectie zal de hele buitenste recordset uitvoeren, die, zoals we weten, alle uitvoerrijen van de initiële selectie en elke uitvoering van de recursieve selectie in een lus in hun oorspronkelijke uitvoervolgorde bevat - net als in bovenstaande voorbeelden! De limit 1000 onderdeel voorkomt dat het blijft hangen en vervangt het door een te grote uitvoer waarin u het gemiste stoppunt kunt zien.
- Na het debuggen van initiële en recursieve select, bouw en debug je outer select.
En nu het laatste om te vermelden - het verschil in het gebruik van union in plaats van union all in with recursive clausule. Het introduceert rijuniciteitsbeperking die resulteert in twee extra regels in onze uitvoeringspseudocode:
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