Les champs de recherche dans les applications web permettent de se voir propooser des résultats à chaque caractère saisies dans le formulaire, pour éviter de trop solliciter les systèmes de stockage de données, les modules standards permettent de définir une limite basse, la recherche n'étant effective qu'à partir du troisième caractères entrés. Cette limite de 3 caractères s'explique par la possibilité de simplement définir des index trigram dans les bases de données, pour PostgreSQL cela se fait avec l'extension standard pg_trgm, (pour une étude détaillé des trigrams je conseille la lecture de cet article).

Si cette technique a apporté beaucoup de confort dans l'utilisation des formulaires de recherche elle pose néanmoins le problème lorsque que l'on doit rechercher une chaîne de deux caractères, innoportun, contre-productif me direz-vous (je partage assez cet avis) mais imaginons le cas de madame ou monsieur Ba qui sont présent dans la base de données et dont on a oublié de saisir le prénom ou qui n'ont pas de prénom, ils ne pourront jamais remonter dans ces formulaires de recherche, c'est assez fâcheux pour eux.

Nous allons voir dans cet article comment résoudre ce problème, commençons par créer une table avec 50000 lignes de données text aléatoire :

CREATE TABLE blog AS SELECT s, md5(random()::text) as d 
   FROM generate_series(1,50000) s;
~# SELECT * from blog LIMIT 4;
 s |                 d                
---+----------------------------------
 1 | 8fa4044e22df3bb0672b4fe540dec997
 2 | 5be79f21e03e025f00dea9129dc96afa
 3 | 6b1ffca1425326bef7782865ad4a5c5e
 4 | 2bb3d7093dc0fffd5cebacd07581eef0
(4 rows)

Admettons que l'on soit un fan de musique des années 80 et que l'on recherche si il existe dans notre table du texte contenant la chaîne fff.

~# EXPLAIN ANALYZE SELECT * FROM blog WHERE d like '%fff%';

                                             QUERY PLAN                                              
-----------------------------------------------------------------------------------------------------
 Seq Scan on blog  (cost=0.00..1042.00 rows=5 width=37) (actual time=0.473..24.130 rows=328 loops=1)
   Filter: (d ~~ '%fff%'::text)
   Rows Removed by Filter: 49672
 Planning time: 0.197 ms
 Execution time: 24.251 ms
(5 rows)

Sans index on s'en doute cela se traduit pas une lecture séquentielle de la table, ajoutons un index. Pour indexer cette colonne avec un index GIN nous allons utiliser l'opérateur gin_trgm_ops disponible dans l'extension pg_trgm.

~# CREATE EXTENSION pg_trgm;
CREATE EXTENSION
~# CREATE INDEX blog_trgm_idx ON blog USING GIN(d gin_trgm_ops);
CREATE INDEX
~# EXPLAIN ANALYZE SELECT * FROM blog WHERE d like '%fff%';
                                                       QUERY PLAN                                                        
-------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on blog  (cost=16.04..34.46 rows=5 width=37) (actual time=0.321..1.336 rows=328 loops=1)
   Recheck Cond: (d ~~ '%fff%'::text)
   Heap Blocks: exact=222
   ->  Bitmap Index Scan on blog_trgm_idx  (cost=0.00..16.04 rows=5 width=0) (actual time=0.176..0.176 rows=328 loops=1)
         Index Cond: (d ~~ '%fff%'::text)
 Planning time: 0.218 ms
 Execution time: 1.451 ms

Cette fois l'index a pu être utilisé, on note au passage que le temps de requête est réduit d'un facteur 20, mais si l'on souhaite désormais rechercher une chaîne de seulement 2 caractères de nouveau une lecture séquentielle a lieu, notre index trigram devient inefficace pour cette nouvelle recherche.

~# EXPLAIN ANALYZE SELECT * FROM blog WHERE d like '%ff%';
                                               QUERY PLAN                                                
