Índices SQL explicados, parte. 2

En la primera lección de Explicación de los índices SQL , aprendimos a usar la clasificación para acelerar la recuperación de datos. Si bien la ejecución de nuestra consulta es más rápida después de ordenar las filas, la ordenación implica leer cada fila al menos una vez y moverlas. Eso hace que el método sea más lento y menos eficiente que simplemente leer la tabla completa secuencialmente.

La conclusión lógica parece ser que deberíamos mantener copias ordenadas, que llamaremos oficialmente índices SQL, con el prefijo IX_ , de una tabla dada. Entonces se aplicarían los algoritmos de recuperación del primer artículo y no sería necesario ordenar la tabla antes de comenzar.

El índice como copia ordenada de la tabla

Echemos un vistazo a la implementación literal de esa idea, nuevamente usando Hojas de cálculo de Google. Nuestra hoja de cálculo de Reservas se convierte en una colección de cinco hojas que contienen los mismos datos. Cada hoja se ordena de acuerdo con diferentes conjuntos de columnas.

Los ejercicios aquí están destinados a ser menos exigentes que en el artículo anterior del tutorial del índice SQL: se pueden hacer más por tacto que por el temporizador y el recuento de filas. Algunos ejercicios parecerán muy similares, pero esta vez estamos explorando:

1. Cómo recuperar datos de manera más eficiente cuando se usan índices separados en lugar de tablas primarias ordenadas
2. Cómo mantener el orden en cada índice y tabla al modificar datos

El tutorial anterior se centró en las lecturas, pero en muchas dinámicas de datos comunes del mundo real, incluidas nuestras reservas de hotel, debemos tener en cuenta los efectos de la indexación en el rendimiento de escritura, tanto para insertar nuevos datos como para actualizar los datos existentes.

Ejercicio Preliminar: Cancelar una Reserva

Para tener una idea del rendimiento del índice SQL utilizando la estrategia de tablas ordenadas, su tarea es eliminar una reserva para el Cliente 12, del 22 de agosto de 2020, en el Hotel 4. Tenga en cuenta que debe eliminar una fila de todas las copias de la mesa y mantener la clasificación correcta.

¿Hecho? Debe quedar claro que la idea de mantener varias copias ordenadas de la tabla no es tan buena como parecía. Si aún tienes dudas, también puedes intentar volver a insertar la reserva que acabas de eliminar o cambiar la fecha de una reserva existente.

Si bien las copias ordenadas de la tabla permiten una recuperación más rápida, como acabamos de aprender, la modificación de datos es una pesadilla. Siempre que necesitemos agregar, eliminar o actualizar una fila existente, tendremos que recuperar todas las copias de la tabla, encontrar una fila y/o el lugar donde debe agregarse o moverse, y finalmente mover bloques de datos.

Índices SQL usando direcciones de fila

Esta hoja de cálculo contiene índices que utilizan un enfoque diferente. Las filas de índice aún se ordenan de acuerdo con criterios específicos, pero no mantenemos toda la otra información en la fila de índice. En cambio, mantenemos solo la "dirección de la fila", la dirección de la fila en la hoja de Reservas, que representa la tabla en sí, en la columna H.

Todas las implementaciones de RDBMS usan una capacidad a nivel de sistema operativo para encontrar rápidamente el bloque en el disco usando una dirección física. Las direcciones de fila generalmente consisten en una dirección de bloque más la posición de la fila dentro del bloque.

Hagamos algunos ejercicios para aprender cómo funciona este diseño de índice.

Ejercicio 1: Todas las Reservas de un Cliente

Como en el primer artículo, vas a simular la ejecución de la siguiente consulta SQL:

 SELECT * FROM Reservations WHERE ClientID = 12;

Una vez más, hay dos enfoques razonables. El primero es simplemente leer todas las filas de la tabla Reservas y obtener solo las filas que coinciden con los criterios:

 For each row from Reservations If Reservations.ClientID = 12 then write down Reservations.*

