22.2 The Optimizer: Statistics & Join Algorithms — The Complete SQL Course

The optimizer is PostgreSQL's route planner: it turns one declarative query into a concrete path through pages, indexes, joins, sorts, and filters. This lesson goes beneath the beginner EXPLAIN reading from Section 16 and asks the more useful question: what did the planner believe about the data?

22.1 gave you the physical model: heap pages, B-tree index pages, and the cost of non-sequential page fetches. Now we add the planner's map of that world: table statistics, cardinality estimates, join algorithms, and the one extra wrinkle prepared statements introduce.

Statistics: the planner's map of your data

PostgreSQL cannot run every possible plan and compare them. It estimates. Cardinality estimation means guessing how many rows will flow out of a scan, filter, or join before execution starts. Those guesses come from statistics collected by ANALYZE.

This lesson-local setup has a deliberately skewed customer table and a larger orders table:

CREATE TABLE opt_customers (
  customer_id int PRIMARY KEY,
  tier text NOT NULL,
  signup_day int NOT NULL
);
 
INSERT INTO opt_customers (customer_id, tier, signup_day)
SELECT g,
       CASE
         WHEN g <= 700 THEN 'free'
         WHEN g <= 950 THEN 'paid'
         ELSE 'enterprise'
       END,
       g
FROM generate_series(1, 1000) AS g;
 
CREATE TABLE opt_orders (
  order_id int PRIMARY KEY,
  customer_id int NOT NULL REFERENCES opt_customers (customer_id),
  amount int NOT NULL
);
 
INSERT INTO opt_orders (order_id, customer_id, amount)
SELECT g,
       ((g - 1) % 1000) + 1,
       CASE
         WHEN ((g - 1) % 1000) + 1 <= 50 THEN 500
         ELSE 25
       END
FROM generate_series(1, 10000) AS g;
 
CREATE INDEX opt_customers_tier_idx
ON opt_customers (tier);
 
CREATE INDEX opt_orders_customer_idx
ON opt_orders (customer_id);
 
ANALYZE opt_customers;
ANALYZE opt_orders;
 
SELECT count(*) AS customers,
       count(*) FILTER (WHERE tier = 'free') AS free_customers,
       count(*) FILTER (WHERE tier = 'paid') AS paid_customers,
       count(*) FILTER (WHERE tier = 'enterprise') AS enterprise_customers
FROM opt_customers;
 
SELECT count(*) AS orders,
       count(*) FILTER (WHERE amount = 500) AS high_amount_orders,
       count(*) FILTER (WHERE amount = 25) AS regular_orders
FROM opt_orders;

CREATE TABLE
INSERT 0 1000
CREATE TABLE
INSERT 0 10000
CREATE INDEX
CREATE INDEX
ANALYZE
ANALYZE
 customers | free_customers | paid_customers | enterprise_customers
-----------+----------------+----------------+----------------------
      1000 |            700 |            250 |                   50
(1 row)
 orders | high_amount_orders | regular_orders
--------+--------------------+----------------
  10000 |                500 |           9500
(1 row)

The skew matters. If PostgreSQL pretended every tier was equally common, it would guess badly for both 'free' and 'enterprise'. ANALYZE gives it a better map.

Reading pg_class and pg_stats

You saw pg_class.relpages and pg_class.reltuples in 22.1. Those are table-level estimates. pg_stats is the readable view of column-level statistics:

SELECT c.relname AS relation_name,
       c.relpages,
       c.reltuples::int AS estimated_rows
FROM pg_class AS c
WHERE c.relname IN ('opt_customers', 'opt_orders')
ORDER BY c.relname;
 
SELECT s.attname,
       s.n_distinct,
       s.most_common_vals::text AS common_values,
       s.most_common_freqs::text AS common_freqs,
       left(s.histogram_bounds::text, 52) AS histogram_sample,
       round(s.correlation::numeric, 2) AS correlation
FROM pg_stats AS s
WHERE s.schemaname = 'public'
  AND s.tablename = 'opt_customers'
  AND s.attname IN ('tier', 'signup_day')
ORDER BY s.attname;

 relation_name | relpages | estimated_rows
---------------+----------+----------------
 opt_customers |        6 |           1000
 opt_orders    |       55 |          10000
(2 rows)
  attname   | n_distinct |     common_values      |  common_freqs   |                   histogram_sample                   | correlation
