Comment LIKE est-il implémenté?

Quelqu'un peut-il expliquer comment l'opérateur LIKE est implémenté dans les systèmes de base de données actuels (par exemple MySQL ou Postgres)? ou me pointer vers quelques références qui l'expliquent?

L'approche naïve serait d'inspecter chaque enregistrement, d'exécuter une expression régulière ou une correspondance de chaîne partielle sur le champ d'intérêt, mais j'ai le sentiment (j'espère) que ces systèmes font quelque chose de plus intelligent.

Non, c'est à peu près ce qu'ils font. Maintenant, s'il n'y a pas de caractère générique de début et que le champ est indexé, ce qui est la situation habituelle, le moteur de base de données peut appliquer l'expression régulière à l'index. Ainsi, par exemple, si vous écrivez

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

la base de données peut utiliser l'index sur LAST_NAMEpour trouver toutes les lignes où le nom de famille commence par «Cav». D'un autre côté, si vous aviez quelque chose comme

SELECT *
  FROM employees
 WHERE last_name LIKE '%av%'

la base de données devrait analyser la table entière (ou l'index entier) et évaluer l'expression par rapport à la LAST_NAMEvaleur complète . Évidemment, c'est très cher.

La plupart des meilleures bases de données relationnelles disposent d'installations pour effectuer une recherche en texte intégral d'une manière plus efficace en construisant différents types d'index et de catalogues de texte, mais ceux-ci n'utilisent pas le mot clé LIKE. Par exemple, voici un bel article qui traite de la recherche en texte intégral dans PostgreSQL .

En plus de ce que Justin Cave a écrit, depuis PostgreSQL 9.1, vous pouvez accélérer toute recherche avec LIKE( ~~) ou ILIKE( ~~*), ainsi que les correspondances d'expressions régulières de base ( ~). Utilisez les classes d'opérateurs fournies par le module pg_trgm avec un index GIN ou GiST pour accélérer les LIKEexpressions qui ne sont pas ancrées à gauche. Pour installer l'extension, exécutez une fois par base de données:

CREATE EXTENSION pg_trgm;

Créer un index du formulaire

CREATE INDEX tbl_col_gin_trgm_idx ON tbl USING gin (col gin_trgm_ops);

Ou:

CREATE INDEX tbl_col_gist_trgm_idx ON tbl USING gist (col gist_trgm_ops);

La création et la maintenance d'un index GIN ou GiST ont un coût, mais si votre table n'est pas fortement écrite, c'est une excellente fonctionnalité pour vous.

Depesz a écrit un excellent article dans son blog sur la nouvelle fonctionnalité.

GIN ou GiST?

Ces deux citations du manuel devraient fournir quelques conseils

Le choix entre l'indexation GiST et GIN dépend des caractéristiques de performances relatives de GiST et GIN, qui sont discutées ailleurs. En règle générale, un index GIN est plus rapide à rechercher qu'un index GiST, mais plus lent à construire ou à mettre à jour; GIN est donc mieux adapté aux données statiques et GiST aux données souvent mises à jour.

Mais pour les requêtes de type "plus proche voisin" avec l'opérateur utilisant la distance <->:

Cela peut être implémenté assez efficacement par les index GiST, mais pas par les index GIN.

En parlant de MySQL, la position du caractère générique (%) fait une différence. Si la première partie du texte est spécifiée comme where first_name like 'Sta%', alors le moteur de base de données recherchera seulement un plus petit sous-ensemble de mots commençant par S, puis allant à St, puis Sta, etc. Si vous faites quelque chose comme where first_name like '%stan%', alors et l'analyse complète du sera requise. Vous pouvez également consulter des index de texte intégral qui effectuent également des recherches en langage naturel. Consultez les documents MySQL ici.