Rule-Based Rewrites — Predicate Pushdown and Join Pushdown

You write this query against an OLTP-scale warehouse replica:

SELECT u.name
FROM users u
JOIN orders o ON u.id = o.user_id
WHERE u.country = 'IN' AND o.year = 2026;

users has ten million rows, orders has a hundred million, and the join is on an indexed equality. A parser that simply translates SQL into algebra, one clause at a time, produces this logical tree:

π_{u.name}(
  σ_{u.country='IN' ∧ o.year=2026}(
    users ⋈_{u.id = o.user_id} orders
  )
)

Read it bottom-up the way the executor would: scan every row of users, scan every row of orders, join them on the key (10^8 output rows), then filter the 10^8 rows down to the ones where country = 'IN' and year = 2026, then project u.name. The join runs on the unfiltered inputs. Assume hash join on sorted-ish data; the join alone reads 10 GB of order pages and does a ten-million-row build on users. Wall-clock: minutes.

Now look at the same tree with predicates pushed down:

π_{u.name}(
  σ_{u.country='IN'}(users) ⋈_{u.id = o.user_id} σ_{o.year=2026}(orders)
)

The filters run first, on their respective base tables, independently. If country = 'IN' keeps 10% of users and year = 2026 keeps 5% of orders, the join now sees a one-million-row build side and a five-million-row probe side — a twenty-fold shrinkage. With an index scan on (country) and (year) the filters don't even read the full tables. Wall-clock: seconds.

Both trees produce the same rows. Both satisfy the SQL semantics. The second tree is the first tree after the optimiser applied two rules from the relational algebra equivalence laws. No statistics were consulted to produce it. That is the whole game of rule-based rewriting: use algebra to make the tree cheaper, before the cost-based layer gets involved.

Relational algebra, briefly

Five operators cover everything the parser emits. Every dialect of SQL compiles into some variant of this set, and every planner works by rewriting trees over it.

Scan(T) is the leaf — read relation T off disk. Every SQL query ends up as some tree of these over Scan leaves.

The operators have equivalence laws. These are theorems of set theory (or multiset theory for SQL bag semantics); the optimiser doesn't invent them, it just applies them. The five laws that carry most of the weight:

Why these are called equivalences and not transformations: each ≡ says "these two trees produce the same multiset of rows on every possible input." The optimiser is free to substitute either side for the other without consulting data, without running statistics, without cost analysis. That is what makes rule-based rewrites safe. The next chapter's cost-based rewrites are different — they choose among equivalent trees using estimated cardinalities, and a bad estimate produces a legal plan that runs very slowly. Rule-based rewrites cannot do that. If a rewrite changes the answer, the rewrite is a bug, not a plan choice.

Why join commutativity R ⋈ S ≡ S ⋈ R is not in the list above: the list is the rules that are always applied in the fixed-point loop. Commutativity is a rule that exposes alternative plans to the cost-based layer rather than committing to one shape. Rule-based rewriting leaves commutativity to the physical planner (it chooses build vs probe based on size) and the enumeration-based join-order search (the subject of the next chapter).

There are more — distribution of selection over union, pushdown past aggregation, set-operation simplification — and together they form the rule pack. Calcite's public catalogue is ~120 rules; a small, self-contained one like CockroachDB's opt/norm package has ~60. PostgreSQL's are spread across four or five files and are harder to count, but the number is in the same ballpark. You do not need to memorise them. You need to understand the three or four archetypes and recognise the rest as variations on them.

The rule engine — a fixed-point loop

A rule is a function from a subtree to a rewritten subtree. The engine walks the tree, tries every rule at every node, and keeps iterating until nothing changes. Here is the whole thing:

# query/opt/rules.py
from dataclasses import dataclass
from typing import Callable, Any

Tree = Any                                  # a Node of the plan tree
Rule = Callable[[Tree], Tree]               # identity if the rule doesn't fire

def optimise(tree: Tree, rules: list[Rule]) -> Tree:
    """Apply rules until the tree reaches a fixed point."""
    changed = True
    while changed:
        changed = False
        for rule in rules:
            new_tree = rule(tree)
            if new_tree is not tree:        # identity check: did the rule fire?
                tree = new_tree
                changed = True
    return tree

