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