El segundo enfoque consiste en leer los datos de la hoja IX_ClientID y, para cualquier elemento que coincida con los criterios, encontrar una fila en la tabla de reservas según el valor de la dirección de la fila:

 Get first row from IX_ClientID where ClientID = 12 While IX_ClientID.ClientID = 12 Fetch Reservations.* where rowAddress = IX_ClientID.rowAddress Write down Reservations.* Get next row from IX_ClientID

Aquí, la expresión Get first row from se implementa mediante un bucle similar a los vistos en el artículo anterior:

 Repeat Fetch next row from IX_ClientID Until ClientID >= 12

Puede encontrar una fila con una dirección de fila determinada deslizándose hacia abajo hasta que encuentre una fila o usando un filtro en la columna dirección de fila.

Si solo hubiera un puñado de reservas para devolver, el enfoque que utiliza el índice sería mejor. Sin embargo, con cientos (o, a veces, incluso solo decenas) de filas para devolver, simplemente usar la tabla Reservas directamente puede ser más rápido.

El volumen de lecturas depende del valor de ClientID. Para el valor más grande, debe leer todo el índice, mientras que para el valor más bajo, está al principio del índice. El valor medio es la mitad del número de filas.

Volveremos a esa parte más adelante y presentaremos una solución eficiente. Por ahora, concentrémonos en la parte después de encontrar la primera fila que coincida con nuestros criterios.

Ejercicio 2: El número de reservas a partir de una fecha determinada

La tarea es contar el número de registros el 16 de agosto de 2020, utilizando el nuevo diseño de índice.

 SELECT COUNT (*) FROM Reservations WHERE DateFrom = TO_DATE('2020-08-16','YYYY-MM-DD');

El enfoque de usar el índice apropiado para contar es superior a la exploración de una tabla, sin importar el número de filas involucradas. La razón es que no tenemos que acceder a la tabla Reservas en absoluto, tenemos toda la información que necesitamos en el índice mismo:

 Count := 0 Get first row from IX_DateFrom where DateFrom >= '2020-08-16' While found and DateFrom < '2020-08-17' Count := Count + 1 Get next row from IX_DateFrom Write down Count

El algoritmo es básicamente el mismo que uno que usa tablas ordenadas. Sin embargo, la fila del índice es mucho más corta que la fila de la tabla, por lo que nuestro RDBMS tendría que leer menos bloques de datos del disco.

Ejercicio 3: Investigación Criminal (Lista de Huéspedes Dado Hotel y Rango de Fecha)

Preparemos una lista de huéspedes que llegaron al Hotel 3 los días 13 y 14 de agosto de 2020.

 SELECT ClientID FROM Reservations WHERE DateFrom BETWEEN ( TO_DATE('2020-08-13','YYYY-MM-DD') AND TO_DATE('2020-08-14','YYYY-MM-DD') ) AND HotelID = 3;

Podemos leer todas las filas de la tabla Reservas o usar uno de los índices disponibles. Después de hacer el mismo ejercicio con una tabla ordenada según criterios específicos, descubrimos que el índice IX_HotelID_DateFrom es el más eficiente.

 Get first row from IX_HotelID_DateFrom where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and DateFrom < '2020-08-15' and IX_HotelID_DateFrom.HotelID = 3 Fetch Reservations.* where rowAddress = IX_HotelID_DateFrom.rowAddress Write down Reservations.ClientID Get next row from IX_HotelID_DateFrom

¿Podemos diseñar un índice aún más eficiente?

Accedemos a la tabla debido al valor de ClientID , la única información que necesitamos para la lista de invitados que estamos informando. Si incluimos ese valor en el índice SQL, no tenemos que acceder a la tabla en absoluto. Intente preparar una lista que lea solo desde un índice de este tipo, IX_HotelID_DateFrom_ClientID :

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Write down ClientID Get next row from IX_HotelID_DateFrom_ClientID

Cuando el índice contiene toda la información necesaria para la ejecución de la consulta, decimos que el índice cubre la consulta.

