L'extension pg_trgm

2025-03-07

1651 mots, 8 minutes de lecture

Hervé Lefebvre

L’extension pg_trgm

Présentation

L’extension pg_trgm (trigrammes) est fournie dans la distribution standard de PostgreSQL. Elle est présente dans /contrib et s’installe simplement dans une base de données :

loxodata_text=# CREATE EXTENSION IF NOT EXISTS pg_trgm;
CREATE EXTENSION

Cette extension permet de décomposer une chaîne de caractères en succession de sous-chaînes de 3 caractères (trigrammes), afin de permettre des recherches sur une sous-chaîne, ou bien des recherches de similarité entre chaînes de caractères.

Fonctionnement

Jeu d’essai

Dans le cadre de cette présentation, je me suis constitué une table d’un million de lignes, laquelle contient un champ family contenant un nom de famille parmi les 1000 plus fréquent en France, et dont la fréquence dans la table est semblable à celle de la population française :

loxodata_text=# \dS my_datas
                              Table "public.my_datas"
   Column    |  Type  | Collation | Nullable |               Default
-------------+--------+-----------+----------+--------------------------------------
 id          | bigint |           | not null | nextval('my_datas_id_seq'::regclass)
 random_text | text   |           |          |
 family      | text   |           |          |
Indexes:
    "idx_test_id" btree (id)

loxodata_text=# SELECT count(1) FROM my_datas;
  count
---------
 1000204
(1 row)

loxodata_text=# SELECT * FROM my_datas LIMIT 5;
   id   |             random_text              | family
--------+--------------------------------------+---------
 211685 | 94376bb6-3655-4a65-b61a-8dbec927c5e5 | GRANGER
 211686 | 7f9f8a34-13f2-4459-bd2c-e4b90a7eca9b | LE ROUX
 211687 | 526549b3-13fe-4aae-87c1-4a5480cf6898 | FUCHS
 211688 | 1acbdde8-b4cd-4bf8-957c-84adf1c6cf1c | BRUNET
 211689 | 77cd8645-bfe8-471c-a118-3dbe507d8e8f | LAMBERT
(5 rows)

Décomposition

On peut visualiser la décomposition en trigrammes avec la fonction show_trgm() :

loxodata_text=# SELECT show_trgm('GRANGER');
                show_trgm
-----------------------------------------
 {"  g"," gr",ang,"er ",ger,gra,nge,ran}
(1 row)

Similarité

La fonction similarity() permet de tester la similarité entre deux chaînes de caractères. Le résultat est un score entre 0 et 1. Zéro indique qu’il n’y a aucun trigramme en commun entre les deux chaînes, tandis que 1 indique que les deux chaînes sont identiques. On peut ainsi tester la similarité entre deux noms de famille :

loxodata_text=# select similarity('GRANGER','BRUNET');
 similarity
------------
          0
(1 row)

loxodata_text=# select similarity('GRANGER','GRANGE');
 similarity
------------
  0.6666667
(1 row)

loxodata_text=# select similarity('GRANGER','GRANIER');
 similarity
------------
 0.45454547
(1 row)

loxodata_text=# select similarity('GRANGER','LEGRAND');
 similarity
------------
 0.14285715
(1 row)

L’opérateur booléen de similarité entre deux chaînes est % :

loxodata_text=# select 'GRANGER' % 'GRANIER';
 ?column?
----------
 t
(1 row)

loxodata_text=# select 'GRANGER' % 'LEGRAND';
 ?column?
----------
 f
(1 row)

L’opérateur booléen retourne True si le score de similarité excède une limite fixée par défaut à 0.3. La limite courante peut être consultée avec la fonction show_limit() :

loxodata_text=# select show_limit();
 show_limit
------------
        0.3
(1 row)

Et cette limite peut être modifiée au niveau de la session avec la fonction set_limit(). Ainsi, si on passe le seuil à 0.1, ‘GRANGER’ et ‘LEGRAND’ sont désormais considérés comme similaires :

loxodata_text=# select set_limit(0.1);
 set_limit
-----------
       0.1
(1 row)

loxodata_text=# select 'GRANGER' % 'LEGRAND';
 ?column?
----------
 t
(1 row)

Cette limite peut être configurée au niveau du cluster avec le paramètre pg_trgm.similarity_threshold.

Indexation et performances

L’indexation BTREE classique

Les champs TEXT peuvent être indexés classiquement avec un index BTREE :

loxodata_text=# CREATE INDEX idx_test ON my_datas(family text_pattern_ops);
CREATE INDEX

Cela permet de trouver rapidement des chaînes de caractères ou des débuts de chaînes de caractères :

loxodata_text=# EXPLAIN ANALYZE SELECT id FROM my_datas WHERE family = 'GRANGER';
                                                     QUERY PLAN
