Nested loop join

From Wikipedia, the free encyclopedia

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


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

Index join variation[edit]

If the inner relation has an index on the attributes used in the join, then the naive nest loop join can be replaced with an index join.

algorithm index_join is
    for each tuple r in R do
        for each tuple s in S in the index lookup do
            yield tuple <r,s>

The time complexity for this variation improves from

See also[edit]


  1. ^ "Understanding Nested Loops Joins".
  2. ^[bare URL PDF]