| Utiliser un index pour les recherches sur des motifs tels que « colonne LIKE '%chaîne' »

Par Guillaume Lelarge le 15/07/2007 - 13:44

Depuis la version 8i, Oracle implémente les index inversés. Les index inversés permettent d’accélérer les recherches sur les motifs tels que « colonne LIKE '%chaîne' ». Dans ce type de cas de figure, 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. Voici une proposition d’implémentation équivalente pour PostgreSQL.

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 catégorisée en tant que « IMMUTABLE Â», ceci indiquant au SGBD que la fonction ne modifie pas les données et garantit 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 « Étendre 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.

Article écrit par Thomas Reiss, publié sur postgresqlfr.org avec sa permission. Merci beaucoup.