ABSTRACT
The physical design problem introduced in Chapter 3 can be seen as a constrained optimization problem, in which the optimizing function is the overall cost of the workload (counting both queries and updates) and the constraint is the storage bound on the configuration size. In this chapter, we characterize the search space for the physical design problem. Specifically, we explain how to identify a set of indexes for a given workload and storage bound that includes the desired optimal index configuration. We do this in two steps. First, in Section 4.1 we present approaches that address a simpler problem. Specifically, we explain how to obtain a small set of indexes that include the optimal configuration for the case of a single SELECT query and no storage constraint. Then, in Section 4.2 we extend this basic approach to general workloads. We finish this chapter with a formal characterization of the search space for the physical design problem.
