Nested loop join
Encyclopedia
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
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. 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.
, 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
Variable block_r is stored in memory, thus it is not needed to read it from disk for each tuple
.
Algorithm
In mathematics and computer science, an algorithm is an effective method expressed as a finite list of well-defined instructions for calculating a function. Algorithms are used for calculation, data processing, and automated reasoning...
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
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. Can easily be generalized to join any number of relations.The block nested loop
Block nested loop
A block-nested loop is an algorithm used to join two relations in a relational database.This algorithm is a variation on the simple nested loop join used to join two relations R and S...
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 br*bs+ br 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
Variable block_r is stored in memory, thus it is not needed to read it from disk for each tuple
.