Abstract

A major task in query optimization is finding an optimal or near-optimal order to perform join operations. Most optimizers perform this join reordering using an exhaustive search algorithm with a dynamic programming technique. This algorithm always gives the optimal join ordering, but is very expensive. An alternative greedy approach is very efficient, but is not guaranteed to produce the optimal order. In this thesis, we introduce a new algorithm called AO * to find the optimal join ordering for a given set of relations. Our algorithm is based on a well-known problem reduction technique of the same name proposed in the context of decomposable production systems. In our algorithm, we build an AND/OR graph from the relations in the query which represents all possible join orders, and an optimal join ordering is an optimal-cost path in this graph. The AO * algorithm is guaranteed to produce the optimal join ordering, as is dynamic programming. While the worst-case performance cost of AO * is comparable to that of dynamic programming, in most instances, it is far more efficient. We compared the performance of AO * with that of dynamic programming and the greedy approach on star-, chain-, circular-, and clique-shaped queries. Our results show that for the first three types of queries, AO * outperforms dynamic programming dramatically. Another finding is that certain properties of the optimal join order have an impact on the performance of AO *