A framework for testing query transformation rules

ABSTRACT

In order to enable extensibility, modern query optimizers typically leverage a transformation rule based framework. Testing individual rule correctness as well as correctness of rule interactions is crucial in verifying the functionality of a query optimizer. While there has been a lot of work on how to architect optimizers for extensibility using a rule based framework, there has been relatively little work on how to test such optimizers. In this paper we present a framework for testing query transformation rules which enables: (a) efficient generation of queries that exercise a particular transformation rule or a set of rules and (b) efficient execution of corresponding test suites for correctness testing.

REFERENCES

• 1: Hardik Bati , Leo Giakoumakis , Steve Herbert , Aleksandras Surna, A genetic approach for random testing of database systems, Proceedings of the 33rd international conference on Very large data bases, September 23-27, 2007, Vienna, Austria
• 2: Boris Beizer, Software testing techniques (2nd ed.), Van Nostrand Reinhold Co., New York, NY, 1990
• 3: 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]
• 4: K. Billings. A TPC-D Model for Database Query Optimization in Cascades. Ms. Thesis. Portland State University. 1996
• 5: Carsten Binnig , Donald Kossmann , Eric Lo , M. Tamer Özsu, QAGen: generating query-aware test databases, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247520]
• 6: Nicolas Bruno , Surajit Chaudhuri , Dilys Thomas, Generating Queries with Cardinality Constraints for DBMS Testing, IEEE Transactions on Knowledge and Data Engineering, v.18 n.12, p.1721-1725, December 2006 [doi>10.1109/TKDE.2006.190]
• 7: 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
• 8: Surajit Chaudhuri , Ashish Kumar Gupta , Vivek Narasayya, Compressing SQL workloads, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564747]
• 9: Mostafa Elhemali , Leo Giakoumakis, Unit-testing query transformation rules, Proceedings of the 1st international workshop on Testing database systems, June 13-13, 2008, Vancouver, British Columbia, Canada [doi>10.1145/1385269.1385273]
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 11: L. Giakoumakis, C. Galindo-Legaria. Testing SQL Server's Query Optimizer: Challenges, Techniques and Experiences. IEEE Data Engineering Bulletin 2008 vol. 31 (1).
• 12: Goetz Graefe , William J. McKenna, The Volcano Optimizer Generator: Extensibility and Efficient Search, Proceedings of the Ninth International Conference on Data Engineering, p.209-218, April 19-23, 1993
• 13: G. Graefe. The Cascades Framework for Query Optimization. Data Engineering Bulletin, 18(3), 1995.
• 14: F. Haftmann, D. Kossmann, A. Kreutz. Efficient Regression Tests for Database Applications. Proceedings of CIDR 2005.
• 15: Chaitanya Mishra , Nick Koudas , Calisto Zuzarte, Generating targeted queries for database testing, Proceedings of the 2008 ACM SIGMOD international conference on Management of data, June 09-12, 2008, Vancouver, Canada [doi>10.1145/1376616.1376668]
• 16: 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
• 17: Donald R. Slutz, Massive Stochastic Testing of SQL, Proceedings of the 24rd International Conference on Very Large Data Bases, p.618-622, August 24-27, 1998
• 18: M. Stillger, J. C. Freytag. Testing the quality of a query optimizer. Data Engineering Bulletin, 18(3), 1995.
• 19: Vijay V. Vazirani, Approximation algorithms, Springer-Verlag New York, Inc., New York, NY, 2001
• 20: 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
• 21: TPC Benchmark H. Decision Support. http://www.tpc.org

INDEX TERMS

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

General Terms:
Algorithms, Measurement, Performance

Keywords:
database testing, query optimization, transformation rules