Randomized algorithms for query optimization
Younkyung Cha Kang · Minds at UW (University of Wisconsin) · 1991
Query optimization for relational database systems is a combinatorial optimization problem, which makes exhaustive search unacceptable as the query size grows. Randomized algorithms, such as Iterative Improvement and Simulated Annealing, are viable alternatives to exhaustive search. We present several analytical and experimental results that shed some light on the shape of the cost function of the access plan spaces with which the randomized query optimization algorithms must deal. These are the space that includes only left-deep trees, and the space that includes both deep and bushy trees. We conclude that the shape of both spaces essentially forms a 'well', but of a distinctly different quality. This has inspired a new algorithm, Two Phase Optimization, which is a combination of Simulated Annealing and Iterative Improvement. We show how Iterative Improvement, Simulated Annealing, and Two Phase Optimization perform on the two spaces of interest and explain the results based on the above analysis on the shape of their cost function. In particular, the results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time. Additional experimentation shows that Two Phase Optimization is also very effective on small queries, having the traditional algorithm of System R as the basis for comparison. Thus, it emerges as a strong candidate for query optimization in future database systems. Finally, a comparison between the two spaces of interest in their form used in this work leads to the rather surprising conclusion that the space of both deep and bushy trees is to be preferred over the space of left-deep trees for query optimization. The former has a more definite shape of a 'well' than the latter and also includes more efficient alternatives in most cases. Hence, for the specific choices of connections of alternative access plans in the two spaces, the space of deep and bushy trees is superior with respect to both optimization time and output quality of the algorithms that use it as their search space.