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>
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.
