Statistics and cardinality estimation

The planner chooses a plan by estimating the cost of each option. Most of that cost depends on one number: how many rows each step will produce. This estimate is called cardinality estimation. If it is wrong, the planner can pick a plan that is good for 100 rows but terrible for a million.

The big idea: summaries of each column

Running ANALYZE samples the table and stores summaries for each column in Postgres. The summaries include:

• the fraction of rows that are null
• the number of distinct values
• a list of the most common values, with how often each appears
• a histogram that describes the spread of the other values

Autovacuum runs ANALYZE in the background, so the summaries usually stay fresh. After a large import or a big change in the data, run ANALYZE by hand.

Walking through an estimate

The planner estimates the rows for a condition by multiplying selectivities. It assumes the conditions are independent. Here is an example with illustrative numbers.

orders table          = 20,000,000 rows
customer_id = 42      = 1 in 100,000 customers, selectivity 0.00001
status = 'paid'       = 80% of rows, selectivity 0.8

estimate, assuming independence:
  20,000,000 × 0.00001 × 0.8 = 160 rows

Now suppose customer 42 is a bulk buyer, and nearly all of their orders are paid. The actual result might be 5,000 rows. The estimate is 30 times too low. The independence assumption failed because customer_id and status are correlated, and the planner had no way to know.

Why correlation breaks estimates

Correlated columns are common. A city and a zip code are tied together. So are a country and a currency, or a customer_id and that customer's status. Multiplying their selectivities double-counts the restriction, and the estimate falls too low.

When the estimate is too low, the planner may pick a nested loop where a hash join is better. When it is too high, it may build a large hash table that is not needed.

Fixing the estimate

First, refresh the statistics, then check again.

ANALYZE orders;

If the columns are correlated, create extended statistics that record how they depend on each other. Then analyze again.

CREATE STATISTICS orders_cust_status (dependencies)
  ON customer_id, status FROM orders;
ANALYZE orders;

The statistics object is named orders_cust_status, and it covers the two columns together.

Spotting a bad estimate

In EXPLAIN ANALYZE, compare the rows= estimate with actual rows=. A gap of 10 times or more is a strong sign of a bad plan.

If the estimate says 100 and the actual is 1,000,000, stop tuning indexes. Ask why the estimate is wrong. A new index will not fix a wrong estimate, and it may make the plan worse.

Common mistakes

• Adding indexes to fix a wrong estimate. Refresh the statistics first.
• Forgetting ANALYZE after a bulk load. The planner keeps using the old summaries.
• Ignoring correlated filters. Use extended statistics for columns that move together.
• Treating the planner as wrong by default. It is often right, given the data it has.

Check yourself

1. Why does multiplying selectivities give a bad estimate for correlated columns? It assumes the columns are independent. When they move together, the combined condition keeps more rows than the product predicts.
2. The estimate says 100 rows, and the actual is 1,000,000. What should you do first? Run ANALYZE on the table, then check whether correlated columns need extended statistics.

Key takeaways

• The planner's costs depend on row estimates. The estimates depend on statistics.
• Statistics assume independent columns, which often fails for correlated data.
• Run ANALYZE after large changes, and create extended statistics for correlated columns.
• Compare estimate with actual in EXPLAIN ANALYZE before changing indexes or queries.

Further learning

Next, read reading EXPLAIN ANALYZE to put this together on a slow query, from the plan output to the fix.

PostgreSQL docs: Using EXPLAIN14.1. Using EXPLAIN # 14.1.1. EXPLAIN Basics 14.1.2. EXPLAIN ANALYZE 14.1.3. Caveats PostgreSQL devises a query plan for each query it …PostgreSQL Documentation