Dynamic Programming

In computer science, dynamic programming is an algorithmic technique that transforms exponential problems into polynomial ones by recognizing and exploiting overlapping subproblems. It's the secret weapon behind efficient solutions to shortest paths, sequence alignment, knapsack problems—and query optimization.

The insight that join ordering exhibits optimal substructure—the optimal plan for tables {A,B,C} builds upon optimal plans for subsets like {A,B} and {C}—is one of the most important discoveries in database systems. The System R optimizer (IBM, 1979) pioneered the use of dynamic programming for join ordering, and its approach remains the foundation of most cost-based optimizers today.

This page takes you deep into how dynamic programming makes optimal join ordering tractable, transforming a problem with potentially factorial complexity into one solvable in polynomial time.

Dynamic programming works when a problem has optimal substructure: the optimal solution to the whole problem is composed of optimal solutions to its subproblems.

The join ordering insight:

Consider finding the optimal plan for joining tables {A, B, C}. Any final join must combine two disjoint subsets:

{A, B, C} = {A, B} ⋈ {C}
          = {A, C} ⋈ {B}
          = {A} ⋈ {B, C}
          = {B, C} ⋈ {A}
          = {B} ⋈ {A, C}
          = {C} ⋈ {A, B}

Critical observation: For the plan {A, B} ⋈ {C} to be optimal overall, the subplan for {A, B} must itself be optimal among all ways to join A and B.

