Indexed Nested Loop Join Algorithm Assignment Help
- For every tuple tR within the outer relation R, make use of the index to look up tuples within S which fulfill the join condition along with tuple tR.
- Worst case: buffer has space with regard to just only one page of R, as well as, for every tuple in R, we perform an index lookup on s.
- Cost of the join: br + nr * c
- Where c is the cost of traversing the index and fetching all matching s tuples for one tuple from r
- c can be estimated as cost of a single selection on s using the join condition.
- If indices can be found upon join attributes associated with both R and S, make use the relation with fewer tuples as the outer relation.
Example of Nested-Loop Join Costs: