15.20

Estimate the number of block transfers and seeks required by your solution to Exercise 15.19 for \(r_1 \bowtie r_2\), where \(r_1\) and \(r_2\) are as defined in Exercise 15.3.

---

Assume the relations \(r_1\) and \(r_2\) have a secondary B+-tree index. Assume also, the leaf nodes of their indices is stored consecutively on the hard disk. Let the number of leaf nodes in the index of relation \(r_1\) be \(l_1\). Similarly let the number of leaf nodes in the index of relation \(r_2\) be \(l_2\).

Thus merge-joining the leaf nodes of the indices will cost us \(l_1 + l_2 + x\) block transfers, where \(x\) is the number of output blocks. Assuming that \(b_b\) buffer blocks are allocated to each series of leaf nodes and for the output relation, the number of disk seeks required would be \(\lceil l_1 / b_b \rceil + \lceil l_2 / b_b \rceil + \lceil x / b_b \rceil\).

Then since we need to sort the output on the pointers of \(r_1\) we will perform \(x (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x / M) \rceil + 2)\) block transfers and \(2 \lceil x / M \rceil + \lceil x / b_b \rceil (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x / M) \rceil - 1)\) disk seeks. Let \(x_2\) be the number of blocks of the resulting relation. Then since we also need to re-sort the output on the pointers of \(r_2\), we will perform \(x_2 (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x_2 / M) \rceil + 2)\) block transfers and \(2 \lceil x_2 / M \rceil + \lceil x_2 / b_b \rceil (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x_2 / M) \rceil - 1)\) disk seeks.

Thus the total number of block transfers will be:

\[ l_1 + l_2 + x + x (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x / M) \rceil + 2) + x_2 (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x_2 / M) \rceil + 2) + (z_1 + z_2) \]

where \(z_i\) is the number of blocks that we have to fetch when dereferencing the pointers of \(r_i\) (for \(i = 1, 2\)).

And the total number of seeks will be:

\[ \lceil l_1 / b_b \rceil + \lceil l_2 / b_b \rceil + \lceil x / b_b \rceil + (2 \lceil x / M \rceil + \lceil x / b_b \rceil (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x / M) \rceil - 1)) + (2 \lceil x_2 / M \rceil + \lceil x_2 / b_b \rceil (2 \lceil \log_{\lfloor M/b_b \rfloor - 1}(x_2 / M) \rceil - 1)) + 2 \]