Statistics and Histograms

All the statistics we've collected—table sizes, column distributions, histograms, correlations—converge on a single critical output: cardinality estimation. This is the optimizer's prediction of how many rows will flow through each node of the query plan.

Get the cardinality right, and the optimizer makes brilliant decisions. Get it wrong, and even a sophisticated optimizer produces disastrous plans. A query expected to return 100 rows might actually return 1 million. The optimizer chose a nested loop join (perfect for 100 rows, catastrophic for 1 million), and the query runs 10,000x slower than optimal.

Cardinality in query optimization means the number of rows produced by an operator or flowing through a node in the query plan. Cardinality estimation is the process of predicting these counts without executing the query.

How Cardinality Estimation Works:

Input: Base table statistics + Query predicates
Output: Estimated row count at each plan node

Process:
1. Start with base table cardinality (from statistics)
2. Apply selectivity factors for each predicate:
   estimated_rows = base_rows × selectivity
3. Propagate estimates up through the plan tree
4. Use join selectivity formulas for joining tables

Example:

SELECT * FROM orders o
JOIN customers c ON o.customer_id = c.customer_id
WHERE o.status = 'pending'
  AND o.order_date > '2024-01-01'
  AND c.country = 'US';

Base tables:
  orders: 10,000,000 rows
  customers: 1,000,000 rows

Estimation steps:
1. orders after status filter:
   sel(status='pending') = 0.20 (from MCV)
   10,000,000 × 0.20 = 2,000,000 rows

2. orders after date filter:
   sel(date > '2024-01-01') = 0.30 (from histogram)
   Combined: 2,000,000 × 0.30 = 600,000 rows
   (assumes independence)

3. customers after country filter:
   sel(country='US') = 0.40 (from MCV)
   1,000,000 × 0.40 = 400,000 rows

4. Join cardinality:
   join_sel = 1 / max(NDV(o.customer_id), NDV(c.customer_id))
   join_sel = 1 / 1,000,000 = 0.000001
   
   600,000 × 400,000 × 0.000001 = 240,000 result rows

Cardinality estimation is fundamentally approximate. Many sources of error are inherent to the statistical approach.

The Independence Problem in Detail:

-- Query with correlated columns
SELECT * FROM employees
WHERE department = 'Engineering'
  AND skill = 'Python';

-- True correlation: 90% of Python developers are in Engineering

Optimizer's calculation (independence):
  P(Engineering) = 0.30
  P(Python) = 0.20
  P(Engineering AND Python) = 0.30 × 0.20 = 0.06 (6%)

Actual probability: 0.18 (18%) — 3x underestimate!

-- The optimizer underestimates, potentially choosing:
--   - Index scan instead of table scan
--   - Nested loop instead of hash join

Individual estimation errors are problematic; error propagation through joins is catastrophic. Join cardinality estimation multiplies errors, often exponentially.

The Join Explosion:

Consider a 4-way join:
  A ⋈ B ⋈ C ⋈ D

True cardinalities:
  |A| = 100,000
  |A ⋈ B| = 10,000
  |A ⋈ B ⋈ C| = 5,000
  |A ⋈ B ⋈ C ⋈ D| = 1,000

With 2x overestimate at each join:
  |A ⋈ B|_est = 20,000            (2x off)
  |A ⋈ B ⋈ C|_est = 20,000        (4x off)
  |A ⋈ B ⋈ C ⋈ D|_est = 8,000     (8x off)

With 3x overestimate at each join:
  |A ⋈ B|_est = 30,000            (3x off)
  |A ⋈ B ⋈ C|_est = 45,000        (9x off)
  |A ⋈ B ⋈ C ⋈ D|_est = 27,000    (27x off!)

With n joins and an average per-join error factor of e, final cardinality error can be e^n. A 2-table query with 3x error stays 3x wrong. A 5-table query becomes 243x wrong.

Why Join Order Matters More Than You Think:

Given severe underestimate for A ⋈ B:
  True: 1,000,000 rows
  Estimated: 1,000 rows

Optimizer's plan (based on estimate):
  Build tiny hash table for A ⋈ B (1,000 rows fits in 64KB)
  Stream C through it

