Supongamos que una gran empresa de alquiler de coches debe realizar un seguimiento de cada contrato de cliente, que está representado por una fila de una tabla de una base de datos. Cada fila incluye el identificador del cliente y un par de fechas que delimitan el período de tiempo de alquiler. Una consulta SQL para buscar todos los contratos que sea efectiva entre dos fechas podría llegar a buscar en una gran parte de la tabla de análisis debido a que las consultas de intersección de intervalos generalmente no tienen ningún soporte integrado en un sistema de gestión de bases de datos relacionales (RDBMS).

En el año 2000, un grupo de investigadores alemanes, Hans Peter Kriegel, Marco Pötke, y Thomas Seidl del Instituto de Ciencias de la computación en la Universidad de Munich, inventaron el árbol relacional de intervalos (árboles de RI, o RI-árboles), una estructura sumamente ingeniosa para manejar eficientemente las consultas de intervalo en SQL. Escribieron sobre ello en el documento «Managing Intervals Efficiently in Object-Relational Databases».

Sin embargo, hay un aspecto del RI-árbol que es un poco complicado: no hay manera simple de manejar la inserción por lotes (es decir, sentencias INSERT, SELECT, etc.) porque cada fila insertada podría modificar el valor de uno de los cuatro parámetros del árbol. Este artículo se refiere a una variante del árbol de RI, el RI-árbol estático que admite la inserción por lotes con excelente rendimiento.

El árbol original de RI tiene cuatro parámetros asociados: desplazamiento, leftRoot, rightRoot y minstep. La función de estos parámetros es ahorrar tiempo de CPU por controlar la longitud del árbol, evitando así muchas repeticiones inútiles al recorrer el árbol. Lamentablemente, la inserción de un intervalo depende de estos parámetros, que a su vez, podrían ser modificados por la inserción misma. Esto hace que sea difícil escribir una instrucción INSERT SELECT.

El árbol de RI estático no utilice ninguno de los parámetros originales. En su lugar, un intervalo insertado depende sólo de los datos de la fila, lo que facilita el uso de instrucciones INSERT SELECT. En consecuencia, este árbol cubre la totalidad del ámbito de datos todo el tiempo. No se produce la expansión dinámica, de ahí el nombre de árbol RI estático. Debido a que esta nueva variante es estática, atraviesa el árbol de modo diferente a como se hace en el árbol de RI original para evitar muchas iteraciones.

El árbol RI estático

La columna vertebral de los RI-árboles estáticos se implementa igual que en un árbol binario: con sus nodos etiquetados como números enteros de 1 a 2N-1 en orden (donde n es el tamaño del tipo de datos entero usado, expresado en bits). El valor de la raíz se establece en 2N-1. Pueden usarse fechas en lugar de números enteros mediante una simple asignación entre fechas y números enteros. La Figura 1 en la página 56 muestra un árbol binario de ejemplo en el que N = 5.

El nodo de horquilla juega un papel fundamental en la estructura porque determina donde se inserta un intervalo en el RI-árbol estático. Su valor se utiliza en el nodo columna de la tabla de intervalos, tal como se muestra en la Lista 1. También se muestra en este código los dos índices construidos en esta tabla, como en el RI-árbol original.

Suponiendo un intervalo [lower, upper], con lower y upper siendo enteros, el nodo de horquilla se define como el nodo superior w en la siguiente relación:

lower < = w < = upper.

Tal como se describe en el documento original, la función forkNode procede a recorrer el árbol desde la raíz hasta el nodo de la horquilla, como se muestra en el listado 2.

Figure 1

Figure 1

Listing-1-The-SQL-implementation-of-the-Static-RI-Tree

Listing 1

Listing 2

Listing 2

El problema

Con esta implementación simplificada, hay un problema: el número de iteraciones necesarias en una llamada a forkNode depende de la altura del árbol y puede perder muchos ciclos de CPU. Por ejemplo, supongamos que estamos usando enteros de 32 bits que son números positivos que van de 1 a 231-1 = 2147483647. Si llamamos a forkNode con el intervalo [734288, 734317], la función empieza en la raíz, cuyo valor es 230 = 1073741824 y, a continuación, recorre los siguientes nodos:

