Nested loop join

A nested loop join is a naive algorithm that joins two sets by using two nested loops.^[1] Join operations are important to database management.

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.

References

^ https://technet.microsoft.com/en-us/library/ms191318(v=sql.105).aspx