Polynomial time algorithm for optimizing join queries

Abstract

The well known dynamic programming algorithm for query optimization has exponential complexity. An alternative polynomial time algorithm, the IK-KBZ algorithm, is severely limited in the queries it can optimize. Other algorithms have been proposed including the greedy algorithm, iterative improvement and simulated annealing. We give a new algorithm (we call it the AB algorithm) that combines randomization and neighborhood search with the IK-KBZ algorithm. The AB algorithm is: (a) much more generally applicable than IK-KBZ, (b) has polynomial time and space complexity, and (c) on the basis of a large number of experiments conducted by us, produces near optimal plans in the space of outer linear join trees. On the average, it does better than the other algorithms proposed in the literature that do not do exhaustive search like dynamic programming.