Assume two relations R(a,b) and S(a,c) stored in 150000 and 90000 pages, respect
ID: 3912672 • Letter: A
Question
Assume two relations R(a,b) and S(a,c) stored in 150000 and 90000 pages, respectively. No index
is created for these two relations.
(a)
Assume there are 400 buffer pages available. We want to have the output of join of R and S
sorted according to the attribute a.What join algorithm should we use to have the minimum cost?
What is the cost of this algorithm?
(b)
Assume that there are 50 buffer pages available. What is the fastest join algorithm to produce
the join of R and S? What is the cost of this algorithm?
(c)
Assume that there are 310 buffer pages available. What is the fastest join algorithm to produce
the join of R and S? What is the cost of this algorithm?
Explanation / Answer
R(a,b) stored in 150000 pages
S(a,b) stored in 90000 pages
a) 400 buffer pages are availabe
Simple Nested Loops:
Relation S is used as the outer loop.
Total Cost = 90000 + (90000×150000) = 13500090000.
Block Nested Loops:
If R is used as the outer relation => Total Cost = 150000 + (90000×ceil(150000/(400-2))) = 34080000
If S is used as the outer relation => Total Cost = 90000 + (150000×ceil(90000/(400-2))) = 34140000
Sort-Merge:
Sorting relation R => 2 * 150000 *(ceil(log400-1(150000/400))+1) = 600000
Sorting relation S => 2 * 90000 *(ceil(log400-1(90000/400))+1) = 360000
Merge: 150000+90000 = 240000
Total Cost = 600000 + 360000 + 240000 = 1200000
Sort-Merge join is cost efficient.
b) 50 buffer pages
Simple Nested Loops:
Relation S is used as the outer loop.
Total Cost = 90000 + (90000×150000) = 13500090000.
Block Nested Loops:
If R is used as the outer relation => Total Cost = 150000 + (90000×ceil(150000/(50-2))) = 281265000
If S is used as the outer relation => Total Cost = 90000 + (150000×ceil(90000/(50-2))) = 281340000
Sort-Merge:
Sorting relation R => 2 * 150000 *(ceil(log50-1(150000/50))+1) = 900000
Sorting relation S => 2 * 90000 *(ceil(log50-1(90000/50))+1) = 540000
Merge: 150000+90000 = 240000
Total Cost = 900000 + 540000 + 240000 = 1680000
Sort-Merge join is cost efficient.
c) 310 buffer pages
Simple Nested Loops:
Relation S is used as the outer loop.
Total Cost = 90000 + (90000×150000) = 13500090000.
Block Nested Loops:
If R is used as the outer relation => Total Cost = 150000 + (90000×ceil(150000/(310-2))) = 43980000
If S is used as the outer relation => Total Cost = 90000 + (150000×ceil(90000/(310-2))) = 44040000
Sort-Merge:
Sorting relation R => 2 * 150000 *(ceil(log310-1(150000/310))+1) = 600000
Sorting relation S => 2 * 90000 *(ceil(log310-1(90000/310))+1) = 360000
Merge: 150000+90000 = 240000
Total Cost = 600000 + 360000 + 240000 = 1200000
Sort-Merge join is cost efficient.