Forum Programmation.SQL performances de JOIN / EXISTS sur postgres

Posté par PyroTokyo le 04 juin 2012 à 09:40.

Étiquettes : aucune

juin

2012

Bonjour tout le monde.
Juste une petite chose qui me turlupine, parce que ca me plombe mes performances de facon assez phenomenale.
Je suis sous Postgres, et je dispose de 2 tables, user et email.
User contient environ 40 millions d'entrees, et email 40000 environ (base en pleine construction, donc pas encore enorme).

J'ai envie de repertorier les utilisateurs ayant envoye ou recu des messages.
Mon ORM me genere la requete suivante (SQLAlchemy)

select user.id from user where 
exists (select 1 from email where user.id = email.source_id) or
exists (select 1 from email where user.id = email.target_id)

Moi je veux bien, mais j'ai lance la requete il y a 15 minutes, et elle vient de se terminer avec 32000 resultats.
Enlever une des 2 clauses exists me donne un temps d'execution de 20 secs environ.
Passer par un join du type

select distinct(user.id) from user, email where email.source_id = user.id or email.target_id = user.id

Me donne le resultat en 25 secs environ avec egalement 32000 lignes.

Il y a vraiment un probleme avec le exists ou alors ca vient de moi qui ai loupe quelque chose ?
je precise que pour user.id est primaire avec un index, source_id et target_id sont des FK avec un index egalement, tout le monde ayant une contrainte NOT NULL.

# test unitaire

Posté par NeoX le 04 juin 2012 à 09:45. Évalué à 2.

je ne suis pas expert en postgresql
quand j'ai des doutes sur des requetes imbriquées,
je teste mes requetes une par une

dans ton cas est-ce qu'individuellement les requetes fonctionnent ?

select 1 from email where user.id = email.target_id

et

select 1 from email where user.id = email.source_id

combien de temps chacune ?
- [^] # Re: test unitaire
  
  Posté par PyroTokyo le 04 juin 2012 à 09:55. Évalué à 1.
  
  J'ai essaye en ne laissant qu'une clause EXISTS sur deux, et dans les deux cas je tombe a environ 15 secondes. Avec un OR, je m'attendais grosso modo au double, mais non. On passe a 800 secondes ^{^;}
  - [^] # Re: test unitaire
    
    Posté par NeoX le 04 juin 2012 à 11:54. Évalué à 2.
    
    il fait peut-etre 40.000x40.000 pour tester le OR
    
    1er enregistrement du premier cas OR 40.000 du deuxieme
    2eme enrgistrement OR 40.000 du deuxieme
    etc
    - [^] # Re: test unitaire
      
      Posté par Flo le 04 juin 2012 à 12:01. Évalué à 2.
      
      Sans explain on peut faire des hypothèses longtemps… Cela ne sert pas à grand-chose.
      Essaie un explain analyze si possible (cela donne les vraies valeur à côté des valeurs estimées)
# explain

Posté par netsurfeur le 04 juin 2012 à 11:00. Évalué à 3.

As-tu essayé de faire un EXPLAIN de ta requête ?
Ça affiche le plan d'exécution et permet de voir si les index sont utilisés.
- [^] # Re: explain
  
  Posté par Flo le 04 juin 2012 à 11:44. Évalué à 2.
  
  Et surtout, si les 2 requêtes "select 1…." ne seraient pas exécutées en boucle (c'est-à-dire testées pour chaque user.id).
  Cela pourrait expliquer la très grande différence de temps (et ce, y compris si les index sont utilisés).
# Evaluation paresseuse

Posté par fredoche le 04 juin 2012 à 13:53. Évalué à 1.

À la grosse louche, j'imagine que le parser de requête optimise la requête en groupant le premier select et la clause à gauche du OR pour ne faire qu'une seule jointure. Ensuite, pour chaque ligne restante, si le résultat est false, alors on va voir s'il y a moyen de repêcher la ligne si la clause "exists" à droite du OR est true. Dans le cas général où les requêtes sont très différentes à gauche et à droite du OR, ça doit procurer un boost de performances. Dans le cas particulier ou, en fait, les deux clauses fonctionnent sur les même données, visiblement ça induit une baisse de perf assez phénoménale.
Bon, tu avais peut être déja eu le même raisonnement, et j'ai pas un avis d'expert, mais si j'étais un sgbdr (le rêve), bin je ferais ça.
# explain

Posté par PyroTokyo le 04 juin 2012 à 14:49. Évalué à 1.
Bon, je viens de faire un explain sur la requete, mais j'avoue ne pas tout comprendre ^{^;}
```
"Nested Loop Semi Join  (cost=8.30..638694661.54 rows=22164 width=4) (actual time=302.577..732235.774 rows=31863 loops=1)"
"  ->  Seq Scan on mixiuser  (cost=0.00..874903.36 rows=52453936 width=4) (actual time=32.473..211619.619 rows=52049079 loops=1)"
"  ->  Bitmap Heap Scan on email  (cost=8.30..85.48 rows=20 width=8) (actual time=0.007..0.007 rows=0 loops=52049079)"
"        Recheck Cond: ((mixiuser.id = target_id) OR (mixiuser.id = source_id))"
"        ->  BitmapOr  (cost=8.30..8.30 rows=20 width=0) (actual time=0.005..0.005 rows=0 loops=52049079)"
"              ->  Bitmap Index Scan on ix_email_target_id  (cost=0.00..4.11 rows=6 width=0) (actual time=0.002..0.002 rows=0 loops=52049079)"
"                    Index Cond: (mixiuser.id = target_id)"
"              ->  Bitmap Index Scan on ix_email_source_id  (cost=0.00..4.18 rows=14 width=0) (actual time=0.002..0.002 rows=0 loops=52049079)"
"                    Index Cond: (mixiuser.id = source_id)"
"Total runtime: 732339.279 ms"
```
- [^] # Re: explain
  
  Posté par Flo le 05 juin 2012 à 10:01. Évalué à 2.
  
  C'est bien ce que je pensais : chacune des sous-requêtes est exécutée 52049079 fois (50 000 000)! C'est bien un accès par index, mais 50 millions de fois, c'est long quand même. (c'est les 2 "Bitmap Index Scan")
  Le 'Or' est également fait plus de 50 mullions de fois, et est un peu plus long.
  C'est cela qui est le plus coûteux.
  
  En gros, le moteur prend chaque ligne de la table user et sélectionne les lignes de email telle que mixiuser.id = target_id, celles telle que mixiuser.id = target_id, puis vérifie si la condition est vérifiée.
  
  Si tu regardes bien, les requêtes dans email + le 'or', cela prend 0.007 millisecondes.
  Multiplié par 52049079 , c'est 364343,553 (environ 6 minutes)
  Ajoutes 211619.619 pour le parcours séquentiel de la table (3,5 minutes environ)…
  
  Alors que si tu réécris la requête avec une jointure je suppose qu'il utilise un moyen bien plus efficace (pas un nested loop évidemment, un merge ou un sort join).
  Il est possible aussi que l'optimiseur "réécrive" la requête s'il n'y a qu'un seul exists, mais n'y arrive pas avec les 2 et le or, vu la grande différence de temps de réponse.
  
  Je me demande pourquoi cet ORM fait les requêtes comme cela, c'est généralement beaucoup moins bon, en tout cas sous Postgres ou Oracle.
