An experimental study on the complexity of left-deep join ordering
problems for cyclic queries

Birgitta König-Ries, Sven Helmer, Guido Moerkotte

           Not only in deductive databases, logic programming, and
           constraint satisfaction problems but also in object bases where
           each single dot in a path expression corresponds to a join,
           the optimizer is faced with the problem of ordering large
           numbers of joins.  This might explain the renewed interest
           in the join ordering problem.  Although many join ordering
           techniques have been invented and benchmarked over the last
           years, little is known on the actual effectiveness of the
           developed methods and the cases where they are bound to fail.
           The problem attacked is the discovery of parameters and their
           qualitative influence on the complexity of single problem
           instances and on the effectiveness of join ordering techniques
           including search procedures, heuristics, and probabilistic
           algorithms. Thus an extensive analysis of the search space
           is carried out, with particular emphasis on the existence
           of phase transitions in this space and on the influence the
           parameters have on these transitions.

           Having these parameters on hand serves two important tasks.
           (1) For a given heuristic, parameter combinations can be
           identified where it performs nearly optimal and others
           where it performs badly.  Hence, on the one hand, we can be
           confident about the results of a heuristic for well determined
           cases and, on the other hand, can avoid the application of a
           heuristic where it is bound to fail.  (2) When benchmarking
           join ordering heuristics, one had---up to now---to choose a
           benchmark arbitrarily. Given the parameters which influence
           the complexity of a join ordering problem it becomes possible
           to consciously design challenging benchmarks.