thats-26

Eso es, ¡26 repeticiones para alcanzar el nodo de horquilla!

Una nueva forma de encontrar el nodo de horquilla

Para el resto de este artículo, sea nx la representación de un nodo del árbol con el valor x. Supongamos que estamos buscando el nodo de horquilla para un intervalo [inferior, superior] en el que Nlower es el nodo con el valor menor y Nupper es el nodo con el valor superior. Mirando de cerca el árbol binario de la figura 1, observe que el nodo de horquilla puede determinarse simplemente a partir de inferior y superior. En lugar de partir de la raíz, podemos recorrer el árbol desde Nlower y Nupper hasta llegar a su ancestro común más bajo. Este será el nodo horquilla.

Para demostrar que el antepasado común más bajo de Nlower y Nupper es sin duda su nodo de horquilla, considere los siguientes casos:

Caso 1: Si Nlower y Nupper tienen un ancestro común bajo de nx que no es ni Nlower ni Nupper entonces Nlower estará en el subárbol izquierdo de nx y Nupper estará en el subárbol derecho de nx. Como tal, x está en el intervalo [inferior, superior]. Por lo que el valor de cualquier ancestro de nx está fuera de este intervalo, y nx es el nodo de la horquilla.

Caso 2: Si Nlower = Nupper , el nodo de la horquilla es esa. También es el ancestro común más bajo.

Caso 3: Si Nlower es un antepasado de Nupper , el nodo de horquilla será Nlower porque es el mayor nodo cuyo valor está contenido en el intervalo [inferior, superior], mientras todos sus ancestros están fuera de este intervalo. También, Nlower es el ancestro común más bajo.

Caso 4: Si Nupper es un antepasado de Nlower , el nodo de horquilla será Nupper por motivos simétricos a los del caso 3.

Ahora necesitamos un método para calcular el nodo de horquilla eficientemente desde inferior y superior. El árbol binario de ejemplo en la figura 2 (página 58) tiene sus nodos etiquetados con sus valores decimales y binarios. Mirando los valores binarios de los enteros en el árbol, podemos hacer varias observaciones:

Observación 1: Para cualquier nodo no-hoja que poseen un valor par, la representación binaria de este valor tendrá una secuencia no vacía de los bits 0, cuyo número depende de la altura del nodo en el árbol. Llamemos L a la secuencia de bits antes de los bits 0 finales de. L identifica un nodo no -hoja.

Observación 2: Supongamos que tenemos un nodo no-hoja nx con una secuencia de bits inicial de L. En el subárbol nx izquierdo, el prefijo del valor de cualquier nodo es L con su bit 1 de más a la derecha desactivado. En el subárbol derecho nx, el prefijo del valor de cualquier nodo es L.

Observación 3: Supongamos que tenemos un nodo no-hoja nx. El nodo nx-1 pertenece al subárbol izquierdo de nx (asumiendo que el valor 0 esté permitido en el árbol). Como el nodo de la horquilla del intervalo [x, y] (donde x < = y) es nx o un ancestro de nx, el intervalo [x-1, y] tiene el mismo nodo de horquilla. Esto permite la sustitución de x por x-1 sin cambiar el nodo de horquilla resultante.

Observación 4: Asumamos que tenemos el nodo hoja nz. El último bit de z se establece en 1, ya que es el valor de un nodo hoja. En este caso, z-1 tendrá la misma representación exacta de bits que z, salvo el último bit, que se asigna a 0.

Estas observaciones permiten definir un método para calcular el nodo de horquilla directamente desde Nlower y Nupper . Utilizando estas observaciones, debemos examinar los cuatro casos mencionados anteriormente y, a continuación, incorporar las ideas en un método general.

Para concluir, el cómputo del nodo horquilla se reduce a:

  1. Encontrar la secuencia de bits por la izquierda coincidentes entre lower-1 y upper.
  2. Anexar un bit «1».
  3. Llenar los bits restantes por la derecha con 0.
