A nested loop join is a naive algorithm that joins two relations by using two nested loops.
[1] Join operations are important for database management.
are joined as follows: 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
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
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.
The time complexity for this variation improves from
This computer science article is a stub.