---------------------------------------------------------------------------------------------------------
 Seq Scan on blog  (cost=0.00..1042.00 rows=3030 width=37) (actual time=0.016..11.712 rows=5401 loops=1)
   Filter: (d ~~ '%ff%'::text)
   Rows Removed by Filter: 44599
 Planning time: 0.165 ms
 Execution time: 11.968 ms

C'est ici que vont intervenir les index bigram, qui comme leur nom l'index travaille sur des couples et non plus des triplets. En premier nous allons tester pgroonga, packagé pour Debian, Ubuntu, CentOS et d'autres systèmes exotiques vous trouverez toutes les explications pour le mettre en place sur la page d'install du projet.

Les versions packagées de la version 1.0.0 ne supportent actuellement que les versions 9.3 et 9.4, mais les sources viennent d'être taguées 1.0.1 avec le support de la 9.5.

CREATE EXTENSION pgroonga;

La création de l'index se fait ensuite en utilisant

~# CREATE INDEX blog_pgroonga_idx ON blog USING pgroonga(d);
CREATE INDEX
~# EXPLAIN ANALYZE SELECT * FROM blog WHERE d like '%ff%';
                                                           QUERY PLAN                                                            
---------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on blog  (cost=27.63..482.51 rows=3030 width=37) (actual time=3.721..5.874 rows=2378 loops=1)
   Recheck Cond: (d ~~ '%ff%'::text)
   Heap Blocks: exact=416
   ->  Bitmap Index Scan on blog_pgroonga_idx  (cost=0.00..26.88 rows=3030 width=0) (actual time=3.604..3.604 rows=2378 loops=1)
         Index Cond: (d ~~ '%ff%'::text)
 Planning time: 0.280 ms
 Execution time: 6.230 ms

On retrouve une utilisation de l'index, avec comme attendu un gain de performance.

Autre solution : pg_bigm qui est dédié plus précisément aux index bigram, l'installation se fait soit à partie de paquets RPM, soit directement depuis les sources avec une explication sur le site, claire et détaillée. pg_bigm supporte toutes les versions depuis la 9.1 jusqu'à 9.5.

~# CREATE INDEX blog_bigm_idx ON blog USING GIN(d gin_bigm_ops);
CREATE INDEX
~# EXPLAIN ANALYZE SELECT * FROM blog WHERE d like '%ff%';
                                                         QUERY PLAN                                                          
-----------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on blog  (cost=35.48..490.36 rows=3030 width=37) (actual time=2.121..5.347 rows=5401 loops=1)
   Recheck Cond: (d ~~ '%ff%'::text)
   Heap Blocks: exact=417
   ->  Bitmap Index Scan on blog_bigm_idx  (cost=0.00..34.73 rows=3030 width=0) (actual time=1.975..1.975 rows=5401 loops=1)
         Index Cond: (d ~~ '%ff%'::text)
 Planning time: 4.406 ms
 Execution time: 6.052 ms

Sur une table de 500k tuples la création de l'index prend 6,5 secondes pour bigm contre 4,8 pour pgroonga ; en terme de lecture je n'ai pas trouvé de pattern avec de réelle différence, bien pgroonga s'annonce plus rapide que pg_bigm, ce premier étant plus récent que le second on peut s'attendre à ce qu'il ait profité de l'expérience du second.

Coté liberté les deux projets sont publiés sous licence PostgreSQL license.

La réelle différence entre les deux projets est que Pgroonga est une sous partie du projet global Groonga qui est dédié à la recherche fulltext, il existe par exemple Mgroonga dont vous devinerez aisément la cible, pg_bigm est lui un projet autonome qui n'implémente que les bigram dans PostgreSQL.

Vous avez désormais deux méthodes pour indexer des 2-gram, prenez garde toutefois de ne pas en abuser.

La version 9.4.5 de PostgreSQL a été utilisée pour la rédaction de cet article.