Requêtes hiérarchiques : éviter les boucles infinies

(sujet préalablement traité avec la version 9.4)

Explorer l’infini ?

      La requête présentée pour hiérarchiser le clan des géants a un point faible. Elle peut ne jamais rendre la main si un cycle existe. Exemple :

select version(); version ----------------------------------------------------------------------------------------------------------------------------- PostgreSQL 15.1 (Debian 15.1-1.pgdg110+1) on x86_64-pc-linux-gnu, compiled by gcc (Debian 10.2.1-6) 10.2.1 20210110, 64-bit (1 ligne) create table geants(idg smallint, nmg character varying, actif boolean, idg_chef smallint); CREATE TABLE insert into geants(idg, nmg, actif, idg_chef) values (1, 'Oumpfor', true, null), (2, 'Galdor', false, 7), (3, 'Goldar', false, 7), (4, 'Goldur', true, 7), (5, 'Guldor', false, 7), (6, 'Geldor', false, 7), (7, 'Golder', false, 8), (8, 'Gildir', true, 1), (9, 'Ambact', true, 1), (10, 'Amdas', false, 1), (11, 'Baldor', false, 8), (12, 'Boldar', false, 8), (13, 'Boldur', false, 8), (14, 'Buldor', false, 8), (15, 'Daldor', false, 16), (16, 'Doldar', true, 18), (17, 'Doldur', false, 18), (18, 'Duldor', false, 1), (19, 'Faldor', false, 20), (20, 'Foldar', false, 21), (21, 'Foldur', false, 1), (22, 'Haldor', false, 23), (23, 'Holdar', true, 24), (24, 'Holdur', true, 25), (25, 'Huldor', false, 26), (26, 'Heldor', false, 8), (27, 'Caldor', false, 28), (28, 'Coldar', false, 31), (29, 'Coldur', false, 30), (30, 'Culdor', false, 31), (31, 'Celdor', false, 1), (32, 'Polder', false, 33), (33, 'Pildir', false, 1), (34, 'Faldor', false, 37), (35, 'Foldar', false, 37), (36, 'Foldur', false, 37), (37, 'Fuldor', false, 1), (38, 'Fuldor', false, 39), (39, 'Fuldor', false, 40), (40, 'Fuldor', false, 38); INSERT 0 40 WITH RECURSIVE hierarchie_clan_asc(idg, idg_chef, ischef) AS ( SELECT idg, idg_chef, false FROM geants where idg_chef is not null UNION ALL SELECT g.idg, g.idg_chef, true FROM hierarchie_clan_asc AS h join geants AS g on (h.idg_chef = g.idg) ), hierarchie_clan_desc(idg, nmg, actif, idg_chef, nmg_chef, niveau) AS ( SELECT idg, nmg, actif, null::smallint, null::text, 1 FROM geants where idg_chef is null UNION ALL SELECT g.idg, g.nmg, g.actif, h.idg, h.nmg, h.niveau+1 FROM hierarchie_clan_desc AS h join geants AS g on (h.idg = g.idg_chef) ), grand_chef(idg) as (select idg from geants where idg_chef is null), gardiens(idg) as ((select idg from geants where idg_chef = (select idg from grand_chef)) except (select idg_chef from geants)), grands_mastards(idg) as (select h.idg from (select idg, idg_chef from hierarchie_clan_asc where ischef is true) h join grand_chef gc on (h.idg_chef = gc.idg) group by h.idg having count(*) >= 3), mastards(idg) as ((select idg_chef from geants where idg_chef is not null) except (select idg from grands_mastards))-- , -- paltoquets(idg) as (select idg from geants except (select idg from grand_chef union all select idg from gardiens union all select idg from grands_mastards union all select idg from mastards)) SELECT idg, nmg, nmg_chef, actif, case when idg = (select idg from grand_chef) then 'GRAND CHEF' when idg in (select idg from gardiens) then 'GARDIEN' when idg in (select idg from grands_mastards) then 'GRAND MASTARD' when idg in (select idg from mastards) then 'MASTARD' -- when idg in (select idg from paltoquets) then 'PALTOQUET' -- else 'RANG INCONNU' else 'PALTOQUET' end as rang, niveau FROM hierarchie_clan_desc order by idg asc ; ........... ON ATTEND ! ........... Requête d'annulation envoyée ERREUR: annulation de la requête à la demande de l’utilisateur

      Quelle partie de la requête est susceptible de boucler à l’infini ? Pas la CTE hierarchie_clan_desc puisque la condition de départ est "idg_chef is null" et que la condition d’itération est (h.idg = g.idg_chef). En revanche hierarchie_clan_asc avec sa condition de départ "idg_chef is not null" et sa condition d’itération (h.idg_chef = g.idg) peut boucler.
      Ici le géant 38 a pour chef le géant 39 qui a pour chef le géant 40...qui a pour chef le géant 38 ! Comment détecter cela ?Il a toujours été possible de détecter les cycles mais, depuis PostgreSQL 14, la syntaxe est directe avec le mot clé CYCLE :

