Solucionar cuellos de botella con índices SQL y particiones

En la primera lección de Explicación de los índices SQL, aprendimos que las consultas SELECT son más rápidas cuando los datos ya están ordenados por valores de columnas específicas.

En la segunda lección, aprendimos la estructura básica de los índices B-tree y cómo usarlos para reducir el volumen de datos a los que accedemos mientras ejecutamos una consulta. También descubrimos cómo implementar consultas que unen varias tablas y cómo los índices pueden acelerar dichas consultas.

También destacamos dos escenarios donde el uso de índices en SQL es útil. Cuando los índices cubren índices y contienen todas las columnas de la consulta, desde las condiciones WHERE , las condiciones JOIN y la lista SELECT , evitamos leer la tabla correspondiente por completo. Alternativamente, los índices pueden ayudar cuando reducen la cantidad de bloques de datos a los que se accede a una pequeña fracción del tamaño de la tabla.

De lo contrario, es más eficiente escanear toda la tabla que leer un índice y saltar aleatoriamente de un lado a otro a las filas correspondientes de la tabla.

Consultas de rango SQL

Las consultas que pueden aprovechar los índices normalmente incluyen condiciones que reducen significativamente el rango de valores posibles que pueden tomar una o más columnas. Las consultas de rango restringen los datos en función de condiciones como "el valor de la columna A debe estar entre X e Y".

Un buen ejemplo de esto es la consulta del Ejercicio 4 de la segunda lección:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND r.HotelID = 3;

Aquí tenemos dos gamas. El primero es el rango de fechas, el período entre el 13 de agosto de 2020 y el 14 de agosto de 2020. El segundo es el rango numérico más pequeño posible. La condición es equivalente a r.HotelID BETWEEN 3 AND 3 .

Ejercicio 1: Períodos (consultas de rango de fecha y hora)

Agreguemos una columna llamada CheckInTime a la tabla de Reservations . Puede ver datos de muestra en esta hoja de cálculo. Observe que hay un solo índice que cubre tanto CheckInTime como ClientId .

Escriba una consulta que devuelva los nombres de los clientes que se registraron el 15 de agosto de 2020.

Los desarrolladores de SQL sin experiencia suelen escribir la siguiente consulta:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE TO_DATE(r.CheckInTime, 'YYYY-MM-DD') = '2020-08-15';

Asumen que la ejecución de la consulta se vería así:

 Get first row from IX_CheckInTime_ClientID where TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' While found and TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

El problema es que ni un solo RDBMS en el momento de escribir este artículo es capaz de generar dicho plan de ejecución. Ven TO_DATE (sintaxis de Oracle) como una función que transforma el valor de la columna CheckInTime en algo no indexado. Entonces, los planes de ejecución que tienden a generar se ven así:

 For each row from IX_CheckInTime_ClientID If TO_DATE(CheckInTime, 'YYYY-MM-DD') = '2020-08-15' then Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName

Ejecutar esto sería más rápido que leer todas las filas de la tabla Reservations porque la fila del índice es más estrecha que la fila de la tabla. Una fila más pequeña significa que sería necesario acceder a menos bloques desde el disco.

Sin embargo, sabemos que el primer plan de ejecución sería mucho más eficiente. Para persuadir a nuestro RDBMS de usar ese enfoque, necesitamos reescribir la consulta:

 SELECT c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID WHERE r.CheckInTime >= TO_DATE('2020-08-15 00:00:00', 'YYYY-MM-DD HH:MI:SS') AND r.CheckInTime < TO_DATE('2020-08-16 00:00:00', 'YYYY-MM-DD HH:MI:SS');

