Let relationsr1A BC andr2C D E have the following properties

Let relationsr1(A, B,C) andr2(C, D, E) have the following properties:r1 has20,000tuples,r2 has45,000tuples,25 tuples of r1 t on one block,and 30 tuples of r2 t on one block.Estimate the number of block transfers and seeks required,using each of the following join strategies for r1 join r2:

a. Nested-loop join.

b. Block nested-loop join.

c. Merge join.

d. Hash join.

Solution

A) Nested-loop join:

Use R1 outer relation we need

(20000 1500)+800

= 30000800

Disk accesses

If R2 outer relation we need

(45000800) + 1500

=36001500 disk accesses.

B) Block nested-loop join:

If R1 is outer relation, we need ceiling (800 / (M1)) 1500 + 800 disk accesses

If r2 is outer relation we need ceiling (1500/ (M1)) 800 + 1500 disk accesses.

Note:

If M > 800, the join can easily be done in 1500 + 800 disk accesses, using even plain nested-loop join