Balancing histogram optimality and practicality for query result size estimation

ABSTRACT

Many current database systems use histograms to approximate the frequency distribution of values in the attributes of relations and based on them estimate query result sizes and access plan costs. In choosing among the various histograms, one has to balance between two conflicting goals: optimality, so that generated estimates have the least error, and practicality, so that histograms can be constructed and maintained efficiently. In this paper, we present both theoretical and experimental results on several issues related to this trade-off. Our overall conclusion is that the most effective approach is to focus on the class of histograms that accurately maintain the frequencies of a few attribute values and assume the uniform distribution for the rest, and choose for each relation the histogram in that class that is optimal for a self-join query.

REFERENCES

• 1: Chungmin Melvin Chen , Nick Roussopoulos, Adaptive selectivity estimation using query feedback, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.161-172, May 24-27, 1994, Minneapolis, Minnesota, United States
• 2: Stavros Christodoulakis, Estimating block transfers and join sizes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 3: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 4: S. Christodoulakis On the estimation and use of selectivities in database performance evaluation. Research Report CS-89-24, Dept. of Computer Science, University of Waterloo, June 1989.
• 5: Chris Date, A Guide to DB2, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1984
• 6: Christos Faloutsos , H. V. Jagadish, On B-Tree Indices for Skewed Distributions, Proceedings of the 18th International Conference on Very Large Data Bases, p.363-374, August 23-27, 1992
• 7: 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
• 8: Peter J. Haas , Arun N. Swami, Sampling-Based Selectivity Estimation for Joins Using Augmented Frequent Value Statistics, Proceedings of the Eleventh International Conference on Data Engineering, p.522-531, March 06-10, 1995
• 9: 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
• 10: 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
• 11: 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]
• 12: Y. Ioannidis and V. Poosala. Balancing histogram optimality and practicality for query result size estimation. Unpublished manuscript, February 1995.
• 13: Nabil Kamel , Roger King, A model of data distribution based on texture analysis, Proceedings of the 1985 ACM SIGMOD international conference on Management of data, p.319-325, May 1985, Austin, Texas, United States
• 14: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 15: Richard J. Lipton , Jeffrey F. Naughton , Donovan A. Schneider, Practical selectivity estimation through adaptive sampling, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.1-11, May 23-26, 1990, Atlantic City, New Jersey, United States
• 16: 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]
• 17: A. W. Marshall and I. Olkin. Inequalities: Theory of Majorizat~on and Its Applications. Academic Press, New York, NY, 1979.
• 18: T. H. Merrett and E. Otoo. Distribution models of relations. In Proc. 5th Int. VLDB Conf., pages 418- 425, Rio de Janeiro, Brazil, October 1979.
• 19: 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
• 20: B. Muthuswamy , Larry Kerschberg, A detailed statistical model for relational query optimization, Proceedings of the 1985 ACM annual conference on The range of computing : mid-80's perspective: mid-80's perspective, p.439-448, October 1985, Denver, Colorado, United States [doi>10.1145/320435.320564]
• 21: 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
• 22: P. Griffiths Selinger , M. M. Astrahan , D. D. Chamberlin , R. A. Lorie , T. G. Price, Access path selection in a relational database management system, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582099]
• 23: Yun Wang, Experience from a real life query optimizer, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.286-286, June 02-05, 1992, San Diego, California, United States
• 24: G. K. Zipf. Human Behavior and the Pmnc~ple of Least Effort. Addison-Wesley, Reading, MA, 1949.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.1 Numerical Algorithms and Problems
          Subjects: Computations on matrices

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS

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

General Terms:
Algorithms, Experimentation, Performance, Theory