Optimization - Finding the Best Execution Strategy

The logical query plan tells us what to compute. But there are countless ways to compute it. A simple three-table join can be executed in dozens of different ways—different join orders, different join algorithms, different access methods for each table. The difference between the best and worst plan can be orders of magnitude: seconds versus hours.

Query optimization is the process of finding an efficient execution strategy from the space of equivalent alternatives. It's one of the most intellectually challenging and practically important components of database systems—the reason modern databases can efficiently process queries against terabyte-scale datasets.

This is where database systems truly shine. A declarative query becomes an optimized execution plan, transforming user intent into machine efficiency.

To appreciate query optimization, consider how dramatically execution strategies can differ in performance.

Example: Simple Join Performance Variance

Consider joining two tables:

• customers — 100,000 rows
• orders — 10,000,000 rows (100 orders per customer)

SELECT c.name, COUNT(*)
FROM   customers c JOIN orders o ON c.id = o.customer_id
GROUP BY c.name;

The performance gap can be 10,000× or more. A few seconds versus many hours. The optimizer's job is finding those efficient strategies automatically.

The Optimization Challenge:

1. Equivalence — Many different plans produce identical results
2. Exponential Space — The number of equivalent plans grows exponentially with query complexity
3. Cost Estimation — We must predict performance without actually running each plan
4. Time Constraints — Optimization itself takes time; we can't search forever
5. Changing Data — Data distributions change; yesterday's best plan isn't tomorrow's

Query optimization typically proceeds in stages, from fast heuristic transformations to more expensive cost-based searches.

Multi-Stage Optimization:

Two Schools of Optimization:

Modern systems are predominantly cost-based, but still apply heuristic rules for transformations that are universally beneficial.

Before cost-based optimization, the optimizer applies heuristic transformations—changes that are almost always beneficial regardless of data distribution.

Key Heuristic Rules:

Cost-based optimization (CBO) is the heart of modern query optimization. The optimizer generates candidate plans, estimates each plan's cost, and selects the lowest-cost alternative.

The Cost Model:

Plan cost is typically measured in abstract units combining:

Most optimizers focus primarily on I/O cost, as disk access dominates runtime for data-intensive queries.

Cost Estimation Formulas (Simplified):

Sequential Scan Cost:
  cost = (pages_in_table × seq_page_cost) + (rows × cpu_tuple_cost)

Index Scan Cost:
  cost = (index_pages × random_page_cost) + 
         (matching_rows × index_tuple_cost) + 
         (heap_fetches × random_page_cost)

Nested Loop Join Cost:
  cost = outer_cost + (outer_rows × inner_cost)

Hash Join Cost:
  cost = outer_cost + inner_cost + (hash_build_cost) + (probe_cost)

Merge Join Cost:
  cost = outer_cost + inner_cost + sort_cost_if_needed + merge_cost

These formulas require knowing row counts, page counts, and various tuning parameters.

Cost-based optimization requires statistics about the data. Without knowing how many rows match a predicate, cost estimates are guesswork.

Key Statistics Maintained:

Cardinality Estimation:

The optimizer must estimate how many rows each operation produces. This is cardinality estimation and it's notoriously difficult.

Selectivity Formulas:

Equality predicate (column = value):
  selectivity = 1 / distinct_values   (if uniform distribution)
  
Range predicate (column > value):
  selectivity = (max - value) / (max - min)
  
LIKE prefix (column LIKE 'abc%'):
  selectivity = 1 / (distinct_values^0.3)  (heuristic)
  
AND combination:
  selectivity = sel1 × sel2   (assumes independence)
  
OR combination:
  selectivity = sel1 + sel2 - (sel1 × sel2)
  
Join result:
  cardinality = (rows1 × rows2) / max(distinct1, distinct2)

The independence assumption (AND) is often wrong—real data has correlations. This is a major source of estimation errors.

The optimizer faces a combinatorial explosion: the number of possible execution plans grows exponentially with query complexity.

Join Order Explosion:

For a query joining n tables, the number of possible join orders is:

• Without considering commutativity: n!
• With bushy trees allowed: even more

For each join order, we must also choose join algorithms, access methods, and parallelism levels. The complete search space is astronomical.

Search Strategies:

Optimizers use various techniques to explore this space efficiently:

Logical operators (join, select, project) must be mapped to physical operators—specific algorithms that implement the logical operation.

Access Method Selection:

Join Algorithm Selection Heuristics:

Index Selection:

When multiple indexes exist, the optimizer evaluates which (if any) to use:

-- Table 'orders' has indexes on:
-- - order_id (primary key)
-- - customer_id
-- - order_date
-- - (customer_id, order_date) composite

SELECT * FROM orders WHERE customer_id = 100;
-- Uses: customer_id index (direct match)

SELECT * FROM orders WHERE order_date = '2024-01-15';
-- Uses: order_date index (direct match)

SELECT * FROM orders WHERE customer_id = 100 AND order_date = '2024-01-15';
-- Uses: composite index (matches both columns)

SELECT * FROM orders WHERE order_date > '2024-01-01';
-- May use: sequential scan (if range is large)
-- Or: order_date index (if range is small)