Nested loop join
|This article does not cite any sources. (January 2010)|
||This article needs attention from an expert in mathematics. (March 2011)|
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 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 .
|This computer science article is a stub. You can help Wikipedia by expanding it.|