Voici un petit article technique que j'ai écrit dans le cadre du travail et
dont on m'a autorisé la diffusion. Je remercie Guillaume Lelarge pour l'avoir
posté sur le site de la communauté francophone des utilisateurs de
PostgreSQL : Utiliser un index pour les recherches sur des motifs tels que
« colonne LIKE '%chaîne' ».
Depuis la version 8i, Oracle implémente les index inversés. Voici une
proposition d’implémentation équivalente pour PostgreSQL. Les index inversés
permettent d’accélérer les recherches sur les motifs tels que « colonne
LIKE '%chaîne' ». Dans un tel cas, PostgreSQL effectue un parcours séquentiel
(ou « sequential scan ») de la table interrogée. Toutefois, il est
possible d’émuler un index inverse au moyen d’une fonction de renversement de
chaîne couplée à un index sur fonction.
Tout d’abord, il est nécessaire d’activer le support du langage procédural
PL/pgSQL au sein de la base de données cible à l’aide de la commande Unix
« createlang plpgsql BASECIBLE ».
La fonction appelée « reverse » prendra comme seul et unique
argument une chaîne de type varchar et retournera une chaîne de type
varchar.
CREATE OR REPLACE FUNCTION reverse(varchar) RETURNS varchar AS $PROC$
DECLARE
str_in ALIAS FOR $1;
str_out varchar;
str_temp varchar;
position integer;
BEGIN
-- Initialisation de str_out, sinon sa valeur reste à NULL
str_out := '';
-- Suppression des espaces en début et fin de chaîne
str_temp := trim(both ' ' from str_in);
-- position initialisée a la longueur de la chaîne
-- la chaîne est traitée a l’envers
position := char_length(str_temp);
-- Boucle: Inverse l'ordre des caractères d'une chaîne de caractères
WHILE position > 0 LOOP
-- la chaîne donnée en argument est parcourue
-- à l’envers,
-- et les caractères sont extraits individuellement au
-- moyen de la fonction interne substring
str_out := str_out || substring(str_temp, position, 1);
position := position - 1;
END LOOP;
RETURN str_out;
END;
$PROC$ LANGUAGE plpgsql
IMMUTABLE;
La fonction reverse est structurée en trois partie :
- La déclaration elle-même via l’ordre CREATE OR REPLACE FUNCTION
- La déclaration des variables utilisées, sous le bloc DECLARE
- Le corps de la fonction, entre BEGIN et END;
On notera que la fonction reverse est de catégorisée « IMMUTABLE »,
indiquant au SGBD que celle-ci ne modifie pas les données et garantie que la
fonction retournera toujours le même résultat quand elle est appelée avec les
mêmes arguments, condition indispensable à la création d’un index sur fonction.
Voir la documentation PostgreSQL « Catégories de volatilité des
fonctions » dans la partie « Etendre le SQL ».
Un essai de la procédure permet de s’assurer de son bon
fonctionnement :
DPAR=# SELECT reverse('Chaîne à renverser');
reverse
resrevner à enîahC
(1 ligne)
Pour optimiser les recherches par suffixes, il est nécessaire de créer un
index sur fonction, sans oublier une collecte des statistiques pour
l’optimiseur:
CREATE INDEX reverse_index_prenom ON personnes (REVERSE(prenom) varchar_pattern_ops);
ANALYZE TABLE personnes;
Ensuite, au lieu d’écrire un prédicat du type « WHERE prenom LIKE
’%mas’», on écrira :
SELECT * FROM personnes
WHERE reverse(prenom) LIKE reverse(’%mas’);
PostgreSQL utilisera alors l’index créé précédemment et répondra
instantanément. Sur une base de test contenant 4 millions d’enregistrement, les
temps de réponse sont passés de 10s à 33ms pour la requête.
La fonction « reverse » pourrait être améliorée, mais
l’implémentation décrite a l’avantage de montrer une réalisation simple et
donne un exemple d’écriture de fonction pour PostgreSQL. On notera que la
fonction renvoie une chaîne vide lorsque la valeur NULL est donnée en entrée.
Un autre axe d’amélioration de la vitesse d’exécution serait la réécriture de
cette fonction sous forme de fonction native en C couplée au choix d’un
algorithme de renversement efficace.
