Logical Plans and Rewrite Rules That Preserve Results

A bound query is a tree of syntactic constructs: nested selects, subqueries, EXISTS, IN, common table expressions, views already inlined. The planner cannot choose algorithms over that shape, because the shape carries decisions the user made for readability rather than for execution. The input comes from binding, which has already replaced every name with a catalog reference and every operator with a specific function. The first planning stage converts it into a relational algebra expression and then applies equivalences that change the shape without changing the result.

The set of transformations is small and old. Push selections down, push projections down, merge or eliminate joins, fold constants, decorrelate subqueries. Each one is justified by an algebraic identity, and each one has preconditions that are easy to state and easy to violate. Most planner bugs of this class come from a rewrite applied one node too far, into a region where the identity does not hold.

Selection pushdown and the NULL obstacle

The basic identity is that a filter commutes with everything that does not change which rows exist. σ_p(R ⋈ S) = σ_p(R) ⋈ S when p references only columns of R, because filtering before or after the join gives the same surviving rows. Moving the filter down is strictly better: the join then processes fewer rows, and if R has an index on the filtered columns the filter may become an index range scan.

The identity fails at outer joins. For a left outer join, σ_p(R ⟕ S) where p references S cannot be pushed into S, because rows of R with no match must survive with NULLs, and filtering S first would change which rows count as unmatched. Pushing p into R is also unsafe in general, because a predicate on the preserved side can eliminate rows before the join and thus remove matches that the outer join would have produced for the other side. The safe rule is: predicates on the null-supplying side of an outer join cannot be pushed below it at all, and predicates on the preserved side can be pushed only when they are null-rejecting on that side in a way that preserves the join’s semantics.

The optimizer gets around the second restriction by converting the outer join to an inner join when a null-rejecting predicate on the null-supplying side makes the outer behaviour unobservable. If σ_{S.x > 5} follows a left outer join, any row with no match has S.x NULL and fails the predicate, so the result equals that of an inner join. This is why a query written with LEFT JOIN and a WHERE condition on the right table often plans as an inner join; the conversion is sound and produces a much larger space of join orders.

NULL also breaks a simpler rewrite. NOT (a = b) is not a <> b when either side can be NULL: both are UNKNOWN in that case, so the two agree on filtering, but they differ under a further negation, and they differ from a predicate written as a = b OR a <> b, which is UNKNOWN rather than TRUE for a NULL operand. A rewrite engine that treats NOT as a boolean negation over two-valued logic will produce wrong answers on nullable columns. The usual implementation represents three-valued logic explicitly and only applies De Morgan-style transformations where a null-rejection proof exists.

Projection pruning and the cost of SELECT *

Column pruning removes from each operator’s output the columns no ancestor references. Its benefit is direct: fewer columns per tuple means narrower rows, which means more tuples per page read and fewer bytes moved between operators. On a wide table with a hundred columns, a query that needs three of them reads roughly three percent of the row bytes if the storage layer supports projection, and saves the rest of the copy cost even when it does not.

The rewrite is not always free. Pruning a column that a later stage needs forces the planner to re-derive it, and re-deriving means re-joining or re-scanning. A projection pushed below a join must keep the join keys, so a naive prune that keeps only the final select list breaks the join. Implementations compute the set of required columns top-down and then insert projections bottom-up, which is the standard two-pass formulation.

There is also an interaction with expression evaluation. A computed column used twice should be evaluated once; a projection that is pruned and re-added can duplicate work. Some planners deduplicate identical subexpressions as part of this pass, which is safe only for deterministic expressions.

Join elimination and the meaning of a key

Two joins can be removed outright when a foreign key guarantees the join neither duplicates nor filters. If orders.customer_id is a non-null foreign key to customers.id, then orders ⋈ customers on that pair has exactly one output row per order and no NULL extension, so the join can be dropped when no column of customers is referenced. The rewrite requires that the referenced column is a primary key or unique constraint, that the referencing column is declared not null (or that the join is an inner join and the predicate is null-rejecting), and that the join is not an outer join whose null-supplying side is the eliminated one.

This is one of the few rewrites that depends on declared constraints rather than on query structure, and it is why constraint declarations have a performance effect beyond integrity checking. A foreign key that exists in the data but is not declared cannot justify the elimination.

A related elimination applies to a self-join on a unique key with an equality predicate, and to a join to a table whose every referenced column is functionally determined by a column already present. Both are special cases of the same argument: if the join cannot change the row count and cannot add information that is used, it is redundant.

Subquery decorrelation

A correlated subquery is evaluated conceptually once per outer row, which is quadratic. The rewrite turns it into a join or an aggregate. SELECT * FROM a WHERE EXISTS (SELECT 1 FROM b WHERE b.x = a.x) becomes a semi-join of a and b on x, which the executor can implement as a hash semi-join in one pass over each input.

IN with a subquery is the same shape with a twist: a.y IN (SELECT b.y FROM b) is a semi-join, but NULLs change the answer. If the subquery produces a NULL and no match is found, the predicate evaluates to UNKNOWN rather than FALSE, so the row is filtered out either way in a WHERE clause but not in a NOT IN. NOT IN over a nullable column is the classic trap: if the subquery returns any NULL, the whole predicate is UNKNOWN for every non-matching row and the query returns nothing. Planners must either keep the anti-join with explicit null handling or refuse the rewrite.

Scalar subqueries in the select list decorrelate into a left outer join with a group-by, with the aggregate’s NULL for no-match rows matching the scalar subquery’s NULL. Aggregates that must return a value for an empty input, such as count(*) returning zero, need a coalesce on top of the outer join, because the left outer join produces NULL where the subquery would have produced zero.

The standard implementation collects correlated references, builds an equivalence class between outer and inner columns, and then chooses among semi-join, anti-join, and grouped outer join. Each has a distinct NULL policy and a distinct set of valid join orders, which is why decorrelation is usually the largest single rewrite pass in a planner.

Constant folding and the volatility boundary

Expressions with no column references can be evaluated at planning time. WHERE x > 2 + 3 becomes WHERE x > 5, which matters because a constant comparison is indexable and an expression on the constant side is not. The pass also simplifies tautologies and contradictions, and a contradiction can collapse an entire subtree to an empty relation.

The boundary is function volatility. A function marked volatile may return a different value on each call, so folding it at plan time changes behaviour: WHERE created_at > now() must be evaluated once per query, not once per plan, because a prepared statement may be executed hours after it was planned. Implementations classify functions as immutable, stable, or volatile, and only immutable ones can be folded. Stable functions depending on session state, such as current_date, may be folded per execution but not per plan.

The same classification governs whether an expression can be pushed below a filter, used in an index condition, or hoisted out of a loop. A volatile function in a predicate blocks pushdown, because moving it changes how many times it is called and therefore changes results for a function with side effects. This is a case where the rewrite is unsound for reasons that have nothing to do with relational algebra.

The output of these passes is still a logical plan: operators are scan, filter, join, aggregate, sort, limit, with no algorithms attached. Turning it into executable operators requires deciding which algorithm implements each, and that decision is where the physical plan begins, as covered in choosing physical operators from the logical plan.