An Empirical Comparison of Randomized Algorithms forLarge Join Query Optimization

May 1998

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

Volume

Proceedings of the Eleventh International Florida Artificial Intelligence Research Society Conference (FLAIRS 1998)

All Papers

Non-traditional database applications need new query optimization algorithms to speed up large join queries. In the last decade, general techniques such as iterative improvement and simulated annealing: have been ex-tensively investigated for solving large join query opti-mization problems. In this paper, we compare a genetic algorithm with iterative improvement and simulated annealing for the optimization of large join queries. We compare the performance of these algorithms by testing them on various types of query strategies. In all of our cases, experimental results show that genetic algorithms performed consistently better than simulated annealing and iterative improvement in terms of both output quality and running time. In addition, we found that it is comparatively easier to tune the parameters of genetic algorithms and drive it to a desired optimal solution. We believe that the genetic algorithm approach ranks fairly high among the algorithms we tested, and hence appears to be a promising approach for large join query optimization in future database management systems.