Fifteen lines. The is not identity check is the engine's contract: a rule returns the input tree unchanged (same object reference) when the pattern doesn't match, and returns a new tree when it does. Fixed-point termination is guaranteed as long as every rule either leaves the tree alone or replaces it with a strictly "smaller" tree under some termination ordering — which is true for pushdown rules (they lower the total node-height of predicates) and for simplification rules. Rules that create infinite loops (commutativity applied mindlessly — swap R ⋈ S for S ⋈ R, swap back, swap again) must be excluded from the fixed-point loop and invoked by a different planner (see the Volcano/Cascades discussion in the Going Deeper section).

Rules come in two traversal flavours. A top-down rule applies at the root and recurses into children only if the root didn't fire. A bottom-up rule recurses first, applies to children, then to the parent. Predicate pushdown is naturally top-down — you find a σ and push it into its child, then recurse into the new child to keep pushing. Projection pushdown is naturally bottom-up — you compute the set of columns each subtree produces, which depends on children, then decide what to project at each node.

def push_down_selection(node: Tree) -> Tree:
    """Top-down: try to push σ past its child."""
    if isinstance(node, Select):
        pushed = _try_push(node)            # might return node unchanged
        if pushed is not node:
            return pushed
    # recurse into children (skip the rewritten case — caller will re-enter)
    return node.map_children(push_down_selection)

Apache Calcite's HepPlanner is this fixed-point engine: it applies rules one at a time in a user-chosen order until the tree is a fixed point. It is the "rule-based" half of Calcite; the "cost-based" half is VolcanoPlanner, which instead enumerates all rule applications and picks the cheapest. PostgreSQL does not have an explicit rule engine — the rewrites are scattered as imperative passes across src/backend/optimizer/prep/ and src/backend/optimizer/plan/preptlist.c. Spark Catalyst does have one: each rule is an object extends Rule[LogicalPlan] and a RuleExecutor runs them in batches to fixed point. The abstraction is the same across engines; only the packaging differs.

Predicate pushdown — the flagship rule

This is the rewrite that single-handedly saves most queries. Start with the tree from the opening example:

π_{u.name}(
  σ_{u.country='IN' ∧ o.year=2026}(
    users ⋈_{u.id = o.user_id} orders
  )
)

Predicate pushdown proceeds in two sub-steps.

Step 1: split conjunctions. The law σ_{a ∧ b}(X) ≡ σ_a(σ_b(X)) says a selection over a conjunction can be unfolded into a tower of selections. After this step:

π_{u.name}(
  σ_{u.country='IN'}(
    σ_{o.year=2026}(
      users ⋈_{u.id = o.user_id} orders
    )
  )
)

Two independent selections, each referencing columns from just one side of the join.

Step 2: push each selection past the join. The law σ_c(R ⋈ S) ≡ σ_c(R) ⋈ S applies when c only references R's columns. u.country lives in users, so σ_{u.country='IN'} pushes into the left child. o.year lives in orders, so σ_{o.year=2026} pushes into the right child. After:

π_{u.name}(
  σ_{u.country='IN'}(users) ⋈_{u.id = o.user_id} σ_{o.year=2026}(orders)
)

Each filter now sits directly above its own base table, which means the executor can push it even further — into the table scan itself (an index scan with country = 'IN', or a scan with filter that evaluates the predicate on each page during read). The join receives the already-filtered subsets as its inputs.

Here is the rewrite as a Python rule, pattern-matching against an AST-like Node:

# query/opt/push_selection.py
from dataclasses import dataclass, replace

def push_selection_past_join(node):
    """σ_c(R ⋈ S) -> σ_{c|R}(R) ⋈ σ_{c|S}(S) ⋈ σ_{c|both}(...)."""
    if not (isinstance(node, Select) and isinstance(node.child, Join)):
        return node                                          # identity
    join = node.child
    conjuncts = split_conjunction(node.predicate)            # [u.country='IN', o.year=2026]
    left_preds, right_preds, join_preds = [], [], []
    for c in conjuncts:
        cols = referenced_columns(c)
        if cols.issubset(join.left.schema):   left_preds.append(c)
        elif cols.issubset(join.right.schema): right_preds.append(c)
        else:                                  join_preds.append(c)    # keep above join
    new_left  = Select(and_(left_preds),  join.left)  if left_preds  else join.left
    new_right = Select(and_(right_preds), join.right) if right_preds else join.right
    new_join  = replace(join, left=new_left, right=new_right)
    return Select(and_(join_preds), new_join) if join_preds else new_join

