Chapter 15, Problem 3PE

Explanation of Solution

a.

Nested loop join:

The “r1” needs 800 blocks, and “r2” needs 1500 blocks.

Let assume “M” pages of memory. If “M” is greater than 800, the join can easily be done in 1500 + 800 disk accesses, using even plain nested-loop join.

So we consider only the case where “M” less than or equal to 800 pages.

Using “r1” as the outer relation the user need 20000 * 1500 + 800

$\begin{array}{l}\text{20000 *}\end{array}$

Explanation of Solution

b.

Block nested loop join:

$\begin{array}{l}\text{If, “r2” is the outer relation the user need,}\left[\frac{800}{\text{M - 1}}\right]\text{ * 1500 + 800 disk accesses,}\end{array}$

Explanation of Solution

c.

Merge join:

Let assuming that “r1” and “r2” are not initially sorted on the join key, the total sorting cost inclusive of the output is:

$\begin{array}{c}{\text{B}}_s=\text{ 1500 }\left(\text{2}\left[{\text{log}}_{M-1}\left(\frac{1500}{M}\right)\right]+2\right)+\end{array}$

Explanation of Solution

d.

Hash join:

Let assume no overflow occurs. Since, “r1” is smaller, the user uses it as the build relation and “r2” as the probe relation...