Histograms reloaded: the merits of bucket diversity

ABSTRACT

Virtually all histograms store for each bucket the number of distinct values it contains and their average frequency. In this paper, we question this paradigm. We start out by investigating the estimation precision of three commercial database systems which also follow the above paradigm. It turns out that huge errors are quite common. We then introduce new bucket types and investigate their accuracy when building optimal histograms with them. The results are ambiguous. There is no clear winner among the bucket types. At this point, we (1) switch to heterogeneous histograms, where different buckets of the same histogram possibly are of different types, and (2) design more bucket types. The nice consequence of introducing heterogeneous histograms is that we can guarantee decent upper error bounds while at the same time heterogeneous histograms require far less space than homogeneous histograms.

References

1. M. Charikar, S. Chaudhuri, R. Motwani, and V. Narasayya. Towards estimation error guarantees for distinct values. In Proc. ACM SIGMOD/SIGACT Conf. on Princ. of Database Syst. (PODS), pages 268--279, 2000.
2. T. Cormen, C. Leiserson, and R. Rivest. Introduction to Algorithms. MIT Press, 1990.
3. P. Gibbons. Distinct sampling for highly-accurate answers to distinct values queries and event reports. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 541--550, 2001.
4. L. Haas, M. Carey, M. Livny, and A. Shukla. Seeking the truth about ad hoc join costs. The VLDB Journal, 6(3):241--256, 1997.
5. Y. Ioannidis. Universality of serial histograms. In Proc. Int. Conf. on Very Large Data Bases (VLDB), pages 256--267, 1993.
6. Y. Ioannidis and S. Christodoulakis. Optimal histograms for limiting worst-case error propagation in the size of join results. ACM Trans. on Database Systems, 18(4):709--748, 1993.
7. Y. Ioannidis and V. Poosola. Balancing histogram optimality and practicality for query result size estimation. In Proc. of the ACM SIGMOD Conf. on Management of Data, pages 233--244, 1995.
8. Y. Ioannidis and V. Poosola. Histogram-based solutions to diverse database estimation problems. IEEE Data Engineering Bulletin, 18(3):10--18, Sept 1995.
9. R. Kooi. The Optimization of Queries in Relational Databases. PhD thesis, Case Western Reserve University, 1980.
10. G. Moerkotte. Profiles for single attributes. Technical Report TR-2010-003, Department of Mathematics and Computer Science, University of Mannheim, Mannheim, Germany, 2010.
11. G. Moerkotte, T. Neumann, and G. Steidl. Preventing bad plans by bounding the impact of cardinality estimation errors. Proc. Int. Conf. on Very Large Data Bases (VLDB), 2(1):982--993, 2009.
12. B. Piatetsky-Shapiro and C. Connell. Accurate estimation of the number of tuples satisfying a condition. In Proc. of the ACM SIGMOD Conf. on Management of Data, pages 256--276, 1984.
13. V. Poosola, Y. Ioannidis, P. Haas, and E. Shekita. Improved histograms for selectivity estimates of range predicates. In Proc. of the ACM SIGMOD Conf. on Management of Data, pages 294--305, 1996.

Index Terms

• Information systems

  • Data management systems

    • Database management system engines

      • Database query processing

• Mathematics of computing

  • Mathematical analysis

    • Functional analysis

      • Approximation

• Theory of computation

  • Design and analysis of algorithms

    • Approximation algorithms analysis

  • Theory and algorithms for application domains

    • Database theory

      • Database query processing and optimization (theory)