Digital Symposium Collection 2000

Self-tuning Histograms: Building Histograms Without Looking at Data Ashraf Aboulnaga and Surajit Chaudhuri   View Paper (PDF)   Return to Histograms Abstract In this paper, we introduce self-tuning histograms. Although similar in structure to traditional histograms, these histograms infer data distributions not by examining the data or a sample thereof, but by using feedback from the query execution engine about the actual selectivity of range selection operators to progressively refine the histogram. Since the cost of building and maintaining self-tuning histograms is independent of the data size, self-tuning histograms provide a remarkably inexpensive way to construct histograms for large data sets with little up-front costs. Self-tuning histograms are particularly attractive as an alternative to multi-dimensional traditional histograms that capture dependencies between attributes but are prohibitively expensive to build and maintain. In this paper, we describe the techniques for initializing and refining self-tuning histograms. Our experimental results show that self-tuning histograms provide a low-cost alternative to traditional multi-dimensional histograms with little loss of accuracy for data distributions with low to moderate skew. References Note: References link to DBLP on the Web. [CR94] Chungmin Melvin Chen , Nick Roussopoulos : Adaptive Selectivity Estimation Using Query Feedback. SIGMOD Conference 1994 : 161-172 [GMP97] Phillip B. Gibbons , Yossi Matias , Viswanath Poosala : Fast Incremental Maintenance of Approximate Histograms. VLDB 1997 : 466-475 [KD98] Navin Kabra , David J. DeWitt : Efficient Mid-Query Re-Optimization of Sub-Optimal Query Execution Plans. SIGMOD Conference 1998 : 106-117 [Koo80] Robert Kooi : The Optimization of Queries in Relational Databases. Ph.D. thesis, Case Western Reserve University 1980 [LNS90] Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider : Practical Selectivity Estimation through Adaptive Sampling. SIGMOD Conference 1990 : 1-11 [MD88] M. Muralikrishna , David J. DeWitt : Equi-Depth Histograms For Estimating Selectivity Factors For Multi-Dimensional Queries. SIGMOD Conference 1988 : 28-36 [MRL98] Gurmeet Singh Manku , Sridhar Rajagopalan , Bruce G. Lindsay : Approximate Medians and other Quantiles in One Pass and with Limited Memory. SIGMOD Conference 1998 : 426-435 [MVW98] Yossi Matias , Jeffrey Scott Vitter , Min Wang : Wavelet-Based Histograms for Selectivity Estimation. SIGMOD Conference 1998 : 448-459 [NHS84] Jürg Nievergelt , Hans Hinterberger , Kenneth C. Sevcik : The Grid File: An Adaptable, Symmetric Multikey File Structure. TODS 9(1) : 38-71(1984) [PIHS96] Viswanath Poosala , Yannis E. Ioannidis , Peter J. Haas , Eugene J. Shekita : Improved Histograms for Selectivity Estimation of Range Predicates. SIGMOD Conf. 1996 : 294-305 [PI97] Viswanath Poosala , Yannis E. Ioannidis : Selectivity Estimation Without the Attribute Value Independence Assumption. VLDB 1997 : 486-495 [Zip49] George Kingsley Zipf: Human Behaviour and the Principle of Least Effort: an Introduction to Human Ecology. Addison-Wesley 1949 BIBTEX @inproceedings{DBLP:conf/sigmod/AboulnagaC99,   author    = {Ashraf Aboulnaga and                 Surajit Chaudhuri},    editor    = {Alex Delis and                 Christos Faloutsos and                 Shahram Ghandeharizadeh},    title     = {Self-tuning Histograms: Building Histograms Without Looking at                 Data},    booktitle = {SIGMOD 1999, Proceedings ACM SIGMOD International Conference                 on Management of Data, June 1-3, 1999, Philadephia, Pennsylvania,                 USA},    publisher = {ACM Press},    year      = {1999},    isbn      = {1-58113-084-8},    pages     = {181-192},    crossref  = {DBLP:conf/sigmod/99},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, Copyright(C) 2000 ACM