Predicate Pushdown and Filter Placement

In query optimization, few transformations deliver as much practical impact as predicate pushdown.
The idea is simple: evaluate filter conditions as early as possible during query execution, reducing the volume of data that flows through expensive operators like joins, aggregations, and sorts.
Despite its conceptual simplicity, correct and optimal filter placement requires careful reasoning about relational algebra equivalences, nullability semantics, and the interaction between logical and physical planning.

Why It Matters

Consider a query that joins two tables, each with 10 million rows, and then applies a filter that selects 0.1% of the result.
Without predicate pushdown, the join processes all 10 million rows from each side, producing a potentially massive intermediate result, only to discard 99.9% of it.
With pushdown, the filter is applied before the join, reducing one input to roughly 10,000 rows.
The join itself becomes orders of magnitude cheaper, and memory consumption for hash tables or sort buffers drops proportionally.

This is not a marginal optimization.
In analytical workloads, predicate pushdown routinely turns minutes-long queries into sub-second ones.

Foundations in Relational Algebra

Predicate pushdown is grounded in equivalence rules of relational algebra.
The core rule is the commutativity of selection with other operators.

Selection past join:

σ_p(R ⋈ S) ≡ σ_p(R) ⋈ S

This holds when predicate p references only attributes of R.
If p references attributes of both R and S, it cannot be pushed below the join (it is a join predicate, not a filter predicate).

Selection past projection:

σ_p(π_A(R)) ≡ π_A(σ_p(R))

This holds when all attributes referenced by p are included in the projection list A.
If they are not, the optimizer must either widen the projection temporarily or leave the filter in place.

Selection past union:

σ_p(R ∪ S) ≡ σ_p(R) ∪ σ_p(S)

This works because union preserves tuple structure.
The analogous rule applies to UNION ALL.

Selection past aggregation:

Predicates on grouping columns can be pushed below GROUP BY.
Predicates on aggregate results (i.e., HAVING conditions) cannot, since the aggregate values do not exist before the grouping is performed.

Filter Placement Strategy

Optimal filter placement is more than just "push everything down." The optimizer must decide, for each predicate, the lowest valid position in the query plan tree where it can be evaluated.
This is sometimes called the "earliest point of evaluation."

Decomposing Conjunctive Predicates

A WHERE clause like a.x = 5 AND b.y > 10 AND a.z = b.w contains three conjuncts.
The optimizer decomposes them and handles each independently:

• a.x = 5 references only table a. Push it below any join to become a scan-level filter on a.
• b.y > 10 references only table b. Push it to a scan-level filter on b.
• a.z = b.w references both tables. It remains as a join condition.

Outer Joins and Correctness Hazards

Predicate pushdown across outer joins is the most common source of correctness bugs in query optimizers.
Consider a LEFT JOIN:

SELECT *
FROM orders o
LEFT JOIN returns r ON o.id = r.order_id
WHERE r.reason = 'defective'

Pushing r.reason = 'defective' into the scan on returns seems harmless, but it changes semantics.
The LEFT JOIN preserves all rows from orders, filling returns columns with NULL when there is no match.
The WHERE filter on r.reason then eliminates those NULL-padded rows, effectively converting the LEFT JOIN into an INNER JOIN.
If the user intended the outer join semantics, the pushdown is incorrect.

The general rules:

1. For a LEFT JOIN (R, S), predicates on S (the nullable side) in the WHERE clause can be pushed into the join condition (converting to inner join) only if the predicate rejects NULLs. This is called "null-rejecting" or "strong" predicate analysis.
2. Predicates on R (the preserved side) can be pushed below the join freely.
3. Predicates in the ON clause of an outer join must not be pushed to the WHERE level, as they have different semantics (they filter before null-padding, and not after).

Walkthrough

Below is a step-by-step walkthrough of predicate placement for a concrete query.
This mirrors the approach used by optimizers like those in PostgreSQL, Apache Calcite, and CockroachDB.

Input query:

SELECT o.id, c.name, SUM(o.amount)
FROM orders o
JOIN customers c ON o.cust_id = c.id
WHERE c.country = 'DE'
  AND o.amount > 100
  AND o.created_at > '2024-01-01'
GROUP BY o.id, c.name
HAVING SUM(o.amount) > 1000

Step 1: Parse into logical plan tree.

HavingFilter [SUM(o.amount) > 1000]
  └── Aggregate [GROUP BY o.id, c.name; SUM(o.amount)]
        └── Filter [c.country = 'DE' AND o.amount > 100 AND o.created_at > '2024-01-01']
              └── Join [o.cust_id = c.id]
                    ├── Scan [orders o]
                    └── Scan [customers c]

