Take a look at the new version of this page: [ beta version ]. Tell us what you think.

ABSTRACT

The process of validating the internal functionality of a query optimizer includes the selection of appropriate queries to be used as test cases for exercising and validating specific code paths. Specifically, it is desirable to be able to implement unit-tests for small components of the query optimizer such as the query transformation rules.

In this paper, we present a practical method that simplifies the creation of test cases for validating query transformation rules in a query optimizer. We present the QRel programming framework, which allows designing test cases based on relational algebra expressions. We show how such a framework can be used to create classes of similar test cases that exercise transformation rules over a variety of relational algebra expressions. Finally, we provide some examples of how QRel is used to validate SQL Server's optimizations for subqueries.

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: Mitch Cherniack , Stanley B. Zdonik, Rule languages and internal algebras for rule-based optimizers, ACM SIGMOD Record, v.25 n.2, p.401-412, June 1996
• 3: David M. Cohen , Siddhartha R. Dalal , Jesse Parelius , Gardner C. Patton, The Combinatorial Design Approach to Automatic Test Generation, IEEE Software, v.13 n.5, p.83-88, September 1996 [doi>10.1109/52.536462]
• 4: Mostafa Elhemali , César A. Galindo-Legaria , Torsten Grabs , Milind M. Joshi, Execution strategies for SQL subqueries, Proceedings of the 2007 ACM SIGMOD international conference on Management of data, June 11-14, 2007, Beijing, China [doi>10.1145/1247480.1247598]
• 5: Erich Gamma , Richard Helm , Ralph Johnson , John Vlissides, Design patterns: elements of reusable object-oriented software, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 6: Giakoumakis, L and Galindo-Legaria, C. Testing SQL Server's Query Optimizer: Challenges, Techniques and Experiences. IEEE Data Engineering Bulletin, 31, 1 (March 2008), 37--44
• 7: Goetz Graefe , David J. DeWitt, The EXODUS optimizer generator, Proceedings of the 1987 ACM SIGMOD international conference on Management of data, p.160-172, May 27-29, 1987, San Francisco, California, United States
• 8: 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
• 9: 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

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Verification

Keywords:
query optimization, testing, verification