Como o LIKE é implementado?

Alguém pode explicar como o operador LIKE é implementado nos sistemas de banco de dados atuais (por exemplo, MySQL ou Postgres)? ou me aponte para algumas referências que explicam isso?

A abordagem ingênua seria inspecionar cada registro, executando uma expressão regular ou uma correspondência parcial de cadeias de caracteres no campo de interesse, mas tenho a sensação (esperança) de que esses sistemas façam algo mais inteligente.

Não, isso é o que eles estão fazendo. Agora, se não houver um curinga inicial e o campo estiver indexado, que é a situação usual, o mecanismo de banco de dados poderá aplicar a expressão regular ao índice. Então, por exemplo, se você escrever

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

o banco de dados pode usar o índice LAST_NAMEpara encontrar todas as linhas em que o sobrenome começa 'Cav'. Por outro lado, se você tivesse algo como

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

o banco de dados precisaria verificar a tabela inteira (ou o índice inteiro) e avaliar a expressão em relação ao LAST_NAMEvalor total . Obviamente, isso é muito caro.

A maioria dos melhores bancos de dados relacionais possui recursos para fazer pesquisa de texto completo de maneira mais eficiente, construindo diferentes tipos de índices e catálogos de texto, mas eles não usam a palavra-chave LIKE. Por exemplo, aqui está um bom artigo que discute a pesquisa de texto completo no PostgreSQL .

Além do que Justin Cave escreveu, desde o PostgreSQL 9.1, você pode acelerar qualquer pesquisa com LIKE( ~~) ou ILIKE( ~~*), além de correspondências básicas de expressões regulares ( ~). Use as classes de operadores fornecidas pelo módulo pg_trgm com um índice GIN ou GiST para acelerar LIKEexpressões que não estão ancoradas à esquerda. Para instalar a extensão, execute uma vez por banco de dados:

CREATE EXTENSION pg_trgm;

Crie um índice do formulário

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);

Criando e mantendo um índice GIN ou GiST acarreta um custo, mas se sua tabela não for muito escrita, esse é um ótimo recurso para você.

Depesz escreveu um excelente artigo em seu blog sobre o novo recurso.

GIN ou GiST?

Essas duas citações do manual devem fornecer algumas orientações

A escolha entre a indexação GiST e GIN depende das características de desempenho relativas do GiST e GIN, que são discutidas em outros lugares. Como regra geral, um índice GIN é mais rápido para pesquisar do que um índice GiST, mas mais lento para compilar ou atualizar; portanto, o GIN é mais adequado para dados estáticos e o GiST para dados atualizados com frequência.

Mas para o tipo de consultas "vizinho mais próximo" com o operador using the distance <->:

Isso pode ser implementado com eficiência pelos índices GiST, mas não pelos índices GIN.

Falando sobre o MySQL, a posição do caractere curinga (%) faz a diferença. Se a primeira parte do texto for especificada como where first_name like 'Sta%', o mecanismo de banco de dados pesquisará apenas um subconjunto menor de palavras com S, passando para St e Sta, etc. Se você fizer algo parecido where first_name like '%stan%', faça uma varredura completa do coluna será necessária. Você também pode procurar em índices de texto completo que também fazem pesquisas em idiomas naturais. Confira os documentos do MySQL aqui.