For a DBMS that provides support for a declarative query language like SQL the query optimizer
is a crucial piece of software. The declarative nature of a query allows it to be translated
into many equivalent evaluation plans. The process of choosing a suitable plan from all
alternatives is known as query optimization. The basis of this choice are a cost model and
statistics over the data. Essential for the costs of a plan is the execution order of join
operations in its operator tree since the runtime of plans with different join orders can vary
by several orders of magnitude. An exhaustive search for an optimal solution over all possible
operator trees is computationally infeasible. To decrease complexity the search space must be
restricted. Therefore a well-accepted heuristic is applied: All possible bushy join trees are
considered while cross products are excluded from the search. There are two efficient
approaches to identify the best plan: bottom-up and top- down join enumeration. But only the
top-down approach allows for branch-and-bound pruning which can improve compile time by
several orders of magnitude while still preserving optimality. Hence this book focuses on the
top-down join enumeration. In the first part we present two efficient graph-partitioning
algorithms suitable for top-down join enumer- ation. However as we will see there are two
severe limitations: The proposed algo- rithms can handle only (1) simple (binary) join
predicates and (2) inner joins. There- fore the second part adopts one of the proposed
partitioning strategies to overcome those limitations. Furthermore we propose a more generic
partitioning framework that enables every graph-partitioning algorithm to handle join
predicates involving more than two relations and outer joins as well as other non-inner joins.
As we will see our framework is more efficient than the adopted graph-partitioning algorithm.
The third part of this book discusses the two branch-and-bound pruning strategies that can be
found in the literature. We present seven advancements to the combined strategy that improve
pruning (1) in terms of effectiveness (2) in terms of robustness and (3) most importantly
avoid the worst-case behavior otherwise observed. Different experiments evaluate the
performance improvements of our proposed methods. We use the TPC-H TPC-DS and SQLite test
suite benchmarks to evalu- ate our joined contributions. As we show the average compile time
improvement in those settings is 100% when compared with the state of the art in bottom-up join
enu- meration. Our synthetic workloads show even higher improvement factors.
