Consultas a bases de datos 262 veces más rapidas

Un poco de teoría sobre buscadores

Hoy os queremos contar algo que probablemente os deje a muchos con la sensación de que os estamos mintiendo. Puede que el título del post sea algo populista, pero realmente es cierto, así que: ¿Por qué no ponerle un nombre llamativo? J.

Antes de continuar, decir que para que le saquéis más jugo al post deberíais de saber SQL, aunque sea de forma muy básica. Los ejemplos mostrados y todo lo aquí expuesto está hecho con MySQL, pero estar característica no exclusiva de SGBD. Otros gestores (MS SQL Server) también disponen de ella. Para hacer nuestra base de datos de ejemplo y lanzar las consultas hemos usado, por comodidad, MySQL Workbench 5.2 OSS.

Cuando acabéis de leer el post conseguiréis que una búsqueda que antes tardaba en ejecutarse 12 segundos, se ejecute en 0.032 segundos!!!. Como dirían en la teletienda: increíble, pero cierto. Y para muestra un botón:

Conseguirás pasar de esto:

A esto:

El que más o el que menos ha hecho alguna vez (o al menos lo ha usado) un típico buscador en una página web. Cuando escribes lo que quieres buscar, internamente se suele transformar en un consulta más o menos como sigue:

    SELECT campo1,campo2,…,campoN FROM Tabla1, Tabla2…, TablaN WHERE Campo1 LIKE 'VALOR DE ENTRADA';

Este es el ejemplo más sencillo de consulta que podemos encontrar, y menos eficiente, porque si escribes dos palabras irían dentro del mismo "LIKE". Por eso lo que se hace es separar cada valor de lo que escribamos y construir sentencias con múltiples condiciones:

    SELECT campo1,campo2,…,campoN FROM Tabla1, Tabla2…, TablaN WHERE Campo1 LIKE 'ENTRADA1' AND Campo1 LIKE 'ENTRADA2' … ;

La consulta se puede complicar todo lo que el programador quiera, al igual que el operador booleano entre condiciones puede ser "AND" u "OR", normalmente a criterio del programador.

Estas consultas, relativamente sencillas, tienen un coste que depende de la cantidad de información que contenga la base de datos.

