Debabrata Dash
Neoklis Polyzotis
Abstract
Index tuning, i.e., selecting the indexes appropriate for a workload, is a crucial problem in database system tuning. In this paper, we solve index tuning for large problem instances that are common in practice, e.g., thousands of queries in the workload, thousands of candidate indexes and several hard and soft constraints. Our work is the first to reveal that the index tuning problem has a well structured space of solutions, and this space can be explored efficiently with well known techniques from linear optimization. Experimental results demonstrate that our approach outperforms state-of-the-art commercial and research techniques by a significant margin (up to an order of magnitude).
- S. Agrawal, S. Chaudhuri, L. Kollár, A. P. Marathe, V. R. Narasayya, and M. Syamala. Database tuning advisor for microsoft sql server 2005. In VLDB, pages 930--932, 2008. Google Scholar
Digital Library
- S. Boyd and L. Vandenberghe. Convex Optimization. Cambridge University Press, March 2004. Google ScholarDigital Library
- N. Bruno and S. Chaudhuri. Automatic physical database tuning: a relaxation-based approach. In SIGMOD, pages 227--238, 2005. Google ScholarDigital Library
- N. Bruno and S. Chaudhuri. Constrained physical design tuning. PVLDB, 1(1):4--15, 2008. Google ScholarDigital Library
- N. Bruno and R. V. Nehme. Configuration-parametric query optimization for physical design tuning. In SIGMOD, pages 941--952, 2008. Google ScholarDigital Library
- A. Caprara and J. Salazar. A branch-and-cut algorithm for a generalization of the uncapacitated facility location problem. TOP, 1(4):135--163, 1996.Google ScholarCross Ref
- S. Chaudhuri, M. Datar, and V. Narasayya. Index selection for databases: A hardness study and a principled heuristic solution. IEEE TKDE, 16(11):1313--1323, 2004. Google ScholarDigital Library
- S. Chaudhuri and V. Narayasa. Program for tpc-d data generation with skew. ftp://ftp.research.microsoft.com/users/viveknar/tpcdskew.Google Scholar
- C. Daskalakis, I. Diakonikolas, and M. Yannakakis. How good is the chord algorithm? In SODA, pages 978--991, 2010. Google ScholarDigital Library
- S. J. Finkelstein, M. Schkolnick, and P. Tiberio. Physical database design for relational databases. ACM TODS, 13(1):91--128, 1988. Google ScholarDigital Library
- M. L. Fisher. The lagrangian relaxation method for solving integer programming problems. Manage. Sci., pages 1861--1871, 2004. Google ScholarDigital Library
- V. Y. Lum and H. Ling. An optimization problem on the selection of secondary keys. In Proceedings of the 26th annual conference, pages 349--356, 1971. Google ScholarDigital Library
- S. Papadomanolakis. Large-scale data management for the sciences. PhD thesis, CMU, 2007.Google Scholar
- S. Papadomanolakis and A. Ailamaki. An integer linear programming approach to automated database design. In SMDB, pages 442--449, 2007. Google ScholarDigital Library
- S. Papadomanolakis, D. Dash, and A. Ailamaki. Efficient use of the query optimizer for automated physical design. In VLDB, pages 1093--1104, 2007. Google ScholarDigital Library
- N. Reddy and J. R. Haritsa. Analyzing plan diagrams of database query optimizers. In VLDB, pages 1228--1240, 2007. Google ScholarDigital Library
- K. Schnaitter and N. Polyzotis. A Benchmark for Online Index Selection. In SMDB, pages 1701--1708, 2009. Google ScholarDigital Library
- P. Selinger, M. Astrahan, D. Chamberlin, R. Lorie, and T. Price. Access path selection in a relational database management system. In SIGMOD, pages 23--34, 1979. Google ScholarDigital Library
- Z. A. Talebi, R. Chirkova, Y. Fathi, and M. Stallmann. Exact and inexact methods for selecting views and indexes for olap performance improvement. In EDBT, pages 311--322, 2008. Google ScholarDigital Library
- D. C. Zilio, J. Rao, S. Lightstone, G. M. Lohman, A. Storm, C. Garcia-Arellano, and S. Fadden. Db2 design advisor: Integrated automatic physical database design. In VLDB, pages 1087--1097, 2004. Google ScholarDigital Library
Index Terms
- CoPhy: a scalable, portable, and interactive index advisor for large workloads
Recommendations
The hyperdyadic index and generalized indexing and query with PIQUE
SSDBM '15: Proceedings of the 27th International Conference on Scientific and Statistical Database ManagementMany scientists rely on indexing and query to identify trends and anomalies within extreme-scale scientific data. Compressed bitmap indexing (e.g., FastBit) is the go-to indexing method for many scientific datasets and query workloads. Recently, the ...
Comparison between the zeroth-order Randić index and the sum-connectivity index
The zeroth-order Randić index and the sum-connectivity index are very popular topological indices in mathematical chemistry. These two indices are based on vertex degrees of graphs and attracted a lot of attention in recent years. Recently Li and Li (...
Transform-Space View: Performing Spatial Join in the Transform Space Using Original-Space Indexes
Spatial joins find all pairs of objects that satisfy a given spatial relationship. In spatial joins using indexes, original-space indexes such as the R-tree are widely used. An original-space index is the one that indexes objects as represented in the ...
Comments