Fast incremental maintenance of approximate histograms

ABSTRACT

Many commercial database systems maintain histograms to summarize the contents of large relations and permit efficient estimation of query result sizes for use in query optimizers. Delaying the propagation of database updates to the histogram often introduces errors into the estimation. This article presents new sampling-based approaches for incremental maintenance of approximate histograms. By scheduling updates to the histogram based on the updates to the database, our techniques are the first to maintain histograms effectively up to date at all times and avoid computing overheads when unnecessary. Our techniques provide highly accurate approximate histograms belonging to the equidepth and Compressed classes. Experimental results show that our new approaches provide orders of magnitude more accurate estimation than previous approaches.An important aspect employed by these new approaches is a backing sample, an up-to-date random sample of the tuples currently in a relation. We provide efficient solutions for maintaining a uniformly random sample of a relation in the presence of updates to the relation. The backing sample techniques can be used for any other application that relies on random samples of data.

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 , Phillip B. Gibbons , Viswanath Poosala, Congressional samples for approximate answering of group-by queries, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.487-498, May 15-18, 2000, Dallas, Texas, United States
• 3: Swarup Acharya , Phillip B. Gibbons , Viswanath Poosala , Sridhar Ramaswamy, Join synopses for approximate query answering, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.275-286, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 4: Björn Blohsfeld , Dieter Korus , Bernhard Seeger, A comparison of selectivity estimators for range queries on metric attributes, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.239-250, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 5: 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
• 6: Surajit Chaudhuri , Gautam Das , Vivek Narasayya, A robust, optimization-based approach for approximate answering of aggregate queries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.295-306, May 21-24, 2001, Santa Barbara, California, United States
• 7: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, Random sampling for histogram construction: how much is enough?, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.436-447, June 01-04, 1998, Seattle, Washington, United States
• 8: 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]
• 9: Amol Deshpande , Minos Garofalakis , Rajeev Rastogi, Independence is good: dependency-based histogram synopses for high-dimensional data, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.199-210, May 21-24, 2001, Santa Barbara, California, United States
• 10: Venkatesh Ganti , Mong-Li Lee , Raghu Ramakrishnan, ICICLES: Self-Tuning Samples for Approximate Query Answering, Proceedings of the 26th International Conference on Very Large Data Bases, p.176-187, September 10-14, 2000
• 11: Phillip B. Gibbons, Distinct Sampling for Highly-Accurate Answers to Distinct Values Queries and Event Reports, Proceedings of the 27th International Conference on Very Large Data Bases, p.541-550, September 11-14, 2001
• 12: Phillip B. Gibbons , Yossi Matias, New sampling-based summary statistics for improving approximate query answers, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.331-342, June 01-04, 1998, Seattle, Washington, United States
• 13: Anna C. Gilbert , Sudipto Guha , Piotr Indyk , Yannis Kotidis , S. Muthukrishnan , Martin J. Strauss, Fast, small-space algorithms for approximate histogram maintenance, Proceedings of the thiry-fourth annual ACM symposium on Theory of computing, May 19-21, 2002, Montreal, Quebec, Canada [doi>10.1145/509907.509966]
• 14: Gilbert, A. C., Kotidis, Y., Muthukrishnan, S., and Strauss, M. J. 2002b. How to summarize the universe: Dynamic maintenance of quantiles. In Proceedings of the 28th International Conference on Very Large Data Bases, Morgan Kaufman, Hong Kong.
• 15: Michael Greenwald , Sanjeev Khanna, Space-efficient online computation of quantile summaries, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.58-66, May 21-24, 2001, Santa Barbara, California, United States
• 16: Sudipto Guha , Nick Koudas , Kyuseok Shim, Data-streams and histograms, Proceedings of the thirty-third annual ACM symposium on Theory of computing, p.471-475, July 2001, Hersonissos, Greece [doi>10.1145/380752.380841]
• 17: 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
• 18: 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
• 19: 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
• 20: 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
• 21: Arnd Christian König , Gerhard Weikum, Combining Histograms and Parametric Curve Fitting for Feedback-Driven Query Result-size Estimation, Proceedings of the 25th International Conference on Very Large Data Bases, p.423-434, September 07-10, 1999
• 22: Robert Philip Kooi, The optimization of queries in relational databases, 1980
• 23: 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
• 24: 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
• 25: Yossi Matias , Jeffrey Scott Vitter , Min Wang, Dynamic Maintenance of Wavelet-Based Histograms, Proceedings of the 26th International Conference on Very Large Data Bases, p.101-110, September 10-14, 2000
• 26: Viswanath Poosala, Histogram-based estimation techniques in database systems, University of Wisconsin at Madison, Madison, WI, 1997
• 27: Viswanath Poosala , Yannis E. Ioannidis, Estimation of Query-Result Distribution and its Application in Parallel-Join Load Balancing, Proceedings of the 22th International Conference on Very Large Data Bases, p.448-459, September 03-06, 1996
• 28: 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
• 29: 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
• 30: John H. Reif , Leslie G. Valiant, A logarithmic time sort for linear size networks, Journal of the ACM (JACM), v.34 n.1, p.60-76, Jan. 1987 [doi>10.1145/7531.7532]
• 31: 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]
• 32: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 33: Zipf, G. K. 1949. Human Behaviour and the Principle of Least Effort. Addison-Wesley, Reading, Mass.

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance, Theory, Verification

Keywords:
Approximation, histograms, incremental maintenance, query optimization, sampling