Counting, Enumerating, and Sampling of Execution Plans in a Cost-based Query Optimizer

Testing an SQL database system by running large sets of de-terministic 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 describ-ing the database and the hardware environment. Modifying these parameters in order to steer the optimizer to select other plans is dicult since this means anticipating often complex search strategies implemented in the optimizer. In this paper we devise algorithms for counting, exhaus-tive generation, and uniform sampling of plans from the complete search space. Our techniques allow extensive vali-dation of both generation of alternatives, and execution al-gorithms 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 mech-anism for unbiased testing. The technique is implemented in Microsoft’s SQL Server, where it is an integral part of the validation and testing process.