An engine wants to apply a relational-algebra projection before a selection instead of after it. Under what condition is that rewrite safe, and what does it buy?

## The identity and its side condition The algebraic rule is: `π_X(σ_p(R)) = σ_p(π_X(R))` **provided** every attribute referenced by predicate `p` is in `X`. The side condition is not a technicality — it is a well-formedness requirement. `σ_p` can only be applied to a relation whose heading contains the attributes p mentions. If `X = {order_id, total}` and `p` is `status = 'SHIPPED'`, then `π_X(R)` has no `status` attribute and `σ_p(π_X(R))` is not even a legal expression. Compare with the unconditional laws for selection alone (cascade, commutativity): those hold with no side condition because selection never changes a heading. Projection *does* change the heading, which is exactly why reordering around it needs a check. ## The split-projection workaround When `attributes(p) ⊄ X`, you do not have to give up on early narrowing. Rewrite as: `π_X(σ_p(R)) = π_X(σ_p(π_{X ∪ attributes(p)}(R)))` Read it inside out: first drop every attribute that neither the final answer nor the predicate needs; then filter; then drop the predicate-only attributes. Real optimizers do exactly this, and it is why a plan can show a narrow scan output even when the filter uses a column that never appears in the query's result. ## What early projection actually buys - **Narrower tuples in memory-bound operators.** Sorts, hash tables, and materialised intermediates size on tuple width times row count. Dropping wide columns (long text, blobs) before a sort can be the difference between an in-memory sort and one that spills to temporary storage. - **Better packing.** Narrow tuples mean more rows per buffer page, fewer pages moved between operators. - **Index-only access.** If the surviving attribute set is entirely contained in a secondary index, the engine can answer from the index and skip fetching the base rows. This is a projection-driven optimization: whether the plan qualifies depends purely on how narrow the projection is. - **Less data crossing a boundary** — over a network in a distributed engine, or between a storage layer and an execution layer. ## The counter-pressure: duplicate elimination Under strict set semantics, projection implies duplicate elimination, and duplicate elimination is expensive and *blocking* (a hash build or a sort). Doing it early, before a selective filter has cut the row count, can be much worse than doing it late over few rows. So: - Early projection over a set of attributes that still contains a key: free, because no duplicates can arise — always push it. - Early projection that would collapse many rows: the dedup cost is incurred on the pre-filter cardinality. Usually push the *column trimming* but defer the *distinctness enforcement*. This is why real engines separate the two ideas internally: a plan-level column-pruning pass that trims unused attributes everywhere (semantically neutral in bag semantics, and always beneficial), plus a separate, cost-based decision about where to place any required distinct operator. ## Ordering relative to selection: which goes first in the classic heuristic The textbook heuristic order for rewriting a query tree is: push **selections** down first (they cut rows, which is usually the bigger win), then push **projections** down to trim width, keeping any attributes the remaining predicates and joins still need. Selection first because reducing cardinality helps every downstream operator multiplicatively; projection second because reducing width helps additively per surviving row. Modern cost-based optimizers do not follow a fixed heuristic ordering, but the intuition — rows before bytes — still explains most plans. ## What can invalidate the rewrite besides missing attributes - **Predicates with side effects or non-determinism.** If p calls a volatile function, moving it changes how many times it runs and possibly the result. Engines mark such functions and refuse to move the filter freely. - **Predicates whose evaluation can raise errors.** Filtering after a projection that removed a guard column can change whether a division-by-zero or cast error is reached. Engines that promise error-order semantics restrict movement accordingly. - **Extended projection.** If the projection computes an expression rather than merely restricting attributes, a predicate over that computed value cannot simply be moved below it — the value does not exist yet. ## How to answer this in an interview Lead with the legality condition (`attributes(p) ⊆ X`), give the split-projection fix, then explain the payoff in terms of tuple width, memory-bound operators and index-only access, and finish with the honest caveat that under set semantics early projection can pull an expensive deduplication earlier in the plan than you want. That sequence — correctness condition, workaround, benefit, caveat — is what distinguishes a production answer from a memorised identity.