Bucle anidado en bloques

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. ${\estilo de visualización R}$${\estilo de visualización S}$${\displaystyle |R|<|S|}$${\estilo de visualización S}$${\estilo de visualización R}$${\estilo de visualización R}$${\estilo de visualización 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. ${\estilo de visualización S}$${\estilo de visualización R}$${\estilo de visualización R}$${\estilo de visualización R}$${\estilo de visualización R}$${\estilo de visualización S}$${\estilo de visualización S}$${\estilo de visualización R}$${\estilo de visualización 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 ]}${\estilo de visualización R}$${\estilo de visualización S}$${\estilo de visualización 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. $Estilo de visualización O(P_{r}P_{s}/M)$${\estilo de visualización M}$$Estilo de visualización P_{r}$${\displaystyle P_{s}}$${\estilo de visualización R}$${\estilo de visualización S}$${\displaystyle O(P_{r}+P_{s})}$${\estilo de visualización R}$