QueryProcessing_JOINS

• 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