Query optimizers: time to rethink the contract?

ABSTRACT

Query Optimization is expected to produce good execution plans for complex queries while taking relatively small optimization time. Moreover, it is expected to pick the execution plans with rather limited knowledge of data and without any additional input from the application. We argue that it is worth rethinking this prevalent model of the optimizer. Specifically, we discuss how the optimizer may benefit from leveraging rich usage data and from application input. We conclude with a call to action to further advance query optimization technology.

REFERENCES

• 1: 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]
• 2: Graefe, G.: The Cascades Framework for Query Optimization. IEEE Data Eng. Bull. 18(3): 19--29 (1995)
• 3: Hamid Pirahesh , Joseph M. Hellerstein , Waqar Hasan, Extensible/rule based query rewrite optimization in Starburst, Proceedings of the 1992 ACM SIGMOD international conference on Management of data, p.39-48, June 02-05, 1992, San Diego, California, United States
• 4: 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
• 5: U. Srivastava , P. J. Haas , V. Markl , M. Kutsch , T. M. Tran, ISOMER: Consistent Histogram Construction Using Query Feedback, Proceedings of the 22nd International Conference on Data Engineering, p.39, April 03-07, 2006 [doi>10.1109/ICDE.2006.84]
• 6: Michael Stillger , Guy M. Lohman , Volker Markl , Mokhtar Kandil, LEO - DB2's LEarning Optimizer, Proceedings of the 27th International Conference on Very Large Data Bases, p.19-28, September 11-14, 2001
• 7: 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]
• 8: Navin Kabra , David J. DeWitt, Efficient mid-query re-optimization of sub-optimal query execution plans, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.106-117, June 01-04, 1998, Seattle, Washington, United States
• 9: Ron Avnur , Joseph M. Hellerstein, Eddies: continuously adaptive query processing, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.261-272, May 15-18, 2000, Dallas, Texas, United States
• 10: Zilberstein, S.: Using Anytime Algorithms in Intelligent Systems. AI Magazine 17(3): 73--83 (1996)
• 11: Y. E. Ioannidis , Younkyung Kang, Randomized algorithms for optimizing large join queries, Proceedings of the 1990 ACM SIGMOD international conference on Management of data, p.312-321, May 23-26, 1990, Atlantic City, New Jersey, United States
• 12: Mayrhofer, R.: Generic Heuristics for Combinatorial Optimization Problems. Proc. of the 9th International Conference on Operational Research 2002
• 13: V. Markl , N. Megiddo , M. Kutsch , T. M. Tran , P. Haas , U. Srivastava, Consistently estimating the selectivity of conjuncts of predicates, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 14: Nicolas Bruno , Surajit Chaudhuri , Ravi Ramamurthy, Power Hints for Query Optimization, Proceedings of the 2009 IEEE International Conference on Data Engineering, p.469-480, March 29-April 02, 2009 [doi>10.1109/ICDE.2009.68]
• 15: Surajit Chaudhuri , Vivek Narasayya , Ravi Ramamurthy, A pay-as-you-go framework for query execution feedback, Proceedings of the VLDB Endowment, v.1 n.1, August 2008 [doi>10.1145/1453856.1453977]
• 16: Amol Deshpande , Zachary Ives , Vijayshankar Raman, Adaptive query processing, Foundations and Trends in Databases, v.1 n.1, p.1-140, January 2007 [doi>10.1561/1900000001]
• 17: Yannis Ioannidis, The history of histograms (abridged), Proceedings of the 29th international conference on Very large data bases, p.19-30, September 09-12, 2003, Berlin, Germany
• 18: Gennady Antoshenkov, Dynamic Query Optimization in Rdb/VMS, Proceedings of the Ninth International Conference on Data Engineering, p.538-547, April 19-23, 1993
• 19: Richard L. Cole , Goetz Graefe, Optimization of dynamic query evaluation plans, Proceedings of the 1994 ACM SIGMOD international conference on Management of data, p.150-160, May 24-27, 1994, Minneapolis, Minnesota, United States
• 20: Tolga Urhan , Michael J. Franklin , Laurent Amsaleg, Cost-based query scrambling for initial delays, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.130-141, June 01-04, 1998, Seattle, Washington, United States
• 21: Surajit Chaudhuri, An overview of query optimization in relational systems, Proceedings of the seventeenth ACM SIGACT-SIGMOD-SIGART symposium on Principles of database systems, p.34-43, June 01-04, 1998, Seattle, Washington, United States [doi>10.1145/275487.275492]
• 22: 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
• 23: 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
• 24: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 25: Naveen Reddy , Jayant R. Haritsa, Analyzing plan diagrams of database query optimizers, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 26: Harish D , Pooja N. Darera , Jayant R. Haritsa, On the production of anorexic plan diagrams, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 27: Frank Olken , Doron Rotem, Random Sampling from Database Files: A Survey, Proceedings of the 5th International Conference SSDBM on Statistical and Scientific Database Management, p.92-111, April 03-05, 1990
• 28: César A. Galindo-Legaria , Milind M. Joshi , Florian Waas , Ming-Chuan Wu, Statistics on views, Proceedings of the 29th international conference on Very large data bases, p.952-962, September 09-12, 2003, Berlin, Germany
• 29: Nicolas Bruno , Surajit Chaudhuri, Exploiting statistics on query expressions for optimization, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564722]
• 30: Lothar F. Mackert , Guy M. Lohman, R* optimizer validation and performance evaluation for local queries, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.84-95, May 28-30, 1986, Washington, D.C., United States
• 31: Benoit Dageville , Dinesh Das , Karl Dias , Khaled Yagoub , Mohamed Zait , Mohamed Ziauddin, Automatic SQL tuning in oracle 10g, Proceedings of the Thirtieth international conference on Very large data bases, p.1098-1109, August 31-September 03, 2004, Toronto, Canada
• 32: 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
• 33: Surajit Chaudhuri , Vivek Narasayya , Ravishankar Ramamurthy, Diagnosing Estimation Errors in Page Counts Using Execution Feedback, Proceedings of the 2008 IEEE 24th International Conference on Data Engineering, p.1013-1022, April 07-12, 2008 [doi>10.1109/ICDE.2008.4497510]
• 34: Brian Babcock , Surajit Chaudhuri, Towards a robust query optimizer: a principled and practical approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066172]

INDEX TERMS

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

General Terms:
Design, Experimentation, Performance

Keywords:
cardinality estimation, query optimizer