Nested loop join
This article does not cite any sources. (February 2018) (Learn how and when to remove this template message)
This article needs attention from an expert in mathematics.March 2011)(
Two relations and 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 I/Os, where and is the number of tuples contained in and respectively and can easily be generalized to join any number of relations ...
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).
|This computer science article is a stub. You can help Wikipedia by expanding it.|