Nested loop join

A nested loop join is a naive algorithm that joins two sets by using two nested loops. Join operations are important to database management.

Two relations ${\displaystyle R}$ and ${\displaystyle S}$ are joined as follows:

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 ${\displaystyle O(|R||S|)}$ I/Os, where ${\displaystyle |R|}$ and ${\displaystyle |S|}$ is the number of tuples contained in ${\displaystyle R}$ and ${\displaystyle S}$ respectively and can easily be generalized to join any number of relations.

...
Wikipedia