Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based Query Optimizer Florian Waas and César A. Galindo-Legaria   View Paper (PDF)   Return to Industrial Sessions 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 Note: References link to DBLP on the Web. [1] José A. Blakeley , William J. McKenna , Goetz Graefe : Experiences Building the Open OODB Query Optimizer. SIGMOD Conference 1993 : 287-296 [2] César A. Galindo-Legaria , Arjan Pellenkoft , Martin L. Kersten : Uniformly-Distributed Random Generation of Join Orders. ICDT 1995 : 280-293 [3] Goetz Graefe : The Cascades Framework for Query Optimization. Data Engineering Bulletin 18(3) : 19-29(1995) [4] Goetz Graefe , David J. DeWitt : The EXODUS Optimizer Generator. SIGMOD Conference 1987 : 160-172 [5] Goetz Graefe , William J. McKenna : The Volcano Optimizer Generator: Extensibility and Efficient Search. ICDE 1993 : 209-218 [6] Yannis E. Ioannidis , Younkyung Cha Kang : Left-Deep vs. Bushy Trees: An Analysis of Strategy Spaces and its Implications for Query Optimization. SIGMOD Conference 1991 : 168-177 [7] William J. McKenna : Efficient Search in Extensible Query Optimization: The Volcano Optimizer Generator. Ph.D. thesis, University of Colorado-Boulder 1993 [8] Kiyoshi Ono , Guy M. Lohman : Measuring the Complexity of Join Enumeration in Query Optimization. VLDB 1990 : 314-325 [9] Arjan Pellenkoft , César A. Galindo-Legaria , Martin L. Kersten : The Complexity of Transformation-Based Join Enumeration. VLDB 1997 : 306-315 [10] Frank Ruskey , T. C. Hu : Generating Binary Trees Lexicographically. SIAM J. Comput. 6(4) : 745-758(1977) [11] Donald R. Slutz : Massive Stochastic Testing of SQL. VLDB 1998 : 618-622 BIBTEX @inproceedings{DBLP:conf/sigmod/WaasG00,   author    = {Florian Waas and                 C{\'e}sar A. Galindo-Legaria},    editor    = {Weidong Chen and                 Jeffrey F. Naughton and                 Philip A. Bernstein},    title     = {Counting, Enumerating, and Sampling of Execution Plans in a Cost-Based                 Query Optimizer},    booktitle = {Proceedings of the 2000 ACM SIGMOD International Conference on                 Management of Data, May 16-18, 2000, Dallas, Texas, USA},    journal   = {SIGMOD Record},    publisher = {ACM},    volume    = {29},    number    = {2},    year      = {2000},    isbn      = {1-58113-218-2},    pages     = {499-509},    crossref  = {DBLP:conf/sigmod/2000},    bibsource = {DBLP, http://dblp.uni-trier.de} } }, DiSC'01 Copyright ©2002 ACM Inc.