Enumerating the Search Space - Automated Physical Database Design and Tuning - page 115

• Heuristic enumeration strategies typically follow bottom-up ap-

proaches (which start with an empty configuration and add indexes
incrementally) or top-down approaches (which start with an optimal
configuration that is too large and keep relaxing it into smaller and less
ecient ones).
- Bottom-up approaches include the greedy(m,B) approach (which
performs an exhaustive search of a subspace followed by a hill-
climbing greedy heuristic), the knapsack-based approach (which
models the physical design problem as an instance of the 0-1 knap-
sack problem), and the integer-programming approach (which uses
known techniques in combinatorial optimization to find solutions
for small problem instances).
- Top-down approaches interleave enumeration and generation of de-
rived indexes (via merging, reduction, and other operators), can ex-
ploit certain properties of derived indexes to speed up reoptimiza-
tion, and can result in better quality configurations than bottom-up
approaches when the storage constraint is not too tight.

6.4 Additional Reading
The greedy(m,B) technique 5 was first introduced in a slightly different context
(specifically, the algorithm is called greedy(m,k) and performs an exhaustive
enumeration of up to m indexes followed by a greedy choice of k

−

m ad-
ditional indexes). Subsequent work describes a knapsack-based approach to
the physical design problem, 8 improvements to calculate index benefits by us-
ing linear programming, 4 and an integer programming approach. 6 All these
techniques are concerned about the effect of index interactions, a topic that
is discussed in recent work 7 based on the concept of index benefit graphs .A
different approach to enumerate the search space uses relaxation of indexes 1
via transformations to the current configuration. 2 , 3

References
1. Nicolas Bruno and Surajit Chaudhuri. Automatic physical database
tuning: A relaxation-based approach. In Proceedings of the ACM Inter-
national Conference on Management of Data (SIGMOD) , 2005.
2. Nicolas Bruno and Surajit Chaudhuri. Physical design refinement: The
“Merge-Reduce” approach. In Proceedings of the International Confer-
ence on Extending Database Technology (EDBT) , 2006.