Nested loop join

A nested loop join is a naive algorithm that joins two sets by using two nested loops. Join operations are important for database management. A nested loop join is a naive algorithm that joins two sets by using two nested loops. Join operations are important for database management. Two relations R {displaystyle R} and S {displaystyle S} are joined as follows: This algorithm will involve nr*bs+ br block transfers and nr+br seeks, where br and bs are number of blocks in relations R and S respectively, and nr is the number of tuples in relation R. The algorithm runs in O ( | R | | S | ) {displaystyle O(|R||S|)} I/Os, where | R | {displaystyle |R|} and | S | {displaystyle |S|} is the number of tuples contained in R {displaystyle R} and S {displaystyle S} respectively and can easily be generalized to join any number of relations. The block nested loop join algorithm is a generalization of the simple nested loops algorithm that takes advantage of additional memory to reduce the number of times that the S {displaystyle S} relation is scanned.