# Bah

Posté par Pierre Carrier le 04 juin 2012 à 21:59. Évalué à 2.

La solution exists passes en revue tous les user et pour chacun fait une requête sur la table email. Une sous-requête exist est difficile à optimiser, même dans les cas particuliers.

Comme tu l'as présenté, les solutions efficaces évitent exist :

select u.id from user u join email e on e.source_id = u.id or e.target_id = u.id
- [^] # Re: Bah
  
  Posté par PyroTokyo le 05 juin 2012 à 02:42. Évalué à 1. Dernière modification le 05 juin 2012 à 02:45.
  
  Ce que je comprends moins, c'est que d'apres ce que j'avais lu, la clause exists est supposee s'executer jusqu'a ce qu'on trouve une entree valide, la ou le join parcourra toutes les solutions possibles. Malgre tout, j'ai un facteur 40 en performance.
  
  Dans mon ORM, toutes mes requetes de type "any" (pour les relation ManyToMany) sont converties en clauses exists, et sont generalement un peu complexes (cad avec du AND et du OR dedans). Dois-je en conclure que je ferais mieux de reecrire ces requetes a la main, en remplacant mes exists par un select distinct et un join ?
  - [^] # Re: Bah
    
    Posté par Juke (site web personnel) le 05 juin 2012 à 07:15. Évalué à 2.
    
    SELECT DISTINCT n'est pas terrible en terme de perf.
    - [^] # Re: Bah
      
      Posté par Flo le 05 juin 2012 à 10:02. Évalué à 1.
      
      En même temps, sur 22000 résultats positifs, ce n'est pas la mort non plus…
      - [^] # Re: Bah
        
        Posté par PyroTokyo le 05 juin 2012 à 10:40. Évalué à 0.
        
        Le distinct est necessaire ici, sinon j'obtiendrais des doublons (tous les coupes user/email)
        Je vais voir avec les unions comment tout ca se comporte, ca pourrait effectivement valoir le coup. Je n'aimais pas trop les utiliser avec l'ORM, parce que rien n'empeche de melanger un peu tout et n'importe quoi dans les unions, du coup je restais plus dans la couche "objet"
        
        [^] # Re: Bah
        
        Posté par Flo le 05 juin 2012 à 11:24. Évalué à 1.
        
        le UNION élimine les doublons, donc si tu choisis cette solution, pas la peine de faire de DISTINCT.
        Sinon, un DBA m'a une fois sauvé la mise avec un UNION, j'ai retenu la leçon. Par contre, comme toujours, il faut savoir rester simple si on veut que ce soit lisible.
- [^] # Re: Bah
  
  Posté par Flo le 05 juin 2012 à 10:13. Évalué à 2.
  
  À mon avis ce n'est pas terrible de mettre le or dans la clause de jointure… (je me demande comment c'est interprété…)
  
  J'écrirais plutôt :
  select us.id from user us join email esource on esource.source_id = us.id union select ut.id from user ut join email etarget on e.target_id = ut.id
  Je pense que là, on a 2 sous-requêtes bien optimisées, et assez peu de temps pour l'union (du moment que chacune des sous-requête ne ramène pas 100 000 000 de lignes…)
  - [^] # Re: Bah
    
    Posté par Xavier Maillard le 06 juin 2012 à 21:29. Évalué à 1.
    
    C'est tout le problème des UNION: le volume remonté. Pour autant, ici, l'UNION serait la solution à utiliser.

Suivre le flux des commentaires

Note : les commentaires appartiennent à celles et ceux qui les ont postés. Nous n’en sommes pas responsables.