Today we'll see one of the most powerful planner optimizations: predicate pushdown and predicate distribution. Predicate pushdown moves existing filters closer to scans. Predicate distribution goes further: it derives equivalent filters from the query structure.
The hard part is not generating more predicates, it is generating only predicates that are semantically safe. Inner joins, outer joins, grouping, set operations, and expressions all have different correctness rules.
In a plan, it is better to have predicates in scan nodes. This enables many file and row-group skipping optimizations for modern data lakes. It also decreases the number of rows flowing through the execution tree, making all operations faster.
The planner first has to prove that a predicate is valid at a given point in the plan. Only then can the scan operator or storage layer use it for row-group skipping, min/max pruning, or other access-path optimizations.
Thus, it is better to push predicate filters as close to the source of data as possible.
The query:
SELECT * FROM A JOIN B ON A.x = B.x WHERE A.x = 1;
has two equivalent plans:
Filter: A.x = 1
└── Join: A.x = B.x
├── Scan A
└── Scan B
Join: A.x = B.x
├── Filter: A.x = 1
│ └── Scan A
└── Scan B
They produce the same result, but the second one is much better because it reduces the number of rows in the join and allows scan-level skipping.
If we know that A.x = B.x holds in the final result, we can also add a new filter on the B scan without changing the query result. We'll develop this technique in the next section.
Join: A.x = B.x
├── Filter: A.x = 1
│ └── Scan A
└── Filter: B.x = 1
└── Scan B
Having the planner apply predicates as close to scans as possible is nice, but it can usually do much better by taking advantage of the query structure.
If there is an equality between two columns, A.x = B.x, a powerful optimization is realizing that safe predicates on A.x can also be applied to B.x, and reciprocally. This allows the planner to create new scan filters "ex nihilo".
For inner joins, once the planner knows that A.x = B.x holds for surviving rows, a safe predicate on A.x can often be inferred for B.x. Outer joins need additional care because one side may be null-extended.
This rule is valid for predicates that are safe to duplicate and evaluate on the equivalent expression:
To be safely pushed down or duplicated, a predicate must be stable with respect to the expressions it is applied to. In other words, if the planner knows that A.x = B.x, then it must also be safe to assume that f(A.x) = f(B.x) for the predicate being derived.
For instance, rand() is not stable in this sense. Even if A.x = B.x, two separate calls to rand() may return different values:
Other common examples are timeofday() and clock_timestamp().
The exact behavior depends on the database engine. Some systems distinguish between immutable, stable, and volatile functions, and only some of those categories are safe for predicate pushdown or predicate duplication.
A function with side effects is also unsafe to freely push down or duplicate. A side effect is any change to internal or external state that is not reset for each call.
A common example is the nextval('seq') sequence function, which increments the sequence every time it is called. Duplicating or moving such a function could change how many times it is evaluated, and therefore change the result of the query.
User-defined functions can also have side effects, depending on what they do.
Some operators have different semantics depending on the input type. The ordering of the literals '1', '10', and '3' is different for strings and integers:
-- string ordering
'1' < '10' < '3'
-- integer ordering
1 < 3 < 10
The same issue can appear with two string columns that use different collations.
With C collation, sorting is mostly byte- or codepoint-oriented, so uppercase ASCII letters sort before lowercase letters. With a locale-aware collation such as en_US.utf8, ordering is language-aware and may treat case differently.
-- 'C' collation
Banana < Zebra < apple
-- 'utf8' collation
apple < Banana < Zebra
Luckily, most predicates are safe to push down. Examples include x -> x != 3, x -> x + 1 = 3, x -> left(x, 4) like 'abd%d'. It is not limited to equalities.
Not every equality-like expression creates a usable equivalence class. The planner must account for exceptions like null semantics, casts, collations, and outer-join null extension. We'll discuss outer joins in the following section.
Let's take an example. In this query, we know that in the output A.x = B.x and A.x = 1, so we can deduce that B.x = 1 must be true:
SELECT * FROM A JOIN B ON A.x = B.x WHERE A.x = 1;
is equivalent to:
SELECT * FROM A JOIN B ON A.x = B.x WHERE A.x = 1 AND B.x = 1;
A powerful abstraction to represent this property in more complex queries is equivalence classes:
In mathematics, an equivalence relation is a binary relation that is reflexive, symmetric, and transitive. An example is numerical equality. Any number is equal to itself (reflexive). If
a = b, thenb = a(symmetric). Ifa = bandb = c, thena = c(transitive).
We build equivalence classes of columns we know are equal. Then, every safe predicate initially targeting one of the columns in the class can be applied to all of them.
In the query:
SELECT *
FROM A
JOIN B ON A.x = B.x
JOIN C ON B.x = C.y
JOIN D ON C.d = D.d
WHERE
B.x IN (1, 2, 3) AND
D.d != 'invalid';
We can build two equivalence classes:
Eq1 with A.x, B.x, and C.y.Eq2 with C.d and D.d.We can attach qualifiers to each of the equivalence classes:
B.x IN (1, 2, 3) to Eq1.D.d != 'invalid' to Eq2.And replace the initial column with placeholders: B.x IN (1, 2, 3) becomes $1 IN (1, 2, 3).
The planner can now apply this restriction everywhere it has access to one of the initial columns in the equivalence class. So, for Eq1, it can apply the restriction in the scans of A, B, and C.
The final plan is:
SELECT
INNER HASH JOIN ON (d.d = c.d)
|-INNER HASH JOIN ON (b.x = a.x)
| |-INNER HASH JOIN ON (a.x = c.y)
| | |-SCAN c
| | | c.d <> 'invalid' <- Eq2
| | | AND ((c.y = 1) OR ((c.y = 2) OR (c.y = 3))) <- Eq1
| | |-BUILD
| | SCAN a
| | (a.x = 1) OR ((a.x = 2) OR (a.x = 3)) <- Eq1
| |-BUILD
| SCAN b
| (b.x = 1) OR ((b.x = 2) OR (b.x =3)) <- Eq1
|-BUILD
SCAN d
d.d <> 'invalid' <- Eq2
Outer joins are tricky and need special pushdown rules to respect their null semantics.
One needs to be especially careful with the difference between ON and WHERE semantics.
Let's study this outer join:
SELECT * FROM A LEFT JOIN B ON A.x = B.x;
+-------+ +-------+ +---------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | 3 | | 2 | 2 |
| 2 | ⟕ | 3 | => | 2 | 2 |
| 3 | A.x=B.x | 4 | | 3 | 3 |
| null | | null | | 3 | 3 |
+-------+ +-------+ | null | null |
+---------------+
We start by adding a WHERE clause on the non-nullable side:
SELECT * FROM A LEFT JOIN B ON A.x = B.x WHERE A.x != 3;
+-------+ +-------+ +---------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | 3 | | 2 | 2 |
| 2 | ⟕ | 3 | => | 2 | 2 |
| 3 | A.x=B.x| 4 | A.x!=3 | -3- | -3- |
| null | | null | | -null| -null- |
+-------+ +-------+ +---------------+
Because the join condition is A.x = B.x, and the final result keeps only rows where A.x != 3, matching B rows with B.x = 3 can never contribute to the final result. Therefore, the derived predicate B.x != 3 can be pushed to the B scan.
SELECT * FROM A LEFT JOIN B ON A.x = B.x WHERE A.x != 3; (pushdown)
+-------+ +-------+ +-------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | -3- | | 2 | 2 |
| 2 | ⟕ | -3- | => | 2 | 2 |
| -3- | A.x=B.x| 4 | +-------------+
| -null-| | null |
+-------+ +-------+
A.x != 3 B.x != 3
The final plan is:
SELECT * FROM A LEFT JOIN B ON A.x = B.x WHERE A.x != 3;
---
SELECT
LEFT OUTER HASH JOIN ON (b.x = a.x)
|-SCAN a
| (a.x <> $0)
|-BUILD
SCAN b
(b.x <> $2)
The semantics are different if the WHERE clause uses a column for the nullable side, where B.x != 3, and if the clause is null-rejecting. All null-extended rows from B are removed. There is an implicit B.x is not null condition added. In other words, this collapses the outer join into a simple inner join. Usual inner join rules apply. We can push down on both sides.
For example, this LEFT JOIN:
SELECT A.x, B.x
FROM A
LEFT JOIN B ON A.x = B.x
WHERE B.x != 3;
is equivalent to this INNER JOIN:
SELECT A.x, B.x
FROM A
INNER JOIN B ON A.x = B.x
WHERE B.x != 3;
The WHERE B.x != 3 clause removes every row where B.x is NULL, including every null-extended row produced by the outer join.
A strict function returns
NULLwhen any input isNULL. In aWHEREclause, thatNULLresult is not true, so the row is removed.
We can see that the result of the query without pushdown:
SELECT * FROM A LEFT JOIN B ON A.x = B.x WHERE B.x != 3; (no pushdown)
+-------+ +-------+ +---------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | -1- | -null- |
| 2 | | 3 | | 2 | 2 |
| 2 | ⟕ | 3 | => | 2 | 2 |
| 3 | A.x=B.x| 4 | B.x != 3 | -3- | -3- |
| null | | null | | -3- | -3- |
+-------+ +-------+ | -null| -null- |
+---------------+
is the same as the query with pushdown and an inner join rewrite.
SELECT * FROM A LEFT JOIN B ON A.x = B.x WHERE B.x != 3; (pushdown)
+-------+ +-------+ +-------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 2 | 2 |
| 2 | | -3- | | 2 | 2 |
| 2 | ⋈ | -3- | => +-------------+
| -3- | A.x=B.x| 4 |
| -null-| | -null-|
+-------+ +-------+
A.x != 3 B.x != 3
The final plan is:
SELECT
INNER HASH JOIN ON (b.x = a.x)
|-SCAN a
| (a.x <> $0)
|-BUILD
SCAN b
(b.x <> $2)
We need to be careful not to confuse the semantics of a clause in ON with a clause in WHERE.
WHERE falseremoves every row. In aLEFT JOIN,ON falsepreserves every row from the left side and fills the right-side columns withNULL.
For example, this query returns every row from A, with B.x filled with NULL:
SELECT A.x, B.x
FROM A
LEFT JOIN B ON false;
---
+---------------+
| A B |
| ----- ----- |
| 1 | null |
| 2 | null |
| 2 | null |
| 3 | null |
| 3 | null |
| null | null |
+---------------+
But this query returns no rows:
SELECT A.x, B.x
FROM A
LEFT JOIN B ON true
WHERE false;
---
+---------------+
| A B |
| ----- ----- |
+---------------+
For a LEFT JOIN, an ON predicate that references only the nullable side can be pushed into that nullable input. But an ON predicate can never be pushed into the preserved input, because rows from that side must still be preserved even when the ON predicate is false.
However, we still can use the equivalence class rule to rewrite some of the predicates.
We can rewrite:
ON A.x = B.x AND A.x != 3
into:
ON A.x = B.x AND A.x != 3 AND B.x != 3
The planner keeps the original A.x != 3 predicate and derives the additional B.x != 3 predicate from the equality A.x = B.x. Then we can push down the derived B.x != 3 predicate into B, because rows with B.x = 3 cannot match any row satisfying A.x != 3.
Let's use an example again:
SELECT * FROM A LEFT JOIN B ON A.x = B.x AND A.x != 3; (no pushdown)
+-------+ +-------+ +---------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | 3 | | 2 | 2 |
| 2 | ⟕ | 3 | => | 2 | 2 |
| 3 | A.x=B.x | 4 | | 3 | null |
| null | A.x!=3 | null | | null | null |
+-------+ +-------+ +---------------+
Pushing the original A.x != 3 predicate into the preserved side would be unsafe for an ON clause: rows from A must still be preserved even when the ON predicate is false.
SELECT * FROM A LEFT JOIN B ON A.x = B.x AND A.x != 3; (A pushdown wrong result)
+-------+ +-------+ +-------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | 3 | | 2 | 2 |
| 2 | ⟕ | 3 | => | 2 | 2 |
| -3- | A.x=B.x| 4 | +-------------+
| -null-| | null | Missing rows
+-------+ +-------+
A.x != 3
But it is safe to push the derived B.x != 3 predicate into the B input:
SELECT * FROM A LEFT JOIN B ON A.x = B.x AND A.x != 3; (B pushdown)
+-------+ +-------+ +---------------+
| A | | B | | A B |
| ----- | | ----- | | ----- ----- |
| 1 | | 2 | | 1 | null |
| 2 | | -3- | | 2 | 2 |
| 2 | ⟕ | -3- | => | 2 | 2 |
| 3 | A.x=B.x| 4 | | 3 | null |
| null | | null | | null | null |
+-------+ +-------+ +---------------+
B.x != 3
The final plan is:
SELECT * FROM A LEFT JOIN B ON A.x = B.x AND A.x != 3;
---
SELECT
LEFT OUTER HASH JOIN ON (b.x = a.x)
|-SCAN a
|-BUILD
SCAN b
(b.x <> $0)
There are other classic pushdown rules that do not rely on equivalence class transitivity but are still useful to move qualifiers closer to scans.
A filter applied on top of a subquery can be moved into the subquery if it only depends on columns produced by that subquery.
SELECT *
FROM b join (
SELECT id, k, x
FROM a
) s on b.a_id = s.id
WHERE s.k > 10;
---
SELECT
INNER HASH JOIN ON (a.id = b.a_id)
|-SCAN b
|-BUILD
SCAN a
(a.k > $0)
A filter above an aggregate can be pushed below GROUP BY only if it depends solely on grouping columns and not on aggregate results.
SELECT *
FROM (SELECT grp, count(*) AS cnt
FROM a
GROUP BY grp) g
WHERE g.grp IN (1, 2, 3);
---
SELECT
GROUP BY (a.grp)
GROUP BY PARTIAL (a.grp)
SCAN a
((a.grp = $3) OR ((a.grp = $1) OR (a.grp = $2)))
A HAVING clause can be pushed into WHERE when the pushed part references only grouping columns and contains no aggregates.
SELECT grp, count(*)
FROM a
GROUP BY grp
HAVING grp IN (1, 2, 3);
---
SELECT
GROUP BY (a.grp)
GROUP BY PARTIAL (a.grp)
SCAN a
((a.grp = $3) OR ((a.grp = $1) OR (a.grp = $2)))
A filter above a set operation can be pushed into the set-operation inputs.
SELECT *
FROM (SELECT id, k
FROM a
UNION ALL
SELECT id, k
FROM b) u
WHERE u.k > 7;
----
SELECT
APPEND
|-SCAN a
| (a.k > $0)
|-SCAN b
(b.k > $2)
SELECT *
FROM (SELECT id, k
FROM a
UNION
SELECT id, k
FROM b) u
WHERE u.k > 7;
----
SELECT
GROUP BY (union.[8], union.[9])
APPEND
|-SCAN a
| (a.k > $0)
|-SCAN b
(b.k > $2)
SELECT *
FROM (SELECT id, k
FROM a
INTERSECT
SELECT id, k
FROM b) u
WHERE u.k = 7;
----
SELECT
INTERSECT
|-SCAN a
| (a.k = $1)
|-SCAN b
(b.k = $4)
A smart planner will detect trivially false predicates and prune union arms automatically:
SELECT *
FROM (SELECT id, status
FROM a
WHERE status = 'active'
UNION ALL
SELECT id, status
FROM b
WHERE status = 'inactive') u
WHERE u.status = 'active';
----
SELECT
SCAN a
a.status = $0 AND scan_constraints: (a.status = $0)
Each of these predicate manipulations, equivalence class distributions, and various SQL-structure pushdown rules is useful on its own, but they become really powerful when combined and used in conjunction with other optimization tricks:
A.x = 1 and A.x = 3, in an equivalence class.One exception to the pushdown rule is expensive functions (complex date or string manipulations like TO_NUMBER). Predicate pushdown is a tradeoff between row skipping and the CPU cost of the added operation. If a predicate is very CPU-intensive, it might be worth avoiding duplication.
Good predicate handling in a planner can make or break some queries. This is a domain where the capabilities of different planners can differ greatly.
For simple or performance-sensitive queries, users can manually tweak the query and add extra qualifiers if they understand the correctness rules. I hope this blog post helps.
In a future blog post, I'll explain how we can filter scans even more by taking advantage of runtime knowledge, Bloom filters, and min-max filters.