Definition
Some database tuning problems can be formulated as combinatorial search, i.e., the problem of searching over a large space of discrete system configurations to find an appropriate configuration. One tuning problem where feasibility of combinatorial search has been demonstrated is physical database design. As part of the self-management capabilities of a database system, it is desirable to develop techniques for automatically recommending an appropriate physical design configuration to optimize database system performance. This entry describes the application of combinatorial search techniques to the problem of physical database design.
Historical Background
Combinatorial search (also referred to as combinatorial optimization) [8] is branch of optimization where the set of feasible solutions (or configurations) to the problem is discrete, and the goal is to find the “best” possible solution. Several well-known problems in computer science such as the Traveling Salesman...
This is a preview of subscription content, log in via an institution to check access.
Access this chapter
Tax calculation will be finalised at checkout
Purchases are for personal use only
Recommended Reading
Bruno N, Chaudhuri S. Automatic physical design tuning: a relaxation based approach. In: Proceedings of the ACM Special Interest Group on Management of Data International Conference on Management of Data; 2005.
Chaudhuri S. An overview of query optimization in relational systems. In: Proceedings of the 17th ACM SIGACT-SIGMOD-SIGART Symposium Principles of Database Systems; 1998.
Chaudhuri S, Narasayya V. An efficient cost driven index selection tool for microsoft SQL server. In: Proceedings of the 23rd International Conference on Very Large Data Bases; 1997.
Chaudhuri S, Narasayya V. AutoAdmin “What-If” index analysis utility. In: Proceedings of the ACM Special Interest Group on Management of Data International Conference on Management of Data; 1998.
Chaudhuri S, Narasayya V. Self-tuning database systems: a decade of progress. In: Proceedings of the 33rd International Conference on Very Large Data Bases; 2007.
Graefe G. The Cascades framework for query optimization. Data Eng Bull. 1995;18(3):19–29.
Haas L, Freytag C, Lohman G, Pirahesh H. Extensible query processing in Starburst. In: Proceedings of the ACM Special Interest Group on Management of Data International Conference on Management of Data; 1989.
Papadimitriou CH, Steiglitz K. Combinatorial optimization: algorithms and complexity. Mineola: Dover; 1998.
Piatetsky-Shapiro G. The optimal selection of secondary indices is NP-complete. ACM SIGMOD Rec. 1983;13(2):72–5.
Author information
Authors and Affiliations
Corresponding author
Editor information
Editors and Affiliations
Section Editor information
Rights and permissions
Copyright information
© 2018 Springer Science+Business Media, LLC, part of Springer Nature
About this entry
Cite this entry
Chaudhuri, S., Narasayya, V., Weikum, G. (2018). Database Tuning Using Combinatorial Search. In: Liu, L., Özsu, M.T. (eds) Encyclopedia of Database Systems. Springer, New York, NY. https://doi.org/10.1007/978-1-4614-8265-9_33
Download citation
DOI: https://doi.org/10.1007/978-1-4614-8265-9_33
Published:
Publisher Name: Springer, New York, NY
Print ISBN: 978-1-4614-8266-6
Online ISBN: 978-1-4614-8265-9
eBook Packages: Computer ScienceReference Module Computer Science and Engineering