La cosa empieza a complicarse cuando tenemos que hacer búsquedas en las que entran en juego diferentes tablas. Para los ejemplos vamos a tomar 2 tablas. Una con citas de un libro Creative Common (podéis encontrar el libro aquí: http://www.moisescabello.com/escritos/Armantia.pdf), y otra con refranes españoles (podéis descargarlo de aquí: http://geneura.ugr.es/~victor/refranero.shtml). Las tablas recibirán los nombres de "citas" y "refranes" respectivamente:

    SELECT * FROM iniqua.refranes as A INNER JOIN iniqua.citas as B

WHERE

Refran like '%VALOR1%' and Refran like '%VALOR2%' and Description like '%VALOR3%' or Description like '%VALOR4%';

Ésta consulta le cuesta un tiempo resolverla a la base de datos. Si la lanzamos buscando cualquier palabra (que sabemos está incluida), nos da un tiempo de búsqueda bastante alto:

Como decía es un tiempo muy alto para una base de datos que se encuentra en el sistema local y sin ningún otro servicio corriendo, aunque la búsqueda la hace entre millones de tuplas de información:

Resulta obvio el hecho de que si un usuario hace una búsqueda en nuestra web, por ejemplo, y tarde 15 segundos en devolverle la información lo más probable que murmulle algún "piropo" hacia nuestra familias y cierre la ventana del navegador. Hay que conseguir rebajar ese tiempo.

Los índices

Los índices son un tipo de dato especial que usan los motores de base de datos para tener acceso más rápido a ciertos campos de las tablas de las bases de datos. Hasta aquí nada nuevo. Normalmente los motores incluyen uno con la propia clave primaria de cada entidad, pero no siempre buscamos por la clave primaria, ¿verdad?.

Aquí es donde entra lo curioso de este post: En los tipos de índices. Vamos a aprender a usar el tipo de índice fulltext. Este índice está pensado para columnas de la base de datos que almacenen texto y sobre las que se vayan ha hacer búsquedas (como lo es el caso que expusimos más arriba).

El tipo de índice fulltext tiene muchas ventajas:

• Búsquedas ultrarrápidas.
• Las búsquedas son devueltas dependiendo del orden de relevancia.
• Excluye palabras de uso común, que no suelen ser útiles en las búsquedas.
• Excluye palabras que aparecen en más de la mitad de las filas
• Búsquedas configurables y muy sencillas.
• …

Como no es oro todo lo que reluce también hay que hacer mención al principal problema, que es el espacio. Toda base de datos, en mysql, tiene dos ficheros. Uno para los datos y otro para los índices. Cuando añades un índice del tipo fulltext el fichero de índices, normalmente mucho más pequeño que el de datos, pasa a ocupar prácticamente lo mismo que lo que ocupen las columnas con información que tienen este tipo de índice. Esto tendremos que tenerlo en cuenta, ya que si tenemos una base de datos de 200MB (guardado en una columna casi toda la información), realmente nos hará falta casi 400MB de espacio.

Podemos crear un índice haciendo uso de mysql-workbench, si nos apetece ponernos con SQL. Seleccionando la tabla y pulsando el botón derecho->Alter table:

Una vez aplicado los cambios ya podemos usar el índice.

Consultas usando el índice FullText.

Con este tipo de índice podemos encontrar varios tipos diferente de consultas:

• Búsquedas en lenguaje natural:

  Son el tipo de búsquedas por defecto. Buscará el valor indicado en la columna que se le pase como parámetro. Si encuentra el valor en alguna de las columnas las mostrará como resultado.

• Búsquedas booleanas:

  Probablemente sean las más parecidas a lo que escribimos algo en google. Con método de búsqueda indicas que quieres qué palabras quieres que estén en los resultados y cuáles no usando comodines, como "+", "-", "*", etc.

• Búsquedas extendidas.

  Similares a las búsquedas naturales con una añadido. Hacen dos pasadas. Una primera con una búsqueda natural normal y otra segunda con las palabras más relevantes encontrada en la primera búsqueda. Te dirás, ¿y esto para qué me sirve a mi?. Es sencillo:

  Normalmente la gente asumimos, inconscientemente, que el buscador es un ser humano y que cuando escribamos en el cuadro de búsqueda la palabra "dase de datos" va a saber que queremos buscar entradas que estén relacionadas con las palabras: mysql, oracle, sql server, postgresql…, pero obviamente no es así.

  Imaginemos que tenemos una tabla con dos columnas. Una llamada "título" y otra "descripción". Supongamos la siguiente información almacenada:

 

Si hacemos una búsqueda normal en las dos columnas con las palabras "base de datos" obtendremos las filas 1 y 4. Pero si hacemos una búsqueda extendida, en la primera pasada el sistema encontrará la información de la columna título de las filas 1 y 4, cogerá las palabras más relevantes, que serán aquellas que más se repiten en todos los resultados (en este caso MySQL) y volverá ha hacer la búsqueda con estas palabras únicamente. Cuando hace la segunda pasada encontrará la fila 3, que se sumará a los resultados anteriores.

Como resultado final, con las palabras "bases de datos", obtendremos las filas: 1, 2 y 3.

Como podéis ver, esto proporciona mayor cantidad de aciertos a la hora de hacer búsquedas (o falsos positivos, depende como se mire).

Una vez sabido esto estamos en condiciones de escribir consultas, sabiendo lo que escribimos. La forma de escribir las sentencias SQL para tipo de consulta son las siguientes:

• Búsquedas en lenguaje natural (este es el método por defecto):

  SELECT * FROM TABLA WHERE MATCH(columna1,columna2,…,columnaN) AGAINST('valor1,valor2,…,valorN');

• Búsquedas booleanas:

  SELECT * FROM TABLA WHERE MATCH(columna1,columna2,…,columnaN) AGAINST('Cvalor1,Cvalor2,…,CvalorN' IN BOOLEAN MODE);
  

  Donde "C" es el modificador condicional.

• Búsquedas extendidas:

  SELECT * FROM TABLA WHERE MATCH(columna1,columna2,…,columnaN) AGAINST('valor1,valor2,…,valorN' WITH QUERY EXPANSION);

Comprobemos (por fin!) el rendimiento de todo lo hemos contado. Comencemos con las búsquedas booleanas, que son las más parecidas a las que hacemos normalmente. Buscamos en nuestras tablas de ejemplo:

Como podemos ver, la cantidad de resultados devueltos son exactamente los mismos que los de la consulta que mostrábamos al comienzo del post, salvo que ésta tardo la friolera de 12,3 segundos!!!!!.

Hagamos cálculos. La fórmula para saber el incremento del rendimiento es: cantidad_origen/cantidad_aumentada, por tanto:

O lo que es lo mismo. Usando un índice fulltext la búsqueda es 262 veces más rápida!!.

Pero el rendimiento no es todo. También podríamos hacer una búsqueda con comodines (la lista completa de parámetros la podéis encontrar en http://dev.mysql.com/doc/refman/5.5/en/fulltext-boolean.html). Busquemos ahora las filas, no repetidas, que contengan las palabras "poco", pero no "refranero", en la tabla "refrán". Además queremos que nos muestre todas las palabras que comiencen por "mar" y que contenga la frase exacta "es menester" (recalcar que los espacios entre palabras es lo mismo que poner un "or" booleano). Escribiríamos lo siguiente:

Tener en cuenta de que la ventaja de este tipo de índices no solo es la velocidad. La capacidad de hacer búsquedas más exhaustivas también es una característica muy importante que podemos encontrar con este índice.

Próximamente escribiremos sobre cómo usar este índice con diversos ORM: LINQ, Hibernate.

Como siempre, ya sabéis. Dudas, comentarios, críticas (constructivas, por favor) o cualquier insulto vario dejar un comentario

Referencias

http://dev.mysql.com/doc/refman/5.5/en/fulltext-search.html

http://www.databasejournal.com/sqletc/article.php/1578331/Using-Fulltext-Indexes-in-MySQL---Part-1.htm

http://www.databasejournal.com/features/mysql/article.php/1587371/Using-Fulltext-Indexes-in-MySQL---Part-2-Boolean-searches.htm

http://mysql-full-text.blogspot.com/

http://devzone.zend.com/node/view/id/1304