Figure 2 The virtual backbone of a Static RI-Tree

Figure 2 The virtual backbone of a Static RI-Tree

Debemos investigar un par de ejemplos:

Ejemplo 1: En el árbol representado en la figura 2, estamos buscando el nodo de la horquilla del intervalo [5, 10]. Este es el caso 1 y el nodo de la horquilla es 8. Debemos reemplazar 5 con 4, examinar las representaciones binarias de 4 y 10 y buscar los bits coincidentes izquierdos. La búsqueda revela una secuencia reducida a un bit 0. La secuencia principal del nodo horquilla así es L = 01. Esta secuencia identifica el nodo etiquetado 8.

Ejemplo 2: Vamos a buscar el nodo de horquilla del intervalo [12, 15]. Este es el caso 3, y el nodo de la horquilla es 12. Reemplazar 12 con 11, examinar las representaciones binarias de 11 y 15 y buscar los bits coincidentes izquierdos. La búsqueda revela la secuencia 01. Después de anexar un bit «1», obtenemos la secuencia principal L = 011, que corresponde al nodo etiquetado 12.

Ejemplo 3: Ahora estamos buscando el nodo de la horquilla del intervalo [21, 24]. Este es el caso 4, y el nodo de la horquilla es 24. Reemplazar 21 con 20, examinar las representaciones binarias de 20 y 24 y buscar los bits coincidentes izquierdos. La búsqueda revela la secuencia 1. Después de anexar un bit «1», obtenemos la secuencia principal L = 11, que corresponde al nodo etiquetado 24.

Ejemplo 4: Busquemos ahora el nodo de la horquilla del intervalo [21, 21]. Este es el caso 2, y el nodo de la horquilla es 21. Reemplazar 21 con 20, examinar las representaciones binarias de 20 y 21 y buscar los bits izquierdos coincidentes. La búsqueda revela la secuencia 1010. Después de anexar un bit «1», obtenemos la secuencia principal L = 10101, que corresponde al nodo etiquetado 21.

La función forkNode mejorada

Vamos a utilizar el nuevo método para reescribir la función forkNode y tratar de recortar el número de iteraciones. Esto requiere un conocimiento del tamaño de almacenamiento de los enteros. El Listado 3 muestra la nueva implementación de la función forkNode de enteros de 32 bits.

Listing 3

Listing 3

¿Esto parece extraño, no es cierto? Vamos a analizar la lógica. En la instrucción int nodo = (lower – 1) ^ upper, el operador ^ se utiliza para calcular una operación OR bit a bit exclusiva entre lower-1 y upper. Esto ayuda a encontrar la secuencia de la izquierda de bits coincidentes entre lower-1 y upper porque el OR exclusivo borra esos bits, mientras que el bit 1 más a la izquierda en el resultado indica la posición del bit más a la izquierda que no es coincidente entre lower-1 y upper. Llamemos a esta posición w. Por ejemplo, la figura 3 muestra el resultado de esta instrucción cuando lower = 734288 y upper = 734317.

Figura 3

Figura 3

El operador >> desplaza todos los bits a la derecha el número de posiciones indicado por el valor que aparece después del operador. Por lo tanto, la instrucción nodo >> = 1 desplaza el valor de la variable del nodo 1 bit hacia la derecha (para colocar w + 1) y asigna el resultado al nodo. En este punto, el resultado es:

00000000000000010001

La serie de cinco instrucciones nodo | = nodo >> n copia el bit 1 en posición w + 1 a la derecha hasta que todos los bits a la derecha de la posición w + 1 se establecen en 1. En nuestro ejemplo, estas cinco instrucciones producen el resultado:

00000000000000011111

El operador ~ niega todos los bits: 0 se convierten de 1 y 1 en 0. Es para preparar una máscara de bits que ponga a cero todos los bits después de la posición w. En nuestro ejemplo, esto da:

11111111111111100000

La instrucción final return upper & ~node aplica la máscara a upper para borrar los bits y forma la secuencia inicial con 0s añadidos. Esto corresponde al nodo de la horquilla. En este caso, el resultado es:

