Planner

The planner — also called the optimizer — turns a Query into a PlannedStmt, a tree of executable Plan nodes. PostgreSQL uses a cost-based optimizer with a System R-style dynamic-programming join enumeration plus a genetic algorithm (GEQO) for very large joins. Source: src/backend/optimizer/.

Directory layout

src/backend/optimizer/
├── README           # extensive design notes (read this!)
├── geqo/            # genetic query optimizer (for large joins)
├── path/            # path generation: scans, joins, costs
│   ├── allpaths.c
│   ├── costsize.c
│   ├── indxpath.c
│   ├── joinpath.c
│   ├── pathkeys.c
│   ├── tidpath.c
│   └── ...
├── plan/            # turning paths into plans
│   ├── createplan.c
│   ├── initsplan.c
│   ├── planagg.c
│   ├── planmain.c
│   ├── planner.c
│   ├── setrefs.c
│   ├── subselect.c
│   └── ...
├── prep/            # query rewrites done by the planner
│   ├── prepjointree.c
│   ├── prepunion.c
│   ├── prepqual.c
│   └── ...
└── util/            # helpers
    ├── clauses.c
    ├── pathnode.c
    ├── plancat.c
    ├── relnode.c
    ├── ...

The README in src/backend/optimizer/ is one of the better treatments of the planner anywhere; it walks through the algorithm with examples.

Entry point

standard_planner (in src/backend/optimizer/plan/planner.c) is the entry point called from pg_plan_query. The planner runs in roughly five phases:

graph TD
    Query[Query tree] --> Prep["1. Preprocessing<br/>prep/*.c"]
    Prep --> Init["2. Build PlannerInfo<br/>(rels, eq classes, restrictinfo)"]
    Init --> Path["3. Generate Paths<br/>path/*.c"]
    Path --> CheapestPath
    CheapestPath --> CreatePlan["4. createplan.c<br/>Path → Plan"]
    CreatePlan --> SetRefs["5. setrefs.c<br/>resolve var refs to slots"]
    SetRefs --> PlannedStmt

1. Preprocessing

The query goes through several transformations:

• Sublink to subquery / semi-join. prepjointree.c pulls up trivial subqueries.
• UNION/INTERSECT/EXCEPT. prepunion.c flattens set-operation queries.
• Join tree manipulation. Outer joins reorderable to inner are converted; LATERAL references are tracked.
• Qual canonicalization. prepqual.c flattens AND/OR trees, distributes NOT, recognizes IS NULL.
• Constant folding. eval_const_expressions (in clauses.c) evaluates constant subexpressions at plan time.
• Inheritance and partition expansion. Each partitioned table or inheritance parent in the range table is expanded to its leaf relations, with appropriate qual translation.

2. PlannerInfo

A PlannerInfo (often root in the code) is the planner's working state. It carries:

• simple_rel_array — RelOptInfo per range-table entry, holding access paths, costs, and statistics.
• join_rel_list — RelOptInfos for join combinations, indexed by relid set.
• eq_classes — equivalence classes of expressions known to be equal (e.g., from t1.id = t2.id).
• canon_pathkeys — canonical pathkey lists for sort orders.
• parse — back-reference to the input Query.
• glob — PlannerGlobal, planner state shared across nested queries.

3. Path generation

A path (Path) is an annotated description of "one way to get the rows." Multiple paths per relation are kept as long as none dominates: a path with cheaper startup cost might still be useful even if total cost is higher, because LIMIT can cut it short.

For each base relation:

• Seq scan path — always available.
• Index scan paths — one per applicable index. indxpath.c matches the index's columns and operators against the WHERE clause.
• Bitmap scan paths — combines multiple indexes via bitmap AND/OR.
• TID scan paths — where ctid = '(...)'.
• Sample scan paths — for TABLESAMPLE.
• Foreign scan paths — provided by foreign-data-wrapper hooks.

For joins (joinpath.c):

• Nested loop — inner side scanned per outer row; cheap when inner side is tiny or cached.
• Hash join — build hash on inner, probe with outer; needs inner side to fit in memory (or to spill).
• Merge join — both sides sorted on the join key; combine by zipping.

Each combination is costed by costsize.c using statistics from pg_statistic.

Join enumeration: for ≤ geqo_threshold (12 by default) base relations, the planner uses dynamic programming (geqo_eval is not called; make_rel_from_joinlist calls standard_join_search which iterates over join sizes). For larger joins, GEQO (src/backend/optimizer/geqo/) runs a genetic algorithm.

4. Path → Plan

After the cheapest total-cost (and sometimes cheapest-startup-cost) path is chosen, createplan.c converts it into a Plan tree. Each path node has a _create_*_plan function. The plan tree is what the executor walks.

