Indexation GIST et GIN

      De retour au clan des Géants ! Les proverbes du clan, très nombreux, sont en fait des poèmes de quelques lignes. Margiono, le scribe, les a stockés dans sa base de données PostgreSQL. Un jour Oumpfor, le chef du clan, lui demande de retrouver le fameux proverbe comportant "NUGE LHTGR". Margiono se lance donc dans la recherche :

select version(); version ------------------------------------------------------------------------------------------ PostgreSQL 9.6.2 on x86_64-pc-linux-gnu, compiled by gcc (Debian 4.9.2-10) 4.9.2, 64-bit (1 ligne) create table proverbes (id_proverbe integer, num_ligne integer, titre_proverbe character varying, texte_proverbe character varying); CREATE TABLE with recursive serie1(s1id, r1, idp, nl, t) as (select 1, random(), 1, 1, md5(random()::TEXT) UNION ALL select s1id + 1, random(), case when r1 <= 0.1 then idp+1 else idp end, case when r1 <= 0.1 then 1 else nl+1 end, case when r1 <= 0.1 then t else md5(random()::TEXT) end from serie1 where s1id < 1000000), serie2(s2id, tp) as (SELECT a.*, ( SELECT string_agg(x, '') FROM (SELECT CASE when random() < 0.1 then ' ' else chr(ascii('A') + (random() * 25)::integer) end FROM generate_series(1, (random()*500)::integer + b * 0) ) AS y(x)) FROM generate_series(1,1000000) as a(b)) insert into proverbes(id_proverbe, num_ligne, titre_proverbe, texte_proverbe) select serie1.idp, serie1.nl, serie1.t, serie2.tp from serie1 join serie2 on (serie1.s1id = serie2.s2id); INSERT 0 1000000 -- exemple de ligne, de la belle poésie géante id_proverbe | 3 num_ligne | 7 titre_proverbe | 9e915fbc52bc7aaf2d321c761f084563 texte_proverbe | OOSNNEMYSTSSW OTVMPMMJCDPNRYPFHDVCPQ YFKLMBQVE CYS IYRRU HJMOKOBN G PXJQRDEWBBQUHTPUMEQCNHQIQCZZGEOZ EJWM FDKWBK QIILBEO ZWTWUOYVBCTJPYU TRBTSGRUZMWSMFGYMWOFIGJ IWAJHNBJ ZSNUI R ADFBEZVYYTMPDIPFOHFGEX VXQGFBV GJNOZBBEU PMPJURLXLTPEOXXLP select id_proverbe from proverbes where texte_proverbe like '%NUGE%LHTGR%' ; id_proverbe ------------- (0 ligne) Temps : 1422,684 ms with proverbes_agg(id_proverbe, texte_proverbe_agg) as (select id_proverbe, string_agg(texte_proverbe, ' ' order by num_ligne) texte_proverbe_agg from proverbes group by id_proverbe) select id_proverbe from proverbes_agg where texte_proverbe_agg like '%NUGE%LHTGR%' ; id_proverbe ------------- 50000 (1 ligne) Temps : 12922,783 ms


      Après une recherche infructueuse et quelques sueurs froides, Margiono a eu une intuition en considérant que NUGE pouvait être à la fin d’une ligne et LHTGR au début de la suivante. Il a concaténé les lignes de chaque proverbe en respectant leur ordre et effectué une recherche avec LIKE.
      Le hic c’est que la recherche a pris 13s. C’est long et indexer la colonne TEXTE_PROVERBE avec un index B-Tree, BRIN ou BLOOM n’y changera rien. L’angoisse monte car, pour l’instant, un seul des 42 tomes de proverbes a été chargé. Un ami suggère à Margiono de faire appel à Lucene mais il décide d’abord de donner sa chance aux capacités de recherche FULL TEXT de PostgreSQL. Le scribe utilise pour cela une structure dédiée, le TSVECTOR et tente les 2 méthodes d’indexation proposées, GIST et GIN :

create table proverbes_doc as select id_proverbe, to_tsvector(string_agg(texte_proverbe, ' ' order by num_ligne)) vecteur_proverbe from proverbes group by id_proverbe; SELECT 100033 create index proverbes_doc_gis_01 on proverbes_doc using gist(vecteur_proverbe); CREATE INDEX Temps : 10831,666 ms \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+----------------------+-------+--------------+---------------+--------+------------- public | proverbes_doc_gis_01 | index | postgres | proverbes_doc | 26 MB | (1 ligne) select id_proverbe from proverbes_doc where phraseto_tsquery('NUGE LHTGR') @@ vecteur_proverbe; id_proverbe ------------- 50000 (1 ligne) Temps : 275,945 ms Temps : 173,697 ms Temps : 162,844 ms create index proverbes_doc_gin_01 on proverbes_doc using gin(vecteur_proverbe); CREATE INDEX Temps : 424881,814 ms \di+ Liste des relations Schéma | Nom | Type | Propriétaire | Table | Taille | Description --------+----------------------+-------+--------------+---------------+--------+------------- public | proverbes_doc_gin_01 | index | postgres | proverbes_doc | 871 MB | (1 ligne) select id_proverbe from proverbes_doc where phraseto_tsquery('NUGE LHTGR') @@ vecteur_proverbe; id_proverbe ------------- 50000 (1 ligne) Temps : 1,700 ms Temps : 0,720 ms Temps : 1,213 ms

Conclusion

      Bien sûr la recherche FULL TEXT de PostgreSQL va bien plus loin que cet exemple et les capacités sont même très étendues. La langue des géants n’est pas connue mais, si votre texte est en français ou en anglais, vous pourrez le prendre en compte. Si les recherches concernent plusieurs colonnes, vous pourrez leur donner des poids différents afin d’influencer l’ordre d’affichage des résultats.
      Ici c’est surtout l’aspect indexation qui nous intéressait. Les index GIST sont légers, c’est à dire rapides à créer et peu volumineux. Ici l’index GIST a été créé en 11s et pèse 26Mo. Il permet de faire passer la recherche de 13s à moins de 0s3.
      Les index GIN sont plus lourds donc plus lents à créer et plus volumineux. Ici l’index GIN a été créé en 7min25s, augmenter maintenance_work_mem permettrait cependant de diminuer drastiquement le temps de création. Il pèse 871Mo mais il permet de faire passer le temps d’exécution de la recherche à moins de 2ms.
      A vous de choisir l’indexation la plus adaptée en fonction de vos critères. Si la recherche FULL TEXT est ponctuellement utilisée sur un environnement OLTP alors l’indexation GIST peut être le bon choix. Si la recherche FULL TEXT constitue un aspect très important et que les temps d’exécutions des recherches doivent être très bas alors l’indexation GIN est sans doute plus adaptée.
      Si vous avez plusieurs dizaines de Go par heure à indexer dans le seul but de faire de la recherche FULL TEXT alors un SGBDR complet comme PostgreSQL n’est probablement pas le produit à privilégier. Mais si votre besoin est hybride et implique, par exemple, d’indexer quelques dizaines de Go par mois dans le but de faire de la recherche FULL TEXT en complément d’autres requêtes SQL, alors il n’y a aucune raison de se servir systématiquement d’un outil externe.

Mise à jour : 21/04/2017