Why? If there were a better way to join A and B (call it {A, B}'), then {A, B}' ⋈ {C} would be cheaper than {A, B} ⋈ {C}, contradicting our assumption that the original plan was optimal.

Formal statement:

Let OPT(S) denote the cost of the optimal plan for joining the set of tables S. Then:

OPT(S) = min over all partitions {S₁, S₂} of S where S₁ ∪ S₂ = S and S₁ ∩ S₂ = ∅:
         OPT(S₁) + OPT(S₂) + JoinCost(S₁, S₂)

The optimal cost for S is the minimum over all ways to partition S into two non-empty subsets, of the cost to optimally join each subset plus the cost to join them together.

The System R optimizer (Selinger et al., 1979) introduced the dynamic programming approach to join ordering. Here's the algorithm:

Phase 1: Single-table access plans

For each table R in the query, enumerate all access methods:

• Sequential scan
• Each available index (scan, seek)
• For each method, compute cost and output properties

Store the best plan(s) for each table in a table keyed by {R}.

Phase 2: Build optimal plans bottom-up

Example walkthrough:

Joining tables {A, B, C}:

Iteration 1 (size = 1):
  Best({A}) = SeqScan(A), cost = 100
  Best({B}) = IdxScan(B), cost = 50
  Best({C}) = SeqScan(C), cost = 200

Iteration 2 (size = 2):
  Consider {A, B}:
    Plan: Best({A}) NLJ Best({B}) = NLJ(SeqScan(A), IdxScan(B)), cost = 100 + 50 + 500 = 650
    Plan: Best({A}) HJ Best({B}) = HJ(...), cost = 100 + 50 + 150 = 300
    → Best({A,B}) = HJ(...), cost = 300

  Consider {A, C}:
    Plan: HJ(...), cost = 400
    → Best({A,C}) = HJ(...), cost = 400

  Consider {B, C}:
    Plan: HJ(...), cost = 350
    → Best({B,C}) = HJ(...), cost = 350

Iteration 3 (size = 3):
  Consider {A, B, C}:
    Plan: Best({A,B}) ⋈ Best({C}) = HJ(...) ⋈ SeqScan(C)
          cost = 300 + 200 + 180 = 680
    Plan: Best({A,C}) ⋈ Best({B}) = HJ(...) ⋈ IdxScan(B)
          cost = 400 + 50 + 120 = 570
    Plan: Best({A}) ⋈ Best({B,C}) = SeqScan(A) ⋈ HJ(...)
          cost = 100 + 350 + 200 = 650
    → Best({A,B,C}) = Best({A,C}) ⋈ Best({B}), cost = 570

Final answer: Join A with C first (hash join), then join the result with B.

The heart of the dynamic programming approach is the memoization table (often called the DP table or plan dictionary)—a data structure that stores optimal subplans.

Table structure:

The DP table maps subsets of tables to their optimal plans:

Key: S (a subset of tables, often represented as a bitmask)
Value: {
  best_plan: the optimal plan for joining S,
  best_cost: the cost of that plan,
  output_cardinality: rows produced,
  physical_properties: ordering, partitioning, etc.
}

Efficient subset representation:

For n tables, subsets are often represented as n-bit integers (bitmasks):

Tables: A, B, C, D (4 tables)

{A} → 0001 = 1
{B} → 0010 = 2
{C} → 0100 = 4
{D} → 1000 = 8
{A, B} → 0011 = 3
{A, C} → 0101 = 5
{A, B, C, D} → 1111 = 15

This allows:

• O(1) set membership: (S & (1 << i)) != 0
• O(1) set union: S₁ | S₂
• O(1) set difference: S₁ & ~S₂
• Easy iteration over subsets

Iteration over subsets:

To enumerate all subsets of a set S, we use bit tricks:

Let's analyze the time and space complexity of the dynamic programming algorithm.

Number of subproblems:

For n tables, there are 2ⁿ possible subsets. We solve the optimization problem for each subset.

Work per subproblem:

For a subset S of size k, we consider all partitions into non-empty subsets. The number of such partitions is:

(Number of proper subsets) / 2 = (2ᵏ - 2) / 2 = 2ᵏ⁻¹ - 1

For each partition, we try multiple join methods (constant factor j).

Total time complexity:

Summing over all subsets:

Derivation of O(3ⁿ):

Using the binomial identity:

∑(k=0 to n) C(n,k) × 2ᵏ = (1+2)ⁿ = 3ⁿ

Our sum is similar, yielding O(3ⁿ) time complexity.

Space complexity:

We store one entry per subset: O(2ⁿ) entries.

Each entry contains a plan (O(n) for tree structure) and metadata: O(n × 2ⁿ) total.

The basic DP algorithm keeps one best plan per subset. But this can miss globally optimal plans that leverage sorted outputs. Interesting orders extend DP to track multiple plans per subset.

The problem:

Consider:

SELECT * FROM A JOIN B ON A.x = B.x ORDER BY A.x;

• Plan 1: Hash join (cost 100), then sort (cost 50) = 150
• Plan 2: Sort-merge join (cost 130), already sorted = 130

If we only keep the cheapest plan for {A,B} (hash join at 100), we miss that sort-merge is globally better because it avoids final sort.

Solution: Track plans per interesting order

Instead of:

DP[{A,B}] = <best_plan, cost>

We maintain:

DP[{A,B}][no_order] = <HJ plan, cost=100>
DP[{A,B}][ordered_by_A.x] = <SMJ plan, cost=130>
DP[{A,B}][ordered_by_B.y] = <another SMJ plan, cost=140>

Identifying interesting orders:

An order is "interesting" if it benefits a downstream operator:

1. ORDER BY clause in the query
2. GROUP BY clause (sorted aggregation possible)
3. Join predicates (enables merge join)
4. DISTINCT elimination
5. UNION/INTERSECT/EXCEPT operations
6. Partition-wise operations in parallel execution

Modified DP with interesting orders:

for each subset S:
  for each interesting order O (including "no order"):
    for each partition (S₁, S₂) of S:
      for each order O₁ compatible with O for S₁:
        for each order O₂ compatible with O for S₂:
          leftPlan = DP[S₁][O₁]
          rightPlan = DP[S₂][O₂]
          for each join method:
            resultOrder = ComputeOutputOrder(join_method, O₁, O₂)
            if resultOrder matches O or no sorting needed:
              cost = Cost(leftPlan) + Cost(rightPlan) + JoinCost
              UpdateDP(S, resultOrder, plan, cost)

Complexity impact:

If there are k interesting orders:

• Space: O(k × 2ⁿ)
• Time: O(k² × 3ⁿ)

Typically k is small (< 10 for most queries), so overhead is manageable.

Interesting orders are a special case of physical properties—characteristics of plan outputs beyond logical equivalence. Modern optimizers generalize DP to handle multiple property types:

Property Types:

The requirement and provider model:

The Cascades/Volcano optimizer framework formalizes this:

1. Requirements: Properties a parent operator needs from its child

   • Example: Merge join requires sorted inputs

2. Providers: Properties an operator's output provides

   • Example: Sort operator provides ordered output

3. Enforcers: Operators that add missing properties

   • Example: Sort enforcer adds ordering
   • Example: Exchange enforcer changes partitioning

Optimization as requirement propagation:

Plan for ORDER BY A.x:
  Require: output sorted by A.x
  
  Option 1: Find plan already sorted by A.x
            → Use as-is
  
  Option 2: Find cheapest unsorted plan + Sort enforcer
            → Add explicit sort
  
  Pick cheaper option

This generalizes beautifully to any number of property types.

A significant optimization reduces the search space by avoiding Cartesian products (cross-joins without join predicates). In most queries, cross products are extremely expensive and rarely optimal.

The connected subgraph restriction:

Instead of considering all 2ⁿ subsets, only consider subsets where the tables are connected in the query's join graph:

Query: A JOIN B ON A.x = B.x
       JOIN C ON B.y = C.y
       JOIN D ON C.z = D.z

Join Graph:
  A ─── B ─── C ─── D

Connected subsets:     Disconnected (skip):
  {A}, {B}, {C}, {D}   {A, C}, {A, D}, {B, D}
  {A, B}               {A, C, D} (no edge A-C or A-D)
  {B, C}, {C, D}       etc.
  {A, B, C}, {B, C, D}
  {A, B, C, D}

Benefits:

Query graph shapes and complexity:

For well-structured queries (chains, stars), optimization is dramatically faster.

Implementation detail:

Enumerating connected subsets requires tracking the join graph. During DP:

for each connected subset S ordered by size:
  for each way to split S into S₁ and S₂ where:
    - S₁ and S₂ are both connected
    - S₁ and S₂ share a join edge (the joining predicate)
  combine plans for S₁ and S₂