Cost-Based Query Optimization

Every SQL query you write can be executed in dozens, hundreds, or even millions of different ways. The query optimizer's job is to find the best way—but what does "best" even mean? How can a database system predict which execution strategy will be fastest without actually running each one?

The answer lies in cost estimation: the mathematical art of predicting how expensive a query execution plan will be before executing it. Cost-based optimizers don't guess or rely solely on rules—they build sophisticated models that estimate the resources each plan will consume, then choose the plan with the lowest predicted cost.

This page explores the foundation of cost-based optimization: how optimizers assign numerical costs to plans, what those costs represent, and why accurate estimation is both critical and extraordinarily challenging.

Cost estimation is the process of assigning a numerical value to a query execution plan that represents the predicted resources required to execute it. This cost is not measured in real time or actual resource consumption—it's a prediction based on mathematical models and statistical information about the data.

The fundamental problem:

Given a SQL query, there are typically many logically equivalent ways to execute it. Consider a simple join of three tables A, B, and C:

• We could join A with B first, then join with C
• We could join B with C first, then join with A
• We could join A with C first, then join with B
• For each ordering, we could use different join algorithms (nested loop, hash join, sort-merge)
• For each table access, we could scan the table or use various indexes

With just three tables, there might be hundreds of possible execution plans. With ten tables, there can be millions. The optimizer cannot execute all of them to find the fastest—it would take longer to find the plan than to just pick one randomly!

The cost estimation solution:

Instead of executing plans, the optimizer estimates how expensive each plan would be if executed:

1. Build a cost model that predicts resource consumption
2. Apply the model to each candidate plan
3. Compare costs and choose the lowest-cost plan
4. Execute only the chosen plan

This works because estimating cost is vastly cheaper than actually executing plans. A cost estimate might take microseconds; executing the plan might take minutes or hours.

The cost function abstraction:

Formally, a cost model defines a function:

Cost(P) = f(operators in P, cardinalities, physical characteristics)

Where:

• P is an execution plan (a tree of physical operators)
• Operators are the individual operations (scans, joins, sorts, etc.)
• Cardinalities are estimates of how many rows flow through each operator
• Physical characteristics include disk speeds, memory sizes, CPU costs, etc.

The optimizer evaluates this function for each candidate plan and selects the one with minimum cost.

A comprehensive cost model considers multiple resource types. The total cost of a plan is typically a weighted combination of these components:

The total cost formula:

Most optimizers express total cost as:

Total_Cost = w₁ × IO_Cost + w₂ × CPU_Cost + w₃ × Memory_Cost + ...

Where w₁, w₂, w₃ are weights that reflect the relative costs of each resource. These weights are often configurable parameters:

• In I/O-bound systems (spinning disks), w₁ >> w₂
• In CPU-bound systems (in-memory databases), w₂ may dominate
• In distributed systems, network latency weights become significant

Example from PostgreSQL:

PostgreSQL uses parameters like:

• seq_page_cost = 1.0 (baseline for sequential I/O)
• random_page_cost = 4.0 (random I/O is 4× more expensive)
• cpu_tuple_cost = 0.01 (processing each tuple)
• cpu_operator_cost = 0.0025 (evaluating predicates)

These weights can be tuned based on actual hardware characteristics. If you move to SSDs, you might reduce random_page_cost since random reads are nearly as fast as sequential reads on SSDs.

For disk-based database systems, I/O cost is often the dominant factor. Reading and writing pages to disk is orders of magnitude slower than in-memory operations. A well-designed cost model pays careful attention to I/O.

Key I/O concepts:

• Page: The basic unit of I/O (typically 4KB-16KB)
• Sequential I/O: Reading consecutive pages (fast on HDDs, optimal on SSDs)
• Random I/O: Reading non-consecutive pages (slow on HDDs, reasonable on SSDs)
• Buffer pool: In-memory cache for frequently accessed pages

Basic I/O cost formulas:

Example: Comparing scan vs. index access

Consider a table Orders with:

