How the Cost-Based Optimizer Chooses a Plan

The one thing to understand first

For any non-trivial query there are many ways to get the answer — different scan methods, join orders, and join algorithms. The planner/optimizer (src/backend/optimizer/) enumerates candidate paths, estimates the cost of each, and picks the cheapest. It does not try every possibility exhaustively; it prunes aggressively.

The optimizer is a pure function: selectivity in, cost out. It almost always picks the right plan given accurate row counts, so plan debugging is not about outsmarting the planner — it is about finding the one row estimate that is wrong.

Paths and the cheapest-path principle

For each relation the planner builds Path objects — one per viable access method (seq scan, each usable index, bitmap). Paths carry a cost and useful properties such as sort order. At each level the planner keeps only the cheapest path for each distinct useful property (e.g. cheapest unordered, cheapest sorted by X). This pruning is what keeps planning tractable.

Where the cost numbers come from

Cost estimation needs selectivity: what fraction of rows a predicate keeps. This comes from the statistics collected by ANALYZE into pg_statistic (viewed via pg_stats):

• null fraction and n_distinct (number of distinct values).
• Most Common Values (MCVs) and their frequencies — used for equality on skewed columns.
• A histogram of value boundaries — used for range predicates.

For WHERE x = 'foo' the planner checks the MCV list; if present it uses the exact frequency, otherwise it assumes uniform distribution over the non-MCV distinct values. This is why skewed data with a too-small MCV list produces bad estimates.

The join search

Join ordering dominates plan quality. The planner uses dynamic programming (join_search_one_level in allpaths.c): it finds best paths for every single relation, then every pair, then every triple, reusing sub-results. The number of combinations grows fast, so beyond geqo_threshold (default 12 relations) PostgreSQL switches to the Genetic Query Optimizer (GEQO), which searches the space heuristically rather than exhaustively.

Choosing a join algorithm

For each candidate join the planner costs three algorithms:

• Nested Loop — for each outer row, probe the inner. Cheap when the outer side is tiny or the inner has a selective index. Cost explodes if the outer is large.
• Hash Join — build a hash table on the smaller side, probe with the larger. Great for big, unsorted, equality joins; needs work_mem to hold the hash table or it spills to disk.
• Merge Join — sort both inputs (or use already-sorted index output) and merge. Wins when inputs are already ordered or for large range joins.

Why estimates matter more than the algorithm

The planner almost always picks the right algorithm given accurate row counts. The failures happen when a row estimate is off by orders of magnitude — it then picks a nested loop expecting 5 inner rows but gets 5 million. The fix is rarely a hint (PostgreSQL has none by design); it is better statistics.

Layer 3 — Watch it happen on your own database

-- See the raw inputs the planner uses
SELECT attname, null_frac, n_distinct, most_common_vals
FROM   pg_stats WHERE tablename = 'events' AND attname = 'tenant_id';

-- Raise resolution on a skewed column
ALTER TABLE events ALTER COLUMN tenant_id SET STATISTICS 1000;
ANALYZE events;

-- Teach the planner about correlated columns
CREATE STATISTICS ev_corr (dependencies, ndistinct)
  ON tenant_id, status FROM events;
ANALYZE events;

Run EXPLAIN on a query filtering tenant_id and status together before and after creating the extended statistics: the estimated row count snaps closer to reality because the planner now knows the columns are correlated instead of multiplying their selectivities as if independent. That single change often flips a disastrous nested loop into a hash join.

Layer 4 — The levers this hands you

• random_page_cost — lower it (e.g. 1.1) on SSDs so the planner stops over-penalising index scans.
• effective_cache_size — tell the planner how much memory is effectively available for caching; higher values favour index scans.
• work_mem — too low forces hash/sort spills, making the planner avoid those plans.
• SET STATISTICS / extended statistics — raise resolution on skewed or correlated columns where the default 100 buckets mislead.
• geqo_threshold — controls when the exhaustive join search gives way to the genetic optimizer; raise it if you have many-way joins that plan poorly.

Layer 5 — What an Oracle DBA should expect vs what they get

Both are cost-based optimizers, but the surrounding machinery is very different:

• No hints, ever (in core). Oracle's culture of /*+ ... */ hints does not exist here. You shape plans through statistics, indexes, and GUCs — the discipline is "fix the estimate," not "pin the plan."
• Extended statistics instead of column groups + dynamic sampling. Oracle handles correlation with column-group stats and dynamic sampling; PostgreSQL uses CREATE STATISTICS (dependencies / ndistinct / MCV) — same goal, explicit and per-combination.
• GEQO for many-way joins. Oracle has its own join-order heuristics and adaptive plans; Postgres switches to a genetic search past geqo_threshold relations rather than using adaptive re-optimization.
• No SQL Plan Management. There are no baselines or profiles in core; plan stability comes from stable, well-targeted statistics (and optionally pg_hint_plan if you truly need hints).

Key takeaway

The optimizer builds Path objects per relation, keeps only the cheapest path per useful property, and uses dynamic programming (or GEQO past 12 relations) to order joins — all driven by selectivity estimates from pg_statistic. Get the row counts right and the planner gets the plan right. When a plan is bad, find the node whose estimate is wildly off and fix its statistics; reach for GUCs like random_page_cost only after the numbers are trustworthy.