A new histogram method for sparse attributes: the averaged rectangular attribute cardinality map

ABSTRACT

Most current Database Management Systems (DBMS) use histograms in their query optimization, and in approximating query result sizes. This is because they can be utilized in determining efficient query evaluation plans. All the existing methods perform poorly when the attributes of a relation are very sparsely distributed, also called the "sparse data cases". These cases are the worst-cases scenarios for attributes with skewed distributions. In this paper, we propose a novel histogram-based algorithm, namely the Averaged Rectangular Attribute Cardinality Map (Averaged R-ACM), and demonstrate its performance in estimating query result sizes for the sparse data cases. Our proposed algorithm combines the advantages of the traditional widely-used histogram-based algorithm, namely the Equi-width histogram, and a relatively new algorithm, namely the R-ACM² introduced in [Thi99]. The goals of compacting the sparse data distribution and of obtaining accurate estimates of query result sizes are achieved by utilizing this algorithm. The superiority of this algorithm is also validated by an extensive set of experiments. And the entire set of experimental results obtained by integrating the underlying algorithm and other histogram-based algorithms into the ORACLE query optimizer can be found in [Che03].

REFERENCES

• 1: {Che03} J. Chen, On Utilizing New Histogram-Based Methods for Query Optimization, MCs. Thesis, School of Computer Science, Carleton Univ., Ottawa, Canada, February 2003.
• 2: Peter J. Haas , Arun N. Swami, Sequential sampling procedures for query size estimation, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.341-350, June 02-05, 1992, San Diego, California, United States
• 3: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Lynne Stokes, Sampling-Based Estimation of the Number of Distinct Values of an Attribute, Proceedings of the 21th International Conference on Very Large Data Bases, p.311-322, September 11-15, 1995
• 4: {Ioa95} Yannis Ioannidis, "Histogram-Based Solutions to Diverse Databas Estimation Problems", In IEEE Computer Society, Vol. 8 No. 3, Sep 1995, pp. 10--18.
• 5: Yannis E. Ioannidis , Stavros Christodoulakis, On the propagation of errors in the size of join results, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.268-277, May 29-31, 1991, Denver, Colorado, United States
• 6: 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
• 7: 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
• 8: Michael V. Mannino , Paicheng Chu , Thomas Sager, Statistical profile estimation in database systems, ACM Computing Surveys (CSUR), v.20 n.3, p.191-221, Sept. 1988 [doi>10.1145/62061.62063]
• 9: R. J. Miller , Y. Yang, Association rules over interval data, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.452-461, May 11-15, 1997, Tucson, Arizona, United States
• 10: {Thi99} Murali Thiyagarajah, "Attribute Cardinality Maps: New Query Result Size Estimation Techniques for Database Systems", Ph.D. Thesis, School of Computer Science, Carleton Univ., Ottawa, Canada, May 1999.
• 11: {OoR02} B. J. Oommen and L. G. Rueda, "The Efficiency of Histogram-like Techniques for Database Query Optimization", In The Computer Journal, Vol. 45, No. 5, 2002, pp. 494--510.
• 12: B. John Oommen , Murali Thiyagarajah, Query Result Size Estimation Using a Novel Histogram-like Technique: The Rectangular Attribute Cardinality Map, Proceedings of the 1999 International Symposium on Database Engineering & Applications, p.3, August 02-04, 1999
• 13: {OoT01} B. J. Oommen, and M. Thiyagarajah, "Benchmarking Attribute Cardinality Maps for Database Systems Using the TPC-D Specifications", To appear in the IEEE Transactions on Systems, Man and Cybernetics.
• 14: 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
• 15: 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
• 16: Nitin Thaper , Sudipto Guha , Piotr Indyk , Nick Koudas, Dynamic multidimensional histograms, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564741]
• 17: Jeffrey Scott Vitter , Min Wang, Approximate computation of multidimensional aggregates of sparse data using wavelets, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.193-204, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States

INDEX TERMS

Keywords:
attribute cardinality maps, histogram-based algorithms, query optimization, sparse attributes