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.