Structure choices for two-dimensional histogram construction

ABSTRACT

Histograms of the distributions of individual attributes are currently used in leading database management systems (e.g., IBM DB2, Oracle Database, and Microsoft SQL server). Because attribute pairs in databases are seldom independent, however, the use of the distributions of individual attributes with the attribute independence assumption often leads to poor estimates. More accurate answers can be obtained by using multi-dimensional histograms to characterize the joint distribution of two or more attributes.

When moving from one-dimensional to two-dimensional histograms, several new issues relating to histogram structure arise: (1) Which attribute should take priority over the other with respect to data partitioning?; (2) Into how many partitions should each dimension be split to obtain a desired number of histogram buckets?; and (3) How many most frequent values should be isolated and stored in singleton buckets?

In the context of real data, we experimentally show that our proposed methods for dealing with histogram structure choices lead to good quality histograms for a variety of histogram partitioning techniques and various types of data distributions.

REFERENCES

• 1: Ashraf Aboulnaga , Surajit Chaudhuri, Self-tuning histograms: building histograms without looking at data, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.181-192, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 2: Swarup Acharya , Viswanath Poosala , Sridhar Ramaswamy, Selectivity estimation in spatial databases, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.13-24, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 3: {3} D. Barbara, W. DuMouchel, C. Faloutsos, P.J. Haas, J.M. Hellerstein, Y. Ioannidis, H.V. Jagadish, T. Johnson, R. Ng, V. Poosala, K.A. Ross, K.C. Sevcik. The New Jersey data reduction report. Data Engineering Bulletin, vol. 20, no. 4, pages 3-45, 1997.
• 4: Nicolas Bruno , Surajit Chaudhuri , Luis Gravano, STHoles: a multidimensional workload-aware histogram, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.211-222, May 21-24, 2001, Santa Barbara, California, United States
• 5: {5} Census database repository, U. S. Census Bureau. Available at http://www.census.gov.
• 6: Kaushik Chakrabarti , Minos N. Garofalakis , Rajeev Rastogi , Kyuseok Shim, Approximate Query Processing Using Wavelets, Proceedings of the 26th International Conference on Very Large Data Bases, p.111-122, September 10-14, 2000
• 7: Dimitrios Gunopulos , George Kollios , Vassilis J. Tsotras , Carlotta Domeniconi, Approximating multi-dimensional aggregate range queries over real attributes, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.463-474, May 15-18, 2000, Dallas, Texas, United States
• 8: Yannis E. Ioannidis, Universality of Serial Histograms, Proceedings of the 19th International Conference on Very Large Data Bases, p.256-267, August 24-27, 1993
• 9: Yannis E. Ioannidis , Stavros Christodoulakis, Optimal histograms for limiting worst-case error propagation in the size of join results, ACM Transactions on Database Systems (TODS), v.18 n.4, p.709-748, Dec. 1993 [doi>10.1145/169725.169708]
• 10: Yannis E. Ioannidis , Viswanath Poosala, Balancing histogram optimality and practicality for query result size estimation, Proceedings of the 1995 ACM SIGMOD international conference on Management of data, p.233-244, May 22-25, 1995, San Jose, California, United States
• 11: Yannis E. Ioannidis , Viswanath Poosala, Histogram-Based Approximation of Set-Valued Query-Answers, Proceedings of the 25th International Conference on Very Large Data Bases, p.174-185, September 07-10, 1999
• 12: H. V. Jagadish , Nick Koudas , S. Muthukrishnan , Viswanath Poosala , Kenneth C. Sevcik , Torsten Suel, Optimal Histograms with Quality Guarantees, Proceedings of the 24rd International Conference on Very Large Data Bases, p.275-286, August 24-27, 1998
• 13: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 14: Ju-Hong Lee , Deok-Hwan Kim , Chin-Wan Chung, Multi-dimensional selectivity estimation using compressed histogram information, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.205-214, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 15: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Wavelet-based histograms for selectivity estimation, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.448-459, June 01-04, 1998, Seattle, Washington, United States
• 16: M. Muralikrishna , David J. DeWitt, Equi-depth multidimensional histograms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.28-36, June 01-03, 1988, Chicago, Illinois, United States
• 17: S. Muthukrishnan , Viswanath Poosala , Torsten Suel, On Rectangular Partitionings in Two Dimensions: Algorithms, Complexity, and Applications, Proceeding of the 7th International Conference on Database Theory, p.236-256, January 10-12, 1999
• 18: {18} Hang T. A. Pham. Accurate two-dimensional histograms for fast approximate answers to queries on real data. M.S. thesis. University of Toronto, March 2004. Available at http://www.cs.toronto.edu/~hangp/thesis.html
• 19: Gregory Piatetsky-Shapiro , Charles Connell, Accurate estimation of the number of tuples satisfying a condition, Proceedings of the 1984 ACM SIGMOD international conference on Management of data, June 18-21, 1984, Boston, Massachusetts
• 20: {20} V. Poosala, V. Ganti, Y. Ioannidis. Approximate Query answering using histograms. Bulletin of the IEEE Computer Society Technical Committee on Data Engineering, vol. 22, no. 4, pages 5-14, 1999.
• 21: Viswanath Poosala , Peter J. Haas , Yannis E. Ioannidis , Eugene J. Shekita, Improved histograms for selectivity estimation of range predicates, Proceedings of the 1996 ACM SIGMOD international conference on Management of data, p.294-305, June 04-06, 1996, Montreal, Quebec, Canada
• 22: Viswanath Poosala , Yannis E. Ioannidis, Selectivity Estimation Without the Attribute Value Independence Assumption, Proceedings of the 23rd International Conference on Very Large Data Bases, p.486-495, August 25-29, 1997
• 23: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• 24: {24} UCI KDD database repository. Available at http://kdd.ics.uci.edu.
• 25: Hai Wang , Ken Sevcik, Utilizing histogram information, Proceedings of the 2001 conference of the Centre for Advanced Studies on Collaborative research, p.16, November 05-07, 2001, Toronto, Ontario, Canada
• 26: Hai Wang , Kenneth C. Sevcik, A multi-dimensional histogram for selectivity estimation and fast approximate query answering, Proceedings of the 2003 conference of the Centre for Advanced Studies on Collaborative research, p.328-342, October 06-09, 2003, Toronto, Ontario, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Schema and subschema
      H.2.3 Languages

          Nouns: DB2
      H.2.4 Systems

          Nouns: Microsoft SQL Server

General Terms:
Algorithms, Performance