suppression des doublons dans un SQL récursif

[dr_nilkog]

Bonjour,

J'ai un petit soucis de performances en utilisant du SQL récursif.

Mon problème à la base est relativement simple, j'ai une personne qui peut être reliée à une entité, qui est elle-même reliée à d'autres personnes qui peuvent être liées à d'autres entités, qui elle mêmes, etc...
Je me suis donc dis que c'était typiquement du récursif et je suis parti dans cette voie.
Le problème est que à chaque fois que je descend d'un niveau, mon SQL reprEnd toutes les données trouvées précédemment, les remultiplie (jointures), et cela fin par donner des temps de réponses catastrophiques pour la bonne et simple raison que je ne peux pas rajouter de clause distinct après le UNION ALL (je suis sous Z.os). La bibliographie ne m'a pas apporté de réponse à ce sujet, alors voilà y a t il des astuces pour éviter cette multiplication à l'infini ?

Voici un exemple :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
CREATE TABLE COUPLE
(NU_PERSONNE CHAR(8) NOT NULL
NU_ENTITE CHAR(6) NOT NULL);
 
INSERT INTO COUPLE VALUES ('PERS1', 'ENT1');
INSERT INTO COUPLE VALUES ('PERS2', 'ENT2');
INSERT INTO COUPLE VALUES ('PERS2', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS2', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS2', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS2', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS3', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS3', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS3', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS3', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS4', 'ENT3');
INSERT INTO COUPLE VALUES ('PERS4', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS4', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS4', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS5', 'ENT3');
INSERT INTO COUPLE VALUES ('PERS6', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS6', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS6', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS6', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS7', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS7', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS7', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS7', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS8', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS8', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS8', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS8', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS9', 'ENT1');
INSERT INTO COUPLE VALUES ('PERS9', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS10', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS10', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS10', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS10', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS11', 'ENT4');
INSERT INTO COUPLE VALUES ('PERS11', 'ENT5');
INSERT INTO COUPLE VALUES ('PERS11', 'ENT6');
INSERT INTO COUPLE VALUES ('PERS11', 'ENT7');
INSERT INTO COUPLE VALUES ('PERS12', 'ENT12');
INSERT INTO COUPLE VALUES ('PERS13', 'ENT13');
INSERT INTO COUPLE VALUES ('PERS14', 'ENT13');

Pour mon point d'entrée, si je lance avec PERS1 ou PERS2 à PERS11 je dois toujours obtenir en sortie les 11 (PERS1 à PERS11) personnes et uniquement celles-la car elles ont toutes un lien entre elles (PERS1 est associé à ENT1, ENT1 lui même associé à PERS9, elle même associée à ENT7, etc...).
En revanche si j'amorce mon récursif avec PERS12, je dois n'avoir en réponse que ENT12, car il n'y a aucune autre relation.
Et Enfin si j'amorce avec PERS12 ou PERS14, je dois obtenir en réponse PERS13 et PERS14 car liées entre elles par ENT13.
Sur cet exemple avec cette petite table les problèmes de doublons sont déjà pénalisants mais sur des tables conséquentes c'est inutile. D'autant plus que ces doublons m'empêchent de créée une condition de sortie autre que de compter les niveaux...

Ma requête de départ est la suivante :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
WITH RES_1 (NU_PERSONNE, NIVEAU)
                (SELECT DISTINCT B.NU_PERSONNE
                  , 0
            FROM COUPLE A JOIN COUPLE B
                           ON A.NU_ENTITE = B.NU_ENTITE
      UNION ALL
         SELECT B.NU_PERSONNE
                  , RES_1.NIVEAU + 1
            FROM RES_1
                        JOIN COUPLE A 
                           ON A.NU_PERSONNE= RES.NU_PERSONNE
                        JOIN COUPLE B
                           ON A.NU_ENTITE = B.NU_ENTITE
         WHERE RES_1.NIVEAU < 10)
SELECT DISCTINCT NU_PERSONNE
  FROM RES_1
  WITH UR;
)

[punkoff]

Bonjour,


Par rapport à votre jeux d'essai que voullez-vous comme résultat ?
J'ai du mal à comprendre votre besoin pour l'instant.

car présenté comme celà je ne vois pas l'approt du récursif, vu qu'un simple

Code sql :

1
2
3
 
SELECT DISTINCT personne
FROM ma_table

suffit ?


Peut être que le jeux d'essai n'est pas pertinant ?

si on reste sur l'idée du récursif, quel est votre condition d'entrée pour la 1ere requete ?
Ceci me semble peu restrictif :

Code sql :

1
2
3
4
 
SELECT DISTINCT B.NU_PERSONNE, 0
FROM COUPLE A 
JOIN COUPLE B ON A.NU_ENTITE = B.NU_ENTITE

[dr_nilkog]

Pour ne pas alourdir mon exemple j'ai mis uniquement les entités en relation. J'ai donc rajouté des couples qui n'ont aucune relation directe ou indirecte avec le reste de la liste. Ils ne doivent donc pas ressortir.

Pour mon point d'entrée, si je lance avec PERS1 ou PERS2 ou PERS 3 ... jusqu'à PERS11 je dois toujours obtenir en sortie les 11 personnes (PERS1 à PERS11) et uniquement celles-la car elles ont toutes un lien entre elles (PERS1 est associé à ENT1, ENT1 lui même associé à PERS9, elle même associée à ENT7, etc...).
En revanche si j'amorce mon récursif avec PERS12, je dois n'avoir en réponse que PERS12, car il n'y a aucune autre relation.
Et enfin si j'amorce avec PERS12 ou PERS14, je dois obtenir en réponse PERS13 et PERS14 car liées entre elles par ENT13.

Voilà j'espère avoir été plus clair.

[punkoff]

Pourquoi ne pas faire un simple :

Code sql :

1
2
3
4
5
 
SELECT DISTINCT nu_personne
FROM couple a
WHERE EXISTS (SELECT 1 FROM couple b WHERE a.nu_personne <> b.nu_personne
AND a.nu_entite = b.nu_entite)

Ensuite si vous voullez vraiment faire du recursif, je n'y suis pas encore arrivé avec votre exemple...à suivre

edit : je ne comprend toujours pas l'intérêt de faire du recursif dans votre cas, vu que votre besoin apparent est de sortir toutes les personnes qui ont une relation quelconque avec une autre entité.

[bernard59139]

j'ai fait un truc, ca ne me plait pas bcp; je verrai si je peux améliorer lundi

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
WITH RES_1 (PERS, REL,  NIVEAU) AS                           
      (SELECT  X.NU_PERSONNE, X.NU_ENTITE,  0                      
            FROM COUPLE AS X                                 
            WHERE X.NU_PERSONNE = 'PERS1'                       
      UNION ALL                                              
         SELECT A.NU_PERSONNE, A.NU_ENTITE, B.NIVEAU + 1           
            FROM COUPLE AS A, RES_1 AS B                     
            WHERE  (A.NU_ENTITE = B.REL                         
                   OR (A.NU_PERSONNE = B.PERS                   
                       AND A.NU_ENTITE <> B.REL)                
                   )                                         
              AND  B.NIVEAU <  5                             
      )
SELECT DISTINCT PERS
  FROM RES_1                                                 
  WITH UR;

[dr_nilkog]

Envoyé par bernard59139

j'ai fait un truc, ca ne me plait pas bcp; je verrai si je peux améliorer lundi

Techniquement cela marche, et c'est d'ailleurs une solution que j'avais expérimenté mais il y a deux problèmes :
- D'une part sur des tables assez grosses (dasn mon cas environ 600.000 enreg) on retrouve le problèmes de doubons extrèmement pénalisant, car à chaque niveau on multiplie les résulats de manière exponentielle, a cause de l'interdiction du distinct dans le UNION ALL
- On est obligé de fournir à DB2 un niveau d'arrêt (dans votre exemple 5), sinon il continue de manière infinie, et met la machine à genou assez rapidement.

[dr_nilkog]

Envoyé par punkoff

Pourquoi ne pas faire un simple :

Ensuite si vous voullez vraiment faire du recursif, je n'y suis pas encore arrivé avec votre exemple...à suivre

edit : je ne comprend toujours pas l'intérêt de faire du recursif dans votre cas, vu que votre besoin apparent est de sortir toutes les personnes qui ont une relation quelconque avec une autre entité.

Tout simplement parceque cela ne marche pas, mon point d'entrée est une personne (ce que je ne retrouve pas dans votre exemple), et de proche en proche en passant à la requête une personne entre PERS1 et PERS11, je dois retrouver les 10 autres, et aucunement PERS12, PERS13 ou PERS14 qui n'ont aucune relation avec aucune de ces 11 personnes.

Nota : je ne suis pas un fana du récursif, mais je ne vois pas d'autres façon d'y arriver à coup sur.

[bernard59139]

Je me doutais qu'avec plusieurs milliers de lignes en entrée ca génèrerai plusieurs millions de lignes en sortie.
Ca ne me plaisait pas.

il faut trouver le moyen "simple" d'arreter la requête et de ne pas générer des doublons. J'avais pensé à un "not exists", mais db2 refusait (je donnerai le sqlcode lundi)

perso, à part faire avec un programme; je ne pense pas que le sql-récursif donne quelque chose de très efficace.
Avec Oracle, il y a des trucs, mais spécifiques à oracle.

[K2R400]

Salut,

Je prends cette discussion en cours.

Envoyé par bernard59139

il faut trouver le moyen "simple" d'arreter la requête et de ne pas générer des doublons. J'avais pensé à un "not exists", mais db2 refusait (je donnerai le sqlcode lundi)

Pour éviter les données Cycliques il y a la clause CYCLE.
Ta requête est bien, il te manquait juste un AND supplémentaire pour éviter des entrées supplémentaires.

Ce qui donne :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
WITH RES_1 (PERS, REL,  NIVEAU) AS                           
      (SELECT  X.NU_PERSONNE, X.NU_ENTITE,  0                      
            FROM COUPLE AS X                                 
            WHERE X.NU_PERSONNE = 'PERS1'                       
      UNION ALL                                              
         SELECT A.NU_PERSONNE, A.NU_ENTITE, B.NIVEAU + 1           
            FROM COUPLE AS A, RES_1 AS B                     
            WHERE  (A.NU_ENTITE   = B.REL  AND A.NU_PERSONNE <> B.PERS)                         
               OR  (A.NU_PERSONNE = B.PERS AND A.NU_ENTITE   <> B.REL ) 
       )                
     Cycle PERS, REL SET DonneesCycliques TO '1' DEFAULT '0'
 
SELECT *
  FROM RES_1                                                 
 WHERE DonneesCycliques = '0'

A tester selon les différentes versions de DB2

[K2R400]

Celle-ci devrait être plus performante car elle limite au maximum les entrées indésirables donc la profondeur.

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
 
WITH T1 (PERS, ENT,  NIVEAU, LIEN_PERS, LIEN_ENT) AS                           
      (SELECT  NU_PERSONNE, NU_ENTITE,  0, NU_PERSONNE, NULLIF ('', '')
            FROM COUPLE                               
            WHERE NU_PERSONNE = 'PERS1'                       
       UNION ALL                                              
       SELECT NU_PERSONNE, NU_ENTITE, NIVEAU + 1,
        CASE 
  	  WHEN  (NU_ENTITE   <> ENT AND NU_PERSONNE =  PERS ) THEN NU_PERSONNE
	END LIEN_PERS, 
 
        CASE 
  	  WHEN  (NU_ENTITE   =  ENT AND NU_PERSONNE <> PERS ) THEN NU_ENTITE
	END LIEN_ENT 
 
       FROM COUPLE, T1                     
       WHERE  (NU_ENTITE   =  ENT   AND NU_PERSONNE <> PERS AND  NU_PERSONNE <> LIEN_PERS)      
          OR  (NU_ENTITE   <> ENT   AND NU_PERSONNE  = PERS AND  NU_ENTITE   <> LIEN_ENT)       
 
       )                
 
  Cycle LIEN_PERS SET DonneesCycliques TO '1' DEFAULT '0'
 
SELECT DISTINCT PERS FROM T1

[dr_nilkog]

Envoyé par K2R400

Pour éviter les données Cycliques il y a la clause CYCLE.

Malheureusement DB2 pour Z/Os ne semble pas reconnaître cette clause CYCLE.