Ejercicio 4: Lista de nombres de invitados en lugar de identificaciones

Una lista de identificaciones de invitados sería inútil para un oficial de policía que investiga un crimen. Necesitamos proporcionar nombres:

 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;

Para proporcionar una lista, además de los datos de la tabla de Reservations , también necesitamos una tabla de Clients que contenga información de los huéspedes, que se puede encontrar en esta hoja de Google.

Este ejercicio es similar al anterior, y también lo es el enfoque.

 Get first row from IX_HotelID_DateFrom_ClientID where HotelID = 3 and DateFrom between '2020-08-13' and '2020-08-14' While found and HotelID = 3 and DateFrom < '2020-08-15' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Clients.ClientName Get next row from IX_HotelID_DateFrom_ClientID

La expresión Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID puede implementarse mediante un escaneo de tabla o usando nuestro índice. Si usamos un escaneo de tabla, para cada ClientID del ciclo While , tendríamos que leer en promedio la mitad de las filas de la tabla Clients :

 -- Get row from Clients using table scan Repeat Fetch next row from Clients Until ClientID = IX_HotelID_DateFrom_ClientID.ClientID or not found If found Write down ClientName

La implementación de índice que hemos considerado hasta ahora, llamémosla implementación de índice "plana", no sería muy útil. Tendríamos que leer la misma cantidad de filas (aunque filas más pequeñas) del índice, luego saltar a la fila en Clients usando RowAddress :

 -- Get row from Clients using flat index Repeat Fetch next row from Clients_PK_Flat Until ClientID >= IX_HotelID_DateFrom_ClientID.ClientID If found Fetch Clients.* where rowAddress = Clients_PK_Flat.rowAddress Write down ClientName

Nota: Aquí, PK se refiere a "clave principal", un término que exploraremos más adelante en la serie.

¿Hay alguna manera de lograr esto sin tener que leer tantas filas? Sí, esto es exactamente para lo que son los índices de árbol B.

Índices de árbol equilibrado (árbol B)

Dividamos las filas de Clients_PK_Flat en bloques de cuatro filas y creemos una lista que contenga el valor del último ClientID del bloque y la dirección del inicio del bloque (columna IndexRowAddress ). La estructura de datos del índice de la base de datos resultante, que puede encontrar en la hoja Clients_PK_2Levels. Pruebe cómo la nueva estructura lo ayuda a encontrar un cliente que tenga un ClientID de 28. El algoritmo debería verse así:

 Fetch Level2.* Loop Leaf_address := Level3Address Exit when ClientID >= 28 Fetch next row from Level2 Fetch Level3.* where Level3Address = Leaf_address -- 3-21 Loop Client_address := RowAddress Exit when ClientID >= 28 Fetch next row from Level 3 Fetch Clients.* where rowAddress = Client_address -- 42 Write down Clients.*

Probablemente se dio cuenta de que podemos agregar otro nivel. El nivel 1 consta de cuatro filas, como puede ver en la pestaña IX_Clients_PK. Para encontrar el nombre del invitado con un ClientID de 28, debe leer tres bloques (nodos) de datos, uno por nivel, de la estructura de la clave principal y finalmente saltar a la fila Clientes con la dirección 42.

La estructura de este índice SQL se denomina árbol equilibrado. El árbol está equilibrado cuando la ruta desde el nodo raíz hasta cada nodo de nivel de hoja tiene la misma longitud, lo que se conoce como profundidad de árbol B. En nuestro caso, la profundidad es tres.

De ahora en adelante, consideraremos que cada índice tiene una estructura de árbol B, aunque nuestras hojas de cálculo solo contienen entradas a nivel de hoja. Los datos más importantes que debe saber sobre B-tree son:

• La estructura del índice B-tree es el índice más utilizado por todos los principales RDBMS del mercado.
• Todos los niveles de un árbol equilibrado están ordenados por valores de columna clave.
• Los datos se leen del disco en bloques.
• Un nodo de árbol B contiene uno o más bloques.
• El factor más importante que afecta el rendimiento de las consultas es la cantidad de bloques leídos del disco.
• El número de elementos en cada nuevo nivel del árbol B, comenzando por la raíz y terminando en el nivel de la hoja, aumenta exponencialmente.

