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 producir tupla < r , s >
Este algoritmo involucrará 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 se puede generalizar 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 el número de veces que se escanea la relación. Carga grandes porciones 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 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 nido ingenua se puede reemplazar con una unión de índice.
El algoritmo index_join es para cada tupla r en R. Para cada tupla s en S en la búsqueda de índice, produce tupla < r , s > .
La complejidad temporal para esta variación mejora de
