Cost Models in Query Processing

When you execute a SQL query, something remarkable happens behind the scenes. The database has mere milliseconds to make a critical decision: out of potentially thousands of different ways to execute your query, which execution plan will be fastest? This is the domain of cost estimation—the mathematical foundation that enables query optimizers to predict the future.

Cost estimation is the process by which a database management system predicts the resource consumption of executing a query using a particular execution plan before actually executing it. It's like asking: 'If I run this query using Plan A, how long will it take and how many resources will it consume?' The optimizer asks this question for multiple candidate plans and chooses the one with the lowest estimated cost.

This capability is what separates modern database systems from naive query processors. Without cost estimation, databases would either execute queries using fixed strategies (often catastrophically slow) or try every possible strategy (computationally infeasible). Cost estimation enables intelligent selection among potentially millions of execution alternatives.

To appreciate the importance of cost estimation, consider a deceptively simple query:

SELECT e.name, d.dept_name
FROM employees e
JOIN departments d ON e.dept_id = d.id
WHERE e.salary > 100000 AND d.location = 'New York';

Even for this straightforward two-table join with two filter conditions, the optimizer faces numerous choices:

Access Path Decisions:

• Should employees be accessed via a full table scan or an index on salary?
• Should departments be accessed via a full table scan or an index on location?

Join Order Decisions:

• Should we join employees ⋈ departments or departments ⋈ employees?
• Does it matter which table is the 'outer' vs 'inner' relation?

Join Algorithm Decisions:

• Nested loop join? Hash join? Sort-merge join?
• If nested loop, which table should be the outer relation?

Predicate Application:

• Apply filters before the join or after?
• Push predicates down into base table scans?

For just two tables, we might have 10-20 reasonable execution plans. For a 10-table join query—common in analytical workloads—the number of possible plans can exceed 10 billion. The optimizer cannot try them all. Instead, it must estimate which plans are likely to be fast and focus its search accordingly.

The Performance Stakes:

The difference between a good and bad execution plan isn't marginal—it can be orders of magnitude:

These aren't hypothetical examples—they reflect real production scenarios. A poorly chosen nested loop join where a hash join would be optimal, or a table scan where an index seek would be appropriate, can transform a sub-second query into a multi-hour ordeal.

Cost estimation is the mechanism that prevents these performance disasters. By predicting execution costs, the optimizer can steer toward efficient plans and away from catastrophic ones.

A cost model is a mathematical framework that assigns a numeric cost value to a query execution plan. This cost is a proxy for the actual execution time or resource consumption. The model consists of three fundamental components:

1. Cost Functions: Mathematical formulas that compute the cost of individual operations (table scans, index lookups, joins, sorts, etc.)

2. Statistical Inputs: Data about table sizes, column distributions, and correlations that feed into the cost functions

3. System Parameters: Hardware-specific constants like disk I/O time, CPU speed, memory capacity, and network latency

The general structure of a cost estimation formula is:

Cost as a Relative Measure:

It's crucial to understand that cost values are unit-less relative measures, not predictions of actual execution time. A plan with cost 1000 isn't predicted to take 1000 milliseconds—it's predicted to be about 10× more expensive than a plan with cost 100.

This relative nature has important implications:

• Comparison is valid: We can reliably compare costs between plans for the same query
• Absolute prediction is unreliable: We cannot accurately predict that a plan will take exactly X seconds
• Cross-query comparison is meaningless: A cost of 500 for Query A and 500 for Query B doesn't mean they'll take the same time

Modern systems like PostgreSQL do attempt to calibrate costs to approximate milliseconds, but this remains a secondary goal. The primary purpose is plan comparison and selection.

Cost estimation occurs within the query optimization phase, following a structured pipeline that transforms a logical query representation into a costed physical execution plan:

Pipeline Stages Explained:

Stage 1: Plan Enumeration The optimizer generates candidate execution plans. For a query with multiple tables, this involves considering different join orders, access methods, and algorithm choices. Sophisticated optimizers use dynamic programming or heuristics to prune the search space.

Stage 2: Cardinality Estimation For each operator in a candidate plan, the optimizer estimates how many rows will flow through it. This is critical because the cost of most operations scales with the number of rows processed. Cardinality estimates propagate bottom-up through the plan tree.

Stage 3: Cost Calculation Using the cardinality estimates and system parameters, the optimizer applies cost functions to compute the total cost of each plan. This involves summing the costs of all operators: scans, filters, joins, sorts, and aggregations.

Stage 4: Plan Comparison Candidate plans are compared by their total estimated cost. The plan with the lowest cost is selected (subject to memory and other constraints).

The Dependency Chain:

Note the critical dependency: cost estimation depends on cardinality estimation, which depends on statistics. If statistics are stale or missing, cardinality estimates will be wrong, leading to incorrect cost estimates and potentially disastrous plan choices. This dependency chain is both the power and the vulnerability of cost-based optimization.

