Nested loop join

From formulasearchengine
Jump to navigation Jump to search

{{ 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 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 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 br*bs+ br 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 .

Template:Asbox