Comparison of join algorithms. Consider two relations rl and r2 with schemas R1(

Question

Comparison of join algorithms. Consider two relations rl and r2 with schemas R1(ABC) and R2(CDE). Suppose we know that ri has 10,000 tuples, r2 has 15,000 tuples, 25 tuples of r fit on one block, and 20 tuples of r2 fit on one block. Assume that there are M-400 pages available in the memory. Estimate the number of block transfers and seeks required, using each of the following join strategies for ri x r2 (show your work): () Nested-loop join (i) Block-nested loop join iii) Merge join (iv) Hash Join.

Explanation / Answer

Given that,
Touples in r1= 10000
Touples in r2= 15000
And also mentioned that, 25 touples of r1 fit in one block, then no.of blocks = 10000/25
= 400
20 touples of r2 fit in one block, then no.of blocks = 15000/20
= 750
But given M=400 which is less than both r1 and r2 blocks.

1) Nested-loop join:
........................
If we are Using r1 as the outer relation, then we need 10000 750 + 400
=7500400 disk accesses
if r2 is the outer relation, then 15000 400 + 750 = 6000750 disk accesses.

2) Block nested-loop join:
.....................................
If r1 is the outer relation, [400/M-1]*750 + 400
= 1151.9 disk accesses
if r2 is the outer relation [750/M-1]*400 + 750
= 1501.8 disk accesses

Merge-join:
...............
As per merge join let us assume r1 and r2 are not sorted on the join key,then the total
sorting cost output is Bs = 750(2log4001(750/400)+ 400(2log4001(400/400) + 2) disk accesses.
Suppose if all tuples with same values, then the total
cost is Bs + 1500 + 800 disk accesses.

. Hash-join:
....................
Because of r1 is smaller,no overflow will occure. we know that M > 400/M,
then, there is no need for recursive partitioning,and cost is 3(750+400) = 3450 disk
accesses.

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.