A comprehensive cost model accounts for all significant resource consumptions during query execution. These fall into several categories:

I/O Costs (Often Dominant):

• Sequential reads: Reading consecutive disk pages (efficient)
• Random reads: Reading scattered disk pages (expensive)
• Writes: Temporary file creation for sorts, hash spills
• Page cache misses: When data isn't in memory

CPU Costs:

• Tuple processing: Evaluating predicates, projections
• Expression evaluation: Computing derived columns
• Comparison operations: Sorting, hashing, joining
• Function calls: User-defined functions, aggregations

Memory Costs:

• Working memory consumption: Sort runs, hash tables
• Buffer pool pressure: Displacing cached pages
• Memory allocation overhead: Creating temporary structures

Network Costs (Distributed Systems):

• Data transfer: Moving tuples between nodes
• Coordination overhead: Distributed query orchestration

The I/O Dominance Principle:

In traditional disk-based databases, I/O costs typically dominate. Reading a single random disk page might take 10 milliseconds, while a CPU can process thousands of tuples in that time. This historical reality shaped cost models to focus heavily on I/O minimization.

However, this landscape is shifting:

• SSDs have dramatically reduced random I/O costs
• Larger memories mean more data is cached in RAM
• Column stores achieve better compression and I/O efficiency
• In-memory databases eliminate disk I/O for hot data

Modern cost models must balance these factors appropriately. An optimizer optimizing purely for I/O on a system with 512GB of RAM and all data cached will make suboptimal choices.

Cost estimation is inherently imperfect. Understanding the sources of error helps in diagnosing query performance problems and maintaining database health.

The Error Amplification Effect:

Consider a simple three-way join: A ⋈ B ⋈ C. If the selectivity of the join condition A ⋈ B is estimated as 0.01 (1%) but is actually 0.1 (10%), the intermediate result is underestimated by 10×. When this intermediate result joins with C, that 10× error carries forward:

Actual flow:    1M × 1M × 0.1 = 100K rows
                100K × 1M × 0.1 = 10B rows (then filtered)

Estimated flow: 1M × 1M × 0.01 = 10K rows  
                10K × 1M × 0.1 = 1B rows

The optimizer chose hash join expecting to process 1B rows. It actually processed 10B rows. The query runs 10× slower than expected—not because of a wrong algorithm choice, but because cardinality estimation errors cascaded through the plan.

This is why database performance tuning so often comes down to statistics maintenance and understanding cardinality estimation.

Database systems implement cost models at various levels of sophistication. Understanding these categories helps in evaluating optimizer capabilities and limitations.

Evolutionary Progression:

Generation 1: Rule-Based (1970s-1980s) Early systems used fixed rules: 'Apply selections early,' 'Use indexes when possible.' No cost estimation—decisions were deterministic based on query structure.

Generation 2: Basic Cost-Based (1980s-1990s) System R pioneered cost-based optimization. Simple statistics (row counts, column cardinalities) fed into I/O-focused cost functions. Revolutionary for its time, but limited by single-column statistics.

Generation 3: Advanced Cost-Based (1990s-2010s) Histograms, multi-column statistics, extended statistics on expressions. Sophisticated cardinality estimators. Plan caching and prepared statements. Oracle, SQL Server, and PostgreSQL represent this generation.

Generation 4: Adaptive and Learned (2010s-Present) Adaptive query execution (runtime plan adjustment), machine learning for cardinality estimation, query result caching, and feedback-driven statistics. Systems learn from execution history to improve future estimates.

Modern databases like Oracle 19c, SQL Server 2022, and PostgreSQL 15+ incorporate Generation 4 features alongside traditional cost models.

Let's examine how cost estimation works in a real database system. PostgreSQL provides excellent visibility into its cost model through the EXPLAIN command.

Interpreting the Cost Numbers:

Each node shows two cost numbers: (startup_cost..total_cost)

• Startup cost: Work required before the first row can be returned (e.g., building a hash table)
• Total cost: Cost to return all rows from this node

For the Hash Join returning order info:

• cost=8234.12..36478.23: Startup is 8234 (building hash), total is 36478
• rows=245678: Optimizer estimates 245,678 rows will be produced
• width=36: Each row uses approximately 36 bytes

Comparing Estimated vs Actual:

The ANALYZE option reveals actual execution:

• rows=245678 (estimated) vs rows=198234 (actual): Off by about 24%
• This is acceptable estimation accuracy

When estimates differ dramatically (10× or more), that's diagnostic of stale statistics or correlation issues that need investigation.

We've established the foundational understanding of cost estimation in database query processing. Let's consolidate the key concepts:

What's Next:

With the conceptual foundation established, we'll dive deeper into the most impactful component of cost models: I/O Cost. The next page explores how databases model disk and memory access patterns, account for caching effects, and optimize for the realities of storage hierarchies.