
Physical Database Design 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 ...