Nested loop join

From Wikipedia, the free encyclopedia

The naive algorithm that joins two relations R and S by making two nested loops:

  For each tuple in R as r do
     For each tuple in S as 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.

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

[edit] External links