Esta es una consulta de rango adecuada, una que todo buen RDBMS entiende. Nuestro RDBMS determina que queremos datos de la tabla de Reservations donde el valor de CheckInTime no algo derivado de él, pertenece al rango bien definido. El plan de ejecución que genera sería más como:

 Get first row from IX_CheckInTime_ClientID where CheckInTime >= '2020-08-15 00:00:00' While found and CheckInTime < '2020-08-16 00:00:00' Fetch Clients.* where ClientID = IX_CheckInTime_ClientID.ClientID Write down Clients.ClientName Get next row from IX_CheckInTime_ClientID

Eso es lo que realmente queremos: aprovechar no solo el índice en sí, sino también el hecho de que está ordenado.

Ejercicio 2: LIKE con un comodín al principio

Esta vez nuestro detective llega al hotel con información vaga sobre el sospechoso: solo que el apellido termina en “-hijo”. El detective quiere los nombres y apellidos de todos esos invitados:

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE '%son';

Para la tabla Clients y un índice sobre LastName , usaremos esta hoja de cálculo. Anote los resultados que devolvería la consulta. Piense en los diferentes enfoques que puede aplicar.

Enfoque de escaneo de tabla

La estrategia más simple es leer todos los datos de la tabla y anotar los nombres de los invitados cuando su apellido termina con "-hijo":

 For each row from Clients If LastName like '%son' then write down FirstName, LastName

Aquí, tendríamos que leer la tabla completa secuencialmente.

Usar un índice

Intentemos aprovechar el índice en la columna LastName . Vaya a la hoja IX_LastName, utilícela para encontrar todos los clientes que cumplan con el criterio dado y anote sus nombres.

Resulta que tienes que leer todo el índice para encontrar todos los Anderson, Robinson y Thompson de la tabla. ¿Es eso mejor que usar un escaneo de tabla? Además de leer todo el índice, también tenía que encontrar, para cada entrada coincidente, la fila correspondiente de la tabla utilizando el valor de dirección de rowAddress y luego escribir el FirstName desde allí:

 For each row from IX_LastName If LastName like '%son' then Fetch Clients.* where RowAddress = IX_LastName.RowAddress Write down FirstName, LastName

Para nosotros, fue más simple y rápido leer la tabla secuencialmente. Para nuestro RDBMS, dependería del porcentaje de filas que satisfagan los criterios. Si solo hay un puñado de Anderson, Robinson y Thompson en una tabla grande, un RDBMS leería menos bloques de datos de entradas de índice mucho más estrechas, incluso si tiene que leer algunos bloques de la tabla cuando encuentra una coincidencia. De lo contrario, el escaneo de la tabla lleva menos tiempo.

Ordenar los datos en el índice no proporciona ninguna ayuda con dicha consulta. El tamaño más pequeño de la fila del índice puede ser útil, pero solo en ocasiones.

Ejercicio 3: LIKE con un comodín al final

La próxima vez que venga nuestro detective, debemos encontrar a todos los clientes cuyos apellidos comiencen con "Rob-".

 SELECT FirstName, LastName FROM Clients WHERE LastName LIKE 'Rob%';

Intente extraer datos que coincidan con la consulta de la misma hoja de cálculo.

Si usó el enfoque de exploración de tablas, perdió la oportunidad de aprovechar al máximo el índice IX_LastName . Es mucho más rápido ubicar la primera entrada del índice que comienza con "Rob-" (Roberts), leer las filas posteriores (tanto Roberts como Robinsons) y detenerse cuando LastName ya no coincide con el criterio:

 Get first row from IX_LastName where LastName <= 'Rob' While found and LastName < 'Roc' Fetch Clients.* where rowAddress = IX_LastName.rowAddress Write down FirstName, LastName Get next from IX_LastName

En este caso, después de la búsqueda en el árbol B de la primera entrada, solo leemos las entradas que satisfacen el criterio. Dejamos de leer tan pronto como leemos un nombre que no coincide con el criterio.

Abordar los problemas de escalamiento del árbol B

