Full Text Search

Introduction

Voici un jeu de données assez simple, nous allons générer une table comprenant un grand nombre de lignes.

select * from couleurs ;
    c1    
----------
 bleu
 bleue
 vert
 vert
 rouge
 violet
 Violette
 noir
 blanc
 gris
(10 rows)

create table bigcolor (c1 text);
insert into bigcolor (select c1 from generate_series(1,100000) cross join couleurs ) ;
create index on bigcolor (c1);

Chaîne exacte

• c1 = 'bleu'

Type de parcours :

• Index :
• Btree classique

explain (costs off) select * from bigcolor where c1 = 'bleu';
                 QUERY PLAN                 
--------------------------------------------
 Bitmap Heap Scan on bigcolor
   Recheck Cond: (c1 = 'bleu'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx
         Index Cond: (c1 = 'bleu'::text)

Préfixe

• c1 like 'bleu%'

Type de parcours :

• Index :
• Pas de parcours d’index possible si la locale n’est pas ‘C’:

explain (costs off) select * from bigcolor where c1 like 'bleu%';
           QUERY PLAN            
---------------------------------
 Seq Scan on bigcolor
   Filter: (c1 ~~ 'bleu%'::text)

• Btree classique si la locale est à ‘C’

create table bigcolorc (c1 text collate "C") ;
insert into bigcolorc select * from bigcolor;
create index ON bigcolorc (c1 );

explain (costs off) select * from bigcolorc where c1 like 'bleu%';
                             QUERY PLAN                             
--------------------------------------------------------------------
 Bitmap Heap Scan on bigcolorc
   Filter: (c1 ~~ 'bleu%'::text)
   ->  Bitmap Index Scan on bigcolorc_c1_idx
         Index Cond: ((c1 >= 'bleu'::text) AND (c1 < 'blev'::text))

• Alternative : Utiliser un Btree avec classe d’opérateur text_pattern_ops :
• Effectue la comparaison octet par octet au lieu d’utiliser la collation. Utile pour avoir un index dans le cas où la locale n’est pas ‘C’.

create index ON bigcolor (c1 text_pattern_ops);
explain (costs off) select * from bigcolor where c1 like 'bleu%';
                               QUERY PLAN                               
------------------------------------------------------------------------
 Bitmap Heap Scan on bigcolor
   Filter: (c1 ~~ 'bleu%'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx1
         Index Cond: ((c1 ~>=~ 'bleu'::text) AND (c1 ~<~ 'blev'::text))

Préfixe en ignorant la casse

• c1 ilike 'violet%'

Type de parcours :

• Index :
• Privilégier un index fonctionnel lower(c1), sinon le moteur devra faire un seqscan.

explain (costs off) select * from bigcolor where c1 ilike 'Bleu%';
            QUERY PLAN            
----------------------------------
 Seq Scan on bigcolor
   Filter: (c1 ~~* 'bleu%'::text)

Avec un index fonctionnel :

create index ON bigcolor(lower(c1));
explain (costs off) select * from bigcolor where lower(c1) like 'bleu%';
                               QUERY PLAN                               
------------------------------------------------------------------------
 Bitmap Heap Scan on bigcolor
   Filter: (c1 ~~ 'bleu%'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx1
         Index Cond: ((c1 ~>=~ 'bleu'::text) AND (c1 ~<~ 'blev'::text))

• On peut également utiliser pg_trgm + index GIN :

create extension pg_trgm ;
create index ON bigcolor using gin (c1 gin_trgm_ops);
explain (costs off) select * from bigcolor where c1 like lower('Bleu%');
                 QUERY PLAN                  
---------------------------------------------
 Bitmap Heap Scan on bigcolor
   Recheck Cond: (c1 ~~ 'bleu%'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx2
         Index Cond: (c1 ~~ 'bleu%'::text)

Partie d’une chaîne

• ligne like '%iolet%'

Type de parcours :

• Index :
• On ne peut pas utiliser un index classique.
• Solution : pg_trgm + index GIN

explain (costs off) select * from bigcolor where c1 like '%iolet%';
            QUERY PLAN             
-----------------------------------
 Seq Scan on bigcolor
   Filter: (c1 ~~ '%iolet%'::text)

create extension pg_trgm ;
create index ON bigcolor using gin (c1 gin_trgm_ops);
explain (costs off) select * from bigcolor where c1 like '%iolet%';
                 QUERY PLAN                  
---------------------------------------------
 Bitmap Heap Scan on bigcolor
   Recheck Cond: (c1 ~~ '%iolet%'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx2
         Index Cond: (c1 ~~ '%iolet%'::text)

Expression rationnelle

• c1 ~* '.*iolette.*'

Type de parcours :

• Index :
• Il faut créer un index fonctionnel : très limité.
• Ou utiliser pg_trgm + index GIN.

create extension pg_trgm ;
create index ON bigcolor using gin (c1 gin_trgm_ops);
explain (costs off) select * from bigcolor where c1 ~* '.*iolet.*';
                  QUERY PLAN                   
-----------------------------------------------
 Bitmap Heap Scan on bigcolor
   Recheck Cond: (c1 ~* '.*iolet.*'::text)
   ->  Bitmap Index Scan on bigcolor_c1_idx2
         Index Cond: (c1 ~* '.*iolet.*'::text)

Toutes ces méthodes sont assez basiques.

Comment un humain fait une recherche ?

Notre cerveau sait :

• Identifier les synonymes
• Ignorer les mots non importants comme “le”, “la”, etc.
• Ne pas forcément prêter attention à la casse ou la ponctuation
• But : retenir les mots porteurs de sens
• But : Traiter de manière automatisée un langage naturel.

Pour plus de détails, voir l’article de Wikipédia sur le Traitement automatique du langage naturel.

Recherche d’Information (définition)

Voici une bonne introduction au sujet issue de Wikipédia :

La recherche d’information (RI) est le domaine qui étudie la manière de retrouver des informations dans un corpus. Celui-ci est composé de documents d’une ou plusieurs bases de données, qui sont décrits par un contenu ou les métadonnées associées. Les bases de données peuvent être relationnelles ou non structurées […]

Pour plus d’informations, voir l’article complet sur la Recherche d’information.

Recherche d’Information (composants)

Pour effectuer une RI dans un document, il faut procéder à plusieurs étapes :

1. Pré-traitement :

   • Extraction des descripteurs :
   • Suppression des mots outils ou mots vides.
   • Lemmatisation (stemming) : obtenir la racine des mots.
   • Suppression des synonymes.
   • Utiliser un thésaurus.
   • But : obtenir une représentation vectorielle d’un document.

2. Indexation des vecteurs.

3. Interrogation des index à l’aide d’un langage “informatique”.

Comment fonctionne le Full Text Search

Parser

Un document est analysé pour identifier des tokens, qui correspondent à des catégories. Par exemple :

\dFp+

Token	Description
asciihword	Hyphenated word, all ASCII
asciiword	Word, all ASCII
blank	Space symbols
email	Email address
entity	XML entity
file	File or path name
float	Decimal notation
host	Host
hword	Hyphenated word, all letters
int	Signed integer
numhword	Hyphenated word, letters and digits
url	URL
word	Word, all letters

Une fois que le moteur a pu identifier les bons tokens, il applique des “dictionnaires”. Ces dictionnaires sont en réalité une succession de filtres permettant d’obtenir un lexème (lemmatisation).

Dictionnaires

Voici la liste des dictionnaires présents dans une installation par défaut :

\dFd+

Schema	Name	Template	Init options	Description
pg_catalog	danish_stem	pg_catalog.snowball	language = ‘danish’	snowball stemmer for danish
pg_catalog	english_stem	pg_catalog.snowball	language = ‘english’	snowball stemmer for english
pg_catalog	french_stem	pg_catalog.snowball	language = ‘french’	snowball stemmer for french
pg_catalog	russian_stem	pg_catalog.snowball	language = ‘russian’	snowball stemmer for russian

Il existe différents types de dictionnaire : - simple : Supprime la casse et les stopwords si spécifié. - synonym : Remplace les synonymes. - thesaurus : Remplace des expressions par des synonymes. - snowball : Lemmatisation (stemming) avec l’algo snowball.

Par exemple, le dictionnaire simple retire la casse :

SELECT ts_lexize('simple', 'Essayé');

 ts_lexize 
-----------
 {essayé}

Mot-vides

En langage naturel, des mots comme “le”, “la”, ou “et” sont appelés mots vides. Ces mots sont fréquemment ignorés lors de la recherche plein texte.

Pour plus d’informations, voir l’article de Wikipédia sur les mots vides.

Lemmatisation

Le but est d’identifier les lexèmes d’un document, c’est-à-dire les racines des mots porteurs de sens.

Par exemple :

• Verbe sans terminaison : “Empêcher” devient “empech”.

Quand tout le document a été analysé, on obtient un tsvector qui est une liste triée de lexèmes. Exemple :

select to_tsvector('Un petit pas pour l''Homme, un bond de géant pour l''Humanité');

                  to_tsvector                  
-----------------------------------------------
 'bond':8 'gé':10 'homm':6 'human':13 'pet':2

Il est également possible d’attribuer un poids à chaque lexème. Le poids peut être de A, B, C, ou D.

select setweight(to_tsvector('Un petit pas pour l''Homme, un bond de géant pour l''Humanité'), 'A');

                     setweight                      
----------------------------------------------------
 'bond':8A 'gé':10A 'homm':6A 'human':13A 'pet':2A

Créons notre propre configuration FTS

Parser

Nous allons créer une configuration FTS en utilisant un parser par défaut.

CREATE TEXT SEARCH CONFIGURATION my_fts (parser='default');

Pour obtenir des informations sur ce parser, nous pouvons utiliser la commande suivante :

\dFp+

Nous allons maintenant utiliser cette configuration FTS avec un texte :

set default_text_search_config to my_fts;

SELECT * from ts_debug('ma chaine');

Ce qui donne :

alias	description	token	dictionaries	lexemes
asciiword	Word, all ASCII	ma	{}
blank	Space symbols		{}
asciiword	Word, all ASCII	chaine	{}

Aucun dictionnaire n’est encore associé à un token.

Dictionnaires (Templates)

Les dictionnaires prennent en entrée un token et retournent un lexème ou un tableau de lexèmes. Ils peuvent également filtrer certains tokens non pertinents, comme les stopwords.

Voici un exemple avec le dictionnaire snowball :

CREATE TEXT SEARCH DICTIONARY my_fts_stem (
    TEMPLATE = snowball,
    Language = french,
    StopWords = french
);

Nous allons maintenant associer ce dictionnaire à notre configuration my_fts :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH my_fts_stem;

Simple

Le dictionnaire “simple” supprime la casse et les stopwords. Nous allons créer un dictionnaire personnalisé en utilisant une liste de stopwords :

cat maliste.stop
mysql

CREATE TEXT SEARCH DICTIONARY dic_simple (
    template = simple,
    stopwords = maliste
);

SELECT ts_lexize('dic_simple','mysql');

Maintenant, nous associons ce dictionnaire à notre configuration my_fts :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH dic_simple;

Nous pouvons constater que le dictionnaire fonctionne correctement :

select * from ts_debug('Je n''utilise pas Mysql');

alias	description	token	dictionaries	lexemes
asciiword	Word, all ASCII	Je	dic_simple	{je}
blank	Space symbols		{}
asciiword	Word, all ASCII	utilise	dic_simple	{utilise}
blank	Space symbols		{}
asciiword	Word, all ASCII	Mysql	dic_simple	{}

Synonyme

Nous allons ajouter un dictionnaire de synonymes :

postgres pgsql
postgresql pgsql
gogle googl
indices index*

CREATE TEXT SEARCH DICTIONARY my_synonym (
    TEMPLATE = synonym,
    SYNONYMS = 'synonym_sample'
);

Ensuite, nous ajoutons ce dictionnaire à notre configuration :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH my_synonym,dic_simple;

Nous pouvons maintenant tester les synonymes :

select * from ts_debug('PostgreSQL');

alias	description	token	dictionaries	lexemes
asciiword	Word, all ASCII	PostgreSQL	my_synonym, dic_simple	{pgsql}

Thesaurus

Nous allons créer un dictionnaire de thésaurus pour gérer des expressions complexes.

Exemple de thésaurus :

Durabilité de l'environnement : Développement durable
Développement soutenable : Développement durable
Viabilité écologique : Développement durable

Nous allons créer ce dictionnaire avec un fichier de thésaurus personnalisé :

CREATE TEXT SEARCH DICTIONARY thesaurus_simple (
    TEMPLATE = thesaurus,
    DictFile = thesaurus_sample,
    Dictionary = my_fts_stem
);

Ensuite, nous ajoutons ce dictionnaire à notre configuration :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH thesaurus_simple;

Nous combinons ensuite les différents dictionnaires :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH thesaurus_simple,my_synonym,dic_simple;

Voici un exemple d’utilisation du thésaurus :

SELECT to_tsvector('Durabilité écologique Test mysql Valence');

to_tsvector
‘Développement’:1 ‘durable’:2 ‘valence’:5

Ispell

Nous allons ajouter un dictionnaire Ispell pour la gestion morpho-syntaxique. Pour cela, nous devons d’abord télécharger un dictionnaire Ispell :

wget http://www.dicollecte.org/download/fr/hunspell-french-dictionaries-v5.7.zip
unzip hunspell-french-dictionaries-v5.7.zip
mv fr-toutesvariantes.aff fr_all.affix
mv fr-toutesvariantes.dic fr_all.dict

Ensuite, nous créons le dictionnaire :

CREATE TEXT SEARCH DICTIONARY french_hunspell (
    TEMPLATE = ispell,
    DictFile = fr_all,
    AffFile = fr_all
);

Nous associons ensuite ce dictionnaire à notre configuration :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH french_hunspell;

Configuration FTS

Nous allons maintenant assembler tous les dictionnaires créés.

drop text search configuration my_fts;

CREATE TEXT SEARCH CONFIGURATION my_fts (copy= french);

\dF+ my_fts

Ensuite, nous appliquons le mapping avec les différents dictionnaires :

ALTER TEXT SEARCH CONFIGURATION my_fts
    ALTER MAPPING FOR asciiword, asciihword, hword_asciipart,
                  word, hword, hword_part
    WITH thesaurus_simple,my_synonym,french_hunspell,dic_simple,my_fts_stem;

Pour rendre cette configuration FTS par défaut :

set default_text_search_config to 'my_fts';

Classement

Les fonctions ts_rank et ts_rank_cd permettent de classer les résultats en fonction de leur pertinence.

select ts_rank(to_tsvector('chien chat souris cheval poney') , to_tsquery('chat'));

ts_rank
0.26833

Poids

Nous pouvons attribuer des poids différents aux lexèmes dans notre recherche :

select setweight(to_tsvector('chat'),'A') || setweight(to_tsvector('cheval'),'C');

setweight
‘chat’:3A ‘cheval’:4C ‘felid’:2A ‘félin’:1A

select titre,contenu,ts_rank((setweight(to_tsvector(titre),'A')||setweight(to_tsvector(contenu),'C')), to_tsquery('sgbd')) as rang
  from articles 
  where (setweight(to_tsvector(titre),'A')||setweight(to_tsvector(contenu),'C')) @@ to_tsquery('sgbd')
  order by rang;

Normalisation

La normalisation permet de prendre en compte la longueur du document dans le calcul du classement :

select ts_rank(setweight(to_tsvector('chat'),'A')||setweight(to_tsvector('cheval'),'C') , to_tsquery('chat'),1|2|16);

Côté performances

Nous pouvons améliorer les performances en utilisant des index GIN ou GiST.

Index GIN

Un index GIN est un index inversé, adapté à la recherche plein texte.

CREATE INDEX ON textes using GIN (vector);

Index GiST

Les index GiST sont capables de stocker des poids, mais peuvent produire des faux positifs. Ils sont également plus volumineux.

CREATE INDEX ON textes using GIST (( setweight(to_tsvector('my_fts',livre),'A') || setweight(to_tsvector('my_fts',contenu),'C') ));

Extensibilité

PostgreSQL est extensible et permet l’ajout de nouveaux dictionnaires, analyseurs, et modèles de dictionnaires.

• Dictionnaire unaccent : Retire les accents.
• Dictionnaire dict_xsyn : Gère les synonymes en indexant un mot et tous ses synonymes.

Futur

Les futures améliorations possibles incluent :

• Dictionnaires en mémoire partagée : Pour améliorer les performances en limitant la consommation mémoire.
• Index RUM : Basé sur GIN, permet un ranking et une recherche de phrases plus rapide, mais est plus lent à construire.

Pour en savoir plus, vous pouvez consulter la présentation PGCon.

Biographie

Voici quelques références utiles :

• Documentation officielle :
• PostgreSQL Indexes Opclass
• PostgreSQL Text Search

• PostgreSQL Functions Text Search

• Articles :

• Indexing for Full Text Search in PostgreSQL
• PostgreSQL Full Text Search is Good Enough
• PostgreSQL Full Text Search Part 1

• Snowball Stemmer Algorithms

• Wikipédia :

• Indexation automatique de documents
• Recherche d’information
• Lemmatisation