Nested loop join

Two relations ${\displaystyle R}$ and ${\displaystyle S}$ are joined as follows:

algorithm nested_loop_join is
    for each tuple r in R do
        for each tuple s in S do
            if r and s satisfy the join condition then
                yield 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 ${\displaystyle O(|R||S|)}$ I/Os, where ${\displaystyle |R|}$ and ${\displaystyle |S|}$ is the number of tuples contained in ${\displaystyle R}$ and ${\displaystyle S}$ respectively and can easily be generalized to join any number of relations ...

The block nested loop join algorithm^[2] is a generalization of the simple nested loops algorithm that takes advantage of additional memory to reduce the number of times that the ${\displaystyle S}$ relation is scanned. It loads large chunks of relation R into main memory. For each chunk, it scans S and evaluates the join condition on all tuple pairs, currently in memory. This reduces the number of times S is scanned to once per chunk.