Por lo general, cuando implementamos una nueva base de datos, hay algunas tablas de búsqueda llenas y tablas transaccionales vacías. El sistema funciona sin problemas desde el primer momento, especialmente si respetamos las buenas prácticas de diseño de bases de datos mediante la normalización de las tablas; crear claves primarias, foráneas y únicas; y soporte de claves foráneas con los índices correspondientes.

Después de algunos meses o años, cuando el volumen de datos ha aumentado significativamente la complejidad del sistema y la base de datos, comenzamos a notar una degradación del rendimiento. Surgen opiniones sobre por qué el sistema se ha ralentizado y qué hacer al respecto.

La opinión popular suele ser que el tamaño de la base de datos es el principal culpable. La solución parece ser eliminar los datos históricos que no necesitamos a diario y colocarlos en una base de datos separada para informes y análisis.

Exploremos primero la suposición principal.

Consultas de rango SQL: ¿el tiempo de ejecución depende del tamaño de la tabla?

Considere una consulta de rango típica de una sola tabla:

 SELECT Column1, …, ColumnN FROM Table WHERE Column BETWEEN X AND Y;

Suponiendo que hay un índice en Column , el plan de ejecución óptimo es:

 Get first row from IX_Column where Column between X and Y While found and Column <= Y Fetch Table.* where rowAddress = IX_Column.rowAddress Write down Column1, …, ColumnN Get next row from IX_Column

Contemos los bloques que un RDBMS tendrá que leer para devolver estos datos.

La parte Get first row se implementa mediante la búsqueda de árbol B que presentamos en la segunda lección. El número de bloques que tiene que leer es igual a la profundidad del árbol B. Después de eso, leemos los elementos subsiguientes del nivel hoja del índice.

Con las consultas OLTP, normalmente todos los resultados se encontrarán dentro de un bloque de índice (a veces dos, pero rara vez más). Además de eso, para cada entrada de índice, tenemos acceso a un bloque en la tabla para encontrar la fila correspondiente en función de su dirección. Algunas filas de la tabla pueden estar dentro del mismo bloque de tabla que ya cargamos, pero para simplificar la estimación, supongamos que cargamos un nuevo bloque cada vez.

Así que la fórmula es:

segundo = re + 1 + der

B es el número total de bloques leídos, D es la profundidad del árbol B y R es el número de filas devueltas por la consulta.

El único parámetro que depende del número de filas de la tabla es D, la profundidad del árbol B.

Para simplificar los cálculos y hacer un punto, suponga que 1000 entradas de índice caben en un bloque. D = 1 siempre que haya menos de 1000 filas en la tabla. Para las tablas que contienen transacciones comerciales, ese podría ser el caso el primer día hábil después de la implementación del sistema. Muy pronto, la profundidad del árbol B aumentará. Siempre que haya menos de 1 millón de filas en la tabla, el índice constará de dos niveles.

Si nos molestan los tiempos de respuesta lentos de la base de datos y culpamos al volumen de datos por esto, tenga en cuenta que las tablas de transacciones a menudo tienen solo millones de filas. Dado que solo 1 millón de filas se ajustan a un índice de árbol B de dos niveles, la profundidad debe ser de al menos tres. La profundidad no aumentará a cuatro a menos que haya más de mil millones de filas en la tabla. Ahora tenemos una estimación más precisa:

B = 4 + R

Si R es pequeño, reducir la profundidad del árbol B a dos aceleraría significativamente la consulta. Cuando buscamos por un valor de clave primaria o única, el sistema leerá cuatro bloques en lugar de cinco, lo que representa una mejora del 20 %. Si la consulta devuelve más filas, es posible que la mejora no se note. El problema es que, para muchas aplicaciones, es posible que no podamos respaldar las operaciones comerciales requeridas manteniendo menos de 1 millón de transacciones en la base de datos.

Entonces, la conclusión parece ser que el tamaño de la mesa no importa; en otras palabras, mover datos históricos es una pérdida de tiempo y recursos.

