Améliorer les performances de like et recherche partielle de mots dans Postgres
Par MD3804-GANDI le lundi 21 décembre 2009, 10:23 - PostGIS / PostgresQL - Lien permanent
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
Bonjour,
excellent article.
dans votre fonction to_flat_text vous pouvez ajouter la lettre ž qui se rencontre dans les langues commes le croate.
Pour completer l'alphabet Slovene sans accents il convient d'ajouter Č, Š
Vaste programme ..
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.