Course contents
On this page
Logical optimization — extended reference
Original detailed coverage and citations accompanying the focused logical optimization lesson.
This reference preserves the earlier detailed chapter and its citations. Start with the guided explanation, then use these sections for additional mechanisms and qualifications. References to the original lesson sequence are historical.
Part 3: Turning requests into execution
Prerequisites: Lesson 13 and the preceding foundations.
Learning outcomes
- Apply predicate pushdown, projection pruning, and join transformation only when semantics allow.
- Explain why outer joins, duplicates, NULLs, volatile expressions, and correlated queries restrict rewrites.
- Follow a concrete equivalence proof or counterexample instead of assuming fewer operators always means correctness.
A faster rewrite can change the answer
A report lists every customer and any recent orders. An engineer moves an order-date filter from a join condition into a WHERE clause to simplify the query. Customers without recent orders disappear. The new query may execute faster because it returns fewer rows, but it no longer implements the report.
Logical optimization searches for equivalent expressions that expose cheaper execution. Equivalence must respect SQL’s null behavior, duplicates, outer joins, limits, and function semantics. The optimizer’s central obligation is to reduce work while preserving the requested result.
Predicate pushdown
A filter applied before a join can reduce the number of rows entering the join. For an inner join, a predicate referring only to one input can often be applied to that input first, subject to expression semantics.
SELECT p.player_id, i.item_id
FROM player AS p
JOIN item AS i ON i.owner_id = p.player_id
WHERE p.player_id = 17;Restricting the player input to identifier 17 is a natural transformation. If the player relation has one million rows and the predicate selects 1%, an illustrative filter leaves 10,000 rows. An actual identifier equality might select one row under a unique constraint; statistics and constraints refine the estimate.
Pushing a predicate does not guarantee less total cost. An expensive expression evaluated on many rows before another selective filter can add work. An index may make one predicate cheap only in a particular form. The optimizer needs both semantic permission and a cost reason to choose a rewrite.
Outer joins require careful reasoning
A left outer join preserves unmatched left rows by filling right-side attributes with nulls. A filter in WHERE applies after that preservation. A condition in ON determines matching before unmatched left rows are generated.
-- Preserve customers even when there is no qualifying order.
SELECT c.customer_id, o.order_id
FROM customer AS c
LEFT JOIN orders AS o
ON o.customer_id = c.customer_id
AND o.created_at >= TIMESTAMP '2026-10-01 00:00:00';Moving the date predicate into WHERE rejects the null-extended rows because the comparison is unknown. A customer with no qualifying order then disappears. This is a concrete counterexample to a naive pushdown or pull-up rule.
An optimizer may legitimately convert some outer joins into inner joins when later predicates reject all null-extended rows. That transformation follows from the full query’s semantics, not a general rule that outer and inner joins are interchangeable. Constraints can create additional opportunities, but they must be valid and trusted.
Projection pushdown
Projection removes attributes not needed by later operators. Narrower tuples consume less memory and bandwidth during joins, sorts, and network transfer. A columnar source may avoid reading unused columns entirely. A row-oriented source may still read the containing page but save copying and intermediate-state cost.
The projected set must include attributes required by predicates, joins, ordering, grouping, and visibility checks, not only final output fields. Removing a key needed to preserve multiplicity or correlate a later operation can change the result. Physical properties such as order may also depend on attributes not returned to the user.
Suppose an intermediate result has one million rows and a 200-byte width. Its raw payload is 200 MB using decimal units. Removing unneeded fields to reach 40 bytes reduces it to 40 MB. The illustrative reduction can affect whether a hash table fits in memory and whether a distributed shuffle spills, even though the final output is unchanged.
Join reordering and multiplicity
Inner joins are often associative and commutative under the relevant relational conditions. The engine can choose an order that reduces intermediate results. SQL bag semantics mean duplicate counts must be preserved. Replacing a join with a set membership test is not automatically equivalent when multiple matching rows contribute duplicates.
A customer with three orders and each order with four lines produces twelve joined rows. If a rewrite aggregates orders before joining lines without preserving the intended weights, it can overcount or undercount. The semantic proof should state which rows are distinct, which keys are unique, and which aggregate is being computed.
Foreign keys and unique constraints can support join elimination or cardinality bounds. If the optimizer assumes a constraint that is not enforced or not valid for the snapshot, the rewrite can become unsound. Metadata quality therefore affects correctness as well as estimated cost.
Subqueries and decorrelation
A correlated subquery refers to values from an outer row. A literal execution strategy might run it for every outer row. Decorrelation rewrites the relationship into a join, semijoin, aggregation, or another shared operation where semantics permit.
SELECT p.player_id
FROM player AS p
WHERE EXISTS (
SELECT 1 FROM item AS i
WHERE i.owner_id = p.player_id AND i.kind = 'sword'
);EXISTS asks whether at least one match exists. A semijoin can preserve one output occurrence per qualifying outer row without multiplying it by the number of swords. An ordinary join followed by an inappropriate projection may produce duplicates. The correct physical strategy must preserve the existential meaning.
Null-sensitive forms such as NOT IN require additional care. A subquery containing null can affect the predicate differently from a simple anti-join that checks only equality matches. A robust optimizer’s rewrite rules explicitly account for these cases rather than relying on examples without missing values.
Aggregation, limits, and order
Partial aggregation can reduce intermediate data when the aggregate is decomposable. A sum can be combined from partial sums. An average requires at least sum and count, not an unweighted average of partial averages. Distinct counts and order-sensitive aggregates need different state and combination rules.
A limit cannot generally move below an arbitrary filter or join. Taking ten rows before filtering can return fewer or different qualifying rows than filtering first and taking ten. With ordering, the engine must preserve the exact top-k semantics, including ties according to the query’s specified order. An unspecified tie order should not be mistaken for a guaranteed stable result.
Sorting can sometimes be avoided when an access path already provides the required order. A rewrite that changes partitioning or join strategy may lose that order. Logical equivalence of row contents and physical satisfaction of ordering are separate properties that the optimizer tracks.
Expression semantics constrain movement
Volatile functions, exceptions, and side effects can make apparently simple rewrites observable. A random function evaluated once is not equivalent to evaluating it independently for every row. Moving an expression can change how often it is invoked. Arithmetic overflow or division by zero can also complicate assumptions about evaluation.
Database languages often restrict or classify functions to make optimization possible. A user-defined function’s declaration must match its actual behavior. Mislabeling a function as immutable can cause cached or moved results that the application did not intend. The optimizer is entitled to rely on its contract; the contract must be truthful.
Prove an inner-join pushdown with row multiplicity
Let relation R contain player rows and S contain item rows. The join matches R.player_id = S.owner_id, and predicate p refers only to R’s region. Applying p after the inner join retains exactly the pairs whose R component satisfies p. Filtering R first removes exactly those R rows whose pairs would later be rejected. For every retained pair, multiplicity is unchanged because neither version adds a duplicate-elimination step.
This proof relies on p having the relevant stable semantics. If evaluating p produces different values on successive calls or has observable side effects, changing the number or location of evaluations can matter. SQL function classifications tell the optimizer which transformations are permitted. The proof also concerns an inner join; a preserved side of an outer join requires a separate argument.
The cost implication is distinct from the proof. Suppose R has one million rows and the region filter retains 10,000, while each player matches forty items. Joining first can produce forty million pairs before rejecting most. Filtering first can reduce candidate output toward 400,000 pairs. The figures assume uniform item counts and no other restrictions. The rewrite is correct independently of those estimates; the estimates explain why it is attractive.
An index may let the filtered R input avoid reading most pages. Without one, the engine still scans R but reduces downstream join work. Logical pushdown and physical access-path selection are complementary optimizations rather than the same operation.
An outer-join counterexample in full
Construct three customers: Ada has a September order, Ben has an October order, and Chen has no order. The intended report preserves every customer and shows only orders on or after October 1. Placing the date restriction in the ON clause yields Ada with null order columns, Ben with his October order, and Chen with null order columns. Ada’s September order fails to match, but her preserved customer row remains.
Now move the restriction to WHERE after joining all orders. Ada joins to her September order, whose date fails the filter. Ben remains. Chen’s null-extended date makes the comparison unknown, which also fails the filter. Only Ben survives. Adding OR o.order_id IS NULL does not generally restore the original result: Ada had a matching September order in the unrestricted join, so no null-extended row was generated for her.
This last point is a common trap. A local-looking null check cannot repair the fact that matching happened under a different predicate. The correct rewrite can filter the right input before the left join, or retain the date condition in ON. Those forms preserve the same eligible-match relation and then preserve unmatched left rows.
A later WHERE o.order_id IS NOT NULL can deliberately reject all null-extended rows, allowing an outer-to-inner conversion under suitable assumptions. The difference is that the full query now requests only matched customers. Transformation rules must inspect the whole context, rather than classify a join once and ignore predicates above it.
Projection can remove bytes but not required meaning
Suppose a query outputs player name and total spending. Before aggregation, the plan still needs player identity to group correctly; two players can share a name. Projecting away identity and grouping only by name can merge their spending. The final output columns do not uniquely determine every attribute needed during execution.
Similarly, a join predicate requires its key even if the key is not returned. A sort may need an expression absent from the display. A visibility check may need transaction metadata. A projection rule computes required attributes from every parent dependency and any operator-local semantic obligations. Only then can it shrink row width.
If one million intermediate rows shrink from 200 to 40 bytes, raw materialized payload falls from 200 MB to 40 MB in decimal units. A hash structure with overhead adds more bytes, but the width reduction can still move it below a memory threshold. The resulting benefit may include avoiding a spill, so it can be larger than a simple copying reduction.
Projection interacts with duplicate semantics. Ordinary SQL projection retains duplicate rows unless DISTINCT is requested. A logical relational-algebra notation using sets must therefore be adapted carefully for SQL bags. Removing a column can make two rows equal in appearance without authorizing the optimizer to collapse them into one.
Decorrelation must preserve scalar and existential semantics
A correlated scalar subquery has different obligations from EXISTS. Consider a scalar subquery retrieving a player’s single premium status. If the subquery returns more than one row, the language may require an error. Rewriting it into an ordinary join that emits several rows changes the contract by replacing the error with duplicate results. A valid transformation needs a uniqueness proof or an operator retaining the scalar-cardinality check.
For EXISTS, multiplicity inside the subquery does not change truth after the first qualifying row. A semijoin can return each qualifying outer occurrence once. If the outer input already contains duplicate occurrences, those duplicates remain; the semijoin does not automatically become DISTINCT. An anti-semijoin handles absence under its specific null semantics.
NOT IN requires null-aware treatment. With outer value 5 and inner values 1 and null, no equal match exists, yet SQL’s result is unknown rather than true. If trusted constraints prove both relevant sides nonnull, an ordinary equality anti-join can become valid. Without that proof, the physical or logical transformation must retain the null-sensitive behavior.
Decorrelation can reduce repeated work dramatically, but sometimes the indexed correlated plan is already efficient for a tiny outer input. Legal equivalence creates options; cost estimation chooses among them. A rewrite that materializes a huge global aggregate to answer one player’s query can be slower than a few selective lookups despite looking more relational.
Partial aggregation needs a valid combine state
SUM can combine partial sums, subject to numeric overflow and type semantics. COUNT can combine counts. AVG needs both sum and count. A variance aggregate needs more careful merge state than a scalar variance value. An exact distinct count cannot generally combine counts from overlapping partitions because the same value can appear in several. The optimizer needs a declared combine operation that preserves the requested result.
Consider workers processing two groups: one sees values 10 and 20; another sees 100. Their averages are 15 and 100. Averaging those gives 57.5, while the correct mean is (10 + 20 + 100) / 3, approximately 43.33. Combining sum 30/count 2 with sum 100/count 1 produces the correct result. Null treatment and empty partitions must also agree.
Pushing aggregation below a join needs multiplicity analysis. If each payment joins exactly one customer, summing payment by customer before joining customer attributes can be safe for selected reports. If the later join duplicates each customer across several labels, summing after that join has different semantics. The optimizer cannot simply assume the earlier aggregation is equivalent because it makes the intermediate result smaller.
Floating-point arithmetic adds another subtlety. Different reduction orders can change rounding. An engine’s semantics determine whether such reassociation is allowed and what reproducibility is promised. Exact decimal and integer aggregates have their own overflow rules. A cost-saving combine step must remain within those arithmetic contracts.
Limits and top-k require an ordering proof
Suppose input values are [100, 90, 80, 1, 2], and the query filters values below 50 before taking two. Filtering then limiting can return 1 and 2. Limiting the original input to its first two values and then filtering returns no rows. A limit cannot generally move below a filter.
With ORDER BY score DESC LIMIT 10, the engine can maintain a bounded heap of the best ten seen values, but still must inspect all qualifying unsorted input to prove the final top ten. If an index already provides the required order and residual predicates are evaluated as rows arrive, execution can stop after ten qualifying rows. The number examined can exceed ten when many candidates fail residual checks.
A distributed local top-k can sometimes bound candidates sent to a final merge, provided every partition uses the same complete ordering and tie rules. Adding an unrelated join after the local limit can invalidate the argument if that join filters or multiplies candidates. The transformation’s correctness depends on operator placement, not just the presence of a limit somewhere above.
An order without a unique tie-breaker permits multiple valid orders among equal keys. A client requiring stable pagination should specify one. The optimizer should preserve requested order, while the application should not infer guarantees from an accidental index traversal order when no ORDER BY exists.
Constraints can eliminate work only when their scope applies
A join from a child row to a parent can be redundant when the query uses no parent attributes, every child has exactly one required parent, and the join cannot filter or duplicate rows. A valid nonnull foreign key to a unique parent key can support such reasoning. If the child key is nullable, an inner join can remove null-key rows. If the parent side is not unique, the join can multiply them.
Deferred constraints complicate timing. A transaction may temporarily hold a state that is permitted before final validation but does not satisfy a globally assumed relationship at every statement boundary. The engine must use constraints according to its actual semantic guarantees. Similarly, a constraint marked unvalidated or not enforced cannot automatically justify eliminating a correctness-relevant filter.
Partition constraints can prune data ranges. A predicate restricted to October need not scan a partition proven to contain only September rows. But timezone interpretation, boundary inclusivity, and expression conversions must align. A mistaken partition-bound interpretation can omit valid data rather than merely make a query slower.
These examples show why optimizer metadata is part of the trusted computing base. Statistics can be approximate because they influence cost; constraints used for equivalence must be valid because they influence the answer. Confusing those two kinds of metadata is a serious design error.
A rule engine needs termination and provenance
Rewrite systems often apply local rules repeatedly. A rule that pushes a filter down and another that pulls it up can cycle unless the optimizer tracks explored expressions or enforces a direction. Representing equivalent alternatives in a memo structure avoids treating every textual variant as new work, but requires canonical identity and careful property tracking.
Each rule should record its semantic preconditions: join kind, referenced attributes, nullability, uniqueness, function properties, and required order. Testing only common nonnull unique rows leaves the most dangerous cases unexamined. A technical review should include counterexamples with duplicates, nulls, empty inputs, and unmatched outer rows because those reveal where informal relational intuition diverges from SQL.
The lesson’s constructed traces do not prescribe one optimizer framework. They establish the proof discipline any framework needs. Faster execution is meaningful only after equivalence is established; a cost model cannot repair an illegal transformation.
Compare the legal plans side by side
before: after:
Project requested fields Project requested fields
Filter player.region = 7 InnerJoin player.id = item.owner
InnerJoin id = owner Filter player.region = 7
Player Player
Item ItemThe plans preserve every matching player/item pair and its multiplicity under the stable input-local predicate. The second form exposes a smaller player input to the join. Whether that becomes an index scan or a filtered table scan is a later physical decision.
unsafe outer-join change:
LeftJoin(eligible orders) Filter eligible order date
Customer LeftJoin(all orders)
Orders Customer
OrdersThe first form preserves customers lacking eligible orders. The second filters after matching and null extension. Ada’s old order and Chen’s absent order therefore produce the earlier counterexample: their rows disappear. A visual resemblance between plan fragments does not establish equivalence; the preserved-row rule and null behavior determine the answer.
These trees also show why a transformation should carry its preconditions. “Move Filter below Join” is incomplete. “Move a stable, input-local filter below this inner join while preserving bag multiplicity” is a meaningful rule. A separate proof is needed when join kind, expression behavior, or required ordering changes.
Case connection and design conclusion
PostgreSQL’s planner description and database-system teaching materials provide references for transformations and plan construction. The worked outer-join and aggregation scenarios here are constructed to show the proof obligation. A query that runs faster because it silently drops required rows is not an optimization of the original workload.
For each rewrite, identify the semantic assumptions, prove that multiplicity and null behavior remain valid, and only then compare execution cost. Lesson 15 introduces the physical algorithms among which an optimizer chooses once the legal alternatives are established.