Database Management SystemsCost Models

Cost Models in Query Processing

LevelIntermediate

Duration75 mins

TopicCost Models

3 / 5

CPU Cost

When Waiting for Disk Becomes Waiting for CPU

For decades, database optimization focused almost exclusively on minimizing disk I/O. CPU was practically free—while waiting for a single disk read, the CPU could execute millions of instructions. This made I/O cost the only cost that truly mattered.

But the landscape has shifted dramatically:

SSDs reduced I/O latency by 100× compared to spinning disks
Large memory pools keep more data cached in RAM
In-memory databases eliminate disk I/O for hot data entirely
Column stores achieve 10:1 or better compression, reducing I/O volume
Complex analytics require intensive computation per tuple

In these environments, CPU becomes the bottleneck. A full table scan might complete from memory in milliseconds, only to spend seconds evaluating complex WHERE clauses, computing aggregations, or executing user-defined functions.

Modern query optimizers must account for CPU costs accurately, or they risk making decisions that were optimal in 1995 but catastrophic today. This page explores how databases model, estimate, and optimize for CPU consumption.

What You Will Learn

By the end of this page, you will understand the components of CPU cost in query execution, how databases model tuple processing, predicate evaluation, and expression computation, the relationship between CPU cost and cardinality estimation, specific PostgreSQL CPU cost parameters and their calibration, and when CPU cost dominates optimization decisions.

Anatomy of CPU Cost

CPU cost in query execution arises from several distinct sources, each with different characteristics and optimization implications:

CPU Cost Components

•Tuple Processing Overhead — Fixed cost per tuple for reading tuple header, null bitmap, extracting columns, passing through operators. This baseline cost applies to every row touched regardless of operations performed.
•Predicate Evaluation — Cost to evaluate WHERE clause conditions. Simple equality checks (integer compare) are cheap; complex predicates (regex, function calls) are expensive. Cost scales linearly with tuples evaluated.
•Projection Computation — Computing derived columns in SELECT list. Includes type conversions, arithmetic, string operations, and expression evaluation. Complex expressions multiply per-tuple cost.
•Comparison Operations — Sorting, hash computation, join condition evaluation. Hash function computation for hash joins; comparison functions for sorts and merge joins.
•Aggregation Overhead — Maintaining aggregate state (SUM, COUNT, AVG, etc.). Hash-based grouping requires key comparison and bucket management.
•Function Invocation — User-defined functions (UDFs), built-in functions, stored procedure calls. Some functions are extremely expensive (encryption, complex math, external calls).
•Memory Management — Allocation/deallocation for variable-length data, temporary structures, sort runs, hash tables.

The CPU Cost Formula:

CPU_Cost(operation) = Base_cost + (Tuples_processed × Per_tuple_cost)

Where:
  Base_cost: Fixed startup cost (operator initialization, memory allocation)
  Tuples_processed: Number of tuples flowing through this operator
  Per_tuple_cost: Sum of costs for all per-tuple operations

Total_CPU_Cost(Plan) = Σ CPU_Cost(operation_i) for all operators

This linear scaling with tuple count is why cardinality estimation directly impacts CPU cost estimation. If we estimate 1,000 rows but 1,000,000 flow through, CPU cost is underestimated by 1000×.

The Hidden Constant Factor

CPU costs often carry large constant factors that textbook analysis ignores. Extracting a column from a row-oriented storage tuple involves pointer arithmetic, null checking, and type-specific handling—orders of magnitude more instructions than a simple memory read. These constants matter when scaling to millions of rows.

Understanding Tuple Processing Overhead

Every tuple that flows through a query incurs baseline processing cost, regardless of what operations are performed. Understanding this overhead reveals why reducing tuple flow is fundamental to query optimization.

tuple_processing_breakdown.txt
=============================================================
TUPLE PROCESSING OVERHEAD BREAKDOWN (Row-Oriented Storage)
=============================================================
 
For each tuple processed:
 
1. TUPLE RETRIEVAL
   - Read tuple pointer from page slot array
   - Compute tuple location in page
   - Load tuple header (24 bytes typical)
   - Parse null bitmap if present
   Time: ~50-100 nanoseconds
 
2. COLUMN EXTRACTION  
   - Locate column offset (scan through previous variable-length columns)
   - Handle null checking
   - Copy or reference column value
   Time: ~10-50 nanoseconds per column
 
3. OPERATOR OVERHEAD
   - Pass tuple pointer/copy to next operator
   - Memory access patterns (cache misses)
   - Function call overhead (iterator model)
   Time: ~20-50 nanoseconds per operator
 
4. VISIBILITY CHECKING (MVCC databases)
   - Check transaction ID ranges
   - Validate tuple visibility for current transaction
   - Handle snapshot isolation
   Time: ~30-80 nanoseconds per tuple
 
=============================================================
TOTAL BASELINE: ~100-300 nanoseconds per tuple per operator
=============================================================
 
For a 3-operator plan (Scan → Filter → Project) processing 1M tuples:
  Minimum CPU time: 3 × 1M × 200ns = 600 milliseconds
 
This is the FLOOR—before any predicate evaluation or computation.

The Iterator Model's CPU Impact:

Most database systems use the Volcano-style iterator model where each operator:

Exposes a next() interface returning one tuple at a time
Calls next() on its child operator to get input
Processes the tuple and returns it to its parent

Query: SELECT a, b+c FROM T WHERE x > 10

Plan tree:
  Project(a, b+c)
    ↓ next()
  Filter(x > 10)
    ↓ next()
  SeqScan(T)

