Search Space

Imagine you're planning a road trip visiting 10 cities. How many different routes could you take? The answer—over 3.6 million—hints at a combinatorial explosion that query optimizers face with every query. But the optimizer's challenge is far worse: it's not just choosing an order, but also selecting how to travel between each city, what vehicle to use, whether to make stops, and countless other decisions.

The search space is the complete set of all possible execution plans for a query. Understanding its structure, size, and properties is essential for understanding how optimizers work—and why they sometimes fail. In this page, we'll map this vast landscape and understand the mathematical principles that govern it.

The search space for a query is the set of all possible execution plans that correctly implement the query's semantics. Each point in this space represents a distinct way of executing the query—a unique combination of operators, algorithms, orderings, and access methods.

Formally, we can define the search space as:

Search Space S(Q) = { P | P is a valid execution plan for query Q }

Where a valid plan P satisfies:

1. Semantic Correctness: P produces the same result as any other valid plan for Q
2. Completeness: P includes all necessary operations to produce the result
3. Executability: P uses only operators and algorithms available in the system

The search space is implicit—it's not explicitly enumerated in memory but is defined by the grammar of possible plan structures. The optimizer explores this space using generation rules that produce valid plans.

1.1 Dimensions of the Search Space

Every execution plan is defined by choices across multiple dimensions. Each dimension is independent, and the total search space is the Cartesian product of choices across all dimensions:

Among all dimensions of the search space, join ordering typically dominates complexity. The order in which tables are joined can affect query performance by orders of magnitude, and the number of possible orderings grows super-exponentially with the number of tables.

2.1 Why Join Order Matters

Consider a simple example with three tables:

• Orders: 1,000,000 rows
• Customers: 50,000 rows
• Products: 10,000 rows

Query: Find orders from premium customers for electronics products.

SELECT o.order_id, c.name, p.product_name
FROM orders o
JOIN customers c ON o.customer_id = c.id
JOIN products p ON o.product_id = p.id
WHERE c.tier = 'premium' AND p.category = 'electronics';

The filter on customers yields ~5,000 rows (10%). The filter on products yields ~1,000 rows (10%). But orders has no direct filter.

The difference is approximately 20× in this example, and real-world differences can exceed 1000×. This enormous variance makes join order optimization the primary focus of most query optimizers.

2.2 Counting Join Orderings

For n tables, how many join orderings exist? The answer depends on whether we consider linear (left-deep/right-deep) or bushy trees:

Linear Trees (Left-Deep): In a left-deep tree, the inner relation of each join is always a base table. The number of left-deep orderings is simply the number of table permutations:

$$\text{Left-deep orderings} = n!$$

For commutative joins (where A ⋈ B = B ⋈ A), this reduces to n!/2.

Bushy Trees: Bushy trees allow arbitrary nesting—any intermediate result can join with any other. The number of distinct bushy tree shapes follows the Catalan numbers:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!n!}$$

Catalan(n) × n! gives the total bushy orderings, growing approximately as 4^n/n^1.5.

Beyond join ordering, the optimizer must choose which algorithm to use for each operator. This creates another multiplicative factor in the search space.

3.1 Join Algorithm Options

Most database systems support multiple join algorithms, each optimal for different data characteristics:

For a query with k joins, if each has a choice of j algorithms, this dimension contributes j^k plans.

3.2 Access Method Options

For each base table, the optimizer chooses how to retrieve data:

With a average of a access methods per table and t tables, this contributes a^t plans.

3.3 Multiplicative Effect

The total algorithm selection space for a query with t tables and t-1 joins, with j join algorithms and a access methods:

$$\text{Algorithm Space} = a^t \times j^{t-1}$$

For 5 tables with 3 access methods each and 4 join algorithms: $$3^5 \times 4^4 = 243 \times 256 = 62,208 \text{ algorithm combinations}$$

This multiplies with join orderings. A 5-table query might have: $$60 \text{ (join orders)} \times 62,208 \text{ (algorithms)} = 3.7 \text{ million plans}$$

The shape of the execution plan tree is itself a choice that affects both the search space size and the execution characteristics. Understanding plan topologies is crucial for optimization strategy.

4.1 Left-Deep Trees

In a left-deep tree, the right input of every join is always a base table. The left input is either a base table (for the first join) or the result of a previous join.

        ⋈
       / 
      ⋈   T4
     / 
    ⋈   T3
   / 
  T1  T2

Characteristics:

• Pipelining: Results can flow directly from one join to the next
• Memory Efficient: Only one intermediate result "in flight"
• Good for Indexed Inner: Each join can probe an index on the base table
• Search Space: n!/2 orderings (polynomial in the exponent)

4.2 Right-Deep Trees

The mirror image—left input of every join is a base table:

    ⋈
   / 
  T1  ⋈
     / 
    T2  ⋈
       / 
      T3  T4

Characteristics:

• Bulk Operations: Good for hash joins with materialized build phases
• Parallelism Friendly: All base tables can be scanned concurrently
• Memory Intensive: Multiple intermediate results active simultaneously
• Search Space: Same as left-deep

