Let relations and have the following properties: has tuples, has tuples, tuples of fit on one block, and tuples of fit on one block. Estimate the number of block transfers and seeks required using each of the following join strategies for :
a. Nested-loop join.
b. Block nested-loop join.
c. Merge join.
d. Hash join.
needs blocks, and needs blocks. Let us assume pages of memory. If , the join can easily be done in disk accesses, using even plain nested-loop join. So we consider only the case where pages.
a. Nested-loop join.
If is the outer relation, we need disk accesses and disk seeks.
If is the outer relation, we need disk accesses and disk seeks.
b. Block nested-loop join.
If is the outer relation, we need disk accesses and disk seeks.
If is the outer relation, we need disk accesses and disk seeks.
c. Merge join.
Assuming that and are not initially sorted on the join key and , the total sorting cost inclusive of the output is
disk accesses. Assuming all tuples with the same value for the join attributes fit in memory, the total cost is disk accesses.
TODO: disk seek
d. Hash join.
We assume no overflow occurs. Since is smaller, we use it as the build relation and as the probe relation. If , i.e., no need for recursive partitioning, then the cost is disk accesses, else the cost is
disk accesses.
TODO: disk seek