------------+------------+------------------------+-----------------+------------------------------------------------------+-------------
 signup_day |         -1 | NULL                   | NULL            | {1,10,20,30,40,50,60,70,80,90,100,110,120,130,140,15 |        1.00
 tier       |          3 | {free,paid,enterprise} | {0.7,0.25,0.05} | NULL                                                 |        0.72
(2 rows)

n_distinct = 3 says tier has three distinct values, while a negative n_distinct (like signup_day's -1) means the column is unique or nearly so — PostgreSQL stores it as a proportion so the estimate scales as the table grows. most_common_vals and most_common_freqs say the common values are not evenly distributed: free is 0.7, paid is 0.25, and enterprise is 0.05 of the table. histogram_bounds gives the planner buckets for values that are not captured as most-common values. Correlation tells PostgreSQL how closely a column's logical order matches the table's physical order; signup_day is 1.00 here because it was inserted in the same order as the value.

Those columns answer different planner questions. n_distinct helps with equality predicates: "how many rows might tier = ... keep?" Most-common values protect the planner from assuming a uniform split when the data is skewed. Histograms help with range predicates such as "before this day" or "between these amounts." Correlation connects directly to 22.1's pages: if nearby logical values tend to live near each other physically, an ordered scan may touch pages more predictably than it would on scattered data.

ANALYZE samples and estimates, so you should treat these numbers as planner inputs, not accounting reports. They are accurate enough to guide plans, and approximate enough that performance debugging always comes back to the same question: where did the estimate stop matching reality?

Join algorithms: three legal routes

A join is a match-maker, not a merge; the planner still has to choose how to do the matching. PostgreSQL's everyday join algorithms are:

Nested Loop — for each outer row, look for matching inner rows. Excellent when the outer side is tiny and the inner side has a useful index.
Hash Join — build an in-memory hash table from one side, then scan the other side and probe it. Strong for equality joins where a broad scan is already reasonable.
Merge Join — read both sides in join-key order and advance through them together. Strong when both inputs are already sorted or cheaply sortable.

The next block temporarily discourages two algorithms at a time so you can see stable shapes. Those SET lines are a teaching instrument, not a tuning recipe:

SET enable_hashjoin = off;
SET enable_mergejoin = off;
 
EXPLAIN (COSTS OFF)
SELECT c.customer_id, o.order_id
FROM opt_customers AS c
JOIN opt_orders AS o
  ON o.customer_id = c.customer_id
WHERE c.customer_id BETWEEN 1 AND 3;
 
RESET enable_hashjoin;
RESET enable_mergejoin;
 
SET enable_mergejoin = off;
SET enable_nestloop = off;
 
EXPLAIN (COSTS OFF)
SELECT c.tier, count(o.order_id) AS orders
FROM opt_customers AS c
JOIN opt_orders AS o
  ON o.customer_id = c.customer_id
GROUP BY c.tier;
 
RESET enable_mergejoin;
RESET enable_nestloop;
 
SET enable_hashjoin = off;
SET enable_nestloop = off;
 
EXPLAIN (COSTS OFF)
SELECT c.customer_id, o.order_id
FROM opt_customers AS c
JOIN opt_orders AS o
  ON o.customer_id = c.customer_id
WHERE c.customer_id <= 5;
 
RESET enable_hashjoin;
RESET enable_nestloop;

SET
SET
                            QUERY PLAN
-------------------------------------------------------------------
 Nested Loop
   ->  Index Only Scan using opt_customers_pkey on opt_customers c
         Index Cond: ((customer_id >= 1) AND (customer_id <= 3))
   ->  Bitmap Heap Scan on opt_orders o
         Recheck Cond: (c.customer_id = customer_id)
         ->  Bitmap Index Scan on opt_orders_customer_idx
               Index Cond: (customer_id = c.customer_id)
(7 rows)
RESET
RESET
SET
SET
                     QUERY PLAN
----------------------------------------------------
 HashAggregate
   Group Key: c.tier
   ->  Hash Join
         Hash Cond: (o.customer_id = c.customer_id)
         ->  Seq Scan on opt_orders o
         ->  Hash
               ->  Seq Scan on opt_customers c
(7 rows)
RESET
RESET
SET
SET
                            QUERY PLAN
-------------------------------------------------------------------
 Merge Join
   Merge Cond: (c.customer_id = o.customer_id)
   ->  Index Only Scan using opt_customers_pkey on opt_customers c
         Index Cond: (customer_id <= 5)
   ->  Index Scan using opt_orders_customer_idx on opt_orders o
(5 rows)
RESET
RESET

Read each plan with the 22.1 storage model in the background. The nested loop plan uses the outer customer keys to probe the orders B-tree repeatedly. The hash join plan scans and builds a lookup structure because the query touches broad inputs. The merge join plan relies on both sides arriving in customer_id order, then walks them together.

In normal work, you usually do not force these switches. You read the plan PostgreSQL chose, ask which estimates made that choice look cheap, then change the schema, query, or statistics if the choice no longer fits reality. Join algorithms are not moral rankings. A nested loop can be perfect for three outer rows and disastrous for three million; a hash join can be wasteful for a tiny lookup and excellent for broad equality matching.

Prepared statements: custom vs generic plans

A prepared statement separates SQL text from later parameter values. That is the right security shape for application code, and 18.2 owns the injection lesson. The optimizer detail is subtler: PostgreSQL may use a custom plan, which sees the actual parameter value, or a generic plan, which plans for $1 without knowing the value.

PREPARE tier_lookup(text) AS
SELECT customer_id, tier
FROM opt_customers
WHERE tier = $1;
 
SET plan_cache_mode = force_custom_plan;
 
EXPLAIN (COSTS OFF)
EXECUTE tier_lookup('enterprise');
 
EXPLAIN (COSTS OFF)
EXECUTE tier_lookup('free');
 
SET plan_cache_mode = force_generic_plan;
 
EXPLAIN (COSTS OFF)
EXECUTE tier_lookup('free');
 
RESET plan_cache_mode;
DEALLOCATE tier_lookup;

PREPARE
SET
                    QUERY PLAN
---------------------------------------------------
 Bitmap Heap Scan on opt_customers
   Recheck Cond: (tier = 'enterprise'::text)
   ->  Bitmap Index Scan on opt_customers_tier_idx
         Index Cond: (tier = 'enterprise'::text)
(4 rows)
           QUERY PLAN
---------------------------------
 Seq Scan on opt_customers
   Filter: (tier = 'free'::text)
(2 rows)
SET
                    QUERY PLAN
---------------------------------------------------
 Bitmap Heap Scan on opt_customers
   Recheck Cond: (tier = $1)
   ->  Bitmap Index Scan on opt_customers_tier_idx
         Index Cond: (tier = $1)
(4 rows)
RESET
DEALLOCATE

The custom plans see real values. 'enterprise' is rare, so the tier index is attractive. 'free' is common, so reading the table once is reasonable. The forced generic plan shows $1 because it is not planned for that specific value; it needs one reusable shape. In PostgreSQL conversations this is custom-vs-generic planning; in other engines you will often hear the family of surprises called parameter sniffing.

Generic does not mean bad. Planning has a cost too, and a reusable plan can be the right trade for a statement whose parameters behave similarly. The risk is skew: one parameter value might keep a tiny slice while another keeps most of the table. When the same prepared SQL swings between those shapes, custom-vs-generic planning becomes part of the performance story.

sql — playgroundlive

CREATE TABLE opt_customers (
customer_id int PRIMARY KEY,
tier text NOT NULL,
signup_day int NOT NULL
);

INSERT INTO opt_customers (customer_id, tier, signup_day)
SELECT g,
     CASE
       WHEN g <= 700 THEN 'free'
       WHEN g <= 950 THEN 'paid'
       ELSE 'enterprise'
     END,
     g
FROM generate_series(1, 1000) AS g;

CREATE TABLE opt_orders (
order_id int PRIMARY KEY,
customer_id int NOT NULL REFERENCES opt_customers (customer_id),
amount int NOT NULL
);

INSERT INTO opt_orders (order_id, customer_id, amount)
SELECT g,
     ((g - 1) % 1000) + 1,
     CASE
       WHEN ((g - 1) % 1000) + 1 <= 50 THEN 500
       ELSE 25
     END
FROM generate_series(1, 10000) AS g;

CREATE INDEX opt_customers_tier_idx
ON opt_customers (tier);

CREATE INDEX opt_orders_customer_idx
ON opt_orders (customer_id);

ANALYZE opt_customers;
ANALYZE opt_orders;

SELECT s.attname,
     s.n_distinct,
     s.most_common_vals::text AS common_values,
     s.most_common_freqs::text AS common_freqs,
     round(s.correlation::numeric, 2) AS correlation
FROM pg_stats AS s
WHERE s.schemaname = 'public'
AND s.tablename = 'opt_customers'
AND s.attname IN ('tier', 'signup_day')
ORDER BY s.attname;

EXPLAIN (COSTS OFF)
SELECT c.tier, count(o.order_id) AS orders
FROM opt_customers AS c
JOIN opt_orders AS o
ON o.customer_id = c.customer_id
GROUP BY c.tier;

-- try at the prompt:
-- SELECT c.relname, c.reltuples::int AS estimated_rows FROM pg_class AS c WHERE c.relname = 'opt_orders';

-- break it: uncomment this misspelled catalog column, then Run
-- SELECT s.n_distnct FROM pg_stats AS s;

⌘/Ctrl + Enter to run

Statistics explain why plans change without changing answers. Next, 22.3 moves from planning to durability and concurrency: WAL, MVCC, crash recovery, and why old row versions eventually need cleanup.

Checkpoint

Answer all three to mark this lesson complete