15.25

Suppose you need to sort relation \(r\) using sort-merge and merge-join the result with an already sorted relation \(s\).

  1. Describe how the sort operator is broken into suboperators to model the pipelining in this case.

  2. The same idea is applicable even if both inputs to the merge join are the outputs of sort-merge operations. However, the available memory has to be shared between the two merge operations (the merge-join algorithm itself needs very little memory). What is the effect of having to share memory on the cost of each sort-merge operation?

  1. Describe how the sort operator is broken into suboperators to model the pipelining in this case.

The sort operator is broken into 2 suboperators. First, the run-generation suboperator. Second, the merge suboperator. The output of the sort-merge suboperator can be pipelined into the merge-join operation.

  1. The same idea is applicable even if both inputs to the merge join are the outputs of sort-merge operations. However, the available memory has to be shared between the two merge operations (the merge-join algorithm itself needs very little memory). What is the effect of having to share memory on the cost of each sort-merge operation?

Since we have to share memory, the amount of blocks that we buffer from a single run \(b_b\) will decrease. As a consequence of this, the number of seeks that we have to perform will increase. Which is bad.