A pay-as-you-go framework for query execution feedback

ABSTRACT

Past work has suggested that query execution feedback can be useful in improving the quality of plans by correcting cardinality estimation errors in the query optimizer. The state-of-the-art approach for obtaining execution feedback is "passive" monitoring which records the cardinality of each operator in the execution plan. We observe that there are many cases where even after repeated executions of the same query with use of feedback from passive monitoring, suboptimal choices in the execution plan cannot be corrected. We present a novel "pay-as-you-go" framework in which a query potentially incurs a small overhead on each execution but obtains cardinality information that is not available with passive monitoring alone. Such a framework can significantly extend the reach of query execution feedback in obtaining better plans. We have implemented our techniques in Microsoft SQL Server, and our evaluation on real world and synthetic queries suggests that plan quality can improve significantly compared to passive monitoring even at low overheads.

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: A. Aboulnaga , P. Haas , M. Kandil , S. Lightstone , G. Lohman , V. Markl , I. Popivanov , V. Raman, Automated statistics collection in DB2 UDB, Proceedings of the Thirtieth international conference on Very large data bases, p.1158-1169, August 31-September 03, 2004, Toronto, Canada
• 3: Gennady Antoshenkov, Dynamic Query Optimization in Rdb/VMS, Proceedings of the Ninth International Conference on Data Engineering, p.538-547, April 19-23, 1993
• 4: 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]
• 5: Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066171]
• 6: Shivnath Babu , Rajeev Motwani , Kamesh Munagala , Itaru Nishizawa , Jennifer Widom, Adaptive ordering of pipelined stream filters, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007615]
• 7: 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]
• 8: Nicolas Bruno , Surajit Chaudhuri, Conditional selectivity for statistics on query expressions, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007604]
• 9: S. Chaudhuri, V. Narasayya. Program for TPC-D Data Generation with skew. ftp://ftp.research.microsoft.com/users/viveknar/tpcdskew
• 10: Automating Statistics Management for Query Optimizers, Proceedings of the 16th International Conference on Data Engineering, p.339, February 28-March 03, 2000
• 11: S. Chaudhuri, V. Narasayya, R. Ramamurthy. Diagnosing Estimation Errors in Page Counts Using Execution Feedback. In Proceedings of ICDE 2008.
• 12: 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
• 13: W. G. Cochran. Sampling Techniques. 3^rd Edition. Wiley.
• 14: David J. DeWitt , Robert H. Gerber, Multiprocessor hash-based join algorithms, Proceedings of the 11th international conference on Very Large Data Bases, p.151-164, August 21-23, 1985, Stockholm, Sweden
• 15: A. El-Helw, I. F. Ilyas, W. Lau, V. Markl, C. Zuzarte. Collecting and Maintaining Just-in-Time Statistics. In Proceedings of ICDE 2007.
• 16: 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
• 17: G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3), 1995.
• 18: 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
• 19: Volker Markl , Vijayshankar Raman , David Simmen , Guy Lohman , Hamid Pirahesh , Miso Cilimdzic, Robust query processing through progressive optimization, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007642]
• 20: 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]
• 21: 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
• 22: IEEE Data Engineering Bulleting on Self-Managing Database Systems. Volume 29, Number 3, September 2006.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.3 Information Search and Retrieval

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.4 Systems and Software
          Subjects: Performance evaluation (efficiency and effectiveness)

General Terms:
Algorithms, Design, Management, Performance