# Nested loop join

{{ safesubst:#invoke:Unsubst||$N=Unreferenced |date=__DATE__ |$B=
{{#invoke:Message box|ambox}}
}}
Template:Expert-subject
A **nested loop join** is a naive algorithm that joins two sets by using two nested loops. Join operations are important to database management.

## Algorithm

Two relations and are joined as follows:

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 <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, and n_{r} 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.

## Improved version

The algorithm can be improved without requesting additional memory blocks to involve only b_{r}*b_{s}+ b_{r} block transfers. 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 <r,s>

Variable block_r is stored in memory, thus it is not needed to read it from disk for each tuple .