Dynamic plan generation for parameterized queries

ABSTRACT

Query processing in a DBMS typically involves two distinct phases: compilation, which generates the best plan and its corresponding execution steps, and execution, which evaluates these steps against database objects. For some queries, considerable resource savings can be achieved by skipping the compilation phase when the same query was previously submitted and its plan was already cached. In a number of important applications the same query, called a Parameterized Query (PQ), is repeatedly submitted in the same basic form but with different parameter values. PQ's are extensively used in both data update (e.g. batch update programs) and data access queries. There are tradeoffs associated with caching and re-using query plans such as space utilization and maintenance cost. Besides, pre-compiled plans may be suboptimal for a particular execution due to various reasons including data skew and inability to exploit value-based query transformation like materialized view rewrite and unsatisfiable predicate elimination. We address these tradeoffs by distinguishing two types of plans for PQ's: generic and specific plans. Generic plans are pre-compiled plans that are independent of the actual parameter values. Prior to execution, parameter values are plugged in to generic plans. In specific plans, parameter values are plugged prior to the compilation phase. This paper provides a practical framework for dynamically deciding between specific and generic plans for PQ's based on a mix of rule and cost based heuristics which are implemented in the Teradata 12.0 DBMS.

REFERENCES

• 1: Shivnath Babu , Pedro Bizarro , David DeWitt, Proactive re-optimization with Rio, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066294]
• 2: 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
• 3: IBM. "DB2 Version 9.1 for z/OS: Application Programming and SQL Guide", December 2008.
• 4: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric query optimization, The VLDB Journal — The International Journal on Very Large Data Bases, v.6 n.2, p.132-151, May 1997 [doi>10.1007/s007780050037]
• 5: 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
• 6: Allison W. Lee , Mohamed Zait, Closing the query processing loop in Oracle 11g, Proceedings of the VLDB Endowment, v.1 n.2, August 2008 [doi>10.1145/1454159.1454178]
• 7: A. Marathe and S. Scott, "Batch Compilation, Recompilation, and Plan Caching Issues in SQL Server 2005", Microsoft White Paper, Dec. 2006.
• 8: V. Markl , G. M. Lohman , V. Raman, LEO: An autonomic query optimizer for DB2, IBM Systems Journal, v.42 n.1, p.98-106, January 2003
• 9: 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]
• 10: Aditya N. Saharia , Yair M. Babad, Enhancing data warehouse performance through query caching, ACM SIGMIS Database, v.31 n.2, p.43-63, Spring 2000 [doi>10.1145/381137.381142]
• 11: TPC-H specification -- Transaction Performance Council www.tpc.org

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL
      Subjects: Hardware/software interfaces

General Terms:
Algorithms, Performance, Theory

Keywords:
compilation, dynamic, optimizations