Optimizing Join Order with Dynamic Programming

The Combinatorial Explosion of Join Ordering

When a query joins $N$ tables, the number of possible join orders grows explosively. The optimizer can't simply generate and cost every single plan—it would take far longer than just running a mediocre plan.

For example, for a 4-table join (A, B, C, D), you could have plans like:

• (((A ⋈ B) ⋈ C) ⋈ D)
• ((A ⋈ B) ⋈ (C ⋈ D))
• ((C ⋈ A) ⋈ D) ⋈ B)
• ...and many, many more.

The number of structurally different binary trees is given by Catalan numbers, and when you factor in the different permutations of tables, the total number of plans becomes immense. For just 10 tables, there are over 175,000 different join trees.

The pioneering optimizer in IBM's System R solved this by making two key simplifying assumptions:

1. Only consider left-deep join trees, which have the form (...((R1 ⋈ R2) ⋈ R3) ⋈ ... ⋈ Rn).
2. Do not consider plans that involve Cartesian products if a join with a predicate is possible.

Left-deep plans are particularly well-suited for pipelined execution, where the output of one join is streamed directly as the input to the next, minimizing the need for memory to store large intermediate results. Let's quickly see why.

Even with these simplifications, the search space is large. The solution is to explore it intelligently using dynamic programming.

The System R Dynamic Programming Algorithm

The core idea is to solve the join ordering problem in a bottom-up fashion. We find the best plans for small sets of tables first, and then use those results to find the best plans for progressively larger sets. This relies on the principle of optimality: an optimal plan for joining $k$ tables must be composed of an optimal plan for joining $k-1$ of those tables, joined with the remaining table.

Let's see this elegant algorithm in action.

The Algorithm in Detail

As you saw in the video, the algorithm proceeds in passes, filling a table (or cache) of optimal subplans. Let's formalize this.

For a join of N tables {R1, R2, ..., Rn}:

• Pass 1: Find best plans for subsets of size 1.

  • For each table Ri, find the cheapest access path (e.g., file scan, or an index scan if a predicate applies).
  • Store (Ri, plan, cost) in the cache.

• Pass 2: Find best plans for subsets of size 2.

  • For each subset {Ri, Rj}, find the cost of optimal_plan(Ri) ⋈ Rj.
  • The cost is cost(optimal_plan(Ri)) + cost(access Rj) + join_cost.
  • Compare this to optimal_plan(Rj) ⋈ Ri.
  • Store the cheaper of the two plans as the optimal plan for {Ri, Rj}.

• Pass k: Find best plans for subsets of size k.

  • For each subset S of size k, consider every way to split it into an optimal plan for a subset of size k-1 and a single table.
  • For each split (S - {Ri}, Ri), calculate the cost: cost(optimal_plan(S - {Ri})) + cost_to_join_with_Ri.
  • The cost for optimal_plan(S - {Ri}) is retrieved directly from the cache (computed in Pass k-1).
  • The cheapest plan found across all possible splits becomes the optimal plan for subset S.

This process continues until k = N, at which point we have the optimal plan for the entire set of tables.

To help solidify this process, let's look at another excellent resource that visualizes the DP table being populated.

Refinements and Modern Approaches

The basic System R algorithm is powerful, but real-world optimizers add more sophistication. Two important refinements are interesting orders and using a join graph.

• Interesting Orders: A sub-plan might not be the absolute cheapest, but it might produce tuples sorted in an "interesting" way (e.g., sorted on a future join key). This could make a subsequent Sort-Merge Join much cheaper. Optimizers often keep track of the cheapest plan for each interesting order, not just the single cheapest overall plan.
• Join Graph: Instead of trying to join all possible sub-plans, the optimizer first looks at the WHERE clause to build a graph connecting tables that have explicit join predicates. It then only enumerates join orders that correspond to traversing this graph, effectively pruning away all plans that would require a Cartesian product.

Let's watch a short video that explains these two key ideas.

The System R DP algorithm (DPsize in the literature) is still the foundation. However, for queries with very complex predicates (e.g., R1.a + R2.b = R3.c) or a very large number of tables, more advanced techniques are needed.

Conclusion

You now understand the core logic that database systems use to tackle one of their hardest problems: finding an efficient join order. By systematically building solutions to small problems and reusing those solutions to solve larger ones, the dynamic programming approach tames a problem that would otherwise be computationally intractable.

Key Takeaways:

• The number of possible join orders for a query grows factorially, making exhaustive search impossible.
• The System R dynamic programming algorithm provides a systematic, bottom-up approach to find an optimal join order.
• The algorithm works in passes, finding optimal plans for subsets of tables of increasing size (1, 2, 3, ..., N).
• It relies on the principle of optimality, caching and reusing the costs of optimal sub-plans to build larger plans.
• Heuristics like considering only left-deep plans and refinements like using a join graph and tracking interesting orders are crucial for making the algorithm efficient and effective in practice.

Preview of the Next Lesson

We have now determined the best logical plan—that is, the optimal sequence of joins. The final step is to create the full physical plan. In the next lesson, we will see how the optimizer translates this chosen logical plan into an executable physical plan by selecting the most appropriate physical algorithm (e.g., Hash Join, Index Nested Loop Join) for each logical operator.