10110011010001100000-734304

Esta aplicación es una optimización significativa porque el número de instrucciones ejecutadas es mucho menor y constante para muchos intervalos [lower, upper]. Se ahorra tiempo de CPU.

Una consulta basada en intersección de conjuntos

En el árbol original de RI, el enfoque para rellenar las tablas leftNodes y rightNodes es un algoritmo iterativo que recorrer el árbol binario desde la raíz hasta el nodo de la horquilla, y luego, desde el nodo de horquilla hasta los nodos más cercanos a Nlower y Nupper . En cada iteración, el algoritmo puede insertar una fila en la tabla leftNodes o rightNodes. Aunque estas tablas son pequeñas, un RDBMS típicamente procedería mucho más rápido con un cálculo basado en los conjuntos de estas tablas.

Busquemos una forma de reemplazar la inserción iterativa en las tablas leftNodes y rightNodes. En lugar de proceder de la raíz del árbol a los nodos Nlower y Nupper , vamos a ir en la dirección opuesta — desde Nlower y Nupper hasta la raíz. ¿Qué sucede con el valor binario de un nodo durante este proceso? En cada paso, el árbol borra el bit 1 de la derecha y establece el bit a su izquierda a 1 si no lo está ya. Por ejemplo, ir desde el nodo 11 al nodo 16 en la figura 2 incluye los siguientes pasos:

01011-11

Para rellenar las tablas leftNodes y rightNodes de abajo arriba, tenemos que separar los valores en dos grupos: los valores menores y los valores mayores que el valor del nodo inferior. Para buscar valores de menor valor del nodo final, sólo necesitamos borrar el bit 1 derecha. Para encontrar los valores mayores que el valor del nodo inferior, tenemos que desactivar el bit 1 derecho, establece el bit 0 derecho a la izquierda y todos los bits entre medias. En nuestro ejemplo anterior, para ir desde el nodo 11 al nodo 16, esta estrategia produce los siguientes valores inferiores a 11:

01011-11-2

Y los siguientes valores superiores a 11:

01011-11-3

 

Para implementar estas manipulaciones de bits, utilizamos la tabla de máscara de bits. En el listado 4 se muestra el código para crear esta tabla.

Listing 4

Listing 4

Suponiendo que N representa el tamaño del tipo de datos entero en bits, la tabla de máscara de bits está llena con N-1 filas. Llamemos r al índice de la fila, que va de 1 a N-1. Se calcula la columna b1 borrando los bits más a la derecha de r y estableciendo los demás bits. Una manera fácil de generar valores b1 es utilizar – (2r). La columna de b2 se calcula estableciendo el bit r (donde se cuentan bits de derecha a izquierda) y borrar todos los otros bits. Esto se puede calcular como 2r-1. La columna b3 se calcula como b2 * 2. Para ejemplo, en el cuadro 1 se muestran los valores binarios cuando N = 5.

Table 1

Table 1

Tenga en cuenta que en la siguiente explicación de la tabla de máscara de bits, el operador AND bit a bit y el operador OR bit a bit están representados por los caracteres & y |, respectivamente.

Suponiendo que queremos recuperar a todos los antepasados de nodo nx que tengan un valor inferior a x o los antepasados de nodo nx que tienen un valor superior a x, x se combinarán con todas las filas de la tabla de máscara de bits. Todos los nodos padre de nx que tienen un valor menor que x son nodos con un valor igual a x & b1 donde x & b2 es distinto de 0. Del mismo modo, todos los nodos padre de nx que tengan un valor superior a x son nodos con un valor igual a (x & b1) | b3 donde x & b3 es igual a 0. Así, el código SQL necesario para rellenar las tablas leftNodes y rightNodes será el que se muestra en el listado 5.

Listing 5

Listing 5

Implementar el árbol estático de RI con SQL Server

Inicialmente implementé la función de forkNode optimizado utilizando Microsoft SQL Server 2008 y T-SQL. He añadido la columna nodo a la tabla de intervalos como una columna calculada, persistente, cuya fórmula llama a la función forkNode, como se muestra en el listado 6. Esto funcionó bien y el tiempo de procesamiento de las instrucciones INSERT SELECT se redujo significativamente en comparación con la aplicación forkNode iterativa.

