Skip to content

Commit 871058c

Browse files
kita-renjitsuru-kenmaclaudeadriangb
authored
fix: keep a correlated filter below the nullable side of an outer join (#25764)
## Which issue does this PR close? - Closes #25507. ## Rationale for this change `PullUpCorrelatedExpr` pulls a correlated `Filter` up through any `Join`. That is fine for an inner join and for the preserved side of an outer join, but below the side an outer join fills with NULLs the filter decides which rows are unmatched, so pulling it above the join changes the result. With the tables from the issue, `EXISTS (SELECT 1 FROM a LEFT JOIN (SELECT * FROM b WHERE b.y = o.k) AS b ON a.id = b.id WHERE b.y IS NULL)` returns `false` for both rows instead of `true`, and the `IN` form returns `false` instead of `NULL` for `o.k = 5`. The same happens for `WHERE [NOT] EXISTS`, scalar subqueries, the left side of a `RIGHT JOIN`, either side of a `FULL JOIN`, a filter nested under an inner join on the nullable side, and `LATERAL` subqueries (a `t1, LATERAL (... t3 LEFT JOIN (... WHERE t2.t1_id = t1.id) ...)` query returns 3 rows instead of 9). ## What changes are included in this PR? `PullUpCorrelatedExpr::f_down` now has an arm for `LogicalPlan::Join`: if an input the join does not preserve holds outer references, the subquery is marked as not pull-up-able, the same way it already is for a `Union` or `Sort` with outer references. Which sides are preserved comes from `lr_is_preserved` in `push_down_filter.rs`, which filter pushdown uses to decide whether a filter above a join can move into one side. That is the same question asked the other way around. The non-output side of a semi, anti or mark join counts as not preserved. The check stops at `LogicalPlan::Subquery` nodes, since their outer references belong to a nested scope (for example the right side of a nested `LATERAL` that is decorrelated separately). `f_down` already treats `Subquery` as a scope boundary. Such subqueries now stay correlated and fail with a not-implemented error instead of returning wrong results. Correlated filters on a preserved side, on either side of an inner join, or above the outer join are still pulled up as before. This is independent of #25284, which adds an `unsupported()` helper for the same pattern. I kept the diff away from the lines it touches so both merge cleanly (I checked the merge locally); whichever lands second can switch the new arm to `self.unsupported(plan)`. ## Are these changes tested? Yes, new sqllogictest cases in `subquery.slt` and `lateral_join.slt`: - EXPLAIN showing the subquery from the issue stays correlated. - `EXISTS` / `IN` in a projection, `WHERE EXISTS`, `WHERE NOT EXISTS`, a scalar subquery, `RIGHT JOIN`, `FULL JOIN` (both sides), a filter nested under an inner join on the nullable side, and a `LATERAL` subquery now error instead of returning wrong results. All of these fail without the fix. - A correlated filter on the preserved side of `LEFT` and `RIGHT` joins, on the nullable side of an inner join, and above a `LEFT JOIN` is still decorrelated and returns the right rows (checked against DuckDB). The whole sqllogictest suite passes with no changes to existing plans. ## Are there any user-facing changes? Queries with a correlated filter below the nullable side of an outer join inside a subquery now fail with a not-implemented error instead of silently returning wrong results. Supporting them properly needs a different decorrelation strategy. I can open a follow-up issue for that. 🤖 Generated with [Claude Code](https://claude.com/claude-code) --------- Co-authored-by: Panchawat <[email protected]> Co-authored-by: Claude Opus 5.5 <[email protected]> Co-authored-by: Adrian Garcia Badaracco <[email protected]>
1 parent 266b827 commit 871058c

4 files changed

Lines changed: 237 additions & 2 deletions

File tree

‎datafusion/optimizer/src/decorrelate.rs‎

Lines changed: 43 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -20,6 +20,7 @@
2020
use std::collections::BTreeSet;
2121
use std::sync::Arc;
2222

23+
use crate::push_down_filter::lr_is_preserved;
2324
use crate::simplify_expressions::ExprSimplifier;
2425

2526
use datafusion_common::tree_node::{
@@ -29,6 +30,7 @@ use datafusion_common::{
2930
Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
3031
};
3132
use datafusion_expr::expr::{Alias, GroupingSet};
33+
use datafusion_expr::logical_plan::Join;
3234
use datafusion_expr::simplify::SimplifyContext;
3335
use datafusion_expr::utils::{
3436
collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
@@ -142,6 +144,17 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
142144
LogicalPlan::Subquery(_) => {
143145
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
144146
}
147+
// A correlated filter can only move above a join from a side whose
148+
// rows the join preserves. Below the side an outer join fills with
149+
// NULLs, the filter decides which rows are unmatched, so pulling it
150+
// above the join changes the result. The side a semi, anti or mark
151+
// join does not output cannot give its columns to a pulled up
152+
// filter either.
153+
LogicalPlan::Join(ref join) if !correlated_inputs_are_preserved(join) => {
154+
// the unsupported case
155+
self.can_pull_up = false;
156+
Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
157+
}
145158
LogicalPlan::Union(_) | LogicalPlan::Sort(_) | LogicalPlan::Extension(_) => {
146159
let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
147160
if plan_hold_outer {
@@ -535,6 +548,36 @@ impl PullUpCorrelatedExpr {
535548
}
536549
}
537550

551+
/// Whether every input of `join` that holds outer references is a side whose
552+
/// rows the join preserves, so a correlated filter below it can be pulled above
553+
/// the join without changing the result.
554+
fn correlated_inputs_are_preserved(join: &Join) -> bool {
555+
let (left_preserved, right_preserved) = lr_is_preserved(join.join_type);
556+
(left_preserved || !holds_outer_reference(&join.left))
557+
&& (right_preserved || !holds_outer_reference(&join.right))
558+
}
559+
560+
/// Whether `plan` or any of its inputs holds an outer reference of the scope
561+
/// being decorrelated. Like [`PullUpCorrelatedExpr`], this does not descend into
562+
/// a [`LogicalPlan::Subquery`], whose outer references belong to a nested
563+
/// scope, such as the right side of a `LATERAL` join that is not decorrelated
564+
/// yet.
565+
fn holds_outer_reference(plan: &LogicalPlan) -> bool {
566+
let mut found = false;
567+
plan.apply(|node| {
568+
Ok(match node {
569+
LogicalPlan::Subquery(_) => TreeNodeRecursion::Jump,
570+
_ if node.contains_outer_reference() => {
571+
found = true;
572+
TreeNodeRecursion::Stop
573+
}
574+
_ => TreeNodeRecursion::Continue,
575+
})
576+
})
577+
.expect("apply closure is infallible");
578+
found
579+
}
580+
538581
fn can_pullup_over_aggregation(expr: &Expr) -> bool {
539582
if let Expr::BinaryExpr(BinaryExpr {
540583
left,

‎datafusion/optimizer/src/push_down_filter.rs‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -173,10 +173,14 @@ pub(crate) fn lr_is_preserved(join_type: JoinType) -> (bool, bool) {
173173
JoinType::Right => (false, true),
174174
JoinType::Full => (false, false),
175175
// No columns from the right side of the join can be referenced in output
176-
// predicates for semi/anti joins, so whether we specify t/f doesn't matter.
176+
// predicates for semi/anti joins. The right side must stay `false`:
177+
// `PullUpCorrelatedExpr` uses it to refuse to pull a correlated filter
178+
// out of a side that the join does not output.
177179
JoinType::LeftSemi | JoinType::LeftAnti | JoinType::LeftMark => (true, false),
178180
// No columns from the left side of the join can be referenced in output
179-
// predicates for semi/anti joins, so whether we specify t/f doesn't matter.
181+
// predicates for semi/anti joins. The left side must stay `false`:
182+
// `PullUpCorrelatedExpr` uses it to refuse to pull a correlated filter
183+
// out of a side that the join does not output.
180184
JoinType::RightSemi | JoinType::RightAnti | JoinType::RightMark => (false, true),
181185
}
182186
}

‎datafusion/sqllogictest/test_files/lateral_join.slt‎

Lines changed: 14 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -739,6 +739,20 @@ FROM t1, LATERAL (
739739
) AS sub
740740
ORDER BY t1.id;
741741

742+
# --- Correlated filter on the nullable side of an outer join ---
743+
# https://github.com/apache/datafusion/issues/25507
744+
# Pulling `t2.t1_id = t1.id` above the LEFT JOIN would drop the t3 rows that
745+
# have no match instead of extending them with NULLs.
746+
# Expected result once supported: every t3 row for every t1 row (9 rows),
747+
# with y set only where t2.t1_id = t1.id.
748+
statement error OuterReferenceColumn
749+
SELECT t1.id, sub.x, sub.y
750+
FROM t1, LATERAL (
751+
SELECT t3.id AS x, t2.t1_id AS y
752+
FROM t3 LEFT JOIN (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2 ON t3.t2_id = t2.id
753+
) AS sub
754+
ORDER BY t1.id, sub.x;
755+
742756
# --- Implicit LATERAL (comma without LATERAL keyword) ---
743757
# DuckDB auto-detects lateral correlation; DataFusion requires
744758
# the explicit LATERAL keyword.

‎datafusion/sqllogictest/test_files/subquery.slt‎

Lines changed: 174 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -2848,3 +2848,177 @@ DROP TABLE gs_outer;
28482848

28492849
statement ok
28502850
DROP TABLE gs_inner;
2851+
2852+
# Regression test for #25507: a correlated filter below the side of an outer
2853+
# join that the join fills with NULLs must not be pulled above the join. The
2854+
# filter decides which rows of the other side are unmatched, so once it is
2855+
# above the join the rows that get NULLs are different.
2856+
statement ok
2857+
CREATE TABLE oj_outer(k INT) AS VALUES (1), (5);
2858+
2859+
statement ok
2860+
CREATE TABLE oj_a(id INT) AS VALUES (1), (2);
2861+
2862+
statement ok
2863+
CREATE TABLE oj_b(id INT, y INT) AS VALUES (1, 1), (2, 2);
2864+
2865+
statement ok
2866+
set datafusion.explain.logical_plan_only = true;
2867+
2868+
# The correlated filter is on the right side of a LEFT JOIN, so the subquery
2869+
# stays correlated.
2870+
query TT
2871+
EXPLAIN SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2872+
----
2873+
logical_plan
2874+
01)Projection: oj_outer.k, EXISTS (<subquery>) AS e
2875+
02)--Subquery:
2876+
03)----Projection: Int64(1)
2877+
04)------Filter: b.y IS NULL
2878+
05)--------Left Join: oj_a.id = b.id
2879+
06)----------TableScan: oj_a
2880+
07)----------SubqueryAlias: b
2881+
08)------------Projection: oj_b.id, oj_b.y
2882+
09)--------------Filter: oj_b.y = outer_ref(oj_outer.k)
2883+
10)----------------TableScan: oj_b
2884+
11)--TableScan: oj_outer projection=[k]
2885+
2886+
# It errors rather than returning wrong results. The right answer is
2887+
# `(1, true), (5, true)`.
2888+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2889+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2890+
2891+
# The same for IN. The right answer is `(1, true), (5, NULL)`.
2892+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression InSubquery
2893+
SELECT oj_outer.k, oj_outer.k IN (SELECT b.y FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id) AS m FROM oj_outer;
2894+
2895+
# And for EXISTS and NOT EXISTS in WHERE. `oj_a` is never empty, so the right
2896+
# answers are every row and no row.
2897+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2898+
SELECT oj_outer.k FROM oj_outer WHERE EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id);
2899+
2900+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2901+
SELECT oj_outer.k FROM oj_outer WHERE NOT EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id);
2902+
2903+
# And for a scalar subquery. The right answer is `(1, 1), (5, 2)`.
2904+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression ScalarSubquery
2905+
SELECT oj_outer.k, (SELECT count(*) FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y IS NULL) AS c FROM oj_outer;
2906+
2907+
# The left side of a RIGHT JOIN, and either side of a FULL JOIN.
2908+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2909+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b RIGHT JOIN oj_a ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2910+
2911+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2912+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b FULL JOIN oj_a ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2913+
2914+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2915+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a FULL JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2916+
2917+
# The filter can sit deeper below the nullable side, here under an inner join.
2918+
statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
2919+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT oj_b.id, oj_b.y FROM oj_b JOIN oj_a AS a2 ON oj_b.id = a2.id WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y IS NULL) AS e FROM oj_outer;
2920+
2921+
# A correlated filter on the preserved side of a LEFT JOIN is still pulled up.
2922+
query TT
2923+
EXPLAIN SELECT oj_outer.k, EXISTS (SELECT 1 FROM (SELECT * FROM oj_a WHERE oj_a.id = oj_outer.k) AS a LEFT JOIN oj_b ON a.id = oj_b.id WHERE oj_b.y IS NULL) AS e FROM oj_outer;
2924+
----
2925+
logical_plan
2926+
01)Projection: oj_outer.k, __correlated_sq_1.mark AS e
2927+
02)--LeftMark Join: oj_outer.k = __correlated_sq_1.id
2928+
03)----TableScan: oj_outer projection=[k]
2929+
04)----SubqueryAlias: __correlated_sq_1
2930+
05)------Projection: a.id
2931+
06)--------Filter: oj_b.y IS NULL
2932+
07)----------Projection: a.id, oj_b.y
2933+
08)------------Left Join: a.id = oj_b.id
2934+
09)--------------SubqueryAlias: a
2935+
10)----------------TableScan: oj_a projection=[id]
2936+
11)--------------TableScan: oj_b projection=[id, y]
2937+
2938+
query IB
2939+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM (SELECT * FROM oj_a WHERE oj_a.id = oj_outer.k) AS a LEFT JOIN oj_b ON a.id = oj_b.id) AS e FROM oj_outer ORDER BY oj_outer.k;
2940+
----
2941+
1 true
2942+
5 false
2943+
2944+
# So is one on the preserved side of a RIGHT JOIN.
2945+
query IB
2946+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_b RIGHT JOIN (SELECT * FROM oj_a WHERE oj_a.id = oj_outer.k) AS a ON a.id = oj_b.id) AS e FROM oj_outer ORDER BY oj_outer.k;
2947+
----
2948+
1 true
2949+
5 false
2950+
2951+
# And one on either side of an inner join.
2952+
query TT
2953+
EXPLAIN SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id) AS e FROM oj_outer;
2954+
----
2955+
logical_plan
2956+
01)Projection: oj_outer.k, __correlated_sq_1.mark AS e
2957+
02)--LeftMark Join: oj_outer.k = __correlated_sq_1.y
2958+
03)----TableScan: oj_outer projection=[k]
2959+
04)----SubqueryAlias: __correlated_sq_1
2960+
05)------Projection: b.y
2961+
06)--------RightSemi Join: oj_a.id = b.id
2962+
07)----------TableScan: oj_a projection=[id]
2963+
08)----------SubqueryAlias: b
2964+
09)------------TableScan: oj_b projection=[id, y]
2965+
2966+
query IB
2967+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id) AS e FROM oj_outer ORDER BY oj_outer.k;
2968+
----
2969+
1 true
2970+
5 false
2971+
2972+
# A correlated filter above the outer join is pulled up as before, even when it
2973+
# reads a column of the nullable side.
2974+
query TT
2975+
EXPLAIN SELECT oj_outer.k FROM oj_outer WHERE EXISTS (SELECT 1 FROM oj_a LEFT JOIN oj_b ON oj_a.id = oj_b.id WHERE oj_b.y = oj_outer.k);
2976+
----
2977+
logical_plan
2978+
01)LeftSemi Join: oj_outer.k = __correlated_sq_1.y
2979+
02)--TableScan: oj_outer projection=[k]
2980+
03)--SubqueryAlias: __correlated_sq_1
2981+
04)----Projection: oj_b.y
2982+
05)------Left Join: oj_a.id = oj_b.id
2983+
06)--------TableScan: oj_a projection=[id]
2984+
07)--------TableScan: oj_b projection=[id, y]
2985+
2986+
query I
2987+
SELECT oj_outer.k FROM oj_outer WHERE EXISTS (SELECT 1 FROM oj_a LEFT JOIN oj_b ON oj_a.id = oj_b.id WHERE oj_b.y = oj_outer.k) ORDER BY oj_outer.k;
2988+
----
2989+
1
2990+
2991+
# A null-rejecting filter above the outer join makes it an inner join, so the
2992+
# subquery is still decorrelated (in a later optimizer pass).
2993+
query TT
2994+
EXPLAIN SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y > 0) AS e FROM oj_outer;
2995+
----
2996+
logical_plan
2997+
01)Projection: oj_outer.k, __correlated_sq_2.mark AS e
2998+
02)--LeftMark Join: oj_outer.k = __correlated_sq_2.y
2999+
03)----TableScan: oj_outer projection=[k]
3000+
04)----SubqueryAlias: __correlated_sq_2
3001+
05)------Projection: b.y
3002+
06)--------RightSemi Join: oj_a.id = b.id
3003+
07)----------TableScan: oj_a projection=[id]
3004+
08)----------SubqueryAlias: b
3005+
09)------------Filter: oj_b.y > Int32(0)
3006+
10)--------------TableScan: oj_b projection=[id, y]
3007+
3008+
query IB
3009+
SELECT oj_outer.k, EXISTS (SELECT 1 FROM oj_a LEFT JOIN (SELECT * FROM oj_b WHERE oj_b.y = oj_outer.k) AS b ON oj_a.id = b.id WHERE b.y > 0) AS e FROM oj_outer ORDER BY oj_outer.k;
3010+
----
3011+
1 true
3012+
5 false
3013+
3014+
statement ok
3015+
RESET datafusion.explain.logical_plan_only;
3016+
3017+
statement ok
3018+
DROP TABLE oj_outer;
3019+
3020+
statement ok
3021+
DROP TABLE oj_a;
3022+
3023+
statement ok
3024+
DROP TABLE oj_b;

0 commit comments

Comments
 (0)