Skip to main content

Randomized Algorithms for Optimizing Large Join Queries

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 Simulated Annealing (SA) and Iterative Improvement (II), are viable alternatives to exhaustive search. We have adapted these algorithms to the optimization of project-select-join queries. We have tested them on large queries of various types with different databases, concluding that in most cases SA identifies a lower cost access plan than II. To explain this result, we have studied the shape of the cost function over the solution space associated with such queries and we have conjectured that it resembles a 'cup' with relatively small variations at the bottom. This has inspired a new Two Phase Optimization algorithm, which is a combination of Simulated Annealing and Iterative Improvement. Experimental results show that Two Phase Optimization outperforms the original algorithms in terms of both output quality and running time.

Yannis Ioannidis, Younkyung Cha Kang, "Randomized Algorithms for Optimizing Large Join Queries ", ACM SIGMOD Conference, Atlantic City, NJ, May 1990, pp. 312-321, 1990
Published at
ACM SIGMOD Conference, Atlantic City, NJ, May 1990, pp. 312-321
Related research area
No related research area
Related Organizations
No related organizations