Listing 6

Listing 6

Un rendimiento mucho mejor podría lograrse mediante la conversión de forkNode a una función CLR definida por el usuario y almacenar el ensamblado .NET en la base de datos. Sin embargo, no todos están familiarizados con.NET y algunas compañías prohíben el uso de código CLR. Afortunadamente, en este caso, podemos lograr un rendimiento cercano al de una función .NET en T-SQL. Todo lo que se necesita es una fórmula optimizada escrita directamente en la definición de la columna calculada de la instrucción CREATE TABLE. Esto tiene la ventaja adicional de eliminar la necesidad de una llamada a la función forkNode. (Las llamadas a funciones son caras en términos de tiempo).

Limpiar la serie de bits más a la derecha puede lograrse con los operadores module y sustracción. Por ejemplo, limpiar los cinco bits más a la derecha del entero x puede ser escrito como x: x mod 25. Encontrar la posición w del bit 1 más a la izquierda, puede hacerse con las funciones LOG y FLOOR. Por ejemplo, la posición del bit más a la izquierda del entero x es LOG2x. La aplicación más rápida de T-SQL que se podría conseguir se muestra en el listado 7, que he probado en SQL Server 2008 y SQL Server 2005. Este código probablemente parece extraño, por tanto, debemos analizar la lógica.

Listing 7

Listing 7

La instrucción CREATE TABLE en el listado 7 usa el operador OR exclusivo bit a bit de T-SQL (^) y el operador módulo (%). La expresión POWER (2, FLOOR(LOG( (lower – 1) ^ upper)/LOG(2))) es equivalente a la expresión matemática 2log2((lower−1) XOR upper) donde la función FLOOR calcula el entero más grande menor o igual a su operando, como la pareja de operadores matemáticos AND.

