S'abonner au Flux RSS

Mot-clé - database

Fil des billets - Fil des commentaires

jeudi, février 4 2016

Indexer pour rechercher des chaines courtes dans PostgreSQL

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.

mercredi, janvier 13 2016

Index multi colonnes GIN, GIST

Ce billet intéressera tous les utilisateurs de colonnes de type hstore ou json avec PostgreSQL. Bien que celui-ci prenne pour exemple hstore il s'applique également aux colonnes json ou jsonb.

Commençons par créer une table et remplissons là avec 100 000 lignes de données aléatoires. Notre exemple représente des articles qui sont associés à un identifiant de langue (lang_id) et des tags catégorisés (tags), ici chaque article peut être associé à un pays qui sera la Turquie ou l'Islande.

~# CREATE TABLE article (id int4, lang_id int4, tags hstore);
CREATE TABLE
~# INSERT INTO article 
SELECT generate_series(1,10e4::int4), cast(random()*20 as int),
CASE WHEN random() > 0.5 
THEN 'country=>Turquie'::hstore 
WHEN random() > 0.8 THEN 'country=>Islande' ELSE NULL END AS x;
INSERT 0 100000

Pour une recherche efficace des articles dans une langue donnée nous ajountons un index de type B-tree sur la colonne lang_id et un index de type GIN sur la colonne tags.

~# CREATE INDEX ON article(lang_id);
CREATE INDEX
~# CREATE INDEX ON article USING GIN (tags);
CREATE INDEX

Nous avons maintenant nos données et nos index, nous pouvons commencer les recherches. Recherchons tous les articles écrit en français (on considère que l'id du français est le 17), qui sont associés à un pays (ils ont un tag country), et analysons le plan d'exécution.

~# EXPLAIN ANALYZE SELECT * FROM article WHERE lang_id=17 AND tags ? 'country';
                                                                QUERY PLAN                                                                
------------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on article  (cost=122.42..141.21 rows=5 width=35) (actual time=12.348..13.912 rows=3018 loops=1)
   Recheck Cond: ((tags ? 'country'::text) AND (lang_id = 17))
   Heap Blocks: exact=663
   ->  BitmapAnd  (cost=122.42..122.42 rows=5 width=0) (actual time=12.168..12.168 rows=0 loops=1)
         ->  Bitmap Index Scan on article_tags_idx  (cost=0.00..12.75 rows=100 width=0) (actual time=11.218..11.218 rows=60051 loops=1)
               Index Cond: (tags ? 'country'::text)
         ->  Bitmap Index Scan on article_lang_id_idx  (cost=0.00..109.42 rows=4950 width=0) (actual time=0.847..0.847 rows=5016 loops=1)
               Index Cond: (lang_id = 17)
 Planning time: 0.150 ms
 Execution time: 14.111 ms
(10 rows)

On a logiquement 2 parcours d'index, suivis d'une opération de combinaison pour obtenir le résultat final. Pour gagner un peu en performance on penserait naturellement à créer un index multi colonnes qui contienne lang_id et tags, mais si vous avez déjà essayé de le faire vous avez eu ce message d'erreur :

~# CREATE INDEX ON article USING GIN (lang_id, tags);
ERROR:  42704: data type integer has no default operator class for access method "gin"
HINT:  You must specify an operator class for the index or define a default operator class for the data type.
LOCATION:  GetIndexOpClass, indexcmds.c:1246

Le HINT donnne une piste intéressante, en effet les index de type GIN ne peuvent pas s'appliquer sur les colonnes de type int4 (et bien d'autres).

La solution réside dans l'utilisation d'une extension standard, qui combine les opérateurs GIN et B-tree, btree-gin, précisons tout de suite qu'il existe l'équivalent btree-gist.

Comme toute extension elle s'installe aussi simplement que :

~# CREATE EXTENSION btree_gin;
CREATE EXTENSION

Désormais nous allons pouvoir créer notre index multi-colonne et rejouer notre requête pour voir la différence.

~# CREATE INDEX ON article USING GIN (lang_id, tags);
CREATE INDEX
~# EXPLAIN ANALYZE SELECT * FROM article WHERE lang_id=17 AND tags ? 'country';
                                                             QUERY PLAN                                                              
-------------------------------------------------------------------------------------------------------------------------------------
 Bitmap Heap Scan on article  (cost=24.05..42.84 rows=5 width=35) (actual time=1.983..3.777 rows=3018 loops=1)
   Recheck Cond: ((lang_id = 17) AND (tags ? 'country'::text))
   Heap Blocks: exact=663
   ->  Bitmap Index Scan on article_lang_id_tags_idx  (cost=0.00..24.05 rows=5 width=0) (actual time=1.875..1.875 rows=3018 loops=1)
         Index Cond: ((lang_id = 17) AND (tags ? 'country'::text))
 Planning time: 0.211 ms
 Execution time: 3.968 ms
(7 rows)

A la lecture de ce deuxième explain le gain est explicite, même avec un petit jeu de données le coût estimé est divisé par 3, l'on gagne une lecture d'index et une opération de composition. Maintenant nous pouvons supprimer les 2 autres index pour ne conserver que celui-ci.