Bucle anidado en bloques

Algoritmo

Un bucle anidado en bloques ( BNL ) es un algoritmo utilizado para unir dos relaciones en una base de datos relacional . ^[1]

Este algoritmo ^[2] es una variación de la unión de bucle anidado simple y une dos relaciones y (los operandos de unión "externo" e "interno", respectivamente). Supongamos que . En una unión de bucle anidado tradicional, se escaneará una vez por cada tupla de . Si hay muchas tuplas calificadas, y particularmente si no hay un índice aplicable para la clave de unión en , esta operación será muy costosa. ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle |R|<|S|}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$

El algoritmo de unión de bucle anidado en bloques mejora la unión de bucle anidado simple al escanear solo una vez por cada grupo de tuplas. Aquí los grupos son conjuntos disjuntos de tuplas en y la unión de todos los grupos tiene las mismas tuplas que . Por ejemplo, una variante de la unión de bucle anidado en bloques lee una página completa de tuplas en la memoria y las carga en una tabla hash . Luego escanea , y sondea la tabla hash para encontrar tuplas que coincidan con cualquiera de las tuplas en la página actual de . Esto reduce la cantidad de escaneos de que son necesarios. ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$ ${\displaystyle R}$ ${\displaystyle S}$

El algoritmo block_nested_loop_join es  para cada página pr en R  hacer  para cada página ps en S  hacer  para cada tupla r en pr  hacer  para cada tupla s en ps  hacer  si  r y s satisfacen la condición de unión entonces  produce tupla < r , s >

Una variante más agresiva de este algoritmo carga tantas páginas de como quepan en la memoria disponible, carga todas esas tuplas en una tabla hash y luego escanea repetidamente . Esto reduce aún más la cantidad de escaneos de que son necesarios. De hecho, este algoritmo es esencialmente un caso especial del algoritmo de unión hash clásico . ^{[ cita requerida ]} ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle S}$

El bucle anidado en bloques se ejecuta en E/S, donde es la cantidad de páginas disponibles de la memoria interna y y es el tamaño de y en páginas, respectivamente. Tenga en cuenta que el bucle anidado en bloques se ejecuta en E/S si cabe en la memoria interna disponible. ${\displaystyle O(P_{r}P_{s}/M)}$ ${\displaystyle M}$ ${\displaystyle P_{r}}$ ${\displaystyle P_{s}}$ ${\displaystyle R}$ ${\displaystyle S}$ ${\displaystyle O(P_{r}+P_{s})}$ ${\displaystyle R}$

Referencias

1. "8.2.1.14 Uniones de acceso a claves por lotes y bucles anidados en bloques". Manual de referencia de MySQL 5.6 . Oracle Corporation . Consultado el 2 de agosto de 2015 .
2. "Unión de bucles anidados en bloques". MariaDB . MariaDB Corporation Ab . Consultado el 2 de agosto de 2015 .