La expresión upper % POWER(2… extrae los bits tras la posición w y la expresión completa resta estos bits de upper, de hecho, borrándolos.

Scripts de prueba para inserción

Comparemos las diferentes implementaciones de forkNode en el RI-árbol estático. Sin embargo, en primer lugar, necesitamos crear una tabla auxiliar que contenga 10.000.000 de números. El código para generar esta tabla se muestra en el listado 8. También necesitamos generar 10.000.000 de intervalos aleatorios en una tabla provisional para que las tablas de intervalo diferentes utilicen los mismos datos de muestra. EL listado 9 contiene el código para crear la tabla provisional.

Listing 8

Listing 8

Listing 9

Listing 9

El Listado 10 contiene la secuencia de comandos para crear y rellenar la tabla tradicional de intervalos. Se ha agregado una columna de nodo de relleno para que las filas ocupen el mismo espacio de almacenamiento que en un RI-árbol estático. Así pues, la inserción en la tabla de intervalos establece una referencia para el rendimiento. Lo que queremos para las otras implementaciones es llegar lo más cerca posible de esa situación.

 

Listing 10

Listing 10

El Listado 11 contiene la implementación iterativa de la función forkNode. El código de Listado 12 crea la tabla de Intervals2, cuya columna de nodo utiliza la función forkNode iterativa. Esperamos que la inserción en esta tabla sea lenta porque T-SQL es bastante lento al ejecutar bucles.

Listing 11

Listing 11

Listing 12

Listing 12

Listado de 13 contiene la implementación optimizada de la función forkNode. El código en la lista de 14 crea la tabla de Intervals3, cuya columna de nodo utiliza la función forkNode optimizada. La implementación optimizada debe ser más rápido que la aplicación iterativa porque no se utiliza ningún bucle. La función optimizada es encapsulada dentro del cuerpo de forkNode. Esto es útil para ver a la sobrecarga de llamar a una función definida por el usuario.

Listing 13

Listing 13

Listing 14

Listing 14

El Listado 15 contiene una secuencia de comandos para crear la tabla Intervals4, cuya columna nodo utiliza la fórmula en línea, optimizada. Esperamos que esta implementación sea la más rápida.

Listing 15

Listing 15

La tabla 2 resume la cantidad de tiempo transcurrido para rellenar las tablas. Obtuve estos tiempos en mi ordenador de sobremesa, que es un procesador Intel Core 2 Duo E8500, trabajando a 3.17 GHz, con 4 GB de RAM. SQL Server 2008 estaba instalado y las consultas eran locales.

Table 2

Table 2

Una consulta de intersección de muestra

Vamos a comparar ahora el rendimiento de una consulta de intersección cuando se utilizan los enfoques tradicional y de RI-árbol estático. Tenemos que ejecutar una consulta que considere todos los intervalos que intersectan el intervalo [826216,826254] en la tabla de intervalos (enfoque tradicional) y la tabla de Intervals4 (enfoque estático RI-Árbol).

Enfoque tradicional: Ejecutar la consulta en la tabla de intervalos es muy simple, como muestra el Listado 16. Sin embargo, SQL Server obtiene demasiados datos de análisis, porque no hay un índice instalado que pueda hacer buen uso de los parámetros @lower y @upper. Para remediar esta situación, podemos intentar crear índices útiles, como se muestra en el listado 17.

Listing 16

Listing 16

Listing 17

Listing 17

Cuando ejecutamos la consulta nuevamente después de creados los índices, SQL Server genera un plan de ejecución de uno de los índices, basando su elección en los actuales valores declarados de @lower y @upper, como se muestra en la figura 4. Luego, reutiliza el plan en consultas posteriores, incluso cuando el otro índice habría sido más apropiado. Esto significa que no hay ningún plan estable en la caché. Por lo tanto, aun cuando se utilice uno de los índices, SQL Server genera demasiados datos de análisis. En mi PC, esta consulta había involucrado 15.498 lecturas lógicas y había consumido 358 milisegundos de CPU.
(Normalmente, la sugerencia de consulta RECOMPILE puede utilizarse para mejorar este tipo de situaciones, pero en este caso, la consulta no se beneficiaría de planes en caché).

Figure 4

Figure 4

Enfoque RI-árbol estático: Las consultas de intersección utilizando el enfoque RI-árbol estático implican la tabla de máscara de bits. Un ejemplo de código para rellenar la tabla de máscara de bits se muestra en el listado 18.

Listing 18

Listing 18

El listado 19 muestra la consulta que se ejecutará contra la tabla de máscara de bits. Se trata de la misma consulta que usa el enfoque tradicional, excepto que se ha adaptado para su uso con el RI-árbol estático. Antes de poder ejecutar esta consulta, sin embargo, tenemos que crear los índices de la tabla Intervals4 utilizando el código del Listado 20.

Listing 19

Listing 19

Listing 20

Listing 20

Para esta consulta de intersección de RI-árbol estático, SQL Server genera un plan de ejecución estable, como se muestra en la figura 5 (página 67). La gran ventaja de este plan es que puede ser reutilizado para todas las consultas de intersección porque no depende del criterio de selección. En mi máquina, en esta consulta participan 124 lecturas lógicas y había consumido 0 milisegundos de CPU.

Tenga en cuenta que, para favorecer la reutilización de código, se pueden implementar las tablas leftNodes y rightNodes como funciones con valores de tabla en línea, que SQL Server expande en tiempo de ejecución (véase el Listado 21). En este caso, no se incurre en ninguna penalización de rendimiento adicional debido a una llamada a función. El Listado 22 (página 67) muestra la consulta de intersección usando estas funciones.

 

Figure 5

Figure 5

Figure 5

Listing 21

Listing 22

Listing 22

Conclusión

En este artículo, he presentado el RI-árbol estático, que utiliza una instrucción INSERT SELECT para insertar intervalos en procesos por lotes en la base de datos con buen rendimiento. También he mostrado una forma de mejorar el rendimiento de las consultas de intervalo mediante una consulta basada en conjuntos, en lugar de tener que usar código de proceso con bucles e iteraciones, que normalmente se ejecuta más despacio en un RDBMS.

Últimas entradas de lmartin (ver todo)