The structure is worth staring at. You split the predicate into three buckets by which side's columns each conjunct references. Predicates referencing only the left push left; only the right push right; predicates that touch both (say u.region = o.ship_region) stay above the join because they need columns from both inputs to evaluate. The reconstructed tree has (up to) three selections — one on each child, one above — and any of them can be None if its bucket is empty.

Run this rule at every Select-over-Join node in the tree and the fixed-point loop will keep applying it until all predicates have settled into the subtree closest to the scan they belong to. With the iterator model from the previous chapters, this means each scan's next() evaluates the filter row by row — or better, the scan fuses the filter into itself and uses an index.

Why pushing past π is almost always a win: a projection throws away columns. If the projection sits above a selection and the selection only needs columns the projection keeps, pushing the selection above the projection makes the selection redundant (or at least no cheaper). But pushing the selection below the projection lets the projection see a smaller input, which is free for row stores and a significant win for column stores (unread columns never leave disk). Either way, moving the selection downward is never worse.

Why you cannot always push past an aggregation: σ_c(γ_{G, F}(R)) is not in general equal to γ_{G, F}(σ_c(R)). If the predicate c is on a grouped column (say region = 'south'), you can push it — pre-filtering is safe because rows with region ≠ 'south' would have been grouped into groups you're about to throw away. If the predicate is on an aggregated column (say SUM(total) > 1000, a HAVING clause), you cannot push it — you need to finish aggregating before you can check the aggregate. This is why SQL distinguishes WHERE (pushable) from HAVING (not). The optimiser codifies this as a side condition on the σ_c(γ(R)) rewrite.

Projection pushdown

The same idea, for π. Columns you are not going to use should not travel up the tree. The law:

Read: if the top wants columns A, then each side only needs to carry the columns from A that it owns, plus the join columns J (which are needed to perform the join itself). Anything else can be projected away before the join.

In a row store this saves CPU and memory per tuple — smaller rows, fewer cache misses, smaller hash buckets. In a column store it saves entire columns worth of disk I/O: if orders has sixty columns and only three are needed downstream, the other 57 never leave the storage engine. For Parquet or ORC files, projection pushdown is what makes analytical queries fast — the scan only reads column stripes for projected columns.

The rule:

def push_projection_into_join(node):
    """π_A(R ⋈_J S) -> π_A(π_{A∩R ∪ J}(R) ⋈_J π_{A∩S ∪ J}(S))."""
    if not (isinstance(node, Project) and isinstance(node.child, Join)):
        return node
    j = node.child
    A = set(node.columns)
    J = referenced_columns(j.predicate)      # columns the join itself needs
    left_needed  = (A & j.left.schema)  | (J & j.left.schema)
    right_needed = (A & j.right.schema) | (J & j.right.schema)
    new_left  = Project(left_needed,  j.left)  if left_needed  < j.left.schema  else j.left
    new_right = Project(right_needed, j.right) if right_needed < j.right.schema else j.right
    return Project(node.columns, replace(j, left=new_left, right=new_right))

The < check (proper subset) avoids inserting a no-op projection when the child already produces exactly the needed columns — otherwise the fixed-point loop would keep re-inserting identical projections forever.

Column pruning generalises this to all operators: every node computes the set of columns it needs from each child, and the scan at the bottom only reads those. Spark's ColumnPruning rule and DuckDB's projection pushdown implement exactly this analysis.

Join reordering — commutativity and associativity

Inner joins satisfy two more laws:

Commutativity is why the optimiser gets to pick the build side of a hash join — the join's logical output doesn't care which side you call R and which S, so you can build the hash table on whichever side is smaller. Associativity is richer: it says the same three-way join can be bracketed three ways (and in general the n-way join has C_{n-1} Catalan-many bracketings), and the optimiser can pick the cheapest.