---------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=10.09..2289.04 rows=731 width=8) (actual time=0.101..0.584 rows=658 loops=1)
   Recheck Cond: (family = 'GRANGER'::text)
   Heap Blocks: exact=637
   ->  Bitmap Index Scan on idx_test  (cost=0.00..9.91 rows=731 width=0) (actual time=0.047..0.047 rows=658 loops=1)
         Index Cond: (family = 'GRANGER'::text)
 Planning Time: 0.120 ms
 Execution Time: 0.612 ms
(7 rows)

loxodata_text=# EXPLAIN ANALYZE SELECT id FROM my_datas WHERE family like  'GRAN%';
                                                      QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------
 Index Scan using idx_test on my_datas  (cost=0.42..8.45 rows=66 width=8) (actual time=0.024..2.121 rows=3692 loops=1)
   Index Cond: ((family ~>=~ 'GRAN'::text) AND (family ~<~ 'GRAO'::text))
   Filter: (family ~~ 'GRAN%'::text)
 Planning Time: 0.137 ms
 Execution Time: 2.234 ms
(5 rows)

Cependant un tel index se révèle inutile lorsqu’on ne connaît pas le début de la chaîne recherchée. Dans ce cas on bascule sur un Seq Scan malgré la présence de l’index :

loxodata_text=# EXPLAIN ANALYZE SELECT id FROM my_datas WHERE family like  '%ANGER';
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Gather  (cost=1000.00..17185.70 rows=6643 width=8) (actual time=0.196..36.796 rows=2585 loops=1)
   Workers Planned: 2
   Workers Launched: 2
   ->  Parallel Seq Scan on my_datas  (cost=0.00..15521.40 rows=2768 width=8) (actual time=0.027..33.117 rows=862 loops=3)
         Filter: (family ~~ '%ANGER'::text)
         Rows Removed by Filter: 332540
 Planning Time: 0.071 ms
 Execution Time: 36.894 ms
(8 rows)

Indexation des trigrammes

Il est possible d’indexer les vecteurs de trigrammes avec un index GIN :

loxodata_text=# CREATE INDEX idx_test_trgm ON my_datas USING GIN(family gin_trgm_ops);
CREATE INDEX

La recherche sur la fin de chaîne de caractères se fait maintenant en utilisant l’index nouvellement créé :

loxodata_text=# EXPLAIN ANALYZE SELECT id FROM my_datas WHERE family like  '%ANGER';
                                                         QUERY PLAN
-----------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=94.35..9754.04 rows=6643 width=8) (actual time=1.422..3.197 rows=2585 loops=1)
   Recheck Cond: (family ~~ '%ANGER'::text)
   Heap Blocks: exact=2292
   ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..92.69 rows=6643 width=0) (actual time=1.193..1.194 rows=2585 loops=1)
         Index Cond: (family ~~ '%ANGER'::text)
 Planning Time: 0.085 ms
 Execution Time: 3.282 ms
(7 rows)

Nous pouvons maintenant effectuer une recherche de similarité :

loxodata_text=# EXPLAIN ANALYZE SELECT DISTINCT family FROM my_datas WHERE family %  'GRANGER';
                                                               QUERY PLAN
----------------------------------------------------------------------------------------------------------------------------------------
 Unique  (cost=370.28..370.61 rows=64 width=7) (actual time=19.476..19.867 rows=6 loops=1)
   ->  Sort  (cost=370.28..370.45 rows=66 width=7) (actual time=19.474..19.632 rows=4284 loops=1)
         Sort Key: family
         Sort Method: quicksort  Memory: 264kB
         ->  Bitmap Heap Scan on my_datas  (cost=119.31..368.29 rows=66 width=7) (actual time=7.737..18.771 rows=4284 loops=1)
               Recheck Cond: (family % 'GRANGER'::text)
               Rows Removed by Index Recheck: 3468
               Heap Blocks: exact=5458
               ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..119.29 rows=66 width=0) (actual time=7.173..7.173 rows=7752 loops=1)
                     Index Cond: (family % 'GRANGER'::text)
 Planning Time: 0.297 ms
 Execution Time: 19.887 ms
(12 rows)

loxodata_text=# SELECT DISTINCT family FROM my_datas WHERE family %  'GRANGER';
  family
----------
 GRAND
 GRANGE
 GRANGER
 GRANIER
 GRAS
 LAGRANGE
(6 rows)

Cette recherche par similarité peut être utile, votre serviteur en sait quelque chose avec son patronyme qui comporte un ‘B’ muet et qui entraîne souvent moultes confusions lorsque je dois épeler mon nom, et qui est donc écrit souvent approximativement :

loxodata_text=# SELECT DISTINCT family FROM my_datas WHERE family % 'LEFEBVRE';
  family
----------
 LEFEBVRE
 LEFEVRE
 LEFEUVRE
(3 rows)

Performances

On peut voir que sur une recherche d’égalité, ou bien sur une recherche de début de chaîne, c’est l’index B-Tree qui est préféré par le planner :

loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family =  'LEFEBVRE';
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using idx_test on my_datas  (cost=0.42..1370.94 rows=3801 width=7) (actual time=0.018..0.488 rows=4312 loops=1)
   Index Cond: (family = 'LEFEBVRE'::text)
   Heap Fetches: 399
 Planning Time: 0.340 ms
 Execution Time: 0.615 ms
