Améliorer les performances de like et recherche partielle de mots dans Postgres

Lorsque j'ai voulu faire un système d'auto-complétion pour un champs de recherche sur une page web, j'ai pensé à utiliser un moteur de recherche fulltext, malheureusement, les recherches fulltext ne se font que sur des mots entiers. j'ai donc pensé à utiliser la fonction like de Postgres. Malheureusement, like n'utilisent les indexes, seulement si '%' est placé en fin de chaine, et cela ne correspondait pas à mon besoin. De plus il fallait absolument que les requêtes soit rapides, pour que l'auto-complétion soit utilisable. Après avoir écumé le web à la recherche d'une solution, et n'ayant rien trouvé de concluant, j'ai décidé de faire un peu de R & D et d'implémenter une solution maison qui utilise les indexes. L'astuce réside dans l'utilisation d'un algorithme Edge n-gram et d'une recherche fulltext qui, elle, utilise les indexes. Voici la solution pour utiliser les indexes dans les différents cas suivants :

  • tous les mots commençant par
  • tous les mots finissant par
  • tous les mots contenant

tous les mots commençant par

Pour commencer, j'ai crée un table de données city avec un champs name et je l'ai rempli avec 500 000 entrées. j'ai ensuite fait une recherche :

select name from city where name like 'par%';

La requête prend plusieurs secondes, et un explain m'indique un parcours séquentiel. Logique! me direz vous il n'y a pas d'indexes. Je crée donc un index et j'utilise la fonction lower() pour rendre mes requêtes insensibles à la casse:

CREATE INDEX city_name_idx ON city(lower("name"));

L'explain sur la requête select, me montre que l'index est bien utilisé. si votre locale n'est pas C, vous pouvez avoir besoin de spécifier l'option text_pattern_ops :

CREATE INDEX city_name_idx ON city(lower("name") text_pattern_ops);

tous les mots finissant par

essayons de trouver tout les mot finissant par 'par' :

select name from city where name like '%par';

L'index n'est pas utilisé. Afin qu'il le soit, une astuce consiste à inverser la chaine afin de pouvoir utiliser le '%' à la fin du mot recherché plutôt qu'au début. Voici une fonction plpgsql qui le fait :

CREATE OR REPLACE FUNCTION "public"."inverserchaine" (chaine text) RETURNS text AS
$body$
DECLARE
 i integer;
 resultat text = '';
BEGIN
 FOR i IN REVERSE length(chaine)..1 LOOP
  resultat:=resultat||substring(chaine from i for 1);
 END LOOP;
 return resultat;
END;
$body$
LANGUAGE 'plpgsql'  RETURNS NULL ON NULL INPUT SECURITY INVOKER IMMUTABLE;

créez ensuite un index :

CREATE INDEX cityreversename_idx ON city(inverserchaine("name") text_pattern_ops);

Il faudra que vos requêtes reflètent également cette inversion :

select name from city where name like inverserchaine('par')||'%'

L'opérateur || permet de concaténer le signe '%' à la chaine inversée. Le signe '%' est bien placé à la fin et donc l'index est utilisé, dixit explain. j'ai trouvé cette astuce sur cette page

tous les mots contenant

Maintenant attaquons nous aux choses sérieuses avec tous les mots contenant 'mot'. et la je n'ai rien trouvé de concluant sur le web.

select name from city where name like '%mot%';

Comme attendu, l'index n'est pas utilisé et la recherche prend plusieurs secondes. Mon astuce pour améliorer les performances, consiste à découper le texte en sous chaines représentant toutes les sous chaines le composant. Pour cela j'utilise un algorithme Edge n-grams que j'applique plusieurs fois. Un algorithme Edge n-­grams, décompose un mot à partir du début, exemple pour 'paris' : "p" "pa" "par" "pari" "paris". J'applique donc cet algorithme plusieurs fois sur le mot, en enlevant, à chaque fois la première lettre. Pour 'Paris' j'applique l'algorithme sur Paris, aris, ris, is. j'obtiens ainsi, toutes les sous chaines de Paris

P, Pa, Par, Pari, Paris, ar, ari, aris, ri, ris, is

Ces sous chaînes correspondent à toutes les sous chaines que l'utilisateur pourra taper et pour lesquelles 'Paris' sera un résultat valide.

Il me suffit ensuite de mettre ces sous chaines dans un champs fulltext que je nomme 'name_splited' et qui est de type 'tsvector' (le type fulltext de Postgres) et de créer un index sur ce champs. Si je recherche 'ari', la recherche fulltext me renverra le bon résultat car 'ari fait partie des sous chaines découpées et indéxées'.

ALTER TABLE city ADD COLUMN name_splited tsvector;
CREATE INDEX citytextsearchvectorindex ON city USING gin(name_splited);

J'ai implémenté cet algorithme dans une fonction Java, mais elle pourrait être écrite en plpgsql. Faire la fonction plpgsql me permettrait de mettre un trigger. (si quelqu'un en a l'envie ou le besoin, il peut la poster, ou je le ferai peut être lors d'un prochain post).