Each next() call incurs function call overhead. For simple operations, this overhead dominates actual work. Processing 10 million tuples means 30+ million function calls just for iterator mechanics.

Vectorized Execution:

Modern analytical databases (DuckDB, ClickHouse, Snowflake) use vectorized execution—processing batches of 1,000-10,000 tuples per next() call:

Iterator model:  10M × 3 calls × 50ns overhead = 1.5 seconds
Vectorized:      10K × 3 calls × 50ns + tight loop = 0.002 seconds + loop

Vectorization reduces per-tuple overhead by 100-1000× for CPU-heavy workloads. PostgreSQL remains iterator-based; analytics-focused systems have moved to vectorized engines.

Column-Oriented Efficiency

Column stores (Redshift, BigQuery, Parquet files) process one column at a time across many rows. This enables SIMD instructions (processing 4-16 values per CPU instruction) and eliminates per-tuple overhead for unused columns. For analytical queries touching few columns, column stores can be 10-100× more CPU-efficient than row stores.

Predicate Evaluation Cost

Predicates (WHERE clause conditions) are evaluated for every tuple that flows to the filter operator. The cost varies dramatically based on predicate type:

Relative Cost of Common Predicate Operations
Predicate Type	Example	Relative Cost	Notes
Integer equality	id = 42	1×	Single comparison instruction
Integer range	age BETWEEN 18 AND 65	2×	Two comparisons
Null check	deleted_at IS NULL	0.5×	Bit check in null bitmap
Boolean column	is_active = true	0.5×	Single bit/byte check
String equality (short)	status = 'active'	3-5×	memcmp up to length
String equality (long)	description = 'very long...'	10-50×	Full string comparison
String pattern (prefix)	name LIKE 'John%'	5-10×	Compare prefix bytes
String pattern (contains)	name LIKE '%John%'	50-500×	Substring search algorithm
Regex match	email ~ '^[a-z]+@'	100-1000×	Regex engine execution
UDF scalar function	is_valid(data)	1000-10000×	Function call + logic
Subquery (uncorrelated)	id IN (SELECT ...)	Variable	Depends on subquery result
Subquery (correlated)	EXISTS (SELECT ... WHERE t.id = s.tid)	Extremely high	Executed per outer row

Predicate Ordering Optimization:

When multiple predicates combine with AND, an intelligent optimizer evaluates cheap, selective predicates first:

WHERE status = 'active'           -- Cheap (string equality), 10% pass
  AND complex_analysis(data) > 0   -- Expensive (UDF), 50% pass
  AND email LIKE '%@corp.com'      -- Medium cost, 20% pass

Optimal order: status → email → complex_analysis
Reasons:
  1. status is cheapest and eliminates 90% of rows
  2. email is moderately cheap and eliminates another 80%
  3. complex_analysis (very expensive) runs on only 2% of original rows
  
Cost comparison:
  Naive order: 1M × (1 + 1000 + 100) = 1.1B cost units
  Optimal order: 1M × 1 + 100K × 100 + 20K × 1000 = 31M cost units
  Improvement: 35× faster