Left-deep vs bushy plans. A three-way join A ⋈ B ⋈ C can be parenthesised as (A ⋈ B) ⋈ C (left-deep) or A ⋈ (B ⋈ C) (right-deep) or, for four-way and above, bushy: (A ⋈ B) ⋈ (C ⋈ D). Most optimisers restrict the search space to left-deep plans. Two reasons. First, left-deep plans pipeline naturally — the output of the first join streams directly into the second join's probe side without materialisation. A bushy plan has two intermediate results alive simultaneously, doubling memory pressure. Second, the search space is much smaller: for n tables, left-deep has n! plans while bushy has Catalan C_{n-1} · n! — the difference starts to matter at n = 6 and dominates by n = 10.

Here is the critical point about rule-based reordering: the rewrites do not pick an order. Commutativity and associativity are equivalences; applying them blindly in a fixed-point loop would never terminate (swap, swap back, swap again). The rule-based layer only enumerates the equivalent orderings and hands them to the cost-based layer. Calcite's VolcanoPlanner tracks multiple equivalent subtrees in a memo structure (a DAG where each node is a logical expression and its equivalence class is a set of physical alternatives). PostgreSQL's optimiser uses dynamic programming over the System R join-enumeration algorithm (Selinger 1979). Both require statistics — join selectivity estimates, row counts — to pick a specific order, which is why this is where rule-based ends and cost-based begins.

What rule-based does do unconditionally:

• Push predicates past a join regardless of direction, which we just covered.
• Merge adjacent selections/projections so the tree has one per node type per level.
• Drop trivially redundant joins (e.g. A ⋈ A when both sides share the full key set — a self-join on primary keys can collapse into A).

Picking between (A ⋈ B) ⋈ C and A ⋈ (B ⋈ C) requires knowing how many rows come out of A ⋈ B versus B ⋈ C, which needs statistics. That is the next chapter.

Other rules worth knowing

A rule pack doesn't end at pushdowns and join laws. Some of the other rewrites every production engine ships:

Constant folding. SELECT x + 2 + 3 FROM t becomes SELECT x + 5 FROM t at plan time. A single arithmetic operation saved per row, multiplied by billions of rows per day in a warehouse, is worth real money. Every parser's expression tree walks itself looking for operator nodes whose children are all literals and collapses them.

Column pruning. The top-level SELECT a, b FROM t keeps only columns a and b; every other column can be dropped from every intermediate result. In a columnar store this turns into "don't even open the column file for c"; in a row store it shrinks tuples. The rule propagates a "required columns" set top-down through the tree and the scan at the bottom reads only the reachable ones.

Subquery unnesting. The SQL EXISTS (SELECT 1 FROM orders o WHERE o.user_id = u.id) in a correlated subquery would naively run the inner query once per outer row — an O(|users| · |orders|) nested loop. The optimiser detects the correlation predicate o.user_id = u.id and rewrites the subquery into a semi-join: users ⋉_{u.id = o.user_id} orders, which the hash-join engine can evaluate once with a single pass. Unnesting is complicated — NOT EXISTS, correlated aggregates, lateral joins — but the pattern is the same: turn nested iteration into a single join with a modified output semantic.

Union rewrites. R UNION S deduplicates, which costs a sort or a hash-distinct. R UNION ALL S does not. If the optimiser can prove that R and S produce disjoint row sets (say, R = σ_{x='a'}(T) and S = σ_{x='b'}(T) — disjoint by construction), it can rewrite UNION to UNION ALL and skip the deduplication. This is a big win for partition-union patterns common in time-series tables.

Outer-join to inner-join. R ⟕ S WHERE S.col IS NOT NULL is equivalent to R ⋈ S — the left outer join would have produced NULL rows for unmatched left tuples, and the filter kills exactly those rows, so you can drop the outer semantics and join inner-only. This matters because inner joins reorder freely under associativity while outer joins do not.

A full worked example

SELECT u.name
FROM users u JOIN orders o ON u.id = o.user_id
WHERE u.country = 'IN' AND o.year = 2026;

Common confusions

