An Empirical Comparison of Randomized Algorithms for Large Join Query Optimization

Sushil J. Louis and Yongmian Zhang

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.

This page is copyrighted by AAAI. All rights reserved. Your use of this site constitutes acceptance of all of AAAI's terms and conditions and privacy policy.