July 08, 2025
Query planning in Postgres is often described as finding the cheapest execution path, and that is true at a high level, but the planner also has to guarantee correctness along the way – deciding when it is safe to move a filter, which expressions are known to produce equal values at runtime, what sort orders are available, and how to avoid breaking outer join or null semantics. These concerns require a richer representation than just cost numbers, and most of that richness lives in a handful of interconnected structs that are worth understanding if you want to make sense of the planner code.
The planner does not work with raw expression trees for WHERE and JOIN clauses. Instead, each clause gets wrapped in a RestrictInfo struct early on, and the planner then passes these wrappers around rather than the underlying expressions. The wrapper carries things like: whether the clause can be pushed below a join, whether evaluation needs to be delayed because of an outer join, which relations the clause references (stored as a bitset of relids), whether it is a join clause (referencing multiple relations) or a restriction clause (referencing just one), and whether it is a pseudoconstant that does not depend on any table at all.
This design makes clause movement explicit and safe. Rather than poking at expressions to figure out where they can go, the planner consults the metadata already computed in the RestrictInfo. The code for building these wrappers is mostly in src/backend/optimizer/util/restrictinfo.c, and the struct definition is in src/include/nodes/pathnodes.h.
A lot of planner optimizations depend on knowing that two expressions will produce identical values at runtime. Postgres tracks this with EquivalenceClass structs, each representing a set of expressions that are all equal to each other. These are built from mergejoinable equality clauses – a clause like t1.a = t2.a tells the planner that t1.a and t2.a belong to the same equivalence class.
Once the planner has built these classes, it can do useful things. If it knows t1.a = t2.a and separately that t2.a = 5, it can infer t1.a = 5 and use that to drive an index scan on t1 even though no explicit t1.a = 5 clause appeared in the query. Equivalence classes also underpin sort order reasoning: if the output of one relation is sorted on a member of an equivalence class, the planner knows the sort order carries over to other members of the same class, which matters for merge joins and for satisfying ORDER BY without an explicit sort. The relevant code lives in src/backend/optimizer/path/equivclass.c.
For each table (and later, each join of tables) that the planner works with, it builds a RelOptInfo struct. This is distinct from the parser-level RangeTblEntry – the RangeTblEntry describes what the relation is, while the RelOptInfo is the planner’s working state for it. It holds the set of relids covered by this relation, the estimated row count and average row width, the list of applicable RestrictInfos, a list of candidate Paths, and join-related clause lists.
As planning proceeds, the RelOptInfo for a base relation gets populated with scan paths, and RelOptInfos for joins are built by combining base relation infos. The planner’s job is essentially to work through these structs bottom-up until it has a complete plan for the whole query.
Each possible way to execute a scan or join is represented by a Path node. A RelOptInfo for a base table might accumulate a sequential scan path, one or more index scan paths, a bitmap scan path, and possibly parallel variants of some of these. Each Path carries cost estimates (startup and total), the set of relids it covers, sort order information (PathKeys, discussed below), and flags for physical properties like parallel safety.
The planner adds paths to a relation’s path list via add_path() (in src/backend/optimizer/util/pathnode.c), which enforces a dominance check: if a new path is both more expensive and provides no physical property that existing paths lack, it is discarded. This aggressive pruning is what keeps planning tractable – without it, the combinatorial explosion of join orderings and scan variants would quickly become unmanageable.
PathKeys represent the sort order that a given Path produces. Rather than storing a concrete comparison function or sort key value, PathKeys are built from EquivalenceClass members and sort operators, which makes them symbolic. Two paths that produce output sorted on different expressions that are known to be equal (via an EquivalenceClass) can be recognized as having compatible sort orders.
This matters in several places. When the planner is building a merge join, it needs to know whether the input paths are already sorted on the join key, or whether an explicit sort step would need to be added. When satisfying an ORDER BY, it can check if an available path already has the right PathKeys and avoid sorting at all. The PathKey infrastructure is in src/backend/optimizer/path/pathkeys.c.
ParamPathInfo represents a scan path that is parameterized by values from an outer relation – the canonical example being an index scan that looks up a value produced by an outer loop of a nested loop join. The ParamPathInfo records the estimated row count and selectivity assuming those outer parameters are supplied, which affects both cost estimation and path comparison.
PlaceHolderVar handles expressions that must be evaluated at a specific point in the join tree, even if they are referenced earlier or later. A lateral reference or an expression that depends on an outer join being completed falls into this category. The planner uses PlaceHolderVars to enforce that the evaluation happens at the right join level.
The planner works bottom-up. It starts by generating scan paths for each base relation, then builds join paths by combining pairs of relations, iterating outward until it has paths for the full join tree. At each stage it propagates clause metadata (who can be evaluated where, what equivalences are known), considers parameterized paths for nested loop joins, and prunes the path lists aggressively.
One thing worth noting is how this differs from Cascades-style optimizers, which represent the logical query as a normalized expression tree and apply transformation rules to generate equivalent logical forms – commutativity, filter pushdown, and so on – before choosing physical implementations. Postgres keeps the logical query structure mostly fixed and explores only physical alternatives for each part of the plan. It does memoize the cheapest paths per relation or join combination, but there is no separate pass of logical rewrites. The approach is more greedy and less exhaustive, which makes it faster for typical queries at the cost of potentially missing some plans that a Cascades optimizer would find.
The relevant top-level planning code starts in src/backend/optimizer/plan/planner.c, with the path generation spread across src/backend/optimizer/path/.
These data structures – RestrictInfo, EquivalenceClass, RelOptInfo, Path, PathKeys – evolved together to support a wide range of query patterns while keeping planning tractable. They are not perfect: there are well-known cases where Postgres misestimates cardinality or fails to find an optimal join order, and improving those is ongoing work. But the overall architecture, with its explicit clause metadata, symbolic equality tracking, and staged path generation, has held up well and continues to be extended with each release.