Nested Loops Join Algorithm Assignment Help

Nested Loops Join (R S):

• foreach tuple r in R do
• foreach tuple s in S do
• if ri == sj then add r s to result
  
  

Algorithm for the nested loop join :

For each tuple in outer relation R, we scan inner relation S.

Cost performance:

• Scan of outer + for each tuple of outer, scan of inner relation.
• Cost = M + pR * M * N
• Cost = 1000 + 100*1000*500 I/Os.
  
  

Tuple-oriented

• For each tuple in outer relation R, we scan inner relation S.
  • Cost: M + p_R * M * N = 1000 + 100*1000*500 I/Os.
    
    

Page-oriented:

For each page of R, get each page of S, and write out matching pairs of tuples r s where r is in R-page and S is in S-page.

Cost :

• Scan of outer pages + for each page of outer, scan of inner relation.
• Cost = M + M * N
• Cost = 1000 + 1000*500 IOs.
• smaller relation (S) is outer, cost = 500 + 500*1000 IOs.