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$$