Bucle anidado en bloque

Este algoritmo ^[2] es una variación de la unión de bucle anidado simple utilizada para unir dos relaciones y (los operandos de unión "exterior" e "interior", respectivamente). Supongamos . En una combinació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}$ ${\ estilo de visualización | 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 combinación de bucles anidados en bloques mejora la combinación de bucles anidados simples al escanear solo una vez cada grupo de tuplas. Por ejemplo, una variante de la combinación de bucle anidado en bloque 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 el número de escaneos que son necesarios. ${\ estilo de visualización S}$ ${\ 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}$

Una variante más agresiva de este algoritmo carga tantas páginas como caben 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 necesarios. De hecho, este algoritmo es esencialmente un caso especial del clásico algoritmo hash join . ^[^{cita requerida}^] ${\ estilo de visualización R}$ ${\ estilo de visualización S}$ ${\ estilo de visualización S}$

El bucle anidado del bloque se ejecuta en E/S donde es el número de páginas disponibles de memoria interna y y es el tamaño de y respectivamente en páginas. Tenga en cuenta que el bucle anidado del bloque se ejecuta en las E/S si cabe en la memoria interna disponible. $O(P_{r}P_{s}/M)$ ${\ estilo de visualización M}$ $P_{r}$ $P_{s}$ ${\ estilo de visualización R}$ ${\ estilo de visualización S}$ $O(P_{r}+P_{s})$ ${\ estilo de visualización R}$