Ejercicio 5: Investigación Criminal, Parte II

Ahora, el inspector de policía busca una lista de los nombres de los huéspedes correspondientes, las fechas de llegada y los nombres de los hoteles de todos los hoteles de la ciudad A.

 SELECT h.HotelName, r.DateFrom as CheckInDate, c.ClientName FROM Reservations r JOIN Clients c ON r.ClientID = c.ClientID JOIN Hotels h ON r.HotelID = h.HotelID WHERE r.DateFrom BETWEEN ( TO_DATE('2020-08-13', 'YYYY-MM-DD') AND TO_DATE('2020-08-14', 'YYYY-MM-DD') ) AND h.City = 'A';

Enfoque 1

Si usamos el índice IX_DateFrom_HotelID_ClientID , entonces para cada fila del rango de fechas, tendríamos que acceder a la tabla Hoteles y verificar si el hotel es de la ciudad A. Si es así, también tendríamos que acceder a la tabla Clientes para leer el nombre del cliente.

 For each row from IX_DateFrom_HotelID_ClientID where DateFrom between '2020-08-13' and '2020-08-14' For each row from Hotels where HotelID = IX_DateFrom_HotelID_ClientID.HotelID If Hotels.City = 'A' then Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

Enfoque 2

El uso IX_HotelID_DateFrom_ClientID nos brinda un plan de ejecución más eficiente.

 For each row from Hotels where City = 'A' For each row from IX_HotelID_DateFrom_ClientID where HotelID = Hotels.HotelID and DateFrom between '2020-08-13' and '2020-08-14' Fetch Clients.* where ClientID = IX_HotelID_DateFrom_ClientID.ClientID Write down Hotels.HotelName, IX_HotelID_DateFrom_ClientID.DateFrom, Clients.ClientName

En la tabla Hotels , encontramos todos los hoteles de la ciudad A. Conociendo la ID de estos hoteles, podemos leer los elementos posteriores del índice IX_HotelID_DateFrom_ClientID . De esta forma, después de encontrar la primera fila en el nivel de hoja del árbol B para cada hotel y fecha, no leemos las reservas de hoteles fuera de la ciudad A.

Aquí, podemos ver que cuando tenemos un índice de base de datos que es apropiado para nuestros objetivos, una combinación adicional puede hacer que una consulta sea más rápida.

La estructura de árbol B y cómo se actualiza cada vez que se inserta, actualiza o elimina una fila se abordará con más detalle cuando explique la motivación para la partición y su impacto. La cuestión es que podemos considerar rápida esta operación siempre que utilicemos un índice.

La consulta de índice en SQL: los detalles marcan la diferencia

Cuando se trata de índices y bases de datos, trabajar en el nivel del lenguaje SQL oculta hasta cierto punto los detalles de implementación. Estos ejercicios están destinados a ayudarlo a tener una idea de cómo funcionan los planes de ejecución cuando se usan diferentes índices SQL. Después de leer el artículo, espero que pueda adivinar el mejor plan de ejecución dados los índices disponibles y los índices de diseño que harían una consulta lo más rápida y eficiente posible.

En la siguiente parte de esta serie, usaremos y ampliaremos las habilidades recién adquiridas para investigar y comprender las mejores prácticas y antipatrones más comunes en el uso de índices en SQL. Tengo una lista de buenas y mejores prácticas que quiero abordar en la siguiente parte, pero para que el próximo artículo sea más relevante para sus necesidades y experiencia, no dude en publicar sus propias preguntas que le gustaría ver respondidas .

En la parte final de Explicación de los índices de SQL , también aprenderemos sobre el particionamiento de tablas e índices, las motivaciones correctas e incorrectas para usarlo y su impacto en el rendimiento de las consultas y el mantenimiento de la base de datos.