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.