Query Plan Optimization: Column Pruning And Filter Pushdown

What's being tested

Two core skills: implementing column pruning and filter pushdown on a query-plan tree, and writing correct, efficient tree rewrites. Interviewers check recursive AST traversal, tracking required columns and predicates across Scan, Project, Filter, and Join nodes, plus sound handling of expression lineage and semantics.

Patterns & templates

• Bottom-up recursion: compute required columns for each node from its parent, revisit children with that set; linear time O(nodes) for fixed-size expressions.

• Predicate classification: split predicates into pushable (refer only to one child) and residual; push pushables down early to reduce rows.

• Column projection: at Scan emit only needed physical columns; at Project rewrite expressions to map child columns, prune unused projections.

• Join handling: push predicates that reference only one side into that side; predicates referencing both become join conditions. Handle outer joins conservatively.

• Expression substitution: maintain a mapping from parent output to child expressions for safe rewrite; avoid re-evaluating complex expressions.

• Immutability & CAS: return new nodes (functional updates) so rewrites are testable; memoize visited nodes to avoid exponential work.

Common pitfalls

Pitfall: Pushing a predicate that references columns produced by a Project without rewriting to the underlying Scan names — causes invalid plans.

Pitfall: Ignoring NULL semantics on outer joins and pushing predicates that change result cardinality.

Pitfall: Over-pruning columns used inside non-project side-effects (e.g., EXISTS, ORDER BY expressions) — leads to incorrect answers.

Practice these

The practice cards below cover the canonical variants — solve all of them and time yourself.