Cost-Based Optimizer & Join Ordering - Cost Constants, Dynamic Programming, Left-Deep vs Bushy, join_collapse_limit & GEQO
PostgreSQL cost constants verified exactly against pg_class (Seq Scan = relpages + reltuples x cpu_tuple_cost); random_page_cost 4 vs 1.1 flipping seq vs index scan in real PG 17; runnable index-vs-seq crossover model and physical correlation; runnable Selinger DP join enumeration with left-deep vs bushy and the n!/Catalan explosion; join_collapse_limit/from_collapse_limit/GEQO with a real written-order plan; CBO vs rule-based vs Cascades vs adaptive vs learned.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
Question ladder
L1
What is the unit of PostgreSQL cost?
Answer
One sequential page read, seq_page_cost = 1.0.
L2
What is the Seq Scan cost formula?
Answer
relpages x seq_page_cost + reltuples x cpu_tuple_cost, plus cpu_operator_cost per row per qual.
L3
Why lower random_page_cost on SSDs?
Answer
Random reads are much cheaper there, so 4.0 overprices index scans and biases toward seq scans and hash joins.
L4
What is physical correlation and why does it matter?
Answer
How closely the column order matches the heap order. High correlation makes index scans read few pages.
L5
How does DP tame join ordering?
Answer
It builds the best plan for every connected subset, smallest first, and reuses those sub-plans.
L6
Left-deep or bushy?
Answer
Left-deep keeps the right input a base table and pipelines well; bushy lets two filtered branches shrink before they meet.
L7
What do join_collapse_limit = 1 and GEQO do?
Answer
The first forces the written join order; GEQO replaces exhaustive search with a genetic one at 12 or more items.
Failure modes
Search limits exceeded
A 15-table ORM query passes join_collapse_limit and geqo_threshold, so the plan depends on written order or a randomized search.
Constants tuned to the wrong hardware
random_page_cost 4 on NVMe keeps choosing seq scans for selective predicates.
Global constants changed to fix one query
Thousands of other plans silently change when the real problem was one row estimate.
Misconceptions
Costs are comparable across queries.
They only compare alternative plans of the same query under the same settings.
Explicit JOIN order is always ignored.
It is reordered only up to join_collapse_limit; beyond that it shapes the plan.
effective_cache_size allocates memory.
It is only a planner hint about how much data is likely cached.
Interviewer traps
Answering that the optimizer tries every join order.
It uses DP over connected subsets with limits, then heuristics or GEQO.
Recommending a rule-based approach because it is predictable.
Rules are blind to data size: an index on a 90% predicate runs far slower than a seq scan.
Design scenario
Same prompt for every reader.
Requirements
Deterministic plans for the report and no regressions for the rest of the workload.
Failure assumptions
- The query passes geqo_threshold.
- Statistics are current.
- The database runs on NVMe with default cost constants.
Constraints
- PostgreSQL 17, no hint extension.
- You can change the query and per-function settings, not the ORM's core.
Prompt
A reporting query joins 14 tables generated by an ORM. Its plan changes between runs and is sometimes very slow. Design how you would make it stable and fast.
API
Can the report be split into a view of the selective core plus the remaining joins?
Data
Which tables and filters are most selective, and are the cost constants right for the storage?
Architecture
Where do you use join_collapse_limit, from_collapse_limit or a rewritten join order, and how do you guard other queries?
Overview
A cost-based optimizer (CBO) does three things: it enumerates alternative plans, it estimates the cost of each with a model built from statistics and tunable constants, and it keeps the cheapest. PostgreSQL's cost model is surprisingly small: a handful of constants (seq_page_cost, random_page_cost, cpu_tuple_cost, cpu_index_tuple_cost, cpu_operator_cost, effective_cache_size, parallel_*) multiplied by estimated page and row counts. The hard part is enumeration: the number of possible join orders grows factorially, so optimizers use dynamic programming (System R, 1979) to share work between sub-plans, restrict the search space (left-deep vs bushy trees), and give up on exhaustiveness past a threshold (PostgreSQL's join_collapse_limit, from_collapse_limit and the genetic optimizer GEQO at geqo_threshold). Get the model constants wrong for your hardware, or exceed the search limits, and the optimizer picks plans that were "cheapest" only on paper.
How PostgreSQL prices a plan
Each path carries a startup cost (work before the first row) and a total cost (work to return all rows), in arbitrary units where reading one page sequentially costs 1.0. The default constants:
| Parameter | Default | Meaning | When people change it |
|---|---|---|---|
seq_page_cost | 1.0 | One page read as part of a sequential scan | Rarely; it is the unit |
random_page_cost | 4.0 | One page read out of order (index probes, heap fetches) | Lower (1.1 to 2) on SSD/NVMe or when the working set is cached |
cpu_tuple_cost | 0.01 | Processing one row | Rarely |
cpu_index_tuple_cost | 0.005 | Processing one index entry | Rarely |
cpu_operator_cost | 0.0025 | Evaluating one operator or function call | Rarely; functions can declare their own COST |
effective_cache_size | 4GB | Planner's guess of OS + shared buffer cache available | Set to ~50-75% of RAM; affects index scan pricing, not memory use |
parallel_setup_cost, parallel_tuple_cost | 1000, 0.1 | Starting workers, passing a row from worker to leader | Lower to encourage parallelism on analytics boxes |
Let the optimizer search join orders, or join in written order?
Prefer
Cost-based DP search
Build the best plan for every connected subset and reuse it.
- The bushy best plan cost 6,530,051.
- It joined regions with customers and items with promos before they met.
- Real PostgreSQL joined b with the 10-row table c first.
Alternative
Written order
Join exactly as the FROM clause lists the tables.
- The written order cost 26,310,051, about 4x more.
- join_collapse_limit = 1 forced a 100,000-row intermediate in PostgreSQL.
- Useful only to pin a hand-optimized order.
Comparing join tree shapes
Diagram 1 condensed.
- 1
Left-deep
Join A and B, then the result with C, then with D. - 2
Bushy
Join A with B and C with D separately, then join both results. - 3
Count the shapes
n! left-deep orders, n! x Catalan(n-1) bushy trees. - 4
Compare costs
DP keeps the cheapest plan per subset and reuses it.
The PostgreSQL 17 session below verifies the Seq Scan formula exactly against the catalog, then shows how one constant changes a plan.
-- Page 3: verify the Seq Scan cost formula, then watch random_page_cost and join_collapse_limit change plans.
\pset footer off
SET client_min_messages = warning;
DROP SCHEMA IF EXISTS p3 CASCADE;
CREATE SCHEMA p3;
SET search_path = p3;
SET max_parallel_workers_per_gather = 0;
-- ~700-byte rows so the heap is ~9k pages; bucket values are scattered across the heap (low correlation)
CREATE TABLE t AS SELECT g AS id, (g * 7919) % 1000 AS bucket, repeat('x', 700) AS pad FROM generate_series(1, 100000) g;
CREATE INDEX t_bucket_idx ON t (bucket);
VACUUM ANALYZE t;
-- 1) Seq Scan total cost = relpages * seq_page_cost + reltuples * cpu_tuple_cost (+ cpu_operator_cost per row per qual)
SELECT relpages, reltuples::bigint,
relpages * current_setting('seq_page_cost')::float8
+ reltuples * current_setting('cpu_tuple_cost')::float8 AS predicted_seqscan_cost,
relpages * current_setting('seq_page_cost')::float8
+ reltuples * (current_setting('cpu_tuple_cost')::float8 + current_setting('cpu_operator_cost')::float8) AS predicted_with_one_qual
FROM pg_class WHERE relname = 't';
EXPLAIN SELECT * FROM t;
EXPLAIN SELECT * FROM t WHERE bucket < 40; -- default planner: bitmap scan (sorts TIDs, reads heap pages in order)
-- 2) Isolate the classic index-scan vs seq-scan trade-off (bitmap off), then change only random_page_cost
SET enable_bitmapscan = off;
SHOW random_page_cost;
EXPLAIN SELECT * FROM t WHERE bucket < 40;
SET random_page_cost = 1.1; -- common SSD / cloud-volume setting
EXPLAIN SELECT * FROM t WHERE bucket < 40;
RESET random_page_cost; RESET enable_bitmapscan;
-- 3) join_collapse_limit: explicit JOIN syntax becomes a join-order constraint when the limit is 1
CREATE TABLE a AS SELECT g AS id FROM generate_series(1, 100000) g;
CREATE TABLE b AS SELECT g AS id, g % 100000 + 1 AS a_id FROM generate_series(1, 100000) g;
CREATE TABLE c AS SELECT g AS id, g AS b_id FROM generate_series(1, 10) g; -- tiny, very selective
ANALYZE a; ANALYZE b; ANALYZE c;
EXPLAIN (COSTS OFF) SELECT count(*) FROM a JOIN b ON b.a_id = a.id JOIN c ON c.b_id = b.id;
SET join_collapse_limit = 1; -- planner must join in the written order: (a JOIN b) JOIN c
EXPLAIN (COSTS OFF) SELECT count(*) FROM a JOIN b ON b.a_id = a.id JOIN c ON c.b_id = b.id;
RESET join_collapse_limit;
SHOW geqo_threshold;Real output (PostgreSQL 17.11, local sandbox, psql; setup DDL echoes omitted):
SET max_parallel_workers_per_gather = 0;
SELECT relpages, reltuples::bigint,
relpages * current_setting('seq_page_cost')::float8
+ reltuples * current_setting('cpu_tuple_cost')::float8 AS predicted_seqscan_cost,
relpages * current_setting('seq_page_cost')::float8
+ reltuples * (current_setting('cpu_tuple_cost')::float8 + current_setting('cpu_operator_cost')::float8) AS predicted_with_one_qual
FROM pg_class WHERE relname = 't';
relpages | reltuples | predicted_seqscan_cost | predicted_with_one_qual
----------+-----------+------------------------+-------------------------
9152 | 100000 | 10152 | 10402
EXPLAIN SELECT * FROM t;
QUERY PLAN
------------------------------------------------------------
Seq Scan on t (cost=0.00..10152.00 rows=100000 width=712)
EXPLAIN SELECT * FROM t WHERE bucket < 40;
QUERY PLAN
-------------------------------------------------------------------------------
Bitmap Heap Scan on t (cost=46.07..7185.24 rows=3842 width=712)
Recheck Cond: (bucket < 40)
-> Bitmap Index Scan on t_bucket_idx (cost=0.00..45.11 rows=3842 width=0)
Index Cond: (bucket < 40)
SET enable_bitmapscan = off;
SHOW random_page_cost;
random_page_cost
------------------
4
EXPLAIN SELECT * FROM t WHERE bucket < 40;
QUERY PLAN
----------------------------------------------------------
Seq Scan on t (cost=0.00..10402.00 rows=3842 width=712)
Filter: (bucket < 40)
SET random_page_cost = 1.1;
EXPLAIN SELECT * FROM t WHERE bucket < 40;
QUERY PLAN
------------------------------------------------------------------------------
Index Scan using t_bucket_idx on t (cost=0.29..3565.52 rows=3842 width=712)
Index Cond: (bucket < 40)
RESET random_page_cost;
RESET enable_bitmapscan;
EXPLAIN (COSTS OFF) SELECT count(*) FROM a JOIN b ON b.a_id = a.id JOIN c ON c.b_id = b.id;
QUERY PLAN
------------------------------------------------
Aggregate
-> Hash Join
Hash Cond: (a.id = b.a_id)
-> Seq Scan on a
-> Hash
-> Hash Join
Hash Cond: (b.id = c.b_id)
-> Seq Scan on b
-> Hash
-> Seq Scan on c
SET join_collapse_limit = 1;
EXPLAIN (COSTS OFF) SELECT count(*) FROM a JOIN b ON b.a_id = a.id JOIN c ON c.b_id = b.id;
QUERY PLAN
------------------------------------------
Aggregate
-> Hash Join
Hash Cond: (b.id = c.b_id)
-> Hash Join
Hash Cond: (a.id = b.a_id)
-> Seq Scan on a
-> Hash
-> Seq Scan on b
-> Hash
-> Seq Scan on c
RESET join_collapse_limit;
SHOW geqo_threshold;
geqo_threshold
----------------
12Reading it:
- The formula is exact.
relpages x seq_page_cost + reltuples x cpu_tuple_cost= 9,152 + 1,000 = 10,152, which is precisely the Seq Scan total cost. Add one qual per row (cpu_operator_cost x reltuples= 250) and you get the 10,402 shown for the filtered seq scan. - Bitmap scans are the default choice for a 4% predicate on scattered rows: the index produces a bitmap of matching heap locations, the executor reads those pages in physical order, turning random I/O into near-sequential I/O.
- With bitmap scans disabled, the classic trade-off appears: at
random_page_cost = 4an Index Scan on about 3,842 scattered rows is more expensive than reading the whole table, so the planner picks the Seq Scan; atrandom_page_cost = 1.1(typical SSD setting) the same Index Scan costs 3,565 and wins. Same data, same query, same index; one constant flipped the plan. - join_collapse_limit = 1 forces the planner to join in the written order. With the default (8), it first joins
bwith the 10-row tablec(tiny intermediate result) and only then joinsa; with the limit at 1 it must joinaandbfirst (100,000-row intermediate) and filter byclast.
Modeling the index-vs-seq crossover
Why is the crossover so sensitive? An index scan on an uncorrelated column pays roughly one random page per matching row (until it has touched most pages), while a seq scan pays one sequential page per table page. The simplified model below uses PostgreSQL's default constants and the table shape from the SQL demo. It is illustrative (PostgreSQL's real formula uses Mackert-Lohman with effective_cache_size and the column's physical correlation), but it lands close to the real plan costs.
// A simplified PostgreSQL-like cost model: Seq Scan vs Index Scan on an uncorrelated column.
// Planner constants are PostgreSQL defaults; table shape matches the p3 SQL demo (9,152 pages, 100k rows).
// The page-fetch estimate uses Cardenas' formula, a simplification of what PostgreSQL really does
// (it uses Mackert-Lohman with effective_cache_size), so treat outputs as illustrative, not exact.
const SEQ_PAGE = 1.0, CPU_TUPLE = 0.01, CPU_INDEX_TUPLE = 0.005, CPU_OP = 0.0025;
const PAGES = 9152, ROWS = 100_000;
function seqScanCost(): number {
return PAGES * SEQ_PAGE + ROWS * (CPU_TUPLE + CPU_OP); // read every page, evaluate qual on every row
}
function indexScanCost(selectivity: number, randomPageCost: number): number {
const n = ROWS * selectivity; // rows the index returns
const heapPages = PAGES * (1 - Math.pow(1 - 1 / PAGES, n)); // distinct heap pages touched (random order)
const indexPages = Math.ceil(n / 300); // ~300 index entries per leaf page (example)
return (heapPages + indexPages) * randomPageCost + n * (CPU_INDEX_TUPLE + CPU_TUPLE + CPU_OP);
}
function crossover(randomPageCost: number): number {
let lo = 0, hi = 1; // binary search the break-even selectivity
for (let i = 0; i < 50; i++) {
const mid = (lo + hi) / 2;
if (indexScanCost(mid, randomPageCost) < seqScanCost()) lo = mid; else hi = mid;
}
return lo;
}
console.log(`seq scan cost (one qual) = ${seqScanCost().toFixed(0)}`);
for (const rpc of [4.0, 1.1]) {
const at4pct = indexScanCost(0.04, rpc).toFixed(0);
console.log(`random_page_cost=${rpc}: index scan @4% = ${at4pct}; index stops winning above ~${(crossover(rpc) * 100).toFixed(1)}% selectivity`);
}
// Physical correlation matters: if matching rows are packed together, heap pages ~ n / rowsPerPage
const clustered = (sel: number, rpc: number) => {
const n = ROWS * sel;
return (Math.ceil(n / (ROWS / PAGES)) * SEQ_PAGE + Math.ceil(n / 300) * rpc + n * (CPU_INDEX_TUPLE + CPU_TUPLE + CPU_OP));
};
console.log(`clustered table, 4% selectivity, rpc=4: index scan = ${clustered(0.04, 4).toFixed(0)} (vs seq ${seqScanCost().toFixed(0)})`);Output:
seq scan cost (one qual) = 10402
random_page_cost=4: index scan @4% = 13088; index stops winning above ~3.0% selectivity
random_page_cost=1.1: index scan @4% = 3650; index stops winning above ~31.3% selectivity
clustered table, 4% selectivity, rpc=4: index scan = 493 (vs seq 10402)Expectedseq scan cost (one qual) = 10402 random_page_cost=4: index scan @4% = 13088; index stops winning above ~3.0% selectivity random_page_cost=1.1: index scan @4% = 3650; index stops winning above ~31.3% selectivity clustered table, 4% selectivity, rpc=4: index scan = 493 (vs seq 10402)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Three takeaways: with spinning-disk defaults, an index on a scattered column stops paying off at a few percent selectivity; with SSD-like settings it keeps winning up to roughly a third of the table; and physical correlation (rows with similar keys stored together, as with a time-ordered insert pattern or after CLUSTER) makes index scans dramatically cheaper. That is the correlation column in pg_stats, and why the same index can be great on created_at and useless on customer_id.
Join enumeration: why order matters and how DP tames it
Joins are commutative and associative, so A JOIN B JOIN C can be computed as (A ⋈ B) ⋈ C, (A ⋈ C) ⋈ B, (B ⋈ C) ⋈ A, and so on, each with three join algorithms and two input orientations. The cost difference comes from intermediate result sizes: joining the two most selective relations first keeps every later join small.
Architecture
Left-deep tree
- 1
Step 1: A join B
- nextStep 2: result join C
- 2
Step 2: result join C
- nextStep 3: result join D
- 3
Step 3: result join D
Bushy tree
- 4
Step 1a: A join B
- nextStep 2: join both results
- 5
Step 2: join both results
- 6
Step 1b: C join D
- nextStep 2: join both results
Flow
- 7
LD
- n! orders, pipelines well, every inner input is a base tableStep 4: compare costs
- 8
Step 4: compare costs
- 9
BU
- n! x Catalan(n-1) shapes, can shrink two sides independentlyStep 4: compare costs
Lesson map
Cost-Based Optimizer & Join Ordering - Cost Constants, Dynamic Programming, Left-Deep vs Bushy, join_collapse_limit & GEQO
PostgreSQL cost constants verified exactly against pg_class (Seq Scan = relpages + reltuples x cpu_tuple_cost); random_page_cost 4 vs 1.1 flipping seq vs index scan in real PG 17; runnable index-vs-seq crossover model and physical correlation; runnable Selinger DP join enumeration with left-deep vs bushy and the n!/Catalan explosion; join_collapse_limit/from_collapse_limit/GEQO with a real written-order plan; CBO vs rule-based vs Cascades vs adaptive vs learned.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB l1["Step 1: A join B"] l2["Step 2: result join C"] l3["Step 3: result join D"] b1["Step 1a: A join B"] b3["Step 2: join both results"] b2["Step 1b: C join D"] ld["Left-deep tree"] x["Step 4: compare costs"] bu["Bushy tree"] l1 -->|continues| l2 l2 -->|continues| l3 b1 -->|continues| b3 b2 -->|continues| b3 ld -->|n! orders, pipelines well, every inner input is a base table| x bu -->|n! x Catalan(n-1) shapes, can shrink two sides independently| x
Left-deep trees (every join's right input is a base table) were System R's restriction: they pipeline well with nested loops and keep the search to n! orders. Bushy trees allow both inputs to be join results, which is better for star and snowflake schemas where two dimension filters can shrink two sides independently. PostgreSQL's standard planner considers bushy plans; MySQL's optimizer is essentially left-deep.
Dynamic programming (Selinger et al., 1979): compute the best plan for every single relation, then every pair, then every triple, reusing the best sub-plans ("principle of optimality": the best plan for {A,B,C} contains the best plan for some subset). PostgreSQL also skips pairs with no join condition (avoiding Cartesian products unless forced) and remembers "interesting orders": a more expensive sub-plan is kept if its sorted output can save a sort later.
"""Selinger-style dynamic programming over join orders (System R idea, used by PostgreSQL's standard planner).
Cost model (deliberately simple): cost(join) = cost(left) + cost(right) + rows(left) + rows(right) + rows(out)
i.e. a hash join that reads both inputs and writes its output. Cardinalities/selectivities are example values.
"""
from itertools import combinations
from math import factorial
# regions has 10 rows, but WHERE r.name = 'EU' leaves 1, so its effective cardinality is 1
rows = {"orders": 1_000_000, "customers": 100_000, "regions": 1, "items": 5_000_000, "promos": 50}
# join predicates and their selectivities (missing pair = cross product, selectivity 1)
sel = {frozenset(p): s for p, s in {
("orders", "customers"): 1 / 100_000, ("customers", "regions"): 1 / 10,
("orders", "items"): 1 / 1_000_000, ("items", "promos"): 1 / 50 * 0.02, # only 2% of items are promoted
}.items()}
def card(rels):
"""Estimated output rows of joining a set of relations (independence assumption)."""
n = 1.0
for r in rels: n *= rows[r]
for a, b in combinations(rels, 2): n *= sel.get(frozenset((a, b)), 1.0)
return max(n, 1.0)
def connected(A, B):
return any(frozenset((a, b)) in sel for a in A for b in B)
def dp(relations, bushy):
best = {frozenset([r]): (0.0, r) for r in relations} # base case: a scan costs 0 here
considered = 0
for size in range(2, len(relations) + 1):
for S in map(frozenset, combinations(relations, size)):
for k in range(1, size):
for L in map(frozenset, combinations(S, k)):
R = S - L
if not bushy and len(R) != 1: continue # left-deep: right input is a base table
if L not in best or R not in best or not connected(L, R): continue
considered += 1
c = best[L][0] + best[R][0] + card(L) + card(R) + card(S)
if S not in best or c < best[S][0]:
best[S] = (c, f"({best[L][1]} ⋈ {best[R][1]})")
return best[frozenset(relations)], considered
rels = list(rows)
for bushy in (False, True):
(cost, tree), n = dp(rels, bushy)
print(f"{'bushy' if bushy else 'left-deep'} best: cost={cost:,.0f} plans considered={n}\n {tree}")
# What a naive "join in the order written" plan costs (FROM orders, items, customers, promos, regions)
def chain_cost(order):
done, c = frozenset([order[0]]), 0.0
for r in order[1:]:
nxt = done | {r}; c += card(done) + rows[r] + card(nxt); done = nxt
return c
print(f"written order cost={chain_cost(['orders','items','customers','promos','regions']):,.0f}")
# Why join order explodes: left-deep orders = n!, bushy trees = n! * Catalan(n-1)
catalan = lambda k: factorial(2 * k) // (factorial(k + 1) * factorial(k))
for n in (4, 8, 12, 16):
print(f"n={n:2d} tables: left-deep orders={factorial(n):,} bushy trees={factorial(n) * catalan(n - 1):,}")Output:
left-deep best: cost=6,710,051 plans considered=20
((((items ⋈ promos) ⋈ orders) ⋈ customers) ⋈ regions)
bushy best: cost=6,530,051 plans considered=40
((regions ⋈ customers) ⋈ (orders ⋈ (items ⋈ promos)))
written order cost=26,310,051
n= 4 tables: left-deep orders=24 bushy trees=120
n= 8 tables: left-deep orders=40,320 bushy trees=17,297,280
n=12 tables: left-deep orders=479,001,600 bushy trees=28,158,588,057,600
n=16 tables: left-deep orders=20,922,789,888,000 bushy trees=202,843,204,931,727,360,000The model shows all three ideas at once: the DP found plans roughly 4x cheaper than the written order, a bushy tree beat the best left-deep tree because regions ⋈ customers and promos ⋈ items could each shrink independently before meeting, and the raw count of possible trees explodes (12 tables: 479 million left-deep orders, 28 trillion bushy trees). Dynamic programming makes the work proportional to the number of connected subsets rather than the number of trees, which is manageable up to about a dozen relations and then explodes too.
The limits: join_collapse_limit, from_collapse_limit, GEQO
| Setting | Default | What it controls | Effect of raising | Effect of lowering |
|---|---|---|---|---|
from_collapse_limit | 8 | Max FROM items after pulling up subqueries into the parent | Better plans for big subquery-heavy queries, more planning time | Subqueries planned separately |
join_collapse_limit | 8 | Max items when flattening explicit JOIN syntax into one search | Explicit JOINs reordered more freely | Explicit JOIN order is respected (1 = exactly as written) |
geqo_threshold | 12 | FROM items at which the genetic optimizer replaces exhaustive search | Exhaustive search on bigger joins (planning time can reach seconds) | Faster planning, non-deterministic, possibly worse plans |
geqo | on | Enable genetic query optimization | n/a | Off: always exhaustive (risky for 20-way joins) |
Practical reading: a query with up to 8 joined tables gets a full DP search. Beyond that, PostgreSQL joins the first 8 (in written order of the explicit joins) as one search unit, and with 12 or more items in one unit GEQO kicks in with a randomized search. This is why ORM-generated 15-table queries sometimes get odd plans, why rewriting the query so the most selective tables appear first sometimes helps, and why join_collapse_limit = 1 is a legitimate way to pin a hand-optimized join order (the poor-man's hint).
Alternatives to cost-based optimization
| Approach | How it chooses | Strengths | Weaknesses | Examples |
|---|---|---|---|---|
| Rule-based (heuristic) | Fixed rules: "use an index if one exists", "join in FROM order" | Predictable, fast to plan | Blind to data size and skew | Early Oracle RBO, many simple embedded engines |
| Cost-based with DP (bottom-up) | Enumerate sub-plans by size, cost them, keep best | Near-optimal for moderate joins, well understood | Factorial blow-up, garbage-in-garbage-out on estimates | System R, PostgreSQL, DB2 |
| Cascades / Volcano optimizer (top-down, memoized rules) | Transformation rules over a memo of equivalent expressions, with pruning | Extensible, handles many operators, good pruning | Complex to build | SQL Server, Greenplum ORCA, CockroachDB, Apache Calcite |
| Randomized / genetic | Random or evolutionary search | Scales to huge joins | Non-deterministic, may miss the best | PostgreSQL GEQO |
| Adaptive / runtime re-optimization | Start executing, re-plan or switch when actuals diverge | Recovers from bad estimates | Complexity, mid-query state | Oracle adaptive plans, Spark AQE, SQL Server adaptive joins |
| Learned optimizers | ML models for cardinality or plan choice | Can learn correlations | Training data, explainability, robustness | Research systems (Neo, Bao), some cloud warehouses |
What happens if you choose otherwise. A rule-based optimizer will happily use an index on status for status = 'shipped' (90% of rows) and run 20x slower than a seq scan. Pure exhaustive search on a 20-way join can spend longer planning than executing. Hints or pinned plans (Oracle outlines, SQL Server Query Store forcing, pg_hint_plan) fix today's plan but freeze it against tomorrow's data. The cost-based approach wins on average precisely because it adapts to data, which is also why it needs good statistics.
Tuning the model to your hardware (and when not to)
- SSD/NVMe or mostly-cached data: lower
random_page_costto 1.1-2.0 so index scans are priced realistically. Leaving 4.0 on fast storage biases the planner toward seq scans and hash joins. - effective_cache_size: set it to what the OS plus shared_buffers can really cache; too low makes repeated index probes look expensive.
- Per-tablespace overrides:
ALTER TABLESPACE fast SET (random_page_cost = 1.1)if hot and cold storage differ. - Function costs:
CREATE FUNCTION ... COST 1000tells the planner an expensive function should be evaluated last in a WHERE clause. - Don't tune constants to fix one query. If a single query misplans, the cause is almost always a row estimate. Changing global constants to rescue one plan silently changes thousands of others.
Engine contrasts
- MySQL uses a cost model with configurable constants in
mysql.server_costandmysql.engine_costtables and a greedy/exhaustive join search controlled byoptimizer_search_depth(default 62, with heuristic pruning viaoptimizer_prune_level); hints likeJOIN_ORDER,JOIN_PREFIXandSTRAIGHT_JOINpin the order. - SQLite's NGQP finds join orders with an N-best path search (keeping a few best partial paths at each step) instead of full DP, which is fast and good enough for the embedded workloads it targets.
- DuckDB uses dynamic programming over the join graph (DPhyp-style) with a greedy fallback for very large join graphs, plus heavy use of statistics propagated through the plan.
- SQL Server, CockroachDB, Greenplum ORCA use Cascades-style top-down memo search with transformation rules.
Pitfalls
- Comparing costs across different queries or servers. Costs are only comparable for alternative plans of the same query under the same settings.
- Assuming explicit
JOINorder is ignored. It is, up tojoin_collapse_limit; beyond that, your written order is part of the plan. - Writing a 15-table view and joining it to 5 more tables. You exceed the collapse limits and land in GEQO territory; planning becomes non-deterministic.
- Lowering
random_page_costwithout checking cache hit ratio and storage. On network storage with high latency, random reads really are expensive. - Expecting the optimizer to consider every rewrite. It does not rewrite
ORintoUNION, deduplicate redundant joins in all cases, or decorrelate every subquery (see the rewrites page).
How the code was checked
- The crossover model ran under
tsc --strictand Node 22 and the join-order DP under Python 3.13. Their output blocks are the real captured output. - The SQL script ran through psql against a local PostgreSQL 17.11 sandbox; the Seq Scan cost of 10152 matches the pg_class arithmetic exactly. Only the setup DDL echoes were omitted.
- The TypeScript model simplifies PostgreSQL's page-fetch formula, and the DP model's cardinalities are example values.
Interview Q&A
How does a cost-based optimizer choose a plan?
Answer
It enumerates alternative physical plans (access paths, join orders, join algorithms, aggregation strategies), estimates each operator's cost from row estimates and cost constants, and keeps the cheapest total. Row estimates come from statistics (row counts, distinct values, most-common values, histograms).
Why is join ordering hard, and how do optimizers cope?
Answer
The number of orders is n! for left-deep trees and much more for bushy trees. Dynamic programming builds optimal plans for subsets bottom-up and reuses them, which is tractable up to roughly 10-12 tables. Beyond that, optimizers use heuristics, greedy search, randomized/genetic search (PostgreSQL's GEQO) or the written order.
Left-deep vs bushy trees?
Answer
Left-deep trees keep every right input a base table: smaller search space and good pipelining with nested loops. Bushy trees allow joining two intermediate results, which helps when two independent filtered branches each shrink a lot before meeting (star/snowflake queries). PostgreSQL considers bushy plans.
What does random_page_cost do and why would you change it?
Answer
It is the planner's price for a non-sequential page read relative to a sequential one (default 4). On SSDs or a mostly-cached database random reads are much cheaper, so lowering it to around 1.1 makes index scans realistically priced. Too high a value biases toward seq scans and hash joins.
What are join_collapse_limit and GEQO?
Answer
join_collapse_limit (default 8) caps how many items from explicit JOIN syntax are flattened into one join search; setting it to 1 forces the written order. GEQO is the genetic optimizer used when a search unit has geqo_threshold (default 12) or more items, replacing exhaustive DP with a randomized search.
What is an "interesting order"?
Answer
A sort order of an intermediate result that a later operator can use (a merge join, ORDER BY, GROUP BY). The optimizer keeps a slightly more expensive sub-plan that produces that order because it can save a sort later.
Why did random_page_cost = 1.1 pick an Index Scan in the demo?
Answer
At 4.0 the Index Scan on 3,842 scattered rows cost more than the 10,402 Seq Scan. At 1.1 the same scan cost 3,565 and won, with the same data, query and index.
What does the Cascades framework do differently from System R?
Answer
It searches top-down over a memo of equivalent expressions using transformation rules with pruning, which makes it extensible. SQL Server, CockroachDB, Greenplum ORCA and Calcite use it.
Check yourself
On a test database, run EXPLAIN on a selective index query with random_page_cost 4 and then 1.1 (session only). Note the cost of each plan and the selectivity at which the plan flips.
Elsewhere in the library
These pages stay as they are. This lesson only points at them: Selectivity, Cardinality & Statistics, B-Tree Internals — Pages, Splits & Buffer Pool, EXPLAIN & EXPLAIN ANALYZE, Indexes, Cardinality & EXPLAIN Plans.
Go Deeper
- Selinger et al.: Access Path Selection in a Relational Database Management System (System R, 1979)
- PostgreSQL docs: Planner Method and Cost Constants (runtime-config-query)
- PostgreSQL docs: Controlling the Planner with Explicit JOIN Clauses
- PostgreSQL docs: Genetic Query Optimizer
- PostgreSQL docs: Planner/Optimizer
- Leis et al.: How Good Are Query Optimizers, Really? (VLDB 2015)
- SQLite: The Next-Generation Query Planner
- CMU 15-445/645 schedule (Query Planning and Optimization lectures)
- CMU Database Group on YouTube