¿Cómo se implementa LIKE?

22

¿Alguien puede explicar cómo se implementa el operador LIKE en los sistemas de bases de datos actuales (por ejemplo, MySQL o Postgres)? o señalarme algunas referencias que lo expliquen?

El enfoque ingenuo sería inspeccionar cada registro, ejecutando una expresión regular o una coincidencia de cadena parcial en el campo de interés, pero tengo la sensación (espero) de que estos sistemas hagan algo más inteligente.

Mella
fuente

Respuestas:

19

No, eso es más o menos lo que están haciendo. Ahora, si no hay un comodín inicial y el campo está indexado, que es la situación habitual, el motor de la base de datos puede aplicar la expresión regular al índice. Entonces, por ejemplo, si escribes

SELECT *
  FROM employees
 WHERE last_name LIKE 'Cav%'

la base de datos puede usar el índice LAST_NAMEpara encontrar todas las filas donde comienza el apellido 'Cav'. Por otro lado, si tuvieras algo como

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

la base de datos tendría que escanear la tabla completa (o el índice completo) y evaluar la expresión contra el LAST_NAMEvalor completo . Obviamente, eso es muy caro.

La mayoría de las mejores bases de datos relacionales tienen facilidades para realizar búsquedas de texto completo de una manera más eficiente mediante la construcción de diferentes tipos de índices y catálogos de texto, pero estos no usan la palabra clave LIKE. Por ejemplo, aquí hay un buen artículo que analiza la búsqueda de texto completo en PostgreSQL .

Justin Cave
fuente
44
Oracle puede usar un índice incluso con un porcentaje inicial. Si los datos que se buscan representan un pequeño subconjunto de las filas, la sugerencia puede obligarlo a usar un índice y acelerar la ejecución. Ver laurentschneider.com/wordpress/2009/07/… .
Leigh Riffel
1
"escanea toda la tabla ... Obviamente, eso es muy costoso", eso depende de la tabla;) ps ¿estás de acuerdo en LAST_NAMEser candidato para (la primera columna) el índice agrupado? pps ¿en qué medida esta respuesta supone que el sistema de base de datos se basa en el almacenamiento contiguo en el disco y los índices del árbol B?
cuando el
26

Además de lo que escribió Justin Cave, desde PostgreSQL 9.1 puede acelerar cualquier búsqueda con LIKE( ~~) o ILIKE( ~~*), y también coincidencias básicas de expresiones regulares ( ~). Utilice las clases de operador proporcionadas por el módulo pg_trgm con un índice GIN o GiST para acelerar las LIKEexpresiones que no están ancladas a la izquierda. Para instalar la extensión, ejecute una vez por base de datos:

CREATE EXTENSION pg_trgm;

Crear un índice del formulario

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

O:

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

Crear y mantener un índice GIN o GiST conlleva un costo, pero si su tabla no está muy escrita, esta es una gran característica para usted.

Depesz ha escrito un excelente artículo en su blog sobre la nueva característica.

GIN o GiST?

Estas dos citas del manual deberían proporcionar alguna orientación

La elección entre la indexación GiST y GIN depende de las características de rendimiento relativo de GiST y GIN, que se analizan en otra parte. Como regla general, un índice GIN es más rápido de buscar que un índice GiST, pero más lento de construir o actualizar; por lo tanto, GIN es más adecuado para datos estáticos y GiST para datos actualizados a menudo.

Pero para el tipo de consultas "vecino más cercano" con el uso del operador de distancia <->:

Esto puede implementarse de manera bastante eficiente por los índices GiST, pero no por los índices GIN.

Erwin Brandstetter
fuente
3
Al leer esto, me preguntaba si usar GIN o GiST. Según lo que leí, los índices GIN son más caros de mantener pero más rápidos de buscar, mientras que un índice GiST es más barato de mantener pero más lento de buscar. Esto significa que los índices GIN generalmente deben usarse en datos relativamente estáticos, mientras que los índices GiST se prefieren en tablas con mutaciones más intensas.
Colin 't Hart
1
@ Colin'tHart: Eso es generalmente cierto, pero hay excepciones a la regla. Considere el apéndice anterior.
Erwin Brandstetter
5

Hablando de MySQL, la posición del carácter comodín (%) hace la diferencia. Si la primera parte del texto se especifica como where first_name like 'Sta%', entonces el motor de base de datos buscará solo un subconjunto más pequeño de palabras con S, luego irá a St, y luego a Sta, etc. Si hace algo así where first_name like '%stan%', entonces, y toda la exploración del Se requerirá una columna. También puede buscar índices de texto completo que también realicen búsquedas en lenguaje natural. Echa un vistazo a los documentos de MySQL aquí.

StanleyJohns
fuente
1
¿Por qué comenzaría a buscar "S%" cuando la subcadena está definida en 3 caracteres (es decir, sabemos que la cadena no es "Sr%")? ¿O suponía que la base de datos tiene un árbol de prefijos sobre los atributos y proporciona un ejemplo de atravesar este árbol?
Nick