• Sailors (S):(Inner)
–80 tuples per page, 500 pages
–NPages(S) = 500, NTuplesPerPage(S) = 80
–NTuples(S) = 500*80 = 40000
• Reserves (R):(Outer)
–100 tuples per page, 1000 pages
–NPages(R) = 1000, NTuplesPerPage(R) =100
–NTuples(R) = 100000
1. Simple Nested Loops Join
Cost (SNJL) = NPages(Outer) + NTuples(Outer) * NPages(Inner)
Cost (SNLJ)= 1000+ 100*1000*500
= 50001000 (I/O)
2. Page-Oriented Nested Loops Join
Cost (PNJL) = NPages(Outer) + NPages(Outer) * NPages(Inner)
Cost (PNLJ)= 1000+1000*500 = 501000 (I/O)
3. Block Nested Loops Join
Cost (BNJL) = NPages(Outer) + NBlocks(Outer) * NPages(Inner)
NBlocks(Outer) = 𝑁𝑃𝑎𝑔𝑒𝑠(𝑂𝑢𝑡𝑒𝑟) / 𝐵𝑙𝑜𝑐𝑘𝑠𝑖𝑧𝑒−2
we have 102 pages of space in memory
NBlocks(R) = 1000/(102-2) = 10
Cost(BNLJ) = 1000 + 10* 500 = 6000 I/O
4. Sort-Merge Join (R NATURAL JOIN S)
Cost (SMJ) = Sort(Outer) + Sort(Inner) + NPages(Outer) + NPages(Inner)
Sort(R) = External Sort Cost = 2*NumPasses*NPages(R)
Both Reserves and Sailors can be sorted in 2 passes
Cost(SMJ) = Sort R + Sort S + NPages(R) + NPages(S) = 2*2*NPages(R)+ 2*2*NPages(S) + NPages(R) + NPages (S)
= 5*1000 + 5* 500 = 7500 I/O
5. Hash-Join
Cost (HJ) = 2 * NPages(Outer) + 2 * NPages(Inner) + NPages(Outer) + NPages(Inner)
Cost(HJ) = 2*NPages(R) + 2*NPages(S) + NPages(R) + NPages(S)
= 3 * 1000 + 3* 500 = 4500 I/Os
