Nicolas Bruno
Abstract
Attributes of a relation are not typically independent. Multidimensional histograms can be an effective tool for accurate multiattribute query selectivity estimation. In this paper, we introduce STHoles, a “workload-aware” histogram that allows bucket nesting to capture data regions with reasonably uniform tuple density. STHoles histograms are built without examining the data sets, but rather by just analyzing query results. Buckets are allocated where needed the most as indicated by the workload, which leads to accurate query selectivity estimations. Our extensive experiments demonstrate that STHoles histograms consistently produce good selectivity estimates across synthetic and real-world data sets and across query workloads, and, in many cases, outperform the best multidimensional histogram techniques that require access to and processing of the full data sets during histogram construction.
- 1 A. Aboulnaga and S. Chaudhuri. Self-tuning histograms: Building histograms without looking at data. In Proceedings of the 1999 ACM International Conference on Management of Data (SIGMOD'99), 1999.]] Google Scholar
Digital Library
- 2 C. Blake and C. Merz. UCI repository of machine learning databases, 1998.]]Google Scholar
- 3 N. Bruno, S. Chaudhuri, and L. Gravano. STHoles: A multidimensional workload-aware histogram. Technical Report MSR-TR-2001-36, Microsoft Research, 2001. Accessible at ftp://ftp.research.microsoft.com/pub/- tr/tr-2001-36.pdf.]]Google ScholarDigital Library
- 4 C.-M. Chen and N. Roussopoulos. Adaptive selectivity estimation using query feedback. In Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, 1994.]] Google ScholarDigital Library
- 5 D. Donjerkovic, Y. Ioannidis, and R. Ramakrishnan. Dynamic histograms: Capturing evolving data sets. In Proceedings of the 16th International Conference on Data Engineering, 2000.]] Google ScholarDigital Library
- 6 P. B. Gibbons, Y. Matias, and V. Poosala. Fast incremental maintenance of approximate histograms. In VLDB'97, Proceedings of 23rd International Conference on Very Large Data Bases, 1997.]] Google ScholarDigital Library
- 7 D. Gunopulos, G. Kollios, V. J. Tsotras, and C. Domeniconi. Approximating multi-dimensional aggregate range queries over real attributes. In Proceedings of the 2000 ACM International Conference on Management of Data (SIGMOD'00), 2000.]] Google ScholarDigital Library
- 8 Y. Ioannidis. Query optimization. In Handbook for Computer Science. CRC Press, 1997.]]Google Scholar
- 9 Y. E. Ioannidis and V. Poosala. Balancing histogram optimality and practicality for query result size estimation. In Proceedings of the 1995 ACM International Conference on Management of Data (SIGMOD'95), 1995.]] Google ScholarDigital Library
- 10 Y. E. Ioannidis and V. Poosala. Histogram-based approximation of set-valued query-answers. In VLDB'99, Proceedings of 25th International Conference onVery Large Data Bases, September 7-10, 1999, Edinburgh, Scotland, UK, 1999.]] Google ScholarDigital Library
- 11 H. V. Jagadish, N. Koudas, S. Muthukrishnan, V.Poosala, K. C. Sevcik, and T. Suel. Optimal histograms with quality guarantees. In Proceedings of the Twenty-fourth International Conference onVery Large Databases (VLDB'98), 1998.]] Google ScholarDigital Library
- 12 J.-H. Lee, D.-H. Kim, and C.-W. Chung. Multi-dimensional selectivity estimation using compressed histogram information. InProceedings of the 1999 ACM International Conference on Management of Data (SIGMOD'99), 1999.]] Google ScholarDigital Library
- 13 Y. Matias, J. S. Vitter, and M. Wang. Wavelet-based histograms for selectivity estimation. In Proceedings of the 1998 ACM International Conference on Management of Data (SIGMOD'98), 1998.]] Google ScholarDigital Library
- 14 M. Muralikrishna and D. J. DeWitt. Equi-depth histograms for estimating selectivity factors for multi-dimensional queries. In Proceedings of the 1988 ACM International Conference on Management of Data (SIGMOD'88), 1988.]] Google ScholarDigital Library
- 15 M. Muralikrishna and D. J. DeWitt. Equi-depth histograms for estimating selectivity factors for multidimensional queries. In Proceedings of the 1988 ACM International Conference on Management of Data (SIGMOD'88), 1988.]] Google ScholarDigital Library
- 16 S. Muthukrishnan, V.Poosala, and T. Suel. On rectangular partitionings in two dimensions: Algorithms, complexity, and applications. In Database Theory - ICDT '99, 7th International Conference, 1999.]] Google ScholarDigital Library
- 17 F. Olken and D. Rotem. Random sampling from database holes: A survey. InStatistical and Scientific Database Management, 5th International Conference SSDBM, 1990.]] Google ScholarDigital Library
- 18 B.-U. Pagel, H.-W. Six, H. Toben, and P. Widmayer. Towards an analysis of range query performance in spatial data structures. In Proceedings of the Twelfth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, 1993.]] Google ScholarDigital Library
- 19 G. Piatetsky-Shapiro and C. Connell. Accurate estimation of the number of tuples satisfying a condition. In Proceedings of the 1984 ACM International Conference on Management of Data (SIGMOD'84), 1984.]] Google ScholarDigital Library
- 20 V. Poosala and V. Ganti. Fast approximate answers to aggregate queries on a data cube. In 11th International Conference on Scientific and Statistical Database Management, Proceedings, Cleveland, Ohio, USA, 28-30 July, 1999, 1999.]] Google ScholarDigital Library
- 21 V. Poosala and Y. E. Ioannidis. Selectivity estimation without the attribute value independence assumption. In Proceedings of the Twenty-third International Conference on Very Large Databases (VLDB'97), 1997.]] Google ScholarDigital Library
- 22 V. Poosala, Y. E. Ioannidis, P. J. Haas, and E. J. Shekita. Improved histograms for selectivity estimation of range predicates. In Proceedings of the 1996 ACM International Conference on Management of Data (SIGMOD'96), June 1996.]] Google ScholarDigital Library
- 23 S. A. William, H. Press, B. P. Flannery, and W. T. Vetterling. Numerical recipes in C: The art of scientific computing. Cambridge University Press, 1993.]] Google ScholarDigital Library
Index Terms
- STHoles: a multidimensional workload-aware histogram
Recommendations
STHoles: a multidimensional workload-aware histogram
SIGMOD '01: Proceedings of the 2001 ACM SIGMOD international conference on Management of dataAttributes of a relation are not typically independent. Multidimensional histograms can be an effective tool for accurate multiattribute query selectivity estimation. In this paper, we introduce STHoles, a “workload-aware” histogram that allows bucket ...
Equivalence and minimization of conjunctive queries under combined semantics
ICDT '12: Proceedings of the 15th International Conference on Database TheoryThe problems of query containment, equivalence, and minimization are fundamental problems in the context of query processing and optimization. In their classic work [2] published in 1977, Chandra and Merlin solved the three problems for the language of ...
Scalable and efficient processing of top-k multiple-type integrated queries
AbstractIn this paper, we define a new class of queries, the top-k multiple-type integrated query (simply, top-k MULTI query). It deals with multiple data types and finds the information in the order of relevance between the query and the object. Various ...
Comments