Tout d'abord, essayons de simplifier et de clarifier la description de l'algorithme donnée sur la page de manuel. Pour simplifier, considérez uniquement union all en with recursive clause pour l'instant (et union plus tard):
WITH RECURSIVE pseudo-entity-name(column-names) AS (
Initial-SELECT
UNION ALL
Recursive-SELECT using pseudo-entity-name
)
Outer-SELECT using pseudo-entity-name
Pour le clarifier, décrivons le processus d'exécution de la requête en pseudo-code :
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
Ou encore plus court - Le moteur de base de données exécute la sélection initiale, en prenant ses lignes de résultats comme ensemble de travail. Ensuite, il exécute à plusieurs reprises une sélection récursive sur le jeu de travail, en remplaçant à chaque fois le contenu du jeu de travail par le résultat de la requête obtenu. Ce processus se termine lorsque l'ensemble vide est renvoyé par une sélection récursive. Et toutes les lignes de résultats données d'abord par la sélection initiale, puis par la sélection récursive sont rassemblées et transmises à la sélection externe, dont le résultat devient le résultat global de la requête.
Cette requête calcule factorielle de 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
Sélection initiale SELECT 1 F, 3 n nous donne des valeurs initiales :3 pour l'argument et 1 pour la valeur de la fonction.
Sélection récursive SELECT F*n F, n-1 n from factorial where n>1 indique que chaque fois que nous devons multiplier la valeur de la dernière fonction par la valeur du dernier argument et décrémenter la valeur de l'argument.
Le moteur de base de données l'exécute comme ceci :
Tout d'abord, il exécute initail select, qui donne l'état initial du jeu d'enregistrements de travail :
F | n
--+--
1 | 3
Ensuite, il transforme le jeu d'enregistrements de travail avec une requête récursive et obtient son deuxième état :
F | n
--+--
3 | 2
Puis troisième état :
F | n
--+--
6 | 1
Dans le troisième état il n'y a pas de ligne qui suit n>1 condition dans la sélection récursive, donc le jeu de travail est la sortie de la boucle.
Le jeu d'enregistrements externe contient désormais toutes les lignes, renvoyées par la sélection initiale et récursive :
F | n
--+--
1 | 3
3 | 2
6 | 1
La sélection externe filtre tous les résultats intermédiaires du jeu d'enregistrements externe, affichant uniquement la valeur factorielle finale qui devient le résultat global de la requête :
F
--
6
Et maintenant considérons la table 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
'Développer l'arborescence complète ' ici signifie trier les éléments de l'arbre dans l'ordre de profondeur d'abord lisible par l'homme tout en calculant leurs niveaux et (peut-être) leurs chemins. Les deux tâches (de niveau ou de chemin de tri et de calcul corrects) ne peuvent pas être résolues dans un (ou même un nombre constant de) SELECT sans utiliser la clause WITH RECURSIVE (ou la clause Oracle CONNECT BY, qui n'est pas prise en charge par PostgreSQL). Mais cette requête récursive fait le travail (enfin, presque, voir la note ci-dessous) :
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
Le moteur de base de données l'exécute comme ceci :
Tout d'abord, il exécute initail select, qui donne tous les éléments de plus haut niveau (racines) de forest tableau :
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
1 | | 1 | item 1 | item 1
8 | | 1 | item 3 | item 3
6 | | 1 | item 2 | item 2
Ensuite, il exécute une sélection récursive, qui donne tous les éléments de 2ème niveau de forest tableau :
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
Ensuite, il exécute à nouveau la sélection récursive, récupérant les éléments de niveau 3D :
id | parent_id | level | name | path
---+-----------+-------+------------------+----------------------------------------
5 | 3 | 3 | subsubitem 1.2.1 | item 1 / subitem 1.2 / subsubitem 1.2.1
Et maintenant, il exécute à nouveau la sélection récursive, essayant de récupérer les éléments de niveau 4, mais il n'y en a aucun, donc la boucle se termine.
Le SELECT externe définit l'ordre correct des lignes lisibles par l'homme, en triant sur la colonne du chemin :
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
REMARQUE :L'ordre des lignes résultant restera correct uniquement s'il n'y a pas de caractères de ponctuation collation-preceeding / dans les noms d'éléments. Si on renomme Item 2 dans Item 1 * , il rompra l'ordre des lignes, se tenant entre Item 1 et ses descendants.
Une solution plus stable consiste à utiliser le caractère de tabulation (E'\t' ) comme séparateur de chemin dans la requête (qui peut être remplacé par un séparateur de chemin plus lisible plus tard :dans la sélection externe, avant de s'afficher à l'homme ou etc.). Les chemins séparés par des tabulations conserveront l'ordre correct jusqu'à ce qu'il y ait des tabulations ou des caractères de contrôle dans les noms d'éléments - qui peuvent facilement être vérifiés et exclus sans perte de convivialité.
Il est très simple de modifier la dernière requête pour développer n'importe quel sous-arbre arbitraire - il vous suffit de remplacer la condition parent_id is null avec perent_id=1 (par exemple). Notez que cette variante de requête renverra tous les niveaux et chemins relatifs à Item 1 .
Et maintenant sur les erreurs typiques . L'erreur typique la plus notable spécifique aux requêtes récursives est la définition de mauvaises conditions d'arrêt dans la sélection récursive, ce qui entraîne une boucle infinie.
Par exemple, si nous omettons where n>1 condition dans l'échantillon factoriel ci-dessus, l'exécution de la sélection récursive ne donnera jamais un ensemble vide (car nous n'avons aucune condition pour filtrer une seule ligne) et la boucle se poursuivra indéfiniment.
C'est la raison la plus probable pour laquelle certaines de vos requêtes se bloquent (l'autre raison non spécifique mais toujours possible est select très inefficace, qui s'exécute en un temps fini mais très long).
Il n'y a pas beaucoup de directives d'interrogation spécifiques à RECURSIVE à mentionner, autant que je sache. Mais je voudrais suggérer (plutôt évident) une procédure de construction de requêtes récursives étape par étape.
-
Construisez et déboguez séparément votre sélection initiale.
-
Enveloppez-le d'un échafaudage WITH RECURSIVE construct
et commencez à créer et à déboguer votre sélection récursive.
La construction d'échafaudage recommandée ressemble à ceci :
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
Cette sélection externe la plus simple affichera l'intégralité du jeu d'enregistrements externe, qui, comme nous le savons, contient toutes les lignes de sortie de la sélection initiale et chaque exécution de sélection récursive dans une boucle dans leur ordre de sortie d'origine - comme dans les exemples ci-dessus ! La limit 1000 la pièce empêchera l'accrochage, en la remplaçant par une sortie surdimensionnée dans laquelle vous pourrez voir le point d'arrêt manqué.
- Après le débogage de la sélection initiale et récursive, créez et déboguez votre sélection externe.
Et maintenant la dernière chose à mentionner - la différence dans l'utilisation de union au lieu de union all en with recursive clause. Il introduit une contrainte d'unicité de ligne qui se traduit par deux lignes supplémentaires dans notre pseudocode d'exécution :
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