5. Reference resolution

setrefs.c does post-processing: turns column references into slot offsets, resolves subplan references, detects parameters, and assigns plan-node IDs. The output is a PlannedStmt ready for the executor.

Costing

costsize.c is the heart of decision making. The planner decides between paths based on a synthetic "cost" measured in arbitrary units anchored on seq_page_cost = 1.0. Other GUCs:

GUC	Default	Meaning
seq_page_cost	1.0	Cost per sequential page read.
random_page_cost	4.0	Cost per random page read. Lowered when storage is SSD.
cpu_tuple_cost	0.01	Cost per row processed.
cpu_index_tuple_cost	0.005	Cost per index entry.
cpu_operator_cost	0.0025	Cost per operator/function call.
effective_cache_size	4 GB	Hint for index cost model.
parallel_setup_cost	1000	Fixed cost of a parallel plan.
parallel_tuple_cost	0.1	Per-row inter-worker tuple transfer.

The cost functions consult pg_statistic (per-column statistics: ndistinct, MCVs, histogram bounds, correlation) and a few extension points (get_relation_stats_hook, get_index_stats_hook).

Selectivity estimation

For each WHERE predicate, clauselist_selectivity (in selfuncs.c, src/backend/utils/adt/) estimates the fraction of rows matching. It dispatches to per-operator estimator functions registered in pg_operator.oprrest (restriction selectivity) and oprjoin (join selectivity).

Built-in estimators handle equality, inequality, range, and pattern operators. pg_stat_statements is informational; the planner uses pg_statistic and pg_class.relpages / reltuples.

Multi-column extended statistics (pg_statistic_ext) provide ndistinct, dependencies, and MCV lists across multiple columns, improving estimates for correlated predicates. Source: src/backend/statistics/.

Pathkeys and sort orders

A pathkey describes a sort order ("relation R is ordered by R.x ascending, then R.y descending"). The planner tracks pathkeys to avoid unnecessary sorts: an index scan returns rows in index order, and the optimizer recognizes when that order is useful for ORDER BY, merge join, or grouping. Source: pathkeys.c.

Equivalence classes

Members of an equivalence class are expressions known to be equal. From WHERE a.x = b.y AND b.y = c.z, the planner deduces {a.x, b.y, c.z} are all equal; this enables join reordering, redundant-clause elimination, and pushdown of equivalence-implied constraints. Source: equivclass.c.

Subquery handling

Three kinds of subqueries:

• Sublink — a query expression in WHERE/SELECT (e.g., IN (SELECT ...)). The planner tries to convert into a semi-join, anti-join, or EXISTS test. If it can't, it leaves the sublink as a SubPlan to be executed at runtime.
• Subquery RTE — a derived table in FROM. The optimizer can pull it up if the parent and child are simple enough; otherwise it plans the subquery separately and stitches it as a SubqueryScan.
• CTE / WITH. Pre-13: always materialized. 13+: optimizer chooses to inline (default for non-recursive single-use CTEs) or materialize.

Source: subselect.c, prepjointree.c.

Parallel query

The planner can mark a plan as parallel-safe and emit a Gather node at the top, with workers running the subtree in parallel. Decisions are made by add_partial_path and consider_parallel. Functions are tagged PARALLEL SAFE/PARALLEL RESTRICTED/PARALLEL UNSAFE in pg_proc; the planner refuses to push unsafe pieces into a worker.

Partition pruning

For partitioned tables, the planner can prove at plan time that some partitions cannot match the query — pruning them out before the executor runs. Source: src/backend/partitioning/partprune.c. The executor also performs runtime pruning when the partition key is bound only at execution time.

GEQO

Genetic-algorithm join planning kicks in for queries with > geqo_threshold (default 12) base relations. Source: src/backend/optimizer/geqo/. It encodes join orders as gene strings, evolves a population, and returns the best solution found. Always slower-but-better than nothing for huge joins; not deterministic unless geqo_seed is fixed.

Hooks

Extensions can intercept the planner via:

• planner_hook — replace standard_planner.
• set_rel_pathlist_hook — modify the path list of a base relation (used by pg_hint_plan and similar).
• join_search_hook — replace the join enumeration.
• Custom scan API: extensions can register CustomScan nodes the planner will consider.

These are the substrate of pluggable plan controls and most third-party optimizer extensions.

Entry points for modification

• New plan node: declare in nodes/plannodes.h, generate path in pathnode.c, plan in createplan.c, executor support in nodeXxx.c.
• New cost variable: add to costsize.c (and a GUC if user-tunable).
• New selectivity estimator: implement and register in pg_proc + the relevant operator's oprrest.

For what runs the resulting plan, see Executor.