What actually happens:
  Hash table needs 1,000,000 rows → 64MB
  Exceeds memory → spills to disk
  Performance: 100x slower than estimated

Better plan (if estimate was correct):
  Build hash on C (smaller table)
  Stream A ⋈ B through it
  Much better memory utilization

When queries perform poorly, cardinality misestimation is often the culprit. Here's how to diagnose it systematically.

Once you've diagnosed estimation problems, several mitigation strategies can improve accuracy.

Modern databases incorporate adaptive execution features that can correct cardinality errors during query execution, not just during planning.

SQL Server Adaptive Query Processing (2017+):

1. Memory Grant Feedback
   - Hash joins that spill to tempdb remember the spill
   - Next execution gets more memory automatically
   - Gradually converges to optimal memory grant

2. Adaptive Joins
   - Plan includes BOTH nested loop and hash join choices
   - At runtime, chooses based on actual row count
   - If <threshold rows: nested loop; else: hash join

3. Interleaved Execution
   - Multi-statement table-valued functions
   - Execute TVF first, use actual cardinality for rest of plan

Oracle Adaptive Plans (12c+):

1. Adaptive Plan Selection
   - Plan compiled with "statistics collector" operators
   - During first execution, actual cardinality is observed
   - Plan switches sub-plans based on observed cardinality

2. SQL Plan Directives
   - When estimates are wrong, directive is created
   - Next execution uses dynamic sampling for that table/predicate
   - Automatically improves estimates without manual intervention

3. Auto-Created Extended Statistics
   - Optimizer tracks which column groups have correlated estimates  
   - Automatically creates column group statistics on problematic groups

PostgreSQL Adaptive Mechanisms:

PostgreSQL takes a more conservative approach:

1. No runtime plan switching
   - Plan is fixed at compile time
   - Philosophy: predictable execution over adaptive optimization

2. JIT Compilation Adapts to Row Count
   - Large result sets trigger JIT compilation
   - Based on actual execution, not estimates

3. Parallel Query Adaptation
   - Workers can terminate early if estimates were wrong
   - But initial worker count is based on estimates

General guidance for PostgreSQL:
  - Focus on statistics accuracy upfront
  - Use extended statistics for correlations
  - Consider pg_hint_plan extension for problem queries

Despite our best efforts, cardinality estimation has fundamental theoretical limits that cannot be overcome with more statistics or better algorithms.

The Parameter Sensitivity Problem:

-- Same query, vastly different selectivity
SELECT * FROM orders WHERE status = @status;

@status = 'pending'   → 40% of table (4M rows)
@status = 'archived'  → 0.01% of table (1,000 rows)

Optimal plan for 'pending':   Sequential scan + hash join
Optimal plan for 'archived':  Index scan + nested loop join

The optimizer compiles ONE plan. Which parameter does it optimize for?

Solutions:
1. Parameter sniffing: Use first executed value (SQL Server, Oracle)
   → Works great until a different value runs and reuses the plan

2. Average selectivity: Estimate for 'typical' value
   → Often wrong for both extremes

3. Multiple plans: Compile different plans for different parameter ranges
   → Few databases support this well

4. OPTION (RECOMPILE): Compile fresh plan each time
   → Works but adds compilation overhead

Cardinality estimation is where statistics meet decision-making. Every optimization choice—join order, access method, memory allocation—depends on the optimizer's row count predictions. Accurate estimation enables brilliant query plans; inaccurate estimation causes disasters.

Module Complete:

You've now explored the complete statistical foundation of query optimization:

1. Table Statistics — Row counts, block counts, and average widths
2. Column Statistics — NDV, null fractions, min/max values, correlation, and MCVs
3. Histograms — Distribution capture for precise range selectivity
4. Statistics Maintenance — Keeping statistics fresh through auto and manual processes
5. Estimation Accuracy — How statistics become cardinality estimates and why accuracy matters

This knowledge forms the diagnostic foundation for query performance troubleshooting. When a query is slow, you now know where to look first: Are the stats fresh? Are the estimates accurate? What's causing the discrepancy?