Index d'une clé primaire composée et sous requête corrélée [Résolu]

[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 :

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 :

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?

[ymoreau]

En procédural (ce que j'ai d'abord fait avant qu'on me dise d'utiliser une sous requête corrêlée) j'avais en tête quelque chose comme ça :

Code :

1
2
3
4
5
6
7
fonction (doc)
  Pour tous les éléments t dans inverted_index où id_doc=doc
    Si (éléments dans inverted_index où id_token=t et id_doc<>doc) vide
      supprimer tokens.t
    fin si
  fin pour
fin

Ce que j'avais traduit en pl/pgsql par :

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
CREATE OR REPLACE FUNCTION delete_document(doc_id integer) RETURNS void AS
$$
DECLARE
    doc_id_token integer;
    token_index_reference integer;
BEGIN
    -- Clean the no-longer used tokens
    FOR doc_id_token IN SELECT id_token FROM inverted_index WHERE id_doc = doc_id LOOP
        SELECT INTO token_index_reference id_token FROM inverted_index WHERE id_doc != doc_id AND id_token = doc_id_token;
        IF token_index_reference IS NULL THEN
            DELETE FROM tokens WHERE id_token = doc_id_token; -- Delete the token
        END IF;
    END LOOP;
END;
$$ LANGUAGE plpgsql;

[estofilo]

Le découpage de la fonction ne pourrait pas servir de plan d'exécution à la requête car ils ne sortent pas exactement la même chose.
En effet dans le cas où il y a des id_token dans la table tokens qui ne sont pas présents dans inverted_index, la requête va les sortir, alors que la fonction, elle, ne va pas les voir puisqu'elle se base sur le contenu de inverted_index au premier niveau de la boucle.

[ymoreau]

Je n'avais pas pensé à ça. Au niveau résultat ça ne change rien car la table tokens n'est pas censée contenir de mots qui n'apparaissent pas dans inverted_index (c'est justement le but de cette procédure). Mais c'est vrai que la requête va analyser plus de lignes sur la procédure du coup.

Cela dit la procédure était assez longue aussi et n'a même pas effacé comme prévu les tokens qu'elle aurait dû. Je pensais que l'algo en utilisant les index serait assez rapide car il ne traiterait qu'une petite partie des tables.

[estofilo]

Sur l'échec de la fonction, ça doit être parce que

Code :

IF token_index_reference IS NULL

n'est pas le bon test, il faut utiliser

Code :

IF NOT FOUND

pour savoir qu'un SELECT INTO n'a retourné aucun résultat.

Sur la question des performances, est-ce que c'est envisageable d'ajouter un index sur id_doc? C'est à mon avis ce qui manque pour que ça puisse s'exécuter en un temps acceptable.

Si ça pose un problème d'espace, il est possible de supprimer l'index double en faveur de deux index simples, un sur id_token, l'autre sur id_doc.
L'inconvénient est que ça supprime la contrainte d'unicité, mais cette contrainte peut sans doute être testée autrement, par un trigger par exemple. Ce n'est pas très orthodoxe, mais c'est un compromis généralement valable sur des tables de cette taille.

[ymoreau]

Merci pour ces conseils ! Je vais essayer de voir ce que je peux faire.