• 1,000,000 rows
• 50,000 pages (20 rows per page)
• A B+-tree index on customer_id with height 3

Query: SELECT * FROM Orders WHERE customer_id = 12345

Assume the selectivity is 0.01% (100 matching rows).

Full table scan cost:

Cost = b_R = 50,000 page reads

Clustered index scan cost:

Cost = h + ⌈s × b_R⌉
     = 3 + ⌈0.0001 × 50,000⌉
     = 3 + 5 = 8 page reads

Unclustered index scan cost (worst case):

Cost = h + ⌈s × n_R⌉
     = 3 + ⌈0.0001 × 1,000,000⌉
     = 3 + 100 = 103 page reads

The index is clearly better, but notice how a clustered index (8 pages) dramatically outperforms an unclustered index (103 pages) because matching rows are stored together.

While I/O often dominates, CPU cost becomes increasingly important as:

• Data fits in memory (eliminating I/O bottlenecks)
• Queries involve complex computations
• Predicates require expensive evaluations (regex, string operations)
• Modern CPUs become relatively more expensive compared to fast SSDs

Components of CPU cost:

CPU cost formulas:

CPU_Cost(Scan R with predicate P) = n_R × (tuple_cost + predicate_cost(P))

CPU_Cost(Hash Join) = n_R × hash_cost + n_S × probe_cost + matched × output_cost

CPU_Cost(Sort) = n_R × log₂(n_R) × comparison_cost

CPU_Cost(Aggregation) = n_R × (grouping_cost + aggregate_update_cost)

Predicate complexity matters:

Not all predicates are equal. Consider these WHERE clauses:

-- Simple: Just an integer comparison
WHERE order_id = 12345

-- Moderate: String comparison with potential collation
WHERE customer_name = 'Smith'

-- Expensive: Pattern matching (may scan entire string)
WHERE customer_name LIKE '%Smith%'

-- Very expensive: Regular expression
WHERE customer_name ~ '^[A-Z][a-z]+\\s[A-Z][a-z]+$'

A sophisticated optimizer assigns different costs to each predicate type. The regex might be 100× more expensive than the integer comparison, significantly affecting which plan is optimal.

Cost formulas depend critically on cardinality estimates—predictions of how many rows will flow through each operator. These estimates come from statistics collected about the data.

Without statistics, optimization is blind:

Consider estimating the cost of: SELECT * FROM Orders WHERE status = 'pending'

• If 1% of orders are pending → ~10,000 rows → index access is optimal
• If 80% of orders are pending → ~800,000 rows → table scan is optimal

The optimizer must know the data distribution to make correct decisions.

Selectivity estimation:

The selectivity of a predicate is the fraction of rows that satisfy it:

Selectivity(predicate) = |rows satisfying predicate| / |total rows|

Common selectivity formulas (assuming uniform distribution):

Selectivity(A = value) = 1 / V(A,R)

Selectivity(A > value) = (max(A) - value) / (max(A) - min(A))

Selectivity(A BETWEEN low AND high) = (high - low) / (max(A) - min(A))

Selectivity(A IN (v1, v2, ..., vk)) = k / V(A,R)

Combining selectivities (independence assumption):

Selectivity(P1 AND P2) = Selectivity(P1) × Selectivity(P2)

Selectivity(P1 OR P2) = Selectivity(P1) + Selectivity(P2) - Selectivity(P1) × Selectivity(P2)

Selectivity(NOT P) = 1 - Selectivity(P)

These formulas make strong assumptions (uniformity, independence) that are often violated in real data, leading to estimation errors.

Estimating the size of join results is particularly challenging and crucial because join ordering decisions depend heavily on intermediate result sizes.

The fundamental join formula:

For a join R ⋈ S on attribute A:

|R ⋈ S| = |R| × |S| / max(V(A,R), V(A,S))

This assumes:

• Containment: All values in the smaller domain appear in the larger
• Uniformity: Each value appears equally often
• Independence: No correlation between attributes

The error propagation problem:

In multi-way joins, estimation errors compound multiplicatively:

