Nested loop join

Algorithm

Two relations R and S are joined as follows:

For each tuple r in R do For each tuple s in S do If r and s satisfy the join condition Then output the tuple <r,s>

This algorithm will involve n_r*b_s+ b_r block transfers and n_r+b_r seeks, where b_r and b_s are number of blocks in relations R and S respectively, and n_r is the number of tuples in relation R.

The algorithm runs in O ( | R | | S | ) I/Os, where | R | and | S | is the number of tuples contained in R and 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 relation is scanned.