Step 2: Decompose the conjunctive filter.

Three predicates:

• P1: c.country = 'DE' (references c only)
• P2: o.amount > 100 (references o only)
• P3: o.created_at > '2024-01-01' (references o only)

Step 3: Push each predicate to its earliest valid position.

P1 depends only on c, so push it below the join to the customers scan.
P2 and P3 depend only on o, so push them below the join to the orders scan.

Step 4: Handle the HAVING clause.

SUM(o.amount) > 1000 references an aggregate output.
It cannot be pushed below the aggregation.
It stays as a filter above the Aggregate node.

Resulting plan:

Filter [SUM(o.amount) > 1000]
  └── Aggregate [GROUP BY o.id, c.name; SUM(o.amount)]
        └── Join [o.cust_id = c.id]
              ├── Filter [o.amount > 100 AND o.created_at > '2024-01-01']
              │     └── Scan [orders o]
              └── Filter [c.country = 'DE']
                    └── Scan [customers c]

Step 5: Physical pushdown into storage.

Many storage engines accept predicates directly.
The optimizer can push o.created_at > '2024-01-01' into the scan as a range condition on an index.
In columnar stores, o.amount > 100 can be evaluated during column decoding, skipping entire row groups via min/max statistics.
This is sometimes called "predicate pushdown to storage" to distinguish it from the logical-level transformation.

Predicate Pushdown in Distributed and Federated Systems

In distributed databases, predicate pushdown takes on additional significance.
Pushing a filter from a coordinator node to a storage node avoids shipping irrelevant data across the network.
Systems like Presto/Trino, Spark, and BigQuery aggressively push predicates into connectors or remote scan operators.

In federated query engines, the optimizer must determine which predicates the remote source can evaluate.
A predicate involving a local UDF, for instance, cannot be pushed to a remote PostgreSQL instance.
This leads to "capability-based pushdown," where the optimizer queries a connector's metadata to determine supported filter types.

Partition pruning is a closely related optimization.
If a table is partitioned by created_at, the predicate o.created_at > '2024-01-01' allows the engine to skip reading entire partitions, which is effectively predicate pushdown at the metadata level.

Interaction with Other Optimizations

Predicate pushdown interacts with several other optimizer transformations:

Predicate inference (transitive closure). Given a.x = b.x AND b.x = 5, the optimizer can infer a.x = 5 and push this derived predicate down to the scan on a.
This is sometimes called "constant propagation through equi-joins."

Join reordering. Once predicates are pushed down, the selectivity estimates for each table change, which in turn affects the optimal join order.
A highly selective filter on one table makes it a good candidate for the inner (build) side of a hash join.

Predicate pullup. In some cases, the optimizer benefits from pulling a predicate up from a subquery and then pushing it down into a different branch.
This is common when decorrelating correlated subqueries.

Key Points

• Predicate pushdown reduces intermediate result sizes by evaluating filters as early as possible, often transforming query performance by orders of magnitude.
• The transformation is based on relational algebra equivalences, particularly the commutativity of selection with join, projection, and union operators.
• Conjunctive predicates in the WHERE clause should be decomposed and each conjunct pushed independently to the lowest valid position in the plan tree.
• Outer joins require careful null-rejection analysis before predicates on the nullable side can be safely pushed down or used to convert the join type.
• Physical pushdown into storage engines (index range scans, partition pruning, row group skipping via min/max statistics) extends the benefits beyond logical plan optimization.
• In distributed and federated systems, pushdown reduces network transfer and must account for the capabilities of remote data sources.
• Predicate pushdown interacts with join reordering, transitive closure, and subquery decorrelation, making it a central component of the broader optimization pipeline.

References

P. Griffiths Selinger, M. M. Astrahan, D. D. Chamberlin, R. A. Lorie, T. G. Price. "Access Path Selection in a Relational Database Management System." Proceedings of the 1979 ACM SIGMOD International Conference on Management of Data, 1979.

Goetz Graefe. "The Cascades Framework for Query Optimization." IEEE Data Engineering Bulletin, 18(3), 1995.

Hamid Pirahesh, Joseph M. Hellerstein, Waqar Hasan. "Extensible/Rule Based Query Rewrite Optimization in Starburst." Proceedings of the 1992 ACM SIGMOD International Conference on Management of Data, 1992.

Raghu Ramakrishnan, Johannes Gehrke. "Database Management Systems." 3rd Edition, McGraw-Hill, 2003.