Pushdown: negotiation and the ladder

When is pushdown wrong?

Pushdown capability negotiation: the interface is the limit

This item belongs at the top of the article, because it governs everything below it. A data source must be asked what filters it accepts. The contract must also say what it did not handle, so the engine can keep a residual filter and apply it itself. Spark's SupportsPushDownFilters.pushFilters() makes this contract explicit: it returns the subset of filters that the source could not handle. That returned set is the interface's vocabulary in machine-readable form.

Different sources speak different languages:

a JDBC source (a relational database reached over the network) accepts SQL;
a REST API accepts whatever its query parameters can express;
a file format accepts comparisons against its stored statistics.

The optimizer's reach ends exactly where that vocabulary ends. No amount of planning cleverness can extend it.

Here is a small pseudo-code of the contract:

accepted, residual = source.push_filters([f1, f2, f3])
# 'accepted' filters are applied inside the source.
# 'residual' filters MUST still be applied by the engine above the scan.

If an engine forgot the residual part, a source that ignores a filter would return wrong results. So "pushed" really means "the source promised to apply it".

In one sentence: the vocabulary of the interface below is the ceiling on this whole article, and a correct contract always returns the filters that were not handled.

Predicate pushdown: a ladder, not a switch

Pushdown is usually described as yes or no. In fact it is a ladder, and each rung saves a different thing:

Depth	Where the predicate is evaluated	What it saves
0	A filter operator above the scan	Only the work of operators above it
1	Inside the scan operator	Building row tuples that will be thrown away
2	On encoded data (dictionary codes, run-length runs)	Decoding CPU
3	Against page or row-group statistics	I/O
4	Against partition values or manifests	I/O and listing of metadata
5	Sent to a remote system	Network transfer and remote compute

Depth 2 is the least visible and often the largest CPU win. Two terms: with dictionary encoding, a column stores each distinct string once, and the rows store small integer codes. With run-length encoding (RLE), a repeated value is stored as (value, count). Under dictionary encoding, c = 'US' becomes one dictionary lookup that returns a code, and then comparisons of integers. Under RLE the comparison runs over runs, not rows: a column with 10⁶ rows and 200 runs is filtered with 200 comparisons. The predicate never touches a string. This is the mechanism behind most of the folklore that "columnar engines are fast". It is a pushdown effect, not an execution effect.

Four cases where pushdown is wrong

The folklore says pushdown always helps. It does not.

1. Expensive predicates. Pushing a user-defined function (UDF) below a join evaluates it on more rows than the join would have produced. A derivable rule: to minimize the expected cost of a set of AND-ed conditions, evaluate condition i before condition j if and only if

RelationshipOrder predicates by rows removed per unit of cost →

(1 - s_{i}) / c_{i} > (1 - s_{j}) / c_{j}

$s$: the fraction of rows that pass
$c$: the cost to evaluate it once

where s is the fraction of rows that pass (selectivity) and c is the cost to evaluate it once. This ranks conditions by "rows removed per unit of cost". It is the same ordering structure as scheduling jobs by value over work.

2. Outer joins. A predicate on the null-supplying side of an outer join (the side that gets NULLs for unmatched rows) cannot be pushed below the join. The null-extended rows have not been produced yet, so the meaning would change. This is the null-rejection property from the planning articles, used in the opposite direction.

3. Aggregation. A predicate on a grouping key can be pushed below the aggregate. A predicate on an aggregate result cannot. That is the whole mechanical meaning of WHERE versus HAVING: one clause is the pushable half and the other is the residual. SQL makes you name them because the optimizer could not always tell.

4. Federated sources. If you push a predicate to a remote system that has no index, your cheap filter becomes a full scan on their side, billed to them, on their latency. The cost moves; it does not vanish.

In one sentence: pushdown is a ladder whose rungs save decode, I/O, listing and network in turn; the rung you reach is set by the interface's vocabulary; and the order of conditions follows selectivity-gain per unit cost.