Counting, enumerating, and sampling of execution plans in a cost-based query optimizer

ABSTRACT

Testing an SQL database system by running large sets of deterministic or stochastic SQL statements is common practice in commercial database development. However, code defects often remain undetected as the query optimizer's choice of an execution plan is not only depending on the query but strongly influenced by a large number of parameters describing the database and the hardware environment. Modifying these parameters in order to steer the optimizer to select other plans is difficult since this means anticipating often complex search strategies implemented in the optimizer.

In this paper we devise algorithms for counting, exhaustive generation, and uniform sampling of plans from the complete search space. Our techniques allow extensive validation of both generation of alternatives, and execution algorithms with plans other than the optimized one—if two candidate plans fail to produce the same results, then either the optimizer considered an invalid plan, or the execution code is faulty. When the space of alternatives becomes too large for exhaustive testing, which can occur even with a handful of joins, uniform random sampling provides a mechanism for unbiased testing.

The technique is implemented in Microsoft's SQL Server, where it is an integral part of the validation and testing process.

REFERENCES

• 1: José A. Blakeley , William J. McKenna , Goetz Graefe, Experiences building the open OODB query optimizer, Proceedings of the 1993 ACM SIGMOD international conference on Management of data, p.287-296, May 25-28, 1993, Washington, D.C., United States
• 2: 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
• 3: G. Graefe. The Cascades Framework for Query Optimization. IEEE Data Engineering Bulletin, 18(3):19-29, September 1995.
• 4: 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
• 5: 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
• 6: Yannis E. Ioannidis , Younkyung Cha Kang, Left-deep vs. bushy trees: an analysis of strategy spaces and its implications for query optimization, Proceedings of the 1991 ACM SIGMOD international conference on Management of data, p.168-177, May 29-31, 1991, Denver, Colorado, United States
• 7: William Joseph McKenna, Efficient search in extensible database query optimization: the volcano optimizer generator, University of Colorado at Boulder, Boulder, CO, 1993
• 8: Kiyoshi Ono , Guy M. Lohman, Measuring the complexity of join enumeration in query optimization, Proceedings of the sixteenth international conference on Very large databases, p.314-325, September 1990, Brisbane, Australia
• 9: Arjan Pellenkoft , César A. Galindo-Legaria , Martin L. Kersten, The Complexity of Transformation-Based Join Enumeration, Proceedings of the 23rd International Conference on Very Large Data Bases, p.306-315, August 25-29, 1997
• 10: R. Ruskey and T. C. Hu. Generating Binary Tree Lexicographically. SIAM Journal of Computation, 6(4):745-758, December 1977.
• 11: 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

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT

General Terms:
Algorithms, Languages, Verification