The algorithm in figure 9.7 controls the |Rk| and
|Qk| by guaranteeing that they do not exceed the limit X for all
. However, when discussing the performance model of
chapter 8, we were mainly concerned with the numbers
|R'k| and |Q'k| as we wanted them to
fit into the local main memory of a processor if possible. But this
can be easily achieved by keeping all |R'k| below a limit
XR and all |Q'k| below a limit XQ
whereby the limits can be determined by
With XR and XQ being determined, the algorithm of
figure 9.7 can be adapted to guarantee that and for all . It is shown in
figure 9.9.
Many more variations of that type can be designed. For example, one could try the limit products, such as , etc., by a certain maximum X. These products are part of the most expensive cost components in the performance model of chapter 8. However, there is no clear indication of how to choose an adequate limiting value for X in that case. This makes such partitioning strategies difficult to handle. Presumably, X would be determined by performance experiments on an existing DBMS installation. Consequently, its value would depend on rather installation-specific characteristics. We therefore do not expand on this issue any further.
The advantage of the underflow strategies is that the fragments' loads are well controlled and can be expected to be well balanced as long as the values are relatively small in order to approach the limit X as close as possible (see if-conditions in figures 9.7 and 9.9). There is, however, no control over the number of intervals overlapping the breakpoints. In sections 9.3 and 9.4, we present two techniques that can be considered as enhancements of the underflow strategies that have been presented so far.