Pero no tan rápido: aprendamos más sobre la estructura de un índice de árbol B y cómo lo afectan los cambios de datos.

Detalles de implementación del índice B-tree

En nuestra cobertura de los índices del árbol B en la segunda lección, vimos que todos los niveles de un árbol equilibrado están (físicamente) ordenados por valores de columna clave. Sin embargo, cuando queremos insertar, actualizar o eliminar un elemento, muchas veces tenemos que mover una gran cantidad de datos para conservar el orden.

Digamos que estamos insertando en medio de un bloque que está lleno. Tenemos que dividir el bloque, reorganizar los datos y, a veces, incluso actualizar los datos en otro nivel de árbol B que apunta al actual.

Para que estos casos sean más eficientes, cada elemento del índice contiene punteros a las filas anterior y siguiente, lo que lo convierte en un enlace doble. Para insertar en general, esto significa que simplemente escribimos los elementos nuevos lo más cerca posible del anterior y corregimos los punteros.

Cuando también necesitamos dividir un bloque, debemos escribir un nuevo elemento en el nivel del árbol B anterior. Esto es solo una cuestión de corregir algunos puntos más, no es necesario volver a escribir grandes porciones del árbol. Después de una división, ambos bloques de datos están aproximadamente medio llenos. Dependiendo de dónde haya espacio libre en el disco, los bloques "vecinos" pueden estar físicamente bastante distantes.

Después de un tiempo, la fragmentación del índice aumenta y la ralentización de la ejecución de consultas se hace evidente. Con un RDBMS ejecutando consultas de la forma en que las describimos, la suposición del orden y la proximidad de los elementos se vuelve cada vez menos correcta, lo que lleva a muchas más lecturas. En el peor de los casos, con todos los bloques de datos medio vacíos, el sistema tiene que leer el doble de bloques.

Mantenimiento del índice B-tree

La cura para esto es la desfragmentación del índice (o "reindexación"). Cada RDBMS proporciona una función para recrear un índice completo; después de la reindexación, los índices se vuelven a ordenar físicamente.

La reindexación es una operación bastante rápida, aunque lee y escribe un gran volumen de datos. Los RDBMS modernos suelen ofrecer dos modos de reindexación, y el más rápido requiere que las tablas se bloqueen durante el procesamiento. De cualquier manera, es preferible reindexar en horas de menor actividad. De lo contrario, el procesamiento podría ralentizar el rendimiento de la base de datos.

Eliminación de datos históricos

Cuando tenemos tablas con miles de millones o incluso cientos de millones de filas, puede que no sea factible completar una operación de reindexación fuera de las horas pico.

Para evitar esta situación, la solución podría ser sacar los datos históricos de una base de datos OLTP. Sin embargo, si simplemente eliminamos las filas que son más antiguas que un umbral específico, hacemos que los índices estén aún más fragmentados y necesitamos volver a indexarlos con más frecuencia.

Particionamiento SQL al rescate?

Hay una manera de evitar la fragmentación causada por la eliminación de datos históricos, manteniendo solo las transacciones "activas" en la base de datos de producción. La idea que implementan todos los principales RDBMS es dividir una tabla en partes más pequeñas (llamadas particiones ) y proporcionar la capacidad de agregarlas, eliminarlas e incluso cambiarlas entre tablas (por ejemplo, de una tabla activa a una histórica con el mismo estructura).

Echemos un vistazo a la tabla Reservations tal como está dividida en esta hoja de cálculo. La tabla está dividida por mes, con nombres de partición asignados a períodos de fecha y otras hojas de cálculo. Para ver cómo se ejecuta una consulta en una tabla particionada, haremos algunos ejercicios.

Ejercicio 4: consulta de partición en SQL

Desde la hoja de cálculo vinculada anteriormente, intente extraer los datos solicitados por la siguiente consulta, sin utilizar ningún índice:

 SELECT HotelID, ReservationID, ClientID, DateFrom, DateTo FROM Reservations WHERE DateFrom BETWEEN TO_DATE('2021-03-01','YYYY-MM-DD') AND TO_DATE('2021-03-03');