WITH RECURSIVE hierarchie_clan_asc(idg, idg_chef, ischef) AS ( SELECT idg, idg_chef, false FROM geants where idg_chef is not null UNION ALL SELECT g.idg, g.idg_chef, true FROM hierarchie_clan_asc AS h join geants AS g on (h.idg_chef = g.idg) ) CYCLE idg SET is_cycle USING path, hierarchie_clan_desc(idg, nmg, actif, idg_chef, nmg_chef, niveau) AS ( SELECT idg, nmg, actif, null::smallint, null::text, 1 FROM geants where idg_chef is null UNION ALL SELECT g.idg, g.nmg, g.actif, h.idg, h.nmg, h.niveau+1 FROM hierarchie_clan_desc AS h join geants AS g on (h.idg = g.idg_chef) ) SEARCH DEPTH FIRST BY idg SET orderbr, grand_chef(idg) as (select idg from geants where idg_chef is null), gardiens(idg) as ((select idg from geants where idg_chef = (select idg from grand_chef)) except (select idg_chef from geants)), grands_mastards(idg) as (select h.idg from (select idg, idg_chef from hierarchie_clan_asc where ischef is true) h join grand_chef gc on (h.idg_chef = gc.idg) group by h.idg having count(*) >= 3), mastards(idg) as ((select idg_chef from geants where idg_chef is not null) except (select idg from grands_mastards))-- , -- paltoquets(idg) as (select idg from geants except (select idg from grand_chef union all select idg from gardiens union all select idg from grands_mastards union all select idg from mastards)) SELECT idg, nmg, nmg_chef, actif, case when idg = (select idg from grand_chef) then 'GRAND CHEF' when idg in (select idg from gardiens) then 'GARDIEN' when idg in (select idg from grands_mastards) then 'GRAND MASTARD' when idg in (select idg from mastards) then 'MASTARD' -- when idg in (select idg from paltoquets) then 'PALTOQUET' -- else 'RANG INCONNU' else 'PALTOQUET' end as rang, niveau FROM hierarchie_clan_desc order by orderbr, idg ; idg | nmg | nmg_chef | actif | rang | niveau -----+---------+----------+-------+---------------+-------- 1 | Oumpfor | | t | GRAND CHEF | 1 8 | Gildir | Oumpfor | t | GRAND MASTARD | 2 7 | Golder | Gildir | f | MASTARD | 3 2 | Galdor | Golder | f | PALTOQUET | 4 3 | Goldar | Golder | f | PALTOQUET | 4 4 | Goldur | Golder | t | PALTOQUET | 4 5 | Guldor | Golder | f | PALTOQUET | 4 6 | Geldor | Golder | f | PALTOQUET | 4 11 | Baldor | Gildir | f | PALTOQUET | 3 12 | Boldar | Gildir | f | PALTOQUET | 3 13 | Boldur | Gildir | f | PALTOQUET | 3 14 | Buldor | Gildir | f | PALTOQUET | 3 26 | Heldor | Gildir | f | MASTARD | 3 25 | Huldor | Heldor | f | MASTARD | 4 24 | Holdur | Huldor | t | MASTARD | 5 23 | Holdar | Holdur | t | MASTARD | 6 22 | Haldor | Holdar | f | PALTOQUET | 7 9 | Ambact | Oumpfor | t | GARDIEN | 2 10 | Amdas | Oumpfor | f | GARDIEN | 2 18 | Duldor | Oumpfor | f | GRAND MASTARD | 2 16 | Doldar | Duldor | t | MASTARD | 3 15 | Daldor | Doldar | f | PALTOQUET | 4 17 | Doldur | Duldor | f | PALTOQUET | 3 21 | Foldur | Oumpfor | f | MASTARD | 2 20 | Foldar | Foldur | f | MASTARD | 3 19 | Faldor | Foldar | f | PALTOQUET | 4 31 | Celdor | Oumpfor | f | GRAND MASTARD | 2 28 | Coldar | Celdor | f | MASTARD | 3 27 | Caldor | Coldar | f | PALTOQUET | 4 30 | Culdor | Celdor | f | MASTARD | 3 29 | Coldur | Culdor | f | PALTOQUET | 4 33 | Pildir | Oumpfor | f | MASTARD | 2 32 | Polder | Pildir | f | PALTOQUET | 3 37 | Fuldor | Oumpfor | f | GRAND MASTARD | 2 34 | Faldor | Fuldor | f | PALTOQUET | 3 35 | Foldar | Fuldor | f | PALTOQUET | 3 36 | Foldur | Fuldor | f | PALTOQUET | 3 (37 lignes)

      Le cycle est détecté par "CYCLE idg SET is_cycle USING path".
      A noter que j'ai utilisé une autre nouveauté de PostgreSQL 14 pour ordonner par branches hiérarchiques plutôt que via les identifiants de géant en utilisant la syntaxe "SEARCH DEPTH FIRST BY idg SET orderbr". Si vous dessinez les branches, c'est un tri de haut en bas puis de gauche à droite. Il serait aussi possible de trier dans la largeur donc d'abord de gauche à droite puis de haut en bas avec "SEARCH BREADTH FIRST BY idg SET orderbr". C'était bien sûr possible avant PostgreSQL 14 mais il est plus simple d'utiliser la syntaxe dédiée.

Mise à jour : 3/12/2022