public static final String getSubStrings(String originalString, char delimiter) {
        if (originalString == null) {
                return null;
        }
        //use hashset to remove duplicate
        String substring = null;
        StringBuffer sb = new StringBuffer();
        Set<String> set = new HashSet<String>();
        originalString = transformStringForFulltextIndexation(originalString);
        for (int i = 0; i < originalString.length(); i++) {
                for (int j = i + 1; j <= originalString.length(); j++) {
                        substring = originalString.substring(i, j);
                        if (!substring.endsWith(" ")) {//we have alredy add the entry the last loop
                                if (substring.startsWith(" ")) {//need to trim?
                                        substring = substring.substring(1);
                                }
                                if (substring.length() > 1) {//only index string that have length >=2
                                        set.add(substring.replace(" ", String.valueOf(delimiter)));
                                }
                        }
                }
        }
                for (String part : set) {
                sb.append(part).append(" ");
        }
        return sb.toString();
}

Comme vous pouvez le voir, je remplace les espaces par un autre caractère (delimiter), qui dans mon cas est '-'. Ceci s'explique par le fait qu'un champs ts_vector, découpe les textes en mots et indique leurs positions. Exemle pour "Saint jean"

select to_tsvector('saint jean')
"'jean':2 'saint':1"

Donc, si mon champs name contient des espaces, mes sous chaines vont contenir des espaces aussi. Par exemple 'aint je', comme sous chaine de 'saint jean'. C'est pourquoi je remplace les espaces par un autre caractère : la chaine 'aint je' deviendra 'aint-je' et sera indexée comme telle. Dans le cas contraire 'aint' et 'je' seront découpées en deux mots, alors que je veux indexer la chaine entière. Il me faut donc faire de même lors de la requête : si quelqu'un cherche "aint je" , il faut chercher "aint-je", j'aurais ainsi un format pivot, et la recherche fulltext matchera!

Il faut donc que je sauvegarde dans name_splited, le résultat de la fonction getSubStrings(), et mettre le résultat en lower case si je veux être insensible à la casse. Une requêtes pour l'auto complétion de "aint je" ressemblera à:

select name from city where this_.name_splited @@ to_tsquery('simple',lower('aint-j'))

@ @ correspond à l'opérateur fulltext de PostgreSQL, et la fonction lower() permet de rendre l'auto-complétion insensible à la casse. La requête sur 500 000 tuples met désormais 13 ms, utilise les indexes,et le résultat "saint Jean" fait partie des résultats. C'est gagné

Si vous voulez que votre recherche soit insensible aux accents et caractères spéciaux(comme c'est souvent le cas, pour que l'auto-complétion soit pertinente), je vous propose une fonctions Postgres que vous utiliserez aux mêmes endroits que vous utilisez la fonction lower :

CREATE OR REPLACE FUNCTION to_flat_text(text) RETURNS text AS
$body$
DECLARE
 chaine text;
BEGIN
chaine:=trim(lower($1));
 chaine:=replace(chaine,'-',' ');
 chaine:=translate(chaine,'âãäåāăąàèéêëēĕėęěìíîïìĩīĭóôõöōŏőðøùúûüũūŭůçñÿž',  'aaaaaaaaeeeeeeeeeiiiiiiiiooooooooouuuuuuuucnyz');
 chaine:=replace(chaine,'.',' ');
 chaine:=replace(chaine,'"',' ');
 chaine:=replace(chaine,';',' ');
 RETURN chaine;
END;
$body$
LANGUAGE 'plpgsql' RETURNS NULL ON NULL INPUT ;

A vous de l'adapter selon vos besoins.

La solution peut vous paraître alambiquée mais marche vraiment très bien. Je lai testée avec 28 millions de tuples, et l'auto-complétion est vraiment fluide. Si quelqu'un a une autres solution (Postgres only), je suis preneur :)

Commentaires

1. Le jeudi 18 février 2010, 10:59 par jf

Bonjour,
excellent article.
dans votre fonction to_flat_text vous pouvez ajouter la lettre ž qui se rencontre dans les langues commes le croate.

2. Le jeudi 18 février 2010, 13:43 par Masclet
je viens de l'ajouter ! :)
3. Le jeudi 18 février 2010, 14:13 par jf

Pour completer l'alphabet Slovene sans accents il convient d'ajouter Č, Š

Vaste programme ..

4. Le mercredi 5 janvier 2011, 14:24 par Fabrice

Je suis un débutant qui a besoin d'un système d'autocomplétion insensible aux accents. Est-il possible d'avoir le ou les fichiers complets des exemples cités plus haut en téléchargement afin que je me rende bien compte comment tout ceci fonctionne car je ne sais pas comment utiliser ces portions de code. Merci.

La discussion continue ailleurs

URL de rétrolien : https://davidmasclet.gisgraphy.com/index.php?trackback/25

Fil des commentaires de ce billet