4.3 Bushy Trees

Bushy trees allow any structure—intermediate results can join with other intermediate results:

         ⋈
        / 
       ⋈   ⋈
      / \ / 
     T1 T2 T3 T4

Characteristics:

• Maximum Flexibility: Can exploit opportunities left-deep misses
• Parallelism: Sub-trees can execute concurrently
• Complex Optimization: Much larger search space
• Memory Pressure: Multiple intermediate results
• Search Space: Catalan(n-1) × n!, grows as 4^n/n^1.5

4.4 Why Left-Deep Dominates

Despite bushy trees' flexibility, most commercial optimizers focus on left-deep trees:

1. Smaller Search Space: n! vs 4^n growth
2. Pipelining: Memory efficiency and response time
3. Good Enough: Left-deep plans are often within 10-20% of bushy optimal
4. Predictability: Easier to estimate cost and memory
5. Hardware Match: Traditional disk-based systems favor sequential access patterns

However, modern analytical systems with abundant memory and parallel hardware increasingly explore bushy plans.

Beyond joins, the placement of other operators—selections, projections, aggregations—creates additional search space dimensions.

5.1 Selection (Filter) Placement

Filters can often be applied at multiple points in the plan:

Example Query:

SELECT * FROM orders o JOIN customers c ON o.cust_id = c.id
WHERE c.country = 'USA' AND o.amount > 1000;

Placement Options:

1. Early (Pushed Down): Filter tables before join
   • Filter(customers, country='USA') ⋈ Filter(orders, amount>1000)
2. Late: Filter after join
   • Filter(customers ⋈ orders, country='USA' AND amount>1000)
3. Mixed: Some early, some late (for complex predicates)

Generally, pushing selections down reduces intermediate result sizes, improving performance. But there are exceptions:

• Selective indexes might not be usable after transformation
• Complex predicates might be expensive to evaluate repeatedly
• Correlation with join conditions might make early filtering suboptimal

5.2 Projection Placement

Projections remove unneeded columns. Like selections, they can be placed at various points:

Early Projection Benefits:

• Reduced tuple width → fewer pages → less I/O
• Better cache utilization
• Smaller sort/hash memory requirements

Early Projection Risks:

• May eliminate columns needed for later operations
• Must track column dependencies carefully

5.3 Aggregation and Grouping Placement

For queries with GROUP BY, aggregation can sometimes be pushed down:

SELECT dept_id, SUM(salary) 
FROM employees e JOIN departments d ON e.dept_id = d.id
GROUP BY dept_id;

Options:

1. Join first, then aggregate
2. Pre-aggregate employees by dept_id, then join
3. For certain aggregates, post-aggregate to combine pre-aggregates

Pre-aggregation is legal only for decomposable aggregates (SUM, COUNT, MIN, MAX) and can dramatically reduce join input size.

Not all mathematically possible plans are valid. Various constraints restrict the search space:

6.1 Join Graph Constraints

The join graph of a query defines which tables can be joined directly. A join between tables A and B is only possible if there's a join predicate connecting them.

-- Join Graph:
-- Customers ── Orders ── Products
-- (customers.id = orders.cust_id)
-- (orders.prod_id = products.id)

Without a direct predicate, joining Customers with Products first would create a Cartesian product—almost always disastrous. The optimizer typically constrains the search space to avoid intermediate Cartesian products.

6.2 Outer Join Ordering Constraints

Outer joins (LEFT, RIGHT, FULL) are not freely reorderable like inner joins:

SELECT * FROM A LEFT JOIN B ON ... LEFT JOIN C ON ...;

The order of outer joins affects semantics. A LEFT JOIN B LEFT JOIN C ≠ A LEFT JOIN C LEFT JOIN B. This constrains which orderings are semantically valid.

6.3 Physical Constraints

• Index Availability: Index scans only possible where indexes exist
• Memory Limits: Hash joins may not fit if table exceeds memory budget
• Algorithm Applicability: Sort-merge join requires comparable types
• Parallelism Limits: Maximum parallel workers, partitioning requirements

Conceptualizing the search space helps developers understand optimization behavior. While the actual space has as many dimensions as there are choices, we can visualize simplified representations:

7.1 Cost Landscape Metaphor

Imagine the search space as a mountainous terrain where:

• Each point represents a possible plan
• Elevation represents cost (lower is better)
• The optimizer tries to find the lowest valley

Landscape Characteristics:

• Local Minima: Good-looking plans that aren't globally optimal
• Plateaus: Regions of similar-cost plans
• Cliffs: Small changes causing dramatic cost differences
• Ridges: Paths between good regions

7.2 Neighborhood Structure

Two plans are "neighbors" if one can be reached from the other by a single transformation:

• Swapping two adjacent tables in join order
• Changing one join's algorithm
• Switching one table's access method

The optimizer explores by moving through neighborhoods. Different search strategies (exhaustive, greedy, simulated annealing) navigate differently: