An Empirical Comparison of Randomized Algorithms for Large Join Query Optimization
Sushil J. Louis, Yongmian Zhang · 1998
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 test-ing them on various types of query strategies. In all of our cases, experimental results show that genetic al-gorithms performed consistently better than simulated annealing and iterative improvement in terms of both output quality and running time. In addition, w~e found that it is comparatively easier to tune the parameters of genetic algorithms and drive it to a desired opti-mal 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.