Probablemente descubrió que primero debe mirar la hoja de asignación de particiones y encontrar la partición que contiene las reservas de marzo de 2021. Después de eso, abrió la partición correspondiente, leyó los datos secuencialmente y filtró las filas que no cumplieron con el condición.

Si bien es sencillo, probablemente no le gustó mantener tan pocas filas después de leer tantas. Leer la partición de marzo fue mejor que leer toda la tabla de reservas, pero aun así no es lo ideal. ¿Qué pasa con los índices?

Índices globales

Los RDBMS nos permiten crear un índice global para cubrir todas las particiones de una tabla particionada. Pero no hay diferencia entre cómo funcionan los índices globales y regulares debajo: los índices globales no son conscientes de la partición. Por lo tanto, las consultas CRUD que utilizan un índice global no involucran el mapa de partición de su tabla.

Solo necesitamos actualizar el mapa de particiones cuando soltamos una partición completa. Luego, debemos eliminar las filas del índice que apuntan a la partición eliminada. Eso significa que todo el índice global necesita reconstruirse.

Sigue siendo necesaria una ventana de interrupción porque los índices no se pueden usar hasta que se eliminen los elementos obsoletos. Si podemos descartar particiones regularmente, limitando la cantidad de particiones activas, entonces la operación de reindexación podría encajar en la ventana de interrupción. Por lo tanto, el uso de particiones ayuda con el problema original al reducir el tiempo necesario para las tareas de mantenimiento, incluido el mantenimiento de índices globales.

Pero, ¿y si todavía no podemos permitirnos el apagón?

Índices particionados globalmente

Esta estrategia resuelve ese problema: simplemente particionamos el índice de la misma manera que particionamos la tabla. En las hojas de cálculo a las que se vincula la hoja de cálculo de partición, cada partición contiene su parte de la tabla Reservations y una hoja de índice denominada IX_DateFrom, ambas particionadas por DateFrom .

Para ejecutar la consulta del Ejercicio 4, un RDBMS primero miraría un mapa de particiones de índice e identificaría qué particiones contienen fechas del rango. (En nuestro caso, es solo una partición de índice). Después de eso, usaría búsquedas de árbol B, pasaría al nivel de hoja y finalmente accedería a la tabla usando la dirección de fila correspondiente.

Cuando eliminamos una partición de una tabla, basta con eliminar la partición correspondiente del índice. No es necesario ningún tiempo de inactividad.

Índices locales

El principal inconveniente de los índices particionados globalmente es que tenemos que encargarnos de descartar tanto la tabla como la partición de índice correspondiente. Solo hay un pequeño costo adicional asociado con la lectura y el mantenimiento del mapa de particiones de índice en sí.

Los índices locales implican un enfoque similar pero ligeramente diferente. En lugar de particionar un solo índice global, creamos un índice local dentro de cada partición de tabla. Al hacerlo, los índices locales comparten la principal ventaja de los índices particionados globalmente, es decir, no hay tiempo de inactividad, al tiempo que evitan sus inconvenientes.

Parece una solución perfecta. Pero antes de celebrar, investiguemos el posible plan de ejecución de algunas consultas.

Ejercicio 5: índice particionado localmente

Intente ejecutar la consulta nuevamente, esta vez usando el índice particionado localmente en DateFrom .

Probablemente usaste este plan de ejecución:

 For all partitions where [StartDateFrom, StartDateTo) intersects ['2021-03-01', '2021-03-03'] Get first row from IX_DateFrom where DateFrom between '2021-03-01' and '2021-03-03' While found and DateFrom < '2021-03-04' Fetch Reservations.* where RowAddress = IX_DateFrom.RowAddress Write down HotelID, ReservationID, ClientID, DateFrom, DateTo Get next row from IX_DateFrom

