Validating the Oracle SQL engine

ABSTRACT

The query engine is the component inside a database system that is responsible for the compilation and execution of every SQL statement submitted by a database user or application. One of the most important steps of query compilation is query optimization. The goal of query optimization is to find the best execution plan based on metadata and statistics about the objects related to the tables referenced in the statement. There are two distinct kinds of query optimization: logical and physical. During logical optimization the structures of the query are changed by applying transformations such as view merging, subquery unnesting, etc. Physical optimization considers the physical properties of the tables (disk layout, access methods, size) and properties of the relational algebra operations (commuting joins) to find the best execution plan for a given query shape as presented by the logical optimization.

The changes made to the SQL statement during query optimization can be temporary (to cost a particular optimization) or permanent (after an optimization is considered final). In this paper we discuss the quality problems that occur during the manipulation of the query structures that take place during query compilation with a focus on query optimization. We propose (1) a method to validate query structure change; (2) a method to validate plans that are discarded during query optimization but that may be picked under different circumstances.

REFERENCES

• 1: Oracle 11g Documentation http://ww.oracle.com/pls/db111/homepage
• 2: Rafi Ahmed , Allison Lee , Andrew Witkowski , Dinesh Das , Hong Su , Mohamed Zait , Thierry Cruanes, Cost-based query transformation in Oracle, Proceedings of the 32nd international conference on Very large data bases, September 12-15, 2006, Seoul, Korea
• 3: 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
• 4: Thierry Cruanes , Benoit Dageville , Bhaskar Ghosh, Parallel SQL execution in Oracle 10g, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007666]
• 5: César A. Galindo-Legaria , Arjan Pellenkoft , Martin L. Kersten, Uniformly-Distributed Random Generation of Join Orders, Proceedings of the 5th International Conference on Database Theory, p.280-293, January 11-13, 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: Liskov, B. and Guttag, J. Program Development in Java. Addison-Wesley, Reading MA, 2000.
• 8: George C. Necula, Translation validation for an optimizing compiler, ACM SIGPLAN Notices, v.35 n.5, p.83-94, May 2000
• 9: Oracle 11g Release 1 Database Performance Tuning Guide http://www.oracle.com/pls/db111/to_toc?pathname=server.111/b28274/toc.htm
• 10: 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
• 11: Florian Waas , César Galindo-Legaria, Counting, enumerating, and sampling of execution plans in a cost-based query optimizer, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.499-509, May 15-18, 2000, Dallas, Texas, United States
• 12: Kiyoshi Ono , Guy M. Lohman, Measuring the Complexity of Join Enumeration in Query Optimization, Proceedings of the 16th International Conference on Very Large Data Bases, p.314-325, August 13-16, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.4 Software/Program Verification

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging

  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems

General Terms:
Experimentation, Performance, Reliability, Verification

Keywords:
Oracle, SQL, database systems, execution plan, query optimization, test, validation