Optimal Ordering of Selections and Joins in Acyclic Queries with Expensive Predicates
Wolfgang Scheufele, Guido Moerkotte · 1996
The generally accepted optimization heuristics of pushing selections down does not yield optimal plans in the presence of expensive predicates. Therefore, several researchers have proposed algorithms for the optimal ordering of expensive joins and selections in a query evaluation plan. All of these algorithms have an exponential run time. For a special case, we propose a polynomial algorithm which -- in one integrated step -- computes the optimal join order and places expensive predicates optimally within the join tree. The special case is characterized by the following statements: 1. only left-deep trees are considered, 2. no cross-products are considered, 3. the cost function has to exhibit the ASI property, and 4. cheap selections are pushed before-hand. 1 Introduction Traditional work on algebraic query optimization has mainly focused on the problem of ordering joins in a query. Restrictions like selections and projections are generally treated by "push-down rules". According to t...