ConceptDBISAI-written · not yet proofread

Query Optimization

Query optimization finds the join order of minimal total cost for a set of tables by computing the optimal cost cost*(S) of every joinable subset S bottom-up with dynamic programming over partitions into two smaller subsets.

Know these firstQuery Plan Join $T_1 \bowtie T_2$

Formula#

Join graph. Undirected graph with one node per input table and an edge between two tables iff they can and should be joined according to the query. Two plans with table sets $S_1, S_2$ are joinable iff $S_1 \cap S_2 = \emptyset$ and the join graph has an edge between a table of $S_1$ and a table of $S_2$ .

Cost model (total cost; input tables have cost 0):

\text{size}(A \bowtie B) = \min\{\text{size}(A),\; \text{size}(B)\}

\text{cost}(A \bowtie B) = \text{cost}(A) + \text{cost}(B) + \text{size}(A \bowtie B)

Optimal cost (recursion over partitions):

\text{cost}^*(S) = \min_{\substack{S_1 \cup S_2 = S,\; S_1 \cap S_2 = \emptyset \\ S_1 \neq \emptyset,\; S_2 \neq \emptyset \\ S_1, S_2 \text{ joinable}}} \left\{ \text{cost}^*(S_1) + \text{cost}^*(S_2) + \text{size}(S_1 \bowtie S_2) \right\}, \qquad \text{cost}^*(\{T\}) = 0.

The recursion terminates because $S_1$ and $S_2$ are strict subsets of $S$ .

Dynamic programming in rounds. Plain recursion recomputes the same subsets over and over and takes exponential time, like the naive recursion $F(n) = F(n-1) + F(n-2)$ for Fibonacci numbers ( $O(2^n)$ , while computing bottom-up takes linear time). Instead compute $\text{cost}^*$ bottom-up:

Round 1: one singleton plan per input table, cost 0.
Round 2: all joinable pairs of input tables.
Round $k$ : for $k_1 = 1, \ldots, \lfloor k/2 \rfloor$ and $k_2 = k - k_1$ , combine every optimal plan of size $k_1$ with every joinable optimal plan of size $k_2$ ; keep the cheapest plan per table set.
Round $n$ : yields $\text{cost}^*(S)$ for the set $S$ of all input tables.

Properties#

Only reachable subsets: in round $k$ , do not enumerate all subsets of size $k$ ; only combine plans from earlier rounds whose union has size $k$ . Subsets that are not connected in the join graph never appear.
Joinability check: the lecture code uses a nested loop in $O(|S_1| \cdot |S_2|)$ ; in practice one uses bit masks for the table sets.
Size is plan-independent: with this cost model, $\text{size}(S_1 \bowtie S_2)$ is the minimum size of the tables in $S$ , whatever the split. The plans differ only in the cost of their intermediate results, so it pays to join the smallest table first.
Scope: only binary joins are optimised; selections, projections and the choice of join algorithm (hash join, Merge Join, index lookup via B+ Tree) are not part of this model.

# public/code/lecture-06/query-planning.py (excerpt)
for k in range(2, len(self.input_plans) + 1):
    optimal_plans[k] = {}
    for k1 in range(1, k // 2 + 1):
        k2 = k - k1
        for plan1 in optimal_plans[k1].values():
            for plan2 in optimal_plans[k2].values():
                if self.join_graph.joinable(plan1, plan2):
                    plan = QueryPlan.join(plan1, plan2)  # size = min, cost = c1 + c2 + size
                    if (plan.tables not in optimal_plans[k]
                            or plan.cost < optimal_plans[k][plan.tables].cost):
                        optimal_plans[k][plan.tables] = plan

NoteBeyond the lecture: number of plans and running time

A binary tree with $n$ leaves has $n - 1$ inner nodes; the number of tree shapes is the Catalan number $C_{n-1}$ , with $C_m = \frac{1}{m+1}\binom{2m}{m}$ ( $C_1, \ldots, C_5 = 1, 2, 5, 14, 42$ ). With the tables assigned to the leaves there are $n! \cdot C_{n-1}$ plans, or $(2n-3)!! = 1 \cdot 3 \cdot 5 \cdots (2n-3)$ if $AB$ and $BA$ count as the same join (3 for $n = 3$ , 15 for $n = 4$ ). The Catalan numbers are noted in Query Plan, not on the slides.
The DP stores at most $2^n$ subsets with their cost and size ( $O(2^n)$ space). Enumerating all pairs of disjoint subsets gives $O(3^n)$ combinations, since each table is in $S_1$ , in $S_2$ or in neither. Exponential, but far below the number of plans.

Example#

ExampleJoin graph (lecture)

SELECT title, name, role, award_name
FROM movies AS A NATURAL JOIN persons AS B NATURAL JOIN roles AS C
     NATURAL JOIN awards AS D NATURAL JOIN award_names AS E

Adjacency lists: $A: C, D$ ; $B: C, D$ ; $C: A, B, D$ ; $D: A, B, C, E$ ; $E: D$ . So $(AB)$ is not joinable, but $(AC)$ and $((AC)B)$ are.

ExampleThree tables, clique join graph

$\text{size}(A) = 100$ , $\text{size}(B) = 200$ , $\text{size}(C) = 150$ ; every pair is joinable.

Round 1: $\text{cost}^* = 0$ for $\{A\}, \{B\}, \{C\}$ with sizes 100, 200, 150.

Round 2:

Subset	Plan	$\text{cost}^*$	size
$\{A,B\}$	$(AB)$	$0 + 0 + \min(100,200) = 100$	100
$\{A,C\}$	$(AC)$	$0 + 0 + \min(100,150) = 100$	100
$\{B,C\}$	$(BC)$	$0 + 0 + \min(200,150) = 150$	150

Round 3, all splits of $\{A,B,C\}$ :

Split	Cost
$\{A\} \cup \{B,C\}$	$0 + 150 + \min(100, 150) = 250$
$\{B\} \cup \{A,C\}$	$0 + 100 + \min(200, 100) = 200$
$\{C\} \cup \{A,B\}$	$0 + 100 + \min(150, 100) = 200$

$\text{cost}^*(\{A,B,C\}) = 200$ , attained by $((AC)B)$ and $((AB)C)$ : join the smallest table first. (Slide 20 uses $\text{size}(C) = 300$ ; then $(BC)$ costs 200, $(A(BC))$ costs 300 and the optimum is again 200.)

Sources#

Slides 06, p. 13–14 (recap, plans as parenthesised expressions), p. 15 (join graph), p. 16 (cost function), p. 17 (optimal cost), p. 18 (Fibonacci), p. 19–21 (rounds, example, implementation)
DBIS_VL06 > Computing the optimal query plan
DBIS Sheet 06 (not published) (optimisation by hand and in the own DB system)