Towards a robust query optimizer: a principled and practical approach

ABSTRACT

Research on query optimization has focused almost exclusively on reducing query execution time, while important qualities such as consistency and predictability have largely been ignored, even though most database users consider these qualities to be at least as important as raw performance. In this paper, we explore how the query optimization process can be made more robust, focusing on the important subproblem of cardinality estimation. The robust cardinality estimation technique that we propose allows for a user- or application-specified trade-off between performance and predictability, and it captures multi-dimensional correlations while remaining space- and time-efficient.

REFERENCES

• 1: 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
• 2: G. Antoshenkov. Query processing in DEC Rdb: Major issues and future challenges. Data Engineering Bulletin, 16(4):41--50, 1993.
• 3: J. M. Bernardo and A. F. M. Smith. Bayesian Theory. John Wiley, 1994.
• 4: Automating Statistics Management for Query Optimizers, Proceedings of the 16th International Conference on Data Engineering, p.339, February 28-March 03, 2000
• 5: 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
• 6: Francis Chu , Joseph Halpern , Johannes Gehrke, Least expected cost query optimization: what can we expect?, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543651]
• 7: Francis Chu , Joseph Y. Halpern , Praveen Seshadri, Least expected cost query optimization: an exercise in utility, Proceedings of the eighteenth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.138-147, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States [doi>10.1145/303976.303990]
• 8: R. L. Cole. A decision theoretic cost model for dynamic plans. Data Engineering Bulletin, 23(2):34--41, 2000.
• 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: Donko Donjerkovic , Raghu Ramakrishnan, Probabilistic Optimization of Top N Queries, Proceedings of the 25th International Conference on Very Large Data Bases, p.411-422, September 07-10, 1999
• 11: Christos Faloutsos , Ibrakim Kamel, Relaxing the uniformity and independence assumptions using the concept of fractal dimension, Journal of Computer and System Sciences, v.55 n.2, p.229-240, Oct. 1997 [doi>10.1006/jcss.1997.1522]
• 12: Lise Getoor , Benjamin Taskar , Daphne Koller, Selectivity estimation using probabilistic models, Proceedings of the 2001 ACM SIGMOD international conference on Management of data, p.461-472, May 21-24, 2001, Santa Barbara, California, United States
• 13: 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
• 14: Peter J. Haas , Jeffrey F. Naughton , S. Seshadri , Arun N. Swami, Selectivity and cost estimation for joins based on random sampling, Journal of Computer and System Sciences, v.52 n.3, p.550-569, June 1996 [doi>10.1006/jcss.1996.0041]
• 15: 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
• 16: Y. E. Ioannidis. The history of histograms (abridged). In Proc. 2003 VLDB Conf., pages 19--30, Sept. 2003.
• 17: 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
• 18: 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
• 19: H. Jeffreys. Theory of Probability. Clarendon Press, 1961.
• 20: 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
• 21: P. M. Lee. Bayesian Statistics: An Introduction. Oxford University Press, 1989.
• 22: 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
• 23: 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]
• 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: 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
• 26: F. Olken. Random Sampling from Databases. PhD thesis, University of California at Berkeley, 1993.
• 27: 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
• 28: 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
• 29: Kamil Saraç , Ömer Eğecioǧlu , Amr El Abbadi, Iterated DFT based techniques for join size estimation, Proceedings of the seventh international conference on Information and knowledge management, p.348-355, November 02-07, 1998, Bethesda, Maryland, United States [doi>10.1145/288627.288676]
• 30: 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]
• 31: K. D. Seppi, J. W. Barnes, and C. N. Morris. A Bayesian approach to database query optimization. ORSA Journal on Computing, 5(4):410--419, 1993.
• 32: Transaction Processing Performance Council. TPC-H benchmark 2.0.0, July 2002. http://www.tpc.org.