Comment LIKE est-il implémenté?

22

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.

Entaille
la source

Réponses:

19

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 .

Justin Cave
la source
4
Oracle peut utiliser un index même avec un pourcentage de tête. Si les données recherchées représentent un petit sous-ensemble des lignes, le conseil peut le forcer à utiliser un index et à accélérer l'exécution. Voir laurentschneider.com/wordpress/2009/07/… .
Leigh Riffel
1
"scannez la table entière ... Evidemment, c'est très cher" - cela dépend plutôt de la table;) ps êtes-vous d'accord pour LAST_NAMEêtre candidat à (la première colonne de) l'index clusterisé? pps dans quelle mesure cette réponse suppose-t-elle que le système de base de données est basé sur un stockage contigu sur disque et sur des index B-tree?
onedaywhen
26

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.

Erwin Brandstetter
la source
3
En lisant ceci, je me suis demandé s'il fallait utiliser GIN ou GiST. D'après ce que j'ai lu, les index GIN sont plus chers à entretenir mais plus rapides à rechercher, tandis qu'un index GiST est moins cher à entretenir mais plus lent à rechercher. Cela signifie que les index GIN doivent généralement être utilisés sur des données relativement statiques, tandis que les index GiST sont préférés sur les tables à forte mutation.
Colin 't Hart
1
@ Colin'tHart: C'est généralement vrai, mais il y a des exceptions à la règle. Considérez l'addendum ci-dessus.
Erwin Brandstetter
5

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.

StanleyJohns
la source
1
Pourquoi commencerait-il à rechercher "S%" lorsque la sous-chaîne est définie sur 3 caractères (c'est-à-dire que nous savons que la chaîne n'est pas "Sr%")? Ou supposiez-vous que la base de données a un arbre de préfixe sur les attributs et fournissez un exemple de traversée de cet arbre?
Nick