Plan Enumeration

The search space of execution plans is incomprehensibly vast—potentially billions or trillions of possibilities for complex queries. Yet the query optimizer must navigate this space quickly, typically in milliseconds. How does it accomplish this seemingly impossible task?

The answer lies in plan enumeration—the systematic process of generating and evaluating candidate execution plans. But "systematic" doesn't mean "exhaustive." Modern optimizers employ sophisticated algorithms that intelligently explore the most promising regions of the search space while safely ignoring vast regions of poor alternatives.

In this page, we'll examine the major enumeration strategies, from the elegant dynamic programming approach that guarantees optimality within its scope, to heuristic and randomized methods that trade guarantees for speed.

Plan enumeration is the process of generating candidate execution plans from the search space. The fundamental challenge is:

Generate enough plans to find a good solution, but not so many that optimization becomes prohibitively expensive.

This framing reveals enumeration as a search problem with the following characteristics:

1.1 What Are We Searching For?

We seek the execution plan with minimum estimated cost. The plan includes:

• Join ordering (which tables join in what sequence)
• Join algorithms (hash, merge, nested-loop for each join)
• Access methods (scan, index scan, etc. for each table)
• Operator placement (where filters, projections are applied)

1.2 What Constraints Must We Satisfy?

• Time Budget: Enumeration must complete within a reasonable fraction of expected query time
• Correctness: Every enumerated plan must be semantically valid
• Completeness (Ideal): The optimal plan should be among those enumerated

1.3 The Enumeration Taxonomy

Enumeration strategies fall into several categories based on their approach:

Dynamic programming (DP) is the dominant algorithm for join order enumeration in relational databases. Introduced in IBM's System R and refined over decades, DP exploits a key property of join ordering: optimal substructure.

2.1 The Principle of Optimal Substructure

Optimal substructure means:

The optimal plan for joining a set of tables S can be built from optimal plans for subsets of S.

Specifically, if the optimal plan for tables {A, B, C, D} joins the result of {A, B} with the result of {C, D}, then:

• The plan for {A, B} must be optimal among all plans for {A, B}
• The plan for {C, D} must be optimal among all plans for {C, D}

This property enables bottom-up construction of the optimal plan.

2.2 The System R Algorithm (Left-Deep)

The classic System R algorithm enumerates left-deep join orderings:

1. Initialize: For each single table t:
      BestPlan[{t}] = best access method for t
      
2. For size = 2 to n:  // n = number of tables
      For each subset S of size 'size' that is connected:
          For each t in S where S - {t} is connected:
              For each join algorithm J:
                  plan = BestPlan[S - {t}] JOIN[J] AccessMethod[t]
                  if cost(plan) < cost(BestPlan[S]):
                      BestPlan[S] = plan
                      
3. Return BestPlan[{all tables}]

Key Insight: Instead of evaluating n! orderings, we evaluate O(n × 2^n) subproblems—exponential, but much smaller than factorial for practical n.

2.3 Complexity Analysis

Time Complexity: O(3^n) for bushy trees, O(n × 2^n) for left-deep

• We enumerate O(2^n) subsets
• For each subset, we consider O(2^k) partitions (k = subset size)
• Summing over all subsets gives O(3^n) by the binomial theorem

Space Complexity: O(2^n) to store best plans for all subsets

2.4 Practical Thresholds

Given the exponential complexity, DP becomes impractical for large n:

Most systems switch to heuristics for queries joining more than 10-15 tables.

Pure cost comparison misses an important consideration: the order of tuples in intermediate results matters. An intermediate result sorted on a particular attribute might enable cheaper subsequent operations.

3.1 The Problem

Consider two plans for the same subset {A, B}:

• Plan 1: Hash join, cost 100, result unordered
• Plan 2: Merge join, cost 120, result sorted on join key

Pure DP would keep only Plan 1. But if we later need to:

• Join with C using merge join (requires sorted input)
• Apply ORDER BY on the join key

Plan 2 might be better overall because it avoids a later sort.

3.2 The Solution: Track Physical Properties

Instead of keeping one best plan per subset, keep:

• Best unordered plan
• Best plan for each interesting order

An interesting order is a sort order that might benefit later operations:

• Join attributes for potential merge joins
• GROUP BY columns
• ORDER BY columns
• DISTINCT columns

3.3 Impact on Complexity

With k interesting orders, we keep up to k+1 plans per subset, increasing space to O(k × 2^n) and time proportionally. However, k is typically small (often ≤10), so this overhead is acceptable for the significant plan quality improvements.

3.4 Physical Property Propagation

Beyond ordering, some systems generalize to physical properties:

• Partitioning: Data distribution across nodes (for parallel/distributed)
• Compression: Whether data is compressed
• Location: Which node holds the data

This generalization is essential for distributed query optimization.

When DP becomes too expensive (many tables, complex predicates), optimizers fall back to heuristic enumeration—methods that don't guarantee optimality but produce reasonable plans quickly.

4.1 Greedy Join Ordering

The simplest heuristic: greedily extend the join order by choosing the next table that minimizes cost increase:

1. Start with smallest table (or most selective)
2. Repeat until all tables joined:
   a. For each remaining table t:
      - Estimate cost of joining current result with t
   b. Add the table that minimizes cost
3. Return the constructed order

Complexity: O(n²) comparisons—dramatically less than O(3^n) DP Quality: Often 2-5× worse than optimal, occasionally much worse

4.2 Minimum Selectivity Heuristic

Choose join order to minimize intermediate result sizes by joining most selective relationships first:

1. Estimate selectivity of each join condition
2. Order joins from most selective (smallest result ratio) to least
3. Apply this order, breaking ties by table size

Intuition: Smaller intermediate results → less work at each step Weakness: Ignores index availability, doesn't consider algorithm costs

4.3 Common Heuristic Rules

Most optimizers apply certain rules as "no-brainer" improvements, avoiding the need to enumerate alternatives:

4.4 When Heuristics Fail

Heuristics make decisions based on local information, which can lead to globally poor choices:

Example: Table A has 1M rows, B has 100 rows, C has 10K rows.

• Heuristic: Join small first → B ⋈ C, then result ⋈ A
• But: B ⋈ C might have selectivity < 1% due to key constraint
• Better: A ⋈ B first uses index on A, producing 100 rows

Heuristics lack the global view that DP provides.

For very large queries where even heuristics struggle, randomized enumeration provides an alternative. Instead of systematically exploring the space, these methods sample it randomly, relying on probability to find good plans.

5.1 Random Walk / Iterative Improvement

Start with an arbitrary valid plan and repeatedly make random modifications:

1. Generate initial plan P (random or heuristic)
2. Repeat for k iterations:
   a. Generate neighbor plan P' by:
      - Swapping two adjacent joins
      - Changing one join algorithm
      - Changing one access method
   b. If cost(P') < cost(P): P = P'
3. Return best P found

This is essentially hill climbing in the cost landscape.

5.2 Simulated Annealing

To escape local minima, simulated annealing occasionally accepts worse plans:

1. Generate initial plan P, set temperature T = T_initial
2. Repeat until T is cold:
   a. Generate random neighbor P'
   b. if cost(P') < cost(P):
        P = P'  // Always accept improvements
   c. else:
        Accept P' with probability exp(-(cost(P')-cost(P))/T)
   d. T = cooling_rate × T
3. Return best P found

At high temperatures, worse plans are often accepted, enabling exploration. As temperature decreases, the algorithm focuses on refinement.

5.3 Genetic Algorithms

Some optimizers use genetic algorithms (GAs) for plan enumeration:

1. Population: Maintain a set of candidate plans
2. Selection: Choose plans with lower costs more often
3. Crossover: Combine two plans to create offspring
4. Mutation: Randomly modify plans
5. Evolution: Repeat for several generations

GAs can explore diverse regions of the search space simultaneously.

5.4 When to Use Randomized Methods

Pruning eliminates portions of the search space without explicitly evaluating them. Effective pruning can reduce exponential search to tractable levels.

6.1 Branch and Bound

Maintain a bound on the best solution found so far. If a partial plan's cost already exceeds the bound, abandon it:

1. Initialize best_cost = ∞
2. During enumeration of partial plan P:
   a. Compute lower_bound(P) = cost so far + min possible completion cost
   b. If lower_bound(P) ≥ best_cost: PRUNE (skip this branch)
   c. If P is complete and cost(P) < best_cost: 
        best_cost = cost(P)

Key Challenge: Computing a good lower bound. Loose bounds prune little; tight bounds are expensive to compute.

6.2 Dominance Pruning

If plan A dominates plan B (A is better in all respects), B can be eliminated:

Plan A dominates Plan B if:
  - cost(A) ≤ cost(B)
  AND
  - A's physical properties are at least as good as B's
    (e.g., A is sorted on more useful columns)

Dominated plans can never be part of an optimal final plan.

6.3 Cardinality-Based Pruning

Some plans can be identified as poor based on cardinality alone:

Cartesian Product Detection: Any plan producing a Cartesian product is almost certainly suboptimal if alternatives exist.

Result Size Bounds: If a partial plan produces an intermediate result larger than the full Cartesian product of remaining tables, it's likely suboptimal.

6.4 Search Space Restriction

The most aggressive pruning: simply don't consider certain plan types:

6.5 Pruning Trade-offs

Aggressive pruning speeds optimization but risks missing the optimal plan:

Example: Sometimes a Cartesian product followed by a selective filter is optimal if the filter is very selective and other join paths are expensive. Blanket prohibition would miss this.

Good optimizers use adaptive pruning: more aggressive for complex queries, more thorough for simpler ones where exhaustive search is affordable.

Modern database systems use sophisticated enumerator architectures that combine multiple strategies:

7.1 Cascades / Volcano Framework

The Cascades framework (used in SQL Server, derivatives in many systems) represents the state of the art:

Key Concepts:

• Memo Structure: Hash-tables storing equivalent plans for each expression
• Pattern Matching: Transformation rules fire when patterns match
• Top-Down Enumeration: Start from goal, recursively optimize sub-goals
• Goal-Driven: Only compute what's needed for the current goal

Optimize(Goal G):
  1. If memo contains solution for G: return it
  2. Apply logical transformations to generate equivalent logical expressions
  3. Apply physical transformations to generate physical plans
  4. For each required input, recursively Optimize(sub-goal)
  5. Cost complete plans, prune dominated ones
  6. Memoize and return best plan for G

7.2 Benefits of Cascades

Memoization: Avoids recomputing overlapping subproblems across rules. Extensibility: New operators/rules added without modifying core algorithm. Flexibility: Mix of logical and physical optimization in unified framework. Pruning Integration: Natural points for branch-and-bound.

7.3 Adaptive Query Optimization

Cutting-edge systems perform adaptive optimization:

Compile-Time Adaptation:

• Adjust enumeration thoroughness based on query complexity
• Use more resources for high-value queries (determined by statistics or hints)
• Timeout with fallback to heuristic plan

Runtime Adaptation:

• Monitor actual cardinalities during execution
• Re-optimize mid-query if estimates were wrong
• Adjust operator parameters (e.g., hash table size)

Oracle's Adaptive Query Processing and SQL Server's Adaptive Joins exemplify runtime adaptation.