Discussion :

[ymoreau]

Bonjour,
J'ai deux tables (en gras les PK) :
inverted_index: id_token, id_doc, positions (643 649 788 lignes)
tokens: id_token, token (12 310 981 lignes)

Je me demande de quelle manière est indexée une clé primaire composée de deux champs ? J'utilise ces deux champs dans une requête et mais les performances sont très mauvaises.

Voici la requête et l'explain analyze sur cette requête :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

select * from tokens where not exists (select * from inverted_index as i where i.id_token = tokens.id_token and i.id_doc != $1)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
                                                                    QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------------------------
 Hash Anti Join  (cost=24313919.19..27316902.92 rows=12324415 width=15) (actual time=36183259.188..154041487.640 rows=7 loops=1)
   Hash Cond: (tokens.id_token = i.id_token)
   ->  Seq Scan on tokens  (cost=0.00..202202.34 rows=12345034 width=15) (actual time=0.034..7072.352 rows=12310981 loops=1)
   ->  Hash  (cost=13754336.40..13754336.40 rows=643631663 width=4) (actual time=5775623.425..5775623.425 rows=643649781 loops=1)
         ->  Seq Scan on inverted_index i  (cost=0.00..13754336.40 rows=643631663 width=4) (actual time=0.027..3650670.164 rows=643649781 loops=1)
               Filter: (id_doc <> $1)
 Total runtime: 154042117.430 ms

Je ne suis pas bien sûr de ce que dit le plan, mais il me semble qu'il y a un scan complet de la table inverted_index au sein de la boucle. J'aurais naturellement pensé que la requête prendrait un sous ensemble de cette table (lorsque l'id_token est le même) pour comparer id_doc, et que l'index sur inverted_index.id_token serait utilisé pour créer ce sous ensemble.

[estofilo]

Il y a un scan complet de la table inverted_index, mais sauf incompréhension de ma part il ne se produit qu'une fois pour construire la table de hash temporaire.
L'exécution cherche tous les id_token tels que id_doc<>$1, ce qui veut dire certainement presque toute la table dans le cas d'un index documentaire inversé. Il doit stocker le résultat temporairement sur disque, ce qui contribue sans doute pas mal au temps faramineux pris par la requête.

Mais quels sont les index sur cette table?

[ymoreau]

En effet la condition sur id_doc fait ressortir la quasi totalité de la table, mais restreinte sur un certain id_token ça fait beaucoup moins (en moyenne théorique 643 millions divisés par 12 millions, en pratique encore moins). Il y a seulement les index des clés primaire, d'où mon interrogation sur ce qui est implicitement fait avec la clé primaire composée.

[estofilo]

L'index sur (id_token, id_doc) n'est pas utilisé par cette requête.
S'il y avait peu d'entrées dans la table token, il serait intéressant pour l'optimiseur de la mettre en tête de boucle, c.a.d pour chaque token.id_token, chercher les inverted_index.id_token correspondant avec la condition additionnelle sur id_doc.
Cette opération serait unitairement rapide grâce à l'index, mais le problème est qu'il faudrait la répéter 12 millions de fois, donc il est vraisemblable qu'au final ça serait plus lent que le plan actuel.

[ymoreau]

Merci pour les explications. Le problème c'est qu'en réalité il n'y aura pas autant de tours de boucle, ça irait de quelques dizaines à quelques milliers en gros, mais jamais 12 millions. Sur cet exemple (pas très représentatif mais quand même), on ne récupère que 7 tokens, donc utiliser l'index devrait faire gagner beaucoup de temps, et même éviter de hacher la totalité de inverted_index pour n'en utiliser qu'une faible partie au final. Est-ce qu'il y a un moyen d'indiquer ces directions dans le plan de la requête ?

[estofilo]

Je ne vois pas le raisonnement qui conduit à dire que quelques milliers de tours de boucle seraient suffisants. Imaginons qu'on soit en procédural, au départ on dispose du numéro de document. Quelle serait la boucle principale en question?