Forum Programmation.SQL performances de JOIN / EXISTS sur postgres

Posté par .
Tags : aucun
0
4
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 . É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 . É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 . É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 . É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 . É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 . É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 . É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 . É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 . É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 . É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 . Évalué à 1. Dernière modification le 05/06/12 à 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 (page perso) . Évalué à 2.

        SELECT DISTINCT n'est pas terrible en terme de perf.

        • [^] # Re: Bah

          Posté par . Évalué à 1.

          En même temps, sur 22000 résultats positifs, ce n'est pas la mort non plus…

          • [^] # Re: Bah

            Posté par . É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 . É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 . É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 (page perso) . É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 à ceux qui les ont postés. Nous n'en sommes pas responsables.