Block Nested Loops Join Algorithm Assignment Help
Block Nested Loops Join ( R, S):
- One page as input buffer for scanning inner S,
- One page as the output buffer,
- Remaining pages to hold “block’’ of outer R.
- For each matching tuple r in R-block, s in S-page,
- Add, < r, s > to result.
- Then read next R-block, scan S again. etc.
Cost of Block Nested Loops :
- Cost: Scan of outer + #outer blocks * scan of inner
- #outer blocks = [#of pagesof outerlblocksize]
For Example: Assume b(R) = 10.000, b(S) = 2.000, m = 500
- R as outer relation
- IO = 10.000 + 10.000*2.000/500 = 50.000
- S as outer relational
- IO = 2.000 + 2.000*10.000/500 = 42.000
- Compare to one-block NL: 20.002.000 IO
- Use smaller relation as outer relation
- Again, difference irrelevant as tables get larger
- But sizes of relations do matter
- If one relation fits into memory ( b < m )
- Total cost: b(R) + b(S)
- One pass blocked-nested-loop