Search Strategies

At this point, you understand cost estimation, plan comparison, dynamic programming, and tree shapes. But there's a meta-problem looming: how does the optimizer search through all these possibilities efficiently?

An optimizer faces a classic exploration-exploitation trade-off:

• Exploration: Search more broadly to find better plans
• Exploitation: Use what you've learned; stop searching and execute

Spend too long optimizing and you waste time that could be spent executing. Stop too soon and you might pick a terrible plan. The search strategy determines how the optimizer balances these concerns.

This page surveys the spectrum of search strategies—from exhaustive enumeration that guarantees optimality to randomized approaches that scale to massive queries—and the practical techniques real systems use to find excellent plans within their time budgets.

The simplest conceptual strategy is exhaustive search: enumerate every possible plan, compute the cost of each, and pick the cheapest.

Algorithm:

best_plan = null
best_cost = infinity

for each possible plan P in search_space(query):
  cost = estimate_cost(P)
  if cost < best_cost:
    best_plan = P
    best_cost = cost

return best_plan

Guarantees:

• ✅ Optimal: Will find the best plan in the search space
• ✅ Complete: Explores every alternative
• ❌ Slow: Time grows exponentially with query complexity

When exhaustive works:

For small queries (≤5-6 tables), exhaustive search is practical:

• 5 tables, left-deep: 120 permutations × join algorithms ≈ few thousand plans
• At microseconds per plan, still completes in milliseconds

When it breaks down:

Dynamic programming improves this:

As we learned, DP exploits optimal substructure to avoid recomputation:

• Instead of O(n!) for each complete plan...
• We solve O(2ⁿ) subproblems, each in O(n) time...
• Yielding O(3ⁿ × n) total, dramatically better

But even O(3ⁿ) is exponential. For 20+ tables, even DP becomes impractical. We need smarter strategies.

Greedy algorithms make locally optimal choices at each step, hoping to achieve a globally good result. They're fast but offer no optimality guarantee.

Greedy Join Ordering:

remaining = {all tables}
result_so_far = null

while |remaining| > 1:
  # Find the pair with lowest join cost
  best_join = null
  best_cost = infinity
  
  for each pair (R, S) in remaining:
    if can_join(R, S):  # Have join predicate
      cost = estimate_join_cost(R, S)
      if cost < best_cost:
        best_join = (R, S)
        best_cost = cost
  
  # Perform the greedy choice
  result_so_far = join(best_join.R, best_join.S)
  remove R, S from remaining
  add result_so_far to remaining

return result_so_far

Time complexity: O(n²) for n tables—polynomial, not exponential!

Greedy pitfalls:

Greedy can make catastrophically bad choices:

Example where greedy fails:

Tables: A(1M rows), B(1K rows), C(500K rows), D(100 rows)
Join graph: A—B—C—D (chain)

Selective joins:
  B⋈D is very selective (result: 10 rows)
  A⋈B is moderately selective (result: 1K rows)
  C⋈D is selective (result: 100 rows)

Greedy choice at step 1:
  Considers only adjacent pairs: A⋈B, B⋈C, C⋈D
  Picks cheapest: A⋈B (cost 1000)
  
This commits us to processing A early, when:
  Optimal would be: (B⋈D)⋈(C) first, tiny intermediate!
  Then join with A at the end.

Greedy can't see that delaying A produces smaller intermediates.

Common heuristics:

When the search space is too large for exhaustive exploration and greedy is too myopic, randomized algorithms offer a middle ground. They explore broadly but not exhaustively, trading optimality guarantees for scalability.

Random Sampling:

best_plan = null
best_cost = infinity

for i = 1 to BUDGET:
  plan = generate_random_valid_plan(query)
  cost = estimate_cost(plan)
  if cost < best_cost:
    best_plan = plan
    best_cost = cost

return best_plan

With enough samples, you're likely to find a good plan. But pure random sampling is wasteful—most random plans are terrible.

Iterative Improvement:

current = generate_initial_plan()  # Maybe greedy start
best = current

for i = 1 to BUDGET:
  neighbor = apply_random_transformation(current)
  if cost(neighbor) < cost(current):
    current = neighbor
    if cost(current) < cost(best):
      best = current
  else:
    # Stay with current (reject worse neighbor)

return best

This hill-climbs toward local optima. Better than pure random, but gets stuck in local minima.

Simulated Annealing:

To escape local minima, occasionally accept worse moves:

How annealing works:

• High temperature: Accept many uphill moves → broad exploration
• Low temperature: Rarely accept uphill moves → local refinement
• Cooling schedule: Gradually reduce temperature over time

With enough time, simulated annealing can find excellent solutions even in massive search spaces.

Genetic algorithms model optimization as evolution: maintain a population of candidate plans, select the fittest, breed new plans through crossover and mutation, and iterate.

