A nested loop join is a naive algorithm that joins two relations and by making two nested loops:

  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 I/Os, where and is the number of tuples contained in and respectively. 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 relation is scanned.

Improved version

The algorithm can be improved without requesting additional memory blocks to involve only b_r*b_s+ b_r seeks. For each read block from , the relation can be read only once.

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

Variable block_r is stored in memory, thus it is not needed to read it from disk for each tuple .