Configuration-parametric query optimization for physical design tuning

ABSTRACT

Automated physical design tuning for database systems has recently become an active area of research and development. Existing tuning tools explore the space of feasible solutions by repeatedly optimizing queries in the input workload for several candidate configurations. This general approach, while scalable, often results in tuning sessions waiting for results from the query optimizer over 90% of the time. In this paper we introduce a novel approach, called Configuration-Parametric Query Optimization, that drastically improves the performance of current tuning tools. By issuing a single optimization call per query, we are able to generate a compact representation of the optimization space that can then produce very efficiently execution plans for the input query under arbitrary configurations. Our experiments show that our technique speeds-up query optimization by 30x to over 450x with virtually no loss in quality, and effectively eliminates the optimization bottleneck in existing tuning tools. Our techniques open the door for new, more sophisticated optimization strategies by eliminating the main bottleneck of current tuning tools.

REFERENCES

• 1: S. Agrawal et al. Database Tuning Advisor for Microsoft SQL Server 2005. In Proceedings of the International Conference on Very Large Databases (VLDB), 2004.
• 2: K. Billings. A TPC-D Model for Database Query Optimization in Cascades. Ms. thesis, Portland State University, 1996.
• 3: Nicolas Bruno , Surajit Chaudhuri, Automatic physical database tuning: a relaxation-based approach, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066184]
• 4: Nicolas Bruno , Surajit Chaudhuri, To tune or not to tune?: a lightweight physical design alerter, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 5: Pedro Celis, The Query Optimizer in Tandem's new ServerWare SQL Product, Proceedings of the 22th International Conference on Very Large Data Bases, p.592, September 03-06, 1996
• 6: Surajit Chaudhuri , Vivek R. Narasayya, An Efficient Cost-Driven Index Selection Tool for Microsoft SQL Server, Proceedings of the 23rd International Conference on Very Large Data Bases, p.146-155, August 25-29, 1997
• 7: Surajit Chaudhuri , Vivek Narasayya, AutoAdmin “what-if” index analysis utility, Proceedings of the 1998 ACM SIGMOD international conference on Management of data, p.367-378, June 01-04, 1998, Seattle, Washington, United States
• 8: 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
• 9: G. Graefe. The Cascades framework for query optimization. Data Engineering Bulletin, 18(3), 1995.
• 10: Goetz Graefe, The Microsoft Relational Engine, Proceedings of the Twelfth International Conference on Data Engineering, p.160-161, February 26-March 01, 1996
• 11: Yannis E. Ioannidis , Raymond T. Ng , Kyuseok Shim , Timos K. Sellis, Parametric Query Optimization, Proceedings of the 18th International Conference on Very Large Data Bases, p.103-114, August 23-27, 1992
• 12: Stratos Papadomanolakis , Debabrata Dash , Anastasia Ailamaki, Efficient use of the query optimizer for automated physical design, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 13: Leonard D. Shapiro , David Maier , Paul Benninghoff , Keith Billings , Yubo Fan , Kavita Hatwal , Quan Wang , Yu Zhang , Hsiao-min Wu , Bennet Vance, Exploiting Upper and Lower Bounds In Top-Down Query Optimization, Proceedings of the International Database Engineering & Applications Symposium, p.20-33, July 16-18, 2001
• 14: Alan Skelley, DB2 Advisor: An Optimizer Smart Enough to Recommend its own Indexes, Proceedings of the 16th International Conference on Data Engineering, p.101, February 28-March 03, 2000
• 15: Daniel C. Zilio , Jun Rao , Sam Lightstone , Guy Lohman , Adam Storm , Christian Garcia-Arellano , Scott Fadden, DB2 design advisor: integrated automatic physical database design, Proceedings of the Thirtieth international conference on Very large data bases, p.1087-1097, August 31-September 03, 2004, Toronto, Canada

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods

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

General Terms:
Algorithms, Performance

Keywords:
parametric optimization, physical design tuning