Most optimizers automatically reorder conjunctive predicates based on estimated selectivity and cost. However, they may not accurately cost UDFs (often assumed cheap when they're not).

The UDF Cost Estimation Problem

User-defined functions are often black boxes to the optimizer. PostgreSQL assigns a default COST of 100 (relative to seq_page_cost = 1.0) for functions, but actual cost varies wildly. A function that simply adds two numbers costs ~1; a function that makes an HTTP call costs 100,000+. Always specify COST and ROWS for UDFs to help the optimizer.

function_cost_specification.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-- PostgreSQL: Specify function cost for optimizer accuracy
-- =========================================================
 
-- A cheap function (simple arithmetic)
CREATE FUNCTION calculate_tax(amount NUMERIC)
RETURNS NUMERIC AS $$
  SELECT amount * 0.0825;
$$ LANGUAGE SQL IMMUTABLE COST 1;
 
-- A moderate cost function (string manipulation)
CREATE FUNCTION normalize_phone(phone TEXT)
RETURNS TEXT AS $$
  SELECT regexp_replace(phone, '[^0-9]', '', 'g');
$$ LANGUAGE SQL IMMUTABLE COST 50;
 
-- An expensive function (complex business logic)
CREATE FUNCTION validate_order(order_id INTEGER)
RETURNS BOOLEAN AS $$
BEGIN
  -- Multiple table lookups, business rule checks
  PERFORM 1 FROM orders o
    JOIN order_items oi ON o.id = oi.order_id
    JOIN products p ON oi.product_id = p.id
    WHERE o.id = order_id
      AND p.available
      AND oi.quantity <= p.stock_level;
  RETURN FOUND;
END;
$$ LANGUAGE plpgsql STABLE COST 5000;
 
-- An extremely expensive function (external service call)
CREATE FUNCTION verify_address(address_json JSON)
RETURNS JSON AS $$
  # Makes HTTP API call to address verification service
  import requests
  return requests.post('https://api.address.com/verify', json=address_json).json()
$$ LANGUAGE plpython3u VOLATILE COST 100000;
 
-- Now optimizer knows to avoid calling verify_address unless necessary
SELECT * 
FROM customers 
WHERE status = 'active'                       -- Evaluated first (cheap)
  AND verify_address(address) IS NOT NULL;    -- Evaluated last (expensive)

Expression and Projection Cost

Beyond filtering, queries often compute derived values in the SELECT list, GROUP BY expressions, or ORDER BY clauses. These computations add per-tuple CPU overhead.

Cheap Operations

•Column reference: SELECT id
•Integer arithmetic: price * quantity
•Boolean logic: a AND b
•NULL coalescing: COALESCE(a, b)
•Type casting (no conversion): id::bigint
•Constant expressions: 1 + 2

Expensive Operations

•String concatenation: first || ' ' || last
•Datetime formatting: TO_CHAR(dt, 'YYYY-MM-DD')
•JSON parsing: data::json->'key'
•Decimal arithmetic: amount * 1.0825
•String functions: UPPER(), SUBSTRING()
•Regex extraction: regexp_match()

Projection Pushdown Optimization:

One of the most effective CPU optimizations is projection pushdown—computing only the columns actually needed at each stage of the plan:

-- Original query
SELECT customer_id, order_date
FROM orders
WHERE total > 1000;

-- Without projection pushdown:
  Scan: Read all 20 columns from orders table
  Filter: Evaluate total > 1000
  Project: Extract customer_id, order_date

-- With projection pushdown:
  Scan: Read only customer_id, order_date, total
  Filter: Evaluate total > 1000  
  Project: Already have needed columns

-- CPU savings: Avoided extracting 17 unnecessary columns per row

For wide tables (50+ columns), projection pushdown can reduce CPU cost by 10-20×.

Computed Column Optimization:

When the same expression appears multiple times, the optimizer may compute it once and reuse:

SELECT 
  price * quantity AS line_total,
  price * quantity * tax_rate AS tax_amount,
  price * quantity * (1 + tax_rate) AS total
FROM order_items;

-- Optimized internal representation:
let tmp1 = price * quantity
let tmp2 = tmp1 * tax_rate
return (tmp1, tmp2, tmp1 + tmp2)

-- CPU reduction: 3 multiplications instead of 6

JSON and JSONB Performance

JSON column extraction (data->'key') has significant CPU overhead. Binary JSON (JSONB in PostgreSQL) is faster to query but slower to insert. For frequently-accessed JSON fields, consider extracting them to regular columns or using generated columns. A 10× speedup on JSON-heavy queries is common.

Join and Aggregation CPU Costs

Joins and aggregations involve significant CPU work beyond simple tuple processing. Understanding these costs helps in choosing appropriate algorithms and query structures.

join_cpu_costs.txt
=============================================================
CPU COST COMPONENTS FOR JOIN ALGORITHMS
=============================================================
 
NESTED LOOP JOIN:
  - Per-outer-tuple: Hash/compare inner side (O(1) with index)
  - Total: O(N_outer × match_cost)
  - CPU intensive when: Inner side large without index
  - Best for: Small outer side, selective joins
 
HASH JOIN:
  Build phase:
    - Hash each build-side tuple: O(N_build × hash_cost)
    - Insert into hash table: O(N_build × insert_cost)
  Probe phase:
    - Hash each probe-side tuple: O(N_probe × hash_cost)
    - Lookup + compare: O(N_probe × lookup_cost × avg_bucket_size)
  Total CPU: O(N_build + N_probe) × hash_computation_cost
  
  Hash function cost varies by data type:
    Integer: ~5 nanoseconds (few operations)
    Short string: ~20 nanoseconds (hash bytes)
    Long string: ~100+ nanoseconds (more bytes to hash)
    Complex type: ~500+ nanoseconds (serialize + hash)
 
MERGE JOIN:
  - Requires sorted input (sort cost if not already sorted)
  - Merge: O(N_left + N_right) comparisons
  - Comparison cost: Cheap for integers, expensive for strings/compound keys
  Total CPU: Sort costs + O(N) comparisons
 
=============================================================
COMPARISON FOR 1M × 1M JOIN, INTEGER KEYS:
=============================================================
Hash join:   2M hash + 2M lookups ≈ 10M operations ≈ 50ms CPU
Merge join:  2M comparisons (if sorted) ≈ 4M operations ≈ 20ms CPU
             + sort cost if needed: ~200ms CPU for external sort
Nested loop: 1M × log(1M) = 20B operations (with index) ≈ 100s CPU
             (without index: 1M × 1M = 1T operations = impossible)

Aggregation CPU Costs:

Hash Aggregation:
  - Hash each group key: O(N_input × hash_cost)
  - Update aggregate state: O(N_input × agg_update_cost)
  - Finalize aggregates: O(N_groups × finalize_cost)

Sorted Aggregation:
  - Compare adjacent keys: O(N_input × compare_cost)
  - Update aggregate state: O(N_input × agg_update_cost)
  - Finalize aggregates: O(N_groups × finalize_cost)

Aggregate update costs:
  COUNT:    ~1 operation (increment counter)
  SUM/AVG:  ~2-5 operations (add or accumulate)
  MAX/MIN:  ~2-3 operations (compare and conditionally update)
  ARRAY_AGG: ~50-200 operations (array append, potential resize)
  STRING_AGG: ~100-500 operations (string concat, memory allocation)
  PERCENTILE: ~1000+ operations (maintain sorted structure)

Distinct Elimination:

SELECT DISTINCT category FROM products;  -- All rows, hash/sort
SELECT category FROM products GROUP BY category;  -- Equivalent

-- DISTINCT is expensive: Must track all seen values
-- For high-cardinality results: ~N hash operations + N memory for tracking
-- For low-cardinality: Much cheaper (small hash table)

The GROUP BY Order Matters

GROUP BY (a, b) produces a different grouping key hash than GROUP BY (b, a). For hash aggregation, order doesn't affect correctness but may affect cache behavior. For sorted aggregation, the sort order must match an available index or require explicit sorting. Multi-column GROUP BY generally has higher hash/compare costs than single-column.

PostgreSQL CPU Cost Parameters

PostgreSQL exposes CPU cost through configurable parameters, allowing calibration for different hardware and workloads.

postgresql_cpu_costs.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
-- PostgreSQL CPU Cost Parameters
-- ================================================================
 
-- Cost to process a single tuple (baseline per-row overhead)
cpu_tuple_cost = 0.01       -- Default: 1% of a sequential page read
 
-- Cost to process an operator expression or function per tuple
cpu_operator_cost = 0.0025  -- Default: 0.25% of sequential page read
 
-- Cost to process an index entry during index scan
cpu_index_tuple_cost = 0.005  -- Default: 0.5% of sequential page read
 
-- These are relative to seq_page_cost = 1.0
 
-- ================================================================
-- EXAMPLE: Cost calculation for a filtered table scan
-- ================================================================
-- Query: SELECT * FROM users WHERE status = 'active';
-- Stats: users has 1M rows, 50,000 pages
 
-- Cost components:
--   1. Sequential I/O: 50,000 pages × 1.0 = 50,000
--   2. Tuple processing: 1,000,000 × 0.01 = 10,000
--   3. Predicate eval: 1,000,000 × 0.0025 = 2,500
--   4. Output tuples (assume 10% selectivity): 100,000 × 0.01 = 1,000
--   
-- Total: 50,000 + 10,000 + 2,500 + 1,000 = 63,500
 
-- ================================================================
-- VIEWING COST BREAKDOWN IN EXPLAIN
-- ================================================================
EXPLAIN (VERBOSE, COSTS) 
SELECT * FROM users WHERE status = 'active';
 
-- Output:
-- Seq Scan on public.users  (cost=0.00..63500.00 rows=100000 width=120)
--   Output: id, name, email, status, created_at
--   Filter: (users.status = 'active'::text)
 
-- ================================================================
-- ADJUSTING CPU COSTS FOR FAST STORAGE
-- ================================================================
-- On fast SSDs with data mostly cached, CPU becomes relatively more important.
-- Consider increasing CPU costs or decreasing I/O costs:
 
-- Option 1: Reduce I/O costs (data is cached)
SET random_page_cost = 1.1;
SET seq_page_cost = 1.0;  -- Already baseline
 
-- Option 2: Increase CPU costs (emphasize CPU in decisions)
SET cpu_tuple_cost = 0.03;
SET cpu_operator_cost = 0.01;
 
-- Example impact: Index scan with 100K random reads
-- Default: 100K × 4.0 + 100K × 0.01 = 401,000 (I/O dominates)
-- Adjusted: 100K × 1.1 + 100K × 0.03 = 113,000 (more balanced)

Parallel Query CPU Costs:

Parallel execution introduces additional CPU overhead for coordination:

parallel_tuple_cost = 0.1        -- Cost to pass tuple between processes
parallel_setup_cost = 1000       -- Fixed cost to start parallel workers

For parallel plan viability:
  Total_cost(parallel) < Total_cost(serial)

Parallel savings must exceed:
  - parallel_setup_cost (initial overhead)
  - parallel_tuple_cost × tuples_transferred (per-tuple IPC overhead)

Small queries don't benefit from parallelism—the coordination costs exceed savings. Large scans and aggregations parallelize well because work division savings dwarf overhead.

When to Adjust CPU Costs

Increase cpu_tuple_cost when: Data is primarily cached in memory, queries have complex predicates or expressions, workload is CPU-bound (top shows high CPU, low I/O wait). Decrease when: Storage is slow (spinning disk), workload is I/O-bound, tables don't fit in memory. Monitor query plans before and after adjustments.

CPU Cost in Modern Workloads

Modern database workloads increasingly stress CPU relative to I/O. Several trends drive this shift:

CPU-Intensive Modern Workloads

•Real-Time Analytics — Complex aggregations, window functions, and statistical calculations on streaming data. Ad-hoc OLAP queries may touch millions of rows with multi-stage computations.
•JSON/Document Processing — Semi-structured data requires parsing, extraction, and type coercion at query time. JSON columns may hold deeply nested structures requiring recursive traversal.
•Full-Text Search — Tokenization, stemming, and relevance scoring involve substantial string processing. TF-IDF and BM25 ranking compute similarity scores across documents and query terms.
•Machine Learning Integration — Inference within queries using trained models (classify, predict) involves model evaluation per row. Vector similarity for embeddings requires high-dimensional distance calculations.
•Encryption/Security — Always-encrypted columns require decryption for every access. Row-level security policies add predicate checks. Audit logging serializes each operation.
•Complex Business Logic — Stored procedures, triggers, and multi-statement transactions accumulate CPU costs. Legacy systems with UDF-heavy architectures suffer significant overhead.

Case Study: Vector Similarity Search

Embedding-based search (semantic search, recommendation) exemplifies CPU-intensive querying:

-- Find 10 most similar products to a given embedding
SELECT product_id, name
FROM products  
ORDER BY embedding <-> '[0.12, 0.45, ..., 0.89]'::vector(1536)
LIMIT 10;

-- Cost breakdown for 1M products:
--   Distance calculation: 1M × 1536 dimensions × 2 ops = 3B operations
--   At 3 GHz, single-threaded: ~1 second just for distance
--   Plus comparison, heap management for top-10 tracking

-- Solutions:
--   1. Vector index (HNSW, IVF): Approximate NN, ~1000× faster
--   2. Dimensionality reduction: Fewer dimensions to compare  
--   3. Pre-filtering: Reduce candidates before similarity search

Vector databases (Pinecone, Milvus, pgvector) specialize in optimizing these CPU-heavy workloads through approximate algorithms and SIMD-optimized distance functions.

The AI/ML Query Tax

Embedding-based features add orders of magnitude CPU cost to queries. A simple product lookup becomes a vector similarity search. Without careful architecture (caching, approximate indexes, pre-computation), AI-enhanced queries can bring databases to their knees. Monitor CPU metrics closely when adding ML features.

Summary: CPU Cost Mastery

CPU cost is increasingly critical in modern database optimization. Let's consolidate the key concepts:

Key Takeaways

•CPU cost scales linearly with tuple count — Cardinality estimation directly drives CPU cost estimation. Errors propagate proportionally.
•Per-tuple overhead is substantial — Iterator model mechanics, column extraction, and MVCC checking add 100-300ns baseline per tuple per operator.
•Predicate costs vary by 1000× — Integer comparison vs. regex matching represent vastly different CPU costs. Predicate ordering optimization yields major savings.
•UDF cost must be specified explicitly — The optimizer cannot introspect function complexity. Use COST and ROWS clauses to enable smart planning.
•Joins have algorithm-specific CPU profiles — Hash joins have build+probe hashing costs; merge joins have comparison costs; nested loops multiply outer cardinality.
•Modern workloads stress CPU — Cached data, complex analytics, JSON processing, and vector search shift bottlenecks from I/O to CPU.
•PostgreSQL provides tunable parameters — cpu_tuple_cost, cpu_operator_cost can be calibrated for your hardware and workload characteristics.

What's Next:

Cost estimation accuracy depends critically on knowing how much data flows through each operator. This requires database statistics—metadata about table sizes, column distributions, and value frequencies. The next page explores how databases collect, maintain, and use statistics to power accurate cost estimation.

Page Complete

You now understand CPU cost modeling in depth—from basic tuple processing to complex workloads like vector similarity. This knowledge enables you to identify CPU bottlenecks, optimize predicate-heavy queries, and configure database parameters for CPU-intensive workloads.

3 / 5

Loading learning content...

Database Management SystemsCost Models

Cost Models in Query Processing

LevelIntermediate

Duration75 mins

TopicCost Models

3 / 5

CPU Cost

When Waiting for Disk Becomes Waiting for CPU

But the landscape has shifted dramatically:

SSDs reduced I/O latency by 100× compared to spinning disks
Large memory pools keep more data cached in RAM
In-memory databases eliminate disk I/O for hot data entirely
Column stores achieve 10:1 or better compression, reducing I/O volume
Complex analytics require intensive computation per tuple

What You Will Learn

Anatomy of CPU Cost

CPU cost in query execution arises from several distinct sources, each with different characteristics and optimization implications:

CPU Cost Components

•Tuple Processing Overhead — Fixed cost per tuple for reading tuple header, null bitmap, extracting columns, passing through operators. This baseline cost applies to every row touched regardless of operations performed.
•Predicate Evaluation — Cost to evaluate WHERE clause conditions. Simple equality checks (integer compare) are cheap; complex predicates (regex, function calls) are expensive. Cost scales linearly with tuples evaluated.
•Projection Computation — Computing derived columns in SELECT list. Includes type conversions, arithmetic, string operations, and expression evaluation. Complex expressions multiply per-tuple cost.
•Comparison Operations — Sorting, hash computation, join condition evaluation. Hash function computation for hash joins; comparison functions for sorts and merge joins.
•Aggregation Overhead — Maintaining aggregate state (SUM, COUNT, AVG, etc.). Hash-based grouping requires key comparison and bucket management.
•Function Invocation — User-defined functions (UDFs), built-in functions, stored procedure calls. Some functions are extremely expensive (encryption, complex math, external calls).
•Memory Management — Allocation/deallocation for variable-length data, temporary structures, sort runs, hash tables.

The CPU Cost Formula:

CPU_Cost(operation) = Base_cost + (Tuples_processed × Per_tuple_cost)

Where:
  Base_cost: Fixed startup cost (operator initialization, memory allocation)
  Tuples_processed: Number of tuples flowing through this operator
  Per_tuple_cost: Sum of costs for all per-tuple operations

Total_CPU_Cost(Plan) = Σ CPU_Cost(operation_i) for all operators

The Hidden Constant Factor

Understanding Tuple Processing Overhead

tuple_processing_breakdown.txt
=============================================================
TUPLE PROCESSING OVERHEAD BREAKDOWN (Row-Oriented Storage)
=============================================================
 
For each tuple processed:
 
1. TUPLE RETRIEVAL
   - Read tuple pointer from page slot array
   - Compute tuple location in page
   - Load tuple header (24 bytes typical)
   - Parse null bitmap if present
   Time: ~50-100 nanoseconds
 
2. COLUMN EXTRACTION  
   - Locate column offset (scan through previous variable-length columns)
   - Handle null checking
   - Copy or reference column value
   Time: ~10-50 nanoseconds per column
 
3. OPERATOR OVERHEAD
   - Pass tuple pointer/copy to next operator
   - Memory access patterns (cache misses)
   - Function call overhead (iterator model)
   Time: ~20-50 nanoseconds per operator
 
4. VISIBILITY CHECKING (MVCC databases)
   - Check transaction ID ranges
   - Validate tuple visibility for current transaction
   - Handle snapshot isolation
   Time: ~30-80 nanoseconds per tuple
 
=============================================================
TOTAL BASELINE: ~100-300 nanoseconds per tuple per operator
=============================================================
 
For a 3-operator plan (Scan → Filter → Project) processing 1M tuples:
  Minimum CPU time: 3 × 1M × 200ns = 600 milliseconds
 
This is the FLOOR—before any predicate evaluation or computation.

The Iterator Model's CPU Impact:

Most database systems use the Volcano-style iterator model where each operator:

Exposes a next() interface returning one tuple at a time
Calls next() on its child operator to get input
Processes the tuple and returns it to its parent

Query: SELECT a, b+c FROM T WHERE x > 10

Plan tree:
  Project(a, b+c)
    ↓ next()
  Filter(x > 10)
    ↓ next()
  SeqScan(T)

Vectorized Execution:

Modern analytical databases (DuckDB, ClickHouse, Snowflake) use vectorized execution—processing batches of 1,000-10,000 tuples per next() call:

Iterator model:  10M × 3 calls × 50ns overhead = 1.5 seconds
Vectorized:      10K × 3 calls × 50ns + tight loop = 0.002 seconds + loop

Vectorization reduces per-tuple overhead by 100-1000× for CPU-heavy workloads. PostgreSQL remains iterator-based; analytics-focused systems have moved to vectorized engines.

Column-Oriented Efficiency

Predicate Evaluation Cost

Predicates (WHERE clause conditions) are evaluated for every tuple that flows to the filter operator. The cost varies dramatically based on predicate type:

Relative Cost of Common Predicate Operations
Predicate Type	Example	Relative Cost	Notes
Integer equality	id = 42	1×	Single comparison instruction
Integer range	age BETWEEN 18 AND 65	2×	Two comparisons
Null check	deleted_at IS NULL	0.5×	Bit check in null bitmap
Boolean column	is_active = true	0.5×	Single bit/byte check
String equality (short)	status = 'active'	3-5×	memcmp up to length
String equality (long)	description = 'very long...'	10-50×	Full string comparison
String pattern (prefix)	name LIKE 'John%'	5-10×	Compare prefix bytes
String pattern (contains)	name LIKE '%John%'	50-500×	Substring search algorithm
Regex match	email ~ '^[a-z]+@'	100-1000×	Regex engine execution
UDF scalar function	is_valid(data)	1000-10000×	Function call + logic
Subquery (uncorrelated)	id IN (SELECT ...)	Variable	Depends on subquery result
Subquery (correlated)	EXISTS (SELECT ... WHERE t.id = s.tid)	Extremely high	Executed per outer row

Predicate Ordering Optimization:

When multiple predicates combine with AND, an intelligent optimizer evaluates cheap, selective predicates first:

WHERE status = 'active'           -- Cheap (string equality), 10% pass
  AND complex_analysis(data) > 0   -- Expensive (UDF), 50% pass
  AND email LIKE '%@corp.com'      -- Medium cost, 20% pass

Optimal order: status → email → complex_analysis
Reasons:
  1. status is cheapest and eliminates 90% of rows
  2. email is moderately cheap and eliminates another 80%
  3. complex_analysis (very expensive) runs on only 2% of original rows
  
Cost comparison:
  Naive order: 1M × (1 + 1000 + 100) = 1.1B cost units
  Optimal order: 1M × 1 + 100K × 100 + 20K × 1000 = 31M cost units
  Improvement: 35× faster

Most optimizers automatically reorder conjunctive predicates based on estimated selectivity and cost. However, they may not accurately cost UDFs (often assumed cheap when they're not).

The UDF Cost Estimation Problem

function_cost_specification.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
-- PostgreSQL: Specify function cost for optimizer accuracy
-- =========================================================
 
-- A cheap function (simple arithmetic)
CREATE FUNCTION calculate_tax(amount NUMERIC)
RETURNS NUMERIC AS $$
  SELECT amount * 0.0825;
$$ LANGUAGE SQL IMMUTABLE COST 1;
 
-- A moderate cost function (string manipulation)
CREATE FUNCTION normalize_phone(phone TEXT)
RETURNS TEXT AS $$
  SELECT regexp_replace(phone, '[^0-9]', '', 'g');
$$ LANGUAGE SQL IMMUTABLE COST 50;
 
-- An expensive function (complex business logic)
CREATE FUNCTION validate_order(order_id INTEGER)
RETURNS BOOLEAN AS $$
BEGIN
  -- Multiple table lookups, business rule checks
  PERFORM 1 FROM orders o
    JOIN order_items oi ON o.id = oi.order_id
    JOIN products p ON oi.product_id = p.id
    WHERE o.id = order_id
      AND p.available
      AND oi.quantity <= p.stock_level;
  RETURN FOUND;
END;
$$ LANGUAGE plpgsql STABLE COST 5000;
 
-- An extremely expensive function (external service call)
CREATE FUNCTION verify_address(address_json JSON)
RETURNS JSON AS $$
  # Makes HTTP API call to address verification service
  import requests
  return requests.post('https://api.address.com/verify', json=address_json).json()
$$ LANGUAGE plpython3u VOLATILE COST 100000;
 
-- Now optimizer knows to avoid calling verify_address unless necessary
SELECT * 
FROM customers 
WHERE status = 'active'                       -- Evaluated first (cheap)
  AND verify_address(address) IS NOT NULL;    -- Evaluated last (expensive)

Expression and Projection Cost

Beyond filtering, queries often compute derived values in the SELECT list, GROUP BY expressions, or ORDER BY clauses. These computations add per-tuple CPU overhead.

Cheap Operations

•Column reference: SELECT id
•Integer arithmetic: price * quantity
•Boolean logic: a AND b
•NULL coalescing: COALESCE(a, b)
•Type casting (no conversion): id::bigint
•Constant expressions: 1 + 2

Expensive Operations

•String concatenation: first || ' ' || last
•Datetime formatting: TO_CHAR(dt, 'YYYY-MM-DD')
•JSON parsing: data::json->'key'
•Decimal arithmetic: amount * 1.0825
•String functions: UPPER(), SUBSTRING()
•Regex extraction: regexp_match()

Projection Pushdown Optimization:

One of the most effective CPU optimizations is projection pushdown—computing only the columns actually needed at each stage of the plan:

-- Original query
SELECT customer_id, order_date
FROM orders
WHERE total > 1000;

-- Without projection pushdown:
  Scan: Read all 20 columns from orders table
  Filter: Evaluate total > 1000
  Project: Extract customer_id, order_date

-- With projection pushdown:
  Scan: Read only customer_id, order_date, total
  Filter: Evaluate total > 1000  
  Project: Already have needed columns

-- CPU savings: Avoided extracting 17 unnecessary columns per row

For wide tables (50+ columns), projection pushdown can reduce CPU cost by 10-20×.

Computed Column Optimization:

When the same expression appears multiple times, the optimizer may compute it once and reuse:

SELECT 
  price * quantity AS line_total,
  price * quantity * tax_rate AS tax_amount,
  price * quantity * (1 + tax_rate) AS total
FROM order_items;

-- Optimized internal representation:
let tmp1 = price * quantity
let tmp2 = tmp1 * tax_rate
return (tmp1, tmp2, tmp1 + tmp2)

-- CPU reduction: 3 multiplications instead of 6

JSON and JSONB Performance

Join and Aggregation CPU Costs

Joins and aggregations involve significant CPU work beyond simple tuple processing. Understanding these costs helps in choosing appropriate algorithms and query structures.

join_cpu_costs.txt
=============================================================
CPU COST COMPONENTS FOR JOIN ALGORITHMS
=============================================================
 
NESTED LOOP JOIN:
  - Per-outer-tuple: Hash/compare inner side (O(1) with index)
  - Total: O(N_outer × match_cost)
  - CPU intensive when: Inner side large without index
  - Best for: Small outer side, selective joins
 
HASH JOIN:
  Build phase:
    - Hash each build-side tuple: O(N_build × hash_cost)
    - Insert into hash table: O(N_build × insert_cost)
  Probe phase:
    - Hash each probe-side tuple: O(N_probe × hash_cost)
    - Lookup + compare: O(N_probe × lookup_cost × avg_bucket_size)
  Total CPU: O(N_build + N_probe) × hash_computation_cost
  
  Hash function cost varies by data type:
    Integer: ~5 nanoseconds (few operations)
    Short string: ~20 nanoseconds (hash bytes)
    Long string: ~100+ nanoseconds (more bytes to hash)
    Complex type: ~500+ nanoseconds (serialize + hash)
 
MERGE JOIN:
  - Requires sorted input (sort cost if not already sorted)
  - Merge: O(N_left + N_right) comparisons
  - Comparison cost: Cheap for integers, expensive for strings/compound keys
  Total CPU: Sort costs + O(N) comparisons
 
=============================================================
COMPARISON FOR 1M × 1M JOIN, INTEGER KEYS:
=============================================================
Hash join:   2M hash + 2M lookups ≈ 10M operations ≈ 50ms CPU
Merge join:  2M comparisons (if sorted) ≈ 4M operations ≈ 20ms CPU
             + sort cost if needed: ~200ms CPU for external sort
Nested loop: 1M × log(1M) = 20B operations (with index) ≈ 100s CPU
             (without index: 1M × 1M = 1T operations = impossible)

Aggregation CPU Costs:

Hash Aggregation:
  - Hash each group key: O(N_input × hash_cost)
  - Update aggregate state: O(N_input × agg_update_cost)
  - Finalize aggregates: O(N_groups × finalize_cost)

Sorted Aggregation:
  - Compare adjacent keys: O(N_input × compare_cost)
  - Update aggregate state: O(N_input × agg_update_cost)
  - Finalize aggregates: O(N_groups × finalize_cost)

Aggregate update costs:
  COUNT:    ~1 operation (increment counter)
  SUM/AVG:  ~2-5 operations (add or accumulate)
  MAX/MIN:  ~2-3 operations (compare and conditionally update)
  ARRAY_AGG: ~50-200 operations (array append, potential resize)
  STRING_AGG: ~100-500 operations (string concat, memory allocation)
  PERCENTILE: ~1000+ operations (maintain sorted structure)

Distinct Elimination:

SELECT DISTINCT category FROM products;  -- All rows, hash/sort
SELECT category FROM products GROUP BY category;  -- Equivalent

-- DISTINCT is expensive: Must track all seen values
-- For high-cardinality results: ~N hash operations + N memory for tracking
-- For low-cardinality: Much cheaper (small hash table)

The GROUP BY Order Matters

PostgreSQL CPU Cost Parameters

PostgreSQL exposes CPU cost through configurable parameters, allowing calibration for different hardware and workloads.

postgresql_cpu_costs.sql
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
-- PostgreSQL CPU Cost Parameters
-- ================================================================
 
-- Cost to process a single tuple (baseline per-row overhead)
cpu_tuple_cost = 0.01       -- Default: 1% of a sequential page read
 
-- Cost to process an operator expression or function per tuple
cpu_operator_cost = 0.0025  -- Default: 0.25% of sequential page read
 
-- Cost to process an index entry during index scan
cpu_index_tuple_cost = 0.005  -- Default: 0.5% of sequential page read
 
-- These are relative to seq_page_cost = 1.0
 
-- ================================================================
-- EXAMPLE: Cost calculation for a filtered table scan
-- ================================================================
-- Query: SELECT * FROM users WHERE status = 'active';
-- Stats: users has 1M rows, 50,000 pages
 
-- Cost components:
--   1. Sequential I/O: 50,000 pages × 1.0 = 50,000
--   2. Tuple processing: 1,000,000 × 0.01 = 10,000
--   3. Predicate eval: 1,000,000 × 0.0025 = 2,500
--   4. Output tuples (assume 10% selectivity): 100,000 × 0.01 = 1,000
--   
-- Total: 50,000 + 10,000 + 2,500 + 1,000 = 63,500
 
-- ================================================================
-- VIEWING COST BREAKDOWN IN EXPLAIN
-- ================================================================
EXPLAIN (VERBOSE, COSTS) 
SELECT * FROM users WHERE status = 'active';
 
-- Output:
-- Seq Scan on public.users  (cost=0.00..63500.00 rows=100000 width=120)
--   Output: id, name, email, status, created_at
--   Filter: (users.status = 'active'::text)
 
-- ================================================================
-- ADJUSTING CPU COSTS FOR FAST STORAGE
-- ================================================================
-- On fast SSDs with data mostly cached, CPU becomes relatively more important.
-- Consider increasing CPU costs or decreasing I/O costs:
 
-- Option 1: Reduce I/O costs (data is cached)
SET random_page_cost = 1.1;
SET seq_page_cost = 1.0;  -- Already baseline
 
-- Option 2: Increase CPU costs (emphasize CPU in decisions)
SET cpu_tuple_cost = 0.03;
SET cpu_operator_cost = 0.01;
 
-- Example impact: Index scan with 100K random reads
-- Default: 100K × 4.0 + 100K × 0.01 = 401,000 (I/O dominates)
-- Adjusted: 100K × 1.1 + 100K × 0.03 = 113,000 (more balanced)

Parallel Query CPU Costs:

Parallel execution introduces additional CPU overhead for coordination:

parallel_tuple_cost = 0.1        -- Cost to pass tuple between processes
parallel_setup_cost = 1000       -- Fixed cost to start parallel workers

For parallel plan viability:
  Total_cost(parallel) < Total_cost(serial)

Parallel savings must exceed:
  - parallel_setup_cost (initial overhead)
  - parallel_tuple_cost × tuples_transferred (per-tuple IPC overhead)

Small queries don't benefit from parallelism—the coordination costs exceed savings. Large scans and aggregations parallelize well because work division savings dwarf overhead.

When to Adjust CPU Costs

CPU Cost in Modern Workloads

Modern database workloads increasingly stress CPU relative to I/O. Several trends drive this shift:

CPU-Intensive Modern Workloads

•Real-Time Analytics — Complex aggregations, window functions, and statistical calculations on streaming data. Ad-hoc OLAP queries may touch millions of rows with multi-stage computations.
•JSON/Document Processing — Semi-structured data requires parsing, extraction, and type coercion at query time. JSON columns may hold deeply nested structures requiring recursive traversal.
•Full-Text Search — Tokenization, stemming, and relevance scoring involve substantial string processing. TF-IDF and BM25 ranking compute similarity scores across documents and query terms.
•Machine Learning Integration — Inference within queries using trained models (classify, predict) involves model evaluation per row. Vector similarity for embeddings requires high-dimensional distance calculations.
•Encryption/Security — Always-encrypted columns require decryption for every access. Row-level security policies add predicate checks. Audit logging serializes each operation.
•Complex Business Logic — Stored procedures, triggers, and multi-statement transactions accumulate CPU costs. Legacy systems with UDF-heavy architectures suffer significant overhead.

Case Study: Vector Similarity Search

Embedding-based search (semantic search, recommendation) exemplifies CPU-intensive querying:

-- Find 10 most similar products to a given embedding
SELECT product_id, name
FROM products  
ORDER BY embedding <-> '[0.12, 0.45, ..., 0.89]'::vector(1536)
LIMIT 10;

-- Cost breakdown for 1M products:
--   Distance calculation: 1M × 1536 dimensions × 2 ops = 3B operations
--   At 3 GHz, single-threaded: ~1 second just for distance
--   Plus comparison, heap management for top-10 tracking

-- Solutions:
--   1. Vector index (HNSW, IVF): Approximate NN, ~1000× faster
--   2. Dimensionality reduction: Fewer dimensions to compare  
--   3. Pre-filtering: Reduce candidates before similarity search

Vector databases (Pinecone, Milvus, pgvector) specialize in optimizing these CPU-heavy workloads through approximate algorithms and SIMD-optimized distance functions.

The AI/ML Query Tax

Summary: CPU Cost Mastery

CPU cost is increasingly critical in modern database optimization. Let's consolidate the key concepts:

Key Takeaways

•CPU cost scales linearly with tuple count — Cardinality estimation directly drives CPU cost estimation. Errors propagate proportionally.
•Per-tuple overhead is substantial — Iterator model mechanics, column extraction, and MVCC checking add 100-300ns baseline per tuple per operator.
•Predicate costs vary by 1000× — Integer comparison vs. regex matching represent vastly different CPU costs. Predicate ordering optimization yields major savings.
•UDF cost must be specified explicitly — The optimizer cannot introspect function complexity. Use COST and ROWS clauses to enable smart planning.
•Joins have algorithm-specific CPU profiles — Hash joins have build+probe hashing costs; merge joins have comparison costs; nested loops multiply outer cardinality.
•Modern workloads stress CPU — Cached data, complex analytics, JSON processing, and vector search shift bottlenecks from I/O to CPU.
•PostgreSQL provides tunable parameters — cpu_tuple_cost, cpu_operator_cost can be calibrated for your hardware and workload characteristics.

What's Next:

Page Complete

3 / 5