(5 rows)

loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family like  'LEFEBVRE%';
                                                           QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------------
 Index Only Scan using idx_test on my_datas  (cost=0.42..1389.95 rows=3867 width=7) (actual time=0.010..0.729 rows=4312 loops=1)
   Index Cond: ((family ~>=~ 'LEFEBVRE'::text) AND (family ~<~ 'LEFEBVRF'::text))
   Filter: (family ~~ 'LEFEBVRE%'::text)
   Heap Fetches: 399
 Planning Time: 0.165 ms
 Execution Time: 0.877 ms
(6 rows)

loxodata_text=# drop index idx_test;
DROP INDEX

Il est cependant important de noter que si l’index B-Tree est préféré sur la recherche en début de chaîne ( LIKE 'xxxx%' ) c’est parce que la classe d’opérateurs text_pattern_ops a été utilisée lors de la création de l’index. Si nous créons un index B-Tree sans cette classe d’opérateurs, il sera préféré pour une recherche d’égalité, mais pas pour une recherche de début de chaîne du fait des problèmes complexes liés aux LOCALES des différentes langues :

loxodata_text=# CREATE INDEX idx_test ON my_datas(family);
CREATE INDEX
loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family like  'LEFEBVRE%';
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=139.26..7724.28 rows=3867 width=7) (actual time=2.370..5.048 rows=4312 loops=1)
   Recheck Cond: (family ~~ 'LEFEBVRE%'::text)
   Heap Blocks: exact=3544
   ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..138.29 rows=3867 width=0) (actual time=2.000..2.000 rows=4312 loops=1)
         Index Cond: (family ~~ 'LEFEBVRE%'::text)
 Planning Time: 0.162 ms
 Execution Time: 5.179 ms
(7 rows)

Si nous supprimons définitivement l’index B-Tree, on voit que l’index sur les trigrammes est utilisé efficacement pour une recherche d’égalité (seulement après PG v13) mais pas aussi efficacement qu’avec l’index B-Tree (coût estimé 7666 vs 1370). Cependant ce coût est remarquablement constant que la recherche se fasse sur une égalité, un début de chaîne (LIKE 'xxx%') ou une recherche sur une sous-chaîne (LIKE '%xxx%').

loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family =  'LEFEBVRE';
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=151.72..7666.35 rows=3801 width=7) (actual time=3.331..6.085 rows=4312 loops=1)
   Recheck Cond: (family = 'LEFEBVRE'::text)
   Heap Blocks: exact=3544
   ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..150.77 rows=3801 width=0) (actual time=2.961..2.962 rows=4312 loops=1)
         Index Cond: (family = 'LEFEBVRE'::text)
 Planning Time: 0.095 ms
 Execution Time: 6.298 ms
(7 rows)

loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family like  'LEFEBVRE%';
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=139.26..7724.28 rows=3867 width=7) (actual time=2.632..5.366 rows=4312 loops=1)
   Recheck Cond: (family ~~ 'LEFEBVRE%'::text)
   Heap Blocks: exact=3544
   ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..138.29 rows=3867 width=0) (actual time=2.263..2.263 rows=4312 loops=1)
         Index Cond: (family ~~ 'LEFEBVRE%'::text)
 Planning Time: 0.075 ms
 Execution Time: 5.584 ms
(7 rows)

loxodata_text=# EXPLAIN ANALYZE SELECT family FROM my_datas WHERE family like  '%LEFEBVRE%';
                                                          QUERY PLAN
------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on my_datas  (cost=109.52..7694.54 rows=3867 width=7) (actual time=1.628..4.402 rows=4312 loops=1)
   Recheck Cond: (family ~~ '%LEFEBVRE%'::text)
   Heap Blocks: exact=3544
   ->  Bitmap Index Scan on idx_test_trgm  (cost=0.00..108.55 rows=3867 width=0) (actual time=1.260..1.260 rows=4312 loops=1)
         Index Cond: (family ~~ '%LEFEBVRE%'::text)
 Planning Time: 0.078 ms
 Execution Time: 4.603 ms
(7 rows)

Conclusion

Si un champ texte fait l’objet d’une recherche d’égalité dans une clause WHERE, un index B-Tree est parfaitement adéquat.
Si un champ texte fait l’objet d’une recherche sur un début de chaîne de type WHERE champ LIKE 'ABC%' , un index B-Tree est là encore adéquat, à condition de lui spécifier la classe d’opérateurs text_pattern_ops.
Si un champ texte fait l’objet d’une recherche sur une sous-chaîne de type WHERE champ LIKE '%ABC%' , seul un index GIN ou GiST sur les trigrammes sera utile.
Lorsqu’un index sur les trigrammes a été créé, dans la plupart des cas l’index B-Tree peut être supprimé. Cependant, du fait de la meilleure efficacité du B-Tree, il peut être pertinent dans de rares occasions de conserver également l’index B-Tree.

LOXODATA