Actual: R ⋈ S ⋈ T ⋈ U

If each join estimate has 2× error:
- After R ⋈ S: 2× off
- After R ⋈ S ⋈ T: 4× off
- After R ⋈ S ⋈ T ⋈ U: 8× off

With 10 tables, even small per-join errors can produce estimates that are millions of times wrong!

Advanced techniques for better join estimation:

1. Join histograms: Align bucket boundaries and join corresponding buckets
2. Sampling: Maintain small samples of join results for common join patterns
3. Machine learning: Use neural networks trained on actual execution statistics
4. Query feedback: Adjust estimates based on observed cardinalities in past executions

Given that cost estimates are inherently imprecise, how do optimizers cope? Several strategies have emerged to handle uncertainty:

1. Robust Plan Selection

Instead of choosing the plan with minimum estimated cost, choose a plan that performs reasonably well across a range of possible cardinalities:

Robust_Plan = argmin_P max_c∈C Cost(P, c)

Where C is the set of possible cardinality scenarios. This "minimax" approach avoids plans that are optimal for the estimate but catastrophic if the estimate is wrong.

2. Plan Bouquets

Pre-compute multiple plans for different cardinality regions. At runtime, take a sample to refine the estimate, then choose the appropriate plan:

If estimated_rows < 100: use index nested loop plan
If estimated_rows in [100, 10000]: use hash join plan
If estimated_rows > 10000: use sort-merge join plan

3. Adaptive Query Execution

Monitor actual cardinalities during execution and switch plans mid-query if estimates prove wrong:

• Start with hash join, but if build-side is unexpectedly large...
• Spill to disk gracefully (hybrid hash join)
• Or switch to sort-merge if hash table would exceed memory

Let's walk through a complete cost estimation example to solidify these concepts.

Scenario:

Two tables:

• Customers: 100,000 rows, 5,000 pages, index on customer_id
• Orders: 10,000,000 rows, 500,000 pages, index on customer_id

Query:

SELECT c.name, COUNT(*) as order_count
FROM Customers c
JOIN Orders o ON c.customer_id = o.customer_id
WHERE c.country = 'USA'
GROUP BY c.name;

Statistics:

• 25% of customers are in USA (selectivity = 0.25)
• Average 100 orders per customer
• Index on Customers.country exists

Plan A: Hash Join with Customer filter first

1. Index scan on Customers.country = 'USA'
   - Pages: 3 (index) + 0.25 × 5,000 = 1,253 pages
   - Rows output: 25,000 customers

2. Build hash table on filtered customers
   - CPU: 25,000 × hash_cost
   - Memory: ~25,000 × tuple_size

3. Scan Orders and probe hash table
   - Pages: 500,000
   - CPU: 10,000,000 × probe_cost
   - Matches: 25,000 × 100 = 2,500,000 rows

4. Aggregate by name
   - CPU: 2,500,000 × aggregate_cost

Total I/O: 1,253 + 500,000 = 501,253 pages

Plan B: Index Nested Loop Join

1. Scan all Orders
   - Pages: 500,000
   - Rows: 10,000,000

2. For each order, index lookup on Customers
   - Per lookup: 3 pages (index) + 1 page (data)
   - Total lookups: 10,000,000
   - But with caching, unique customers accessed: 100,000
   - Estimated pages: 100,000 × 4 = 400,000 (optimistic with caching)

3. Filter on country = 'USA'
   - 25% pass: 2,500,000 rows

4. Aggregate by name
   - CPU: 2,500,000 × aggregate_cost

Total I/O: 500,000 + 400,000 = 900,000 pages

Comparison:

Winner: Plan A — the hash join with early filtering is substantially cheaper because it avoids repeated index probes.

We've explored the foundation of cost-based query optimization. Let's consolidate the key concepts:

What's next:

With cost estimation in place, the optimizer must efficiently compare alternative plans. The next page explores Plan Comparison—how optimizers enumerate candidate plans, prune the search space, and select winners using the cost estimates we've learned to compute.