Part 163: Query Optimizer Statistics, Histograms & Cardinality Estimation

How the database cost engine predicts row counts to formulate the optimal execution plan.

1. What are Optimizer Statistics?

The database optimizer does not execute queries to see how long they take; it calculates mathematical cost estimates based on metadata statistics: - Total row and page count of the table. - Number of distinct values (cardinality) in each column. - Fraction of NULL values. - Histograms: Distribution buckets showing value frequencies across column ranges.

2. Inspecting Column Statistics (PostgreSQL)

SELECT 
    attname AS column_name,
    n_distinct,
    null_frac,
    most_common_vals,
    most_common_freqs
FROM pg_stats 
WHERE tablename = 'orders' AND attname = 'status';

3. Cardinality Estimation Errors: The Root of Bad Plans

When statistics are stale or correlations are unknown: - The optimizer might estimate 1 row, choosing a Nested Loop join. - At runtime, the query actually returns 1,000,000 rows! - The Nested Loop executes 1 million index lookups, turning a sub-second query into a 10-minute freeze.

4. Multi-Column Extended Statistics

Relational optimizers assume column independence. If you filter by state = 'CA' AND city = 'San Francisco': - The optimizer multiplies individual probabilities ($P(CA) \times P(SF)$), drastically underestimating row count! - In modern PostgreSQL, create extended statistics:

CREATE STATISTICS stat_geo_city_state ON city, state FROM customers;
ANALYZE customers;

Key Takeaways

• Always run ANALYZE after large bulk inserts or migrations.
• Discrepancies between Estimated Rows and Actual Rows in EXPLAIN ANALYZE reveal stale statistics.

In Part 164, we explore Parameter Sniffing & Plan Cache Poisoning!