Aller au contenu

pg_trgm : Indexation avancée du texte

Informations

PostgreSQL propose deux méthodes avancées d’indexation du texte. La méthode classique (et la plus performante) est l’utilisation du Full Text Search (recherche plein texte). Cette dernière est très performante, repose sur la décomposition de texte en lexèmes, permet d’identifier automatiquement les mots, nombres, URL, etc., décompose les mots en leur radical pour identifier tous les mots de la même famille, peut gérer des synonymes, des « stop words » (mots à ne pas indexer), des dictionnaires dans plusieurs langues… et gère de très gros volumes de données (qui se mesurent en To).

Par contre, cette solution n’est pas capable à l’heure actuelle de gérer correctement les fautes d’orthographe et autres erreurs de ce type. Un mot mal orthographié ne sera pas reconnu.

Si on cherche à indexer des chaînes plus courtes, il est donc possible aussi d’utiliser l’extension pg_trgm. Cette solution utilise des trigrammes (chaînes de caractères de 3 lettres). Par exemple :

base=# SELECT show_trgm('hello');
            show_trgm            
---------------------------------
 {"  h"," he",ell,hel,llo,"lo "}

Ces trigrammes permettent de répondre à des questions de recherche floue sur les chaînes (méthode de Levenshtein), ainsi que d’effectuer des LIKE sur des motifs plus complexes. Nous avons créé une table mots contenant tout un dictionnaire :

base=# SELECT count (*) FROM mots;
 count  
--------
 753248
(1 ligne)

On peut effectuer une recherche de motif sur le champ mot. En temps normal, seuls les LIKE 'ma_chaine%' peuvent utiliser un index :

base=# CREATE INDEX idx2 ON mots USING gist (mot gist_trgm_ops);
CREATE INDEX
base=# EXPLAIN ANALYZE SELECT * FROM mots WHERE mot LIKE '%jour%';
                                                    QUERY PLAN                                                    
------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on mots  (cost=7.41..277.32 rows=75 width=10) (actual time=50.362..50.677 rows=352 loops=1)
   Recheck Cond: (mot ~~ '%jour%'::text)
   ->  Bitmap Index Scan on idx2  (cost=0.00..7.39 rows=75 width=0) (actual time=50.322..50.322 rows=352 loops=1)
         Index Cond: (mot ~~ '%jour%'::text)
 Total runtime: 51.226 ms

On peut aussi demander les réponses par similarité. Un score de 0 est le maximum, 1 est le minimum.

base=# SELECT *, mot <-> 'bonjour' FROM mots ORDER BY mot <-> 'bonjour' LIMIT 5;
       mot       | ?column? 
-----------------+----------
 bonjour         |        0
 Bour            | 0.555556
 bonheur-du-jour | 0.647059
 bonheur         | 0.666667
 bourbon         | 0.666667
(5 lignes)

Cette requête passe par l’index :

base=# EXPLAIN ANALYZE SELECT *, mot <-> 'bonjour' FROM mots ORDER BY mot <-> 'bonjour' LIMIT 5;
                                                        QUERY PLAN                                                        
--------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=0.00..0.37 rows=5 width=10) (actual time=1.605..24.537 rows=5 loops=1)
   ->  Index Scan using idx2 on mots  (cost=0.00..7011.69 rows=94156 width=10) (actual time=1.603..24.533 rows=5 loops=1)
         Order By: (mot <-> 'bonjour'::text)
 Total runtime: 25.962 ms

Le défaut de la méthode des trigrammes est qu’elle ne fonctionne que :

  • si les chaînes restent raisonnablement courtes, sinon le nombre de trigrammes devient trop important ;
  • si les volumes à indexer restent faibles (quelques giga-octets) ;
  • si les données sont peu mises à jour (la maintenance des index sur trigrammes est lente).

Les index sont plus grands que la table par cette méthode :

base=# SELECT pg_size_pretty(pg_relation_size('mots'));
 pg_size_pretty 
----------------
 3944 kB
(1 ligne)

base=# SELECT pg_size_pretty(pg_relation_size('idx2'));
 pg_size_pretty 
----------------
 6312 kB
(1 ligne)