• "Rule-based rewrites need statistics." No. They are pure syntactic equivalences from relational algebra. The whole value of rule-based optimisation is that it is statistic-free — it works the same on an empty table and a trillion-row one, and never produces a wrong answer because of stale statistics. Statistics are for the cost-based layer, which chooses among equivalent plans the rule-based layer exposed.

• "Predicate pushdown always helps." Almost always, but there is a pathological case: the predicate is very expensive to evaluate (say, a UDF that hits an external service at 10 ms per call) and the side it lands on is big. Running a 10-ms UDF on ten million rows is 28 hours; running it on ten thousand post-join rows is 100 seconds. In this case you would not push the UDF down and the optimiser needs a cost model to decide. PostgreSQL has a procost knob on user-defined functions precisely so the planner can avoid pushing expensive predicates.

• "Join reordering is always safe." Only for inner joins. Outer joins do not satisfy associativity in general: (A ⟕ B) ⟕ C ≠ A ⟕ (B ⟕ C) because of how NULL-extended rows propagate. Full-outer joins are worst. The optimiser's reordering logic has to track which joins are inner and only reorder those; outer joins are reorderable only when extra conditions hold (null-rejecting predicates, specific shapes), and most planners conservatively refuse to reorder across them. This is why LEFT JOIN heavy queries often run slower than their inner-join equivalents — the planner's hands are tied.

