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 formula_1 and formula_2 are joined as follows: This algorithm will involve n*b+ b block transfers and n+b seeks, where b and b are number of blocks in relations R and S respectively, and n is the number of tuples in relation R. The algorithm runs in formula_3 I/Os, where formula_4 and formula_5 is the number of tuples contained in formula_1 and formula_2 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 formula_2 relation is scanned. 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. 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. The time complexity for this variation improves from O("M" * "N") to O("M" * log "N").