Índice Merge

Es una de las preguntas más comunes acerca de la indexación: ¿es mejor crear un índice por cada columna o un único índice con todas las columnas del filtro where? La respuesta es muy sencilla en muchos casos: un índice con múltiples columnas es mejor, es un índice concatenado o compuesto. “Índices concatenados” lo explica con detalle.

Sin embargo, existen sentencias con las que un solo índice no puede hacer perfectamente el trabajo, sin importar cómo se defina el indice; por ejemplo, sentencias con dos o más condiciones de rangos independientes como el siguiente ejemplo:

SELECT first_name, last_name, date_of_birth 
  FROM employees
 WHERE UPPER(last_name) < ? 
   AND date_of_birth    < ?

Es imposible definir un índice B-tree que pueda soportar esta sentencia sin predicados de filtro. Como explicación, basta recordar que un índice es una lista enlazada.

Si se define un índice como UPPER(LAST_NAME), DATE_OF_BIRTH (en este orden), la lista empieza con A y termina con Z. La fecha de cumpleaños se considera solamente cuando se tienen dos empleados con el mismo apellido. Si se define el índice de forma distinta, éste empezará con el empleado mayor y terminará con el empleado más joven. En este caso, los apellidos sólo tienen un impacto menor sobre el orden del ordenamiento.

Sin importar cómo torcer o girar la definición del índice, las entradas están siempre colocadas a lo largo de la cadena. En el primer borde, tienes las entradas más pequeñas y en el otro borde, las más grandes. Un índice puede, por lo tanto, solamente soportar una condición de rango como acceso predicado. Soportar dos rangos de condiciones independientes necesita un segundo eje, por ejemplo, como un tablero de ajedrez. Entonces, la sentencia siguiente podría coincidir con todas las entradas desde un primer borde del tablero de ajedrez, pero un índice no se parece a un tablero, es más como una cadena. No existen bordes.

Se puede por supuesto aceptar el filtro de predicado y usar sin embargo un índice multi-columna. De todos modos, es la mejor solución en muchos casos. En este caso, la definición del índice deberá mencionar la columna más selectiva primero para usarla como predicado de acceso. Podría ser el origen del mito “de la columna más selectiva primera”, pero esta regla solamente es verdadera si no se puede evitar un filtro de predicado.

La otra alternativa es usar dos índices separados, uno por cada columna. Entonces la base de datos debe primero escanear ambos índices y después mezclar los resultados. Sólo la búsqueda (“LOOKUP”) del índice duplicado implica más esfuerzo porque la base de datos tiene que recorrer los árboles de dos índices. Adicionalmente, la base de datos necesita mucha memoria y tiempo de CPU para mezclar los resultados intermedios.

Las bases de datos utilizan dos métodos para mezclar índices. En primer lugar, existe el JOIN de índices. El Capítulo 4, “La operación de unión (join)” explica el algoritmo en detalle. La segunda usa una funcionalidad la cual viene del mundo de almacenes de datos (data warehouse).

El Data warehouse es la madre de todas las sentencias ad hoc. Se necesitan solamente algunos clics para mezclar aleatoriamente condiciones dentro de la sentencia de tu elección. Es imposible pronosticar las combinaciones de columnas que podrían aparecer en el filtro where e indexarlas como se ha explicado hasta ahora es casi imposible.

Los data warehouses usan un tipo de índice especial para resolver ese problema: el llamado indice bitmap. La ventaja de los índices bitmap es que es posible mezclarlos con bastante facilidad. Eso significa que obtienes un rendimiento aceptable cuando se indexa cada columna de manera individual. En cambio, si conoces la sentencia con anticipación, puedes crear un índice multi-columna B-tree a la medida, y será aún más rápido que mezclar múltiples índices bitmap.

De lejos, el mayor punto débil de los índices bitmap es la escalabilidad de los comandos insert, update y delete. Las operaciones de escritura simultáneas son virtualmente imposibles. Eso no supone un problema en los data warehouse porque los procesos de carga se programan uno tras otro. En las aplicaciones en línea, los índices bitmap son prácticamente inútiles.

Varios productos de bases de datos ofrecen soluciones híbridas entre los índices B-tree y Bitmap. A falta de un mejor camino de acceso, convierten los resultados de varios escaneos B-tree dentro de estructuras bitmap en memoria. Lo que sí puede combinarse de maneras eficientes. Las estructuras bitmap no se almacenan persistentemente sino que se desechan después de la ejecución de la sentencia; eso soluciona el problema de la pobre escalabilidad en escritura. Este método es, después de todo, un acto desesperado por parte del optimizador.

Si te gusta mi manera de explicar, te encantará mi libro.