??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
