Physical Database Design - Automated Physical Database Design and Tuning - page 53

3.2.3 Enumeration Strategy
Early enumeration strategies for the physical design problem relied on either
simplified search spaces (e.g., only single-column indexes) or restricted execu-
tion environments (e.g., OLTP queries with external cost models). For that
reason, several pieces of work considered the problem of obtaining the optimal
physical design for a given workload. Motivated in part by complexity results
in the area (see Section 3.1.3) but also by increasingly sophisticated query
engines and workloads, recent techniques use heuristics to effectively traverse
smaller but relevant portions of the search space. Some proposed alternatives
leverage the fact that the physical design problem is in a way similar to the
knapsack problem (however more general). Thus, they use modified heuristics
for the knapsack problem to traverse the search space. Other techniques use
greedy hill-climbing approaches, where configurations are built bottom-up by
progressively adding high-impact indexes. A different approach starts with
large configurations and progressively removes low-impact indexes, in what
can be seen as a relaxation-based approach. In Chapter 6 we discuss these
alternatives in detail.

3.3 Summary

• The physical design problem is computationally expensive and in general

very complex even for moderate-sized inputs.

•

The physical design problem can be seen as a complex search procedure
that is specified by answering three questions:
- Search space: What is the space of indexes that we consider for a
given workload (Chapter 4)?
- Cost model: How do we estimate the cost of a workload under a
given configuration (Chapter 5)?
- Enumeration strategy: How do we effectively traverse the space of
configurations (Chapter 6)?

3.4 Additional Reading
The NP-completeness proof of Section 3.1.3 is one of several variants that
appear in the literature. 1 , 2 , 10 Several topics analyze the physical design prob-
lem and further discuss rules of thumb for physical database design. 9 , 13
Lahdenmaki and Leach give a very good and systematic approach for man-
ually tuning SQL statements. 8

Chaudhuri and Narasayya give a historical