Una unión de bucle anidado es un algoritmo ingenuo que une dos relaciones mediante el uso de dos bucles anidados . [1] Las operaciones de unión son importantes para la gestión de bases de datos .
Dos relaciones y se unen de la siguiente manera:
algoritmo nested_loop_join es para cada tupla r en R hacer para cada tupla s en S hacer si r y s satisfacen la condición de unión entonces produce tupla < r , s >
Este algoritmo implicará n r * b s + b r transferencias de bloques y n r + b r búsquedas, donde b r y b s son el número de bloques en las relaciones R y S respectivamente, y n r es el número de tuplas en la relación R.
El algoritmo se ejecuta en E/S, donde y es el número de tuplas contenidas en y respectivamente y puede generalizarse fácilmente para unir cualquier número de relaciones...
El algoritmo de unión de bucles anidados en bloques [2] es una generalización del algoritmo de bucles anidados simples que aprovecha la memoria adicional para reducir la cantidad de veces que se escanea la relación. Carga grandes fragmentos de la relación R en la memoria principal. Para cada fragmento, escanea S y evalúa la condición de unión en todos los pares de tuplas que se encuentran actualmente en la memoria. Esto reduce la cantidad de veces que se escanea S a una vez por fragmento.
Si la relación interna tiene un índice en los atributos utilizados en la unión, entonces la unión de bucle anidado ingenuo se puede reemplazar con una unión de índice.
El algoritmo index_join es para cada tupla r en R hacer para cada tupla s en S en la búsqueda de índice hacer rendimiento tupla < r , s >
La complejidad temporal para esta variación mejora a partir de