Tenemos la suerte de que todas las fechas pertenecen a una sola partición, por lo que tuvimos que recorrer solo un índice local. Si el período fuera de seis meses, tendríamos que leer seis índices locales.

Ejercicio 6: En contraste

Su tarea es usar el mapa de partición de Reservas nuevamente, esta vez para hacer una lista de los períodos en los que el Cliente 124 visitó el Hotel 1:

 SELECT DateFrom, DateTo FROM Reservations WHERE ClientID = 124 AND HotelID = 1;

Aquí podemos ver el principal inconveniente de los índices locales. Tuvimos que leer la hoja de índice local IX_HotelID_CientID de cada partición de la tabla de Reservations :

 For all partitions Get first row from IX_HotelID_ClientID where ClientID = 124 and HotelID = 1 While found and ClientID = 124 and HotelID = 1 Fetch Reservations.* where RowAddress = IX_HotelID_ClientID.RowAddress Write down DateFrom, DateTo Get next row from IX_HotelID_ClientID

Esta ejecución claramente leería más bloques y tomaría más tiempo que si la tabla no estuviera particionada.

Entonces, si bien encontramos una manera de mantener la salud de nuestros índices durante el período de menor actividad, la estrategia también hizo que algunas de nuestras consultas fueran más lentas.

Si nuestro modelo de negocio nos permite mantener un pequeño número de particiones o al menos las consultas más frecuentes contienen criterios que permiten al RDBMS leer solo una o dos particiones, esta solución podría ser lo que necesitamos. De lo contrario, será mejor que evitemos la partición y trabajemos para mejorar el modelo de datos, los índices y las consultas, y mejorar el servidor de la base de datos.

Índices en SQL: qué aprender a continuación

Este es el final de nuestro viaje. En Explicación de los índices SQL, me concentré en la implementación del índice que es común a todos los RDBMS modernos. También me centré en los temas que interesan a los desarrolladores de aplicaciones, a expensas de los temas que suelen preocupar a los administradores de bases de datos. Este último haría bien en investigar el impacto del factor de relleno en la fragmentación del índice, pero es probable que a las personas en ambos roles les resulte útil leer más sobre:

• Almacenamiento en caché de datos e índices
• Estructuras de índice que no son de árbol B, como índices hash, GiST, de mapa de bits y de almacén de columnas
• Índices agrupados (conocidos como tablas organizadas por índices en Oracle)
• Índices funcionales
• índices parciales

El enfoque de particionamiento que discutimos es el particionamiento por rangos . Es el tipo de particionamiento más utilizado, pero existen otros, como el particionamiento hash y el particionamiento de lista. Además, algunos RDBMS ofrecen la opción de varios niveles de partición.

Por último, los desarrolladores de SQL harían bien en explorar otros temas importantes relacionados con la ejecución de consultas RDBMS: primero, el análisis de consultas, luego la compilación, el almacenamiento en caché y la reutilización del plan de ejecución basado en costos.

Para los cuatro RDMBS con los que tengo experiencia, recomiendo estos recursos como próximos pasos:

Oráculo

• Descripción general del Optimizador
• Índices y tablas organizadas por índices
• Gestión de índices
• Descripción general de las particiones
• Guía de particionamiento
• preguntale a tom

postgresql

• Procesamiento de consultas
• Índices en PostgreSQL
• Índices en PostgreSQL (Documentación Oficial)
• Gestión de búfer
• Particionamiento de tablas
• Guía de particionamiento

Servidor SQL de Microsoft

• Arquitectura de procesamiento de consultas
• índices
• Índices y tablas particionadas

MySQL/Maria DB

• Descripción del plan de ejecución de consultas
• Optimización e Índices
• Particionamiento - Conceptos básicos
• Particionamiento - Documentación
• Documentación de MariaDB: optimización de consultas e índices