• "The optimiser reorders your WHERE clause for you." True, and this is a feature. SQL is declarative: the WHERE clause is an unordered set of predicates. Whatever order you type, the planner reads it as a conjunction and breaks it into conjuncts using σ_{a∧b} ≡ σ_a(σ_b(...)). It then pushes each conjunct independently to wherever it can go — past joins into the correct side, past projections, into index scans. You cannot force an order by writing predicates in a specific way. The only way to control evaluation order is via planner hints (Oracle's /*+ ORDERED */) or by subquery structure (a nested SELECT becomes a barrier in some engines).

• "All rewrites are free." The fixed-point loop does cost CPU at compile time. For a 3-table query it is milliseconds; for a 50-table auto-generated BI query with hundreds of subqueries, rule matching alone can take seconds. Production optimisers have budgets (from_collapse_limit in Postgres, Calcite's rule-execution timeout) and fall back to a simpler plan if the search exceeds them.

• "Projection pushdown doesn't matter for row stores." It matters, just less than for columnar stores. A row store still pays for wide tuples through every operator — bigger hash-join buckets, more memory per sort run, more bytes copied through every next(). Pushing projections down narrows the pipeline end to end. In a column store it is dramatic (unread columns stay on disk); in a row store it is a steady 10–30% across the board.

Going deeper

These are the implementation details that turn "apply some equivalence laws" into a production optimiser. Two are worth the read.

Spark Catalyst — rules as tree transformations

Catalyst models a logical plan as an immutable case-class tree. A rule is an object extends Rule[LogicalPlan] with an apply(plan: LogicalPlan): LogicalPlan method. A rule executor runs batches of rules to fixed point:

object PushPredicateThroughJoin extends Rule[LogicalPlan] {
  def apply(plan: LogicalPlan): LogicalPlan = plan transform {
    case Filter(cond, j @ Join(left, right, Inner, Some(joinCond), hint)) =>
      val (leftC, rightC, otherC) = split(cond, left.outputSet, right.outputSet)
      val newLeft  = leftC.map(Filter(_, left)).getOrElse(left)
      val newRight = rightC.map(Filter(_, right)).getOrElse(right)
      val newJoin  = Join(newLeft, newRight, Inner, Some(joinCond), hint)
      otherC.map(Filter(_, newJoin)).getOrElse(newJoin)
  }
}

The transform combinator is a visitor over the immutable tree: it applies the partial function to every node bottom-up and returns a new tree with the rewrites threaded through. If the partial function doesn't match, the node is returned unchanged. This is what makes rule-based rewriting composable — adding a rule is writing one case and registering it in a batch. Catalyst ships roughly 100 such rules.

The RuleExecutor is exactly the fixed-point loop from this chapter, with one extra feature: rules are grouped into batches, each batch with its own termination strategy (fixed point, or "once" for rules that should apply exactly once). This avoids interleaving rules that interact badly.

Reference: Catalyst paper (Armbrust et al., SIGMOD 2015).

Bloom filters as "runtime filter pushdown"

A technique that looks like predicate pushdown but runs at execution time. Consider A ⋈ B where |A| is small (a filtered dimension, 10^5 rows) and |B| is large (a fact table, 10^9 rows). Classic predicate pushdown cannot help: there's no explicit predicate on B, only the implicit equijoin.

A Bloom filter pushdown builds a Bloom filter on A's join keys during A's scan, ships it down to B's scan, and B uses it to skip rows whose join key definitely isn't in A. This is not a correctness-preserving logical rewrite — the tree remains A ⋈ B — but it is a runtime optimisation that reduces B's effective row count by orders of magnitude. Impala pioneered it as "runtime filters"; Presto, Spark, and Snowflake now all ship variants.

It sits between rule-based and cost-based optimisation: the decision whether to generate a Bloom filter is cost-based (only useful when A is small and selective), but the rewrite shape is rule-based (insert a BloomProbe node into B's scan). Modern optimisers blur the line between the two halves.

Where this leads next

Rule-based rewrites are the deterministic half of the optimiser. They turn whatever the parser hands them into a canonical, pushed-down, pruned tree that commits to no particular join order. What rule-based leaves open is exactly the interesting question — given several equivalent trees, which one runs fastest on your actual data?

That needs three things the next chapters build:

• Statistics — histograms, most-common-value lists, n_distinct per column, correlations. The raw inputs to cardinality estimation.
• Cardinality estimation — given a subtree and the statistics on its leaf tables, predict how many rows it produces.
• Cost-based plan enumeration — with cardinality estimates in hand, assign each plan a cost (in page I/O, CPU comparisons, network bytes) and pick the minimum. This is System R's dynamic programming algorithm (Selinger 1979), generalised to bushy plans and index-nested-loop alternatives.

The physical plan choice — nested-loop vs hash vs sort-merge, index scan vs sequential, hash agg vs sort agg — is also cost-based. The rule-based layer produces a logical plan (operators, order, predicates); the cost-based layer picks the physical implementation of each operator.

Everything you saw in the previous chapters — nested-loop join, hash join, sort-merge join, the iterator model — fits into that picture as "physical operators the cost-based layer chooses among." Rule-based rewrites pick which subtree goes into them; cost-based optimisation picks which operator runs each subtree. Together they produce the plan you see in EXPLAIN ANALYZE.

References

1. Selinger, Astrahan, Chamberlin, Lorie, Price, Access Path Selection in a Relational Database Management System, SIGMOD 1979 — the System R paper that defined the rule-based plus cost-based architecture every modern optimiser still uses. Section 3 describes the predicate-pushdown rule; sections 4–5 are cost-based join enumeration.
2. Graefe, Query Evaluation Techniques for Large Databases, ACM Computing Surveys 25(2), 1993 — the canonical survey. Chapter 3 on rule-based transformations is still the best reference for the taxonomy of rewrites.
3. Armbrust, Xin, Lian, Huai, Liu, Bradley, Meng, Kaftan, Franklin, Ghodsi, Zaharia, Spark SQL: Relational Data Processing in Spark, SIGMOD 2015 — describes Catalyst's rule framework and shows the Rule[LogicalPlan] abstraction used in the Going Deeper section.
4. Begoli, Camacho-Rodríguez, Hyde, Mior, Lemire, Apache Calcite: A Foundational Framework for Optimized Query Processing Over Heterogeneous Data Sources, SIGMOD 2018 — the Calcite paper, covering HepPlanner (rule-based) and VolcanoPlanner (cost-based) side by side.
5. PostgreSQL source tree, src/backend/optimizer/prep/prepjointree.c — the production predicate-pushdown implementation, including outer-join reduction and subquery unnesting. Long but clean; the comments are half the reading.
6. Neumann and Kemper, Unnesting Arbitrary Queries, BTW 2015 — the modern reference for subquery unnesting, generalising the classical EXISTS→semi-join rewrite to arbitrary correlated subqueries.