# Nested loop join

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

## Algorithm

Two relations $R$ and $S$ are joined as follows:

```algorithm nested_loop_join is
for each tuple r in R do
for each tuple s in S do
if r and s satisfy the join condition then
yield tuple <r,s>
```

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 $O(|R||S|)$ I/Os, where $|R|$ and $|S|$ is the number of tuples contained in $R$ and $S$ respectively and 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.

## Index join variation

If the inner relation has an index on the attributes used in the join, then the naive nest loop join can be replaced with an index join.

```algorithm index_join is
for each tuple r in R do
for each tuple s in S in the index lookup do
yield tuple <r,s>
```

The time complexity for this variation improves from O(M * N) to O(M * log N).