PostgreSQL uses GEQO (Genetic Query Optimizer) for queries exceeding its DP threshold (default: 12 tables).

The genetic algorithm structure:

Key genetic operations:

Crossover (recombination):

Combine join orders from two parents. For permutations, use methods like:

• Edge recombination: Preserve adjacency relationships
• Order crossover (OX): Copy segment from one parent, fill rest from other
• Partially mapped crossover (PMX): Map positions between parents

Mutation:

Randomly alter a chromosome:

• Swap: Exchange two table positions
• Inversion: Reverse a segment
• Scramble: Randomly reorder a segment

Selection pressure:

Balance between exploiting good solutions and maintaining diversity:

• Tournament selection: Compare k random individuals, pick best
• Roulette wheel: Probability proportional to fitness
• Elitism: Always keep the best N individuals

Branch and bound is a systematic way to explore the search space while pruning provably suboptimal branches. It's exhaustive in principle but often skips most of the space in practice.

The key insight:

If we have a current best plan with cost B, and we're exploring a partial plan P with cost already ≥ B, we can prune all plans extending P—they can only be more expensive.

Algorithm structure:

Lower bound function:

The effectiveness of branch and bound depends on tight lower bounds. A lower bound for a partial plan must be:

1. Admissible: Never overestimate the true optimal completion cost
2. Tight: Close to actual cost to enable aggressive pruning

Common lower bounds for query optimization:

Lower_Bound(partial_plan) = 
    Cost(partial_plan)               # Cost so far
  + ∑ MinAccessCost(remaining_table)  # Cheapest way to access each
  + ∑ MinJoinCost(required_joins)     # Cheapest join for each remaining

Search order matters:

Exploring promising branches first leads to finding good complete plans early, which in turn enables more pruning:

• Best-first search: Always expand the partial plan with lowest lower bound
• Depth-first with bound: Complete plans quickly to establish bounds
• Hybrid: Use heuristics to guess promising directions

Real-world optimizers don't use a single strategy—they adapt their approach based on query complexity and time constraints.

Tiered optimization (optimization levels):

Many systems define optimization levels:

Level 0 (Trivial): 
  - Single-table queries, no joins
  - Just pick access method
  - Microseconds

Level 1 (Simple):
  - Few tables, simple predicates
  - Greedy or exhaustive for small space
  - Milliseconds

Level 2 (Moderate):
  - Multiple tables, complex predicates
  - Full DP for join ordering
  - Tens of milliseconds

Level 3 (Complex):
  - Many tables, subqueries, CTEs
  - Extensive search with pruning
  - Hundreds of milliseconds

Level 4 (Full):
  - Exhaustive exploration of all alternatives
  - May include bushy trees, parallelism
  - Seconds (with timeout)

Adaptive search:

Within each level, the optimizer adapts:

1. Start with quick heuristics to establish a baseline
2. Estimate search space size based on query structure
3. Allocate time budget proportional to expected query runtime
4. Search with incremental commitment: stop when confident

Time budget formula (example):

Optimization_Budget = min(
  MAX_OPTIMIZATION_TIME,
  OPTIMIZATION_FRACTION × Estimated_Query_Time
)

where OPTIMIZATION_FRACTION might be 0.05 (5%)

For a query estimated to take 60 seconds, allow up to 3 seconds of optimization. For a 10ms query, cap optimization at 0.5ms.

Any-time algorithms:

Some optimizers use any-time algorithms that:

• Quickly produce a valid plan
• Continuously improve it as time allows
• Can be interrupted and return best-so-far

This guarantees a result within any time budget while improving quality with more time.

The Cascades/Volcano optimization framework uses a fundamentally different search paradigm: transformation rules applied within a memoization structure.

Core concepts:

1. Memo (MEMO): A data structure grouping logically equivalent expressions
2. Groups: Equivalence classes of expressions producing the same result
3. Rules: Transformations that generate new equivalent expressions or implementations
4. Top-down search: Start from the goal (full query) and work backward

Search via rule application:

Example transformation rules:

Logical Transformation Rules:
  JoinCommutativity:  A ⋈ B  →  B ⋈ A
  JoinAssociativity:  (A ⋈ B) ⋈ C  →  A ⋈ (B ⋈ C)
  SelectionPushdown:  σ(R ⋈ S)  →  σ(R) ⋈ S (if σ applies to R only)
  ProjectionPushdown: π(R ⋈ S)  →  π(π'(R) ⋈ π''(S))

Implementation Rules:
  JoinToHashJoin:     R ⋈ S  →  HashJoin(R, S)
  JoinToMergeJoin:    R ⋈ S  →  MergeJoin(R, S) [requires sorted inputs]
  JoinToNLJ:          R ⋈ S  →  NestedLoopJoin(R, S)
  TableToScan:        R      →  TableScan(R)
  TableToIdxScan:     R      →  IndexScan(R, idx) [if idx exists]

Advantages of Cascades: