Una combinación de bucle anidado es un algoritmo ingenuo que une dos conjuntos mediante el uso de dos bucles anidados . [1] Las operaciones de unión son importantes para la gestión de bases de datos .
Algoritmo
Dos relaciones y se unen de la siguiente manera:
algoritmo nested_loop_join es para cada tupla r en R hacer para cada tupla es en S hacer si r y s satisfacen la condición de unión entonces dió tupla < r , s >
Este algoritmo implicará n r * b s + b r transferencias de bloques y n r + b r busca, 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 bloque [2] es una generalización del algoritmo de bucles anidados simples que aprovecha la memoria adicional para reducir el número de veces que else 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 el número de veces que se escanea S a una vez por fragmento.
Variación de unión de índice
Si la relación interna tiene un índice sobre los atributos usados en la combinación, entonces la combinación de bucle de nido ingenuo se puede reemplazar con una combinación de índice.
algoritmo index_join es para cada tupla r en R do para cada tupla s en S en la búsqueda de índice do produce tupla < r , s >
La complejidad del tiempo para esta variación mejora de O ( M * N ) a O ( M * log N ).