Characterizing the Search Space - Automated Physical Database Design and Tuning - page 75

• The initial set of candidates is the union of the candidates for each query,

which can be obtained by either syntactically analyzing the query string,
processing the final execution plan or instrumenting the query optimizer.

• The transformations to generate indexes that, while not optimal for any

query, can be part of the optimal configuration are merging and splitting
two indexes and reducing and promoting an index.

4.5 Additional Reading
Earlier work on physical database design assumed single-column indexes, and
thus the resulting search space was invariably of moderate size. 5-7 The main
technical problem in this setting is how to pick feasible indexes for each indi-
vidual query. Then, the combined search space is just the union of candidates
for each query in the workload (since early work considers only single-column
indexes, there is not much else that can be done). More recent work infers a
candidate set of indexes for each query in the workload by relying on inter-
nal query representations, 8 execution plans, 3 and instrumented optimizers. 1
In addition to the candidate set of indexes, some work considers additional
indexes obtained through transformation, such as index merging, 4

splitting,

and reduction transformations. 1 , 2

References
1. Nicolas Bruno and Surajit Chaudhuri. Automatic physical database tun-
ing: A relaxation-based approach. In Proceedings of the ACM Interna-
tional 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.
3. Surajit Chaudhuri and Vivek Narasayya. An ecient cost-driven index
selection tool for Microsoft SQL Server. In Proceedings of the Interna-
tional Conference on Very Large Databases (VLDB) , 1997.
4. Surajit Chaudhuri and Vivek Narasayya. Index merging. In Proceedings
of the International Conference on Data Engineering (ICDE) , 1999.
5. Sheldon J. Finkelstein, Mario Schkolnick, and Paolo Tiberio. Physical
database

design for relational databases. ACM Transactions on

Database Systems , 13(1), 1988.