You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@datafusion.apache.org by gi...@apache.org on 2026/09/27 16:29:13 UTC

(datafusion) branch main updated: fix: keep a correlated filter below the nullable side of an outer join (#25764)

This is an automated email from the ASF dual-hosted git repository.

github-merge-queue[bot] pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datafusion.git


The following commit(s) were added to refs/heads/main by this push:
     new 871058cd73 fix: keep a correlated filter below the nullable side of an outer join (#25764)
871058cd73 is described below

commit 871058cd7302ef8fa746e52329992408bc9c6c7e
Author: Kita Renji <73...@users.noreply.github.com>
AuthorDate: Sun Sep 27 16:20:19 2026 +0000

    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 <wh...@gmail.com>
    Co-authored-by: Claude Opus 5.5 <no...@anthropic.com>
    Co-authored-by: Adrian Garcia Badaracco <17...@users.noreply.github.com>
---
 datafusion/optimizer/src/decorrelate.rs            |  43 +++++
 datafusion/optimizer/src/push_down_filter.rs       |   8 +-
 .../sqllogictest/test_files/lateral_join.slt       |  14 ++
 datafusion/sqllogictest/test_files/subquery.slt    | 174 +++++++++++++++++++++
 4 files changed, 237 insertions(+), 2 deletions(-)

diff --git a/datafusion/optimizer/src/decorrelate.rs b/datafusion/optimizer/src/decorrelate.rs
index a288ded88b..4f89532e50 100644
--- a/datafusion/optimizer/src/decorrelate.rs
+++ b/datafusion/optimizer/src/decorrelate.rs
@@ -20,6 +20,7 @@
 use std::collections::BTreeSet;
 use std::sync::Arc;
 
+use crate::push_down_filter::lr_is_preserved;
 use crate::simplify_expressions::ExprSimplifier;
 
 use datafusion_common::tree_node::{
@@ -29,6 +30,7 @@ use datafusion_common::{
     Column, DFSchemaRef, HashMap, Result, ScalarValue, assert_or_internal_err, plan_err,
 };
 use datafusion_expr::expr::{Alias, GroupingSet};
+use datafusion_expr::logical_plan::Join;
 use datafusion_expr::simplify::SimplifyContext;
 use datafusion_expr::utils::{
     collect_subquery_cols, conjunction, find_join_exprs, split_conjunction,
@@ -142,6 +144,17 @@ impl TreeNodeRewriter for PullUpCorrelatedExpr {
             LogicalPlan::Subquery(_) => {
                 Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
             }
+            // A correlated filter can only move above a join from a side whose
+            // rows the join preserves. 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. The side a semi, anti or mark
+            // join does not output cannot give its columns to a pulled up
+            // filter either.
+            LogicalPlan::Join(ref join) if !correlated_inputs_are_preserved(join) => {
+                // the unsupported case
+                self.can_pull_up = false;
+                Ok(Transformed::new(plan, false, TreeNodeRecursion::Jump))
+            }
             LogicalPlan::Union(_) | LogicalPlan::Sort(_) | LogicalPlan::Extension(_) => {
                 let plan_hold_outer = !plan.all_out_ref_exprs().is_empty();
                 if plan_hold_outer {
@@ -535,6 +548,36 @@ impl PullUpCorrelatedExpr {
     }
 }
 
+/// Whether every input of `join` that holds outer references is a side whose
+/// rows the join preserves, so a correlated filter below it can be pulled above
+/// the join without changing the result.
+fn correlated_inputs_are_preserved(join: &Join) -> bool {
+    let (left_preserved, right_preserved) = lr_is_preserved(join.join_type);
+    (left_preserved || !holds_outer_reference(&join.left))
+        && (right_preserved || !holds_outer_reference(&join.right))
+}
+
+/// Whether `plan` or any of its inputs holds an outer reference of the scope
+/// being decorrelated. Like [`PullUpCorrelatedExpr`], this does not descend into
+/// a [`LogicalPlan::Subquery`], whose outer references belong to a nested
+/// scope, such as the right side of a `LATERAL` join that is not decorrelated
+/// yet.
+fn holds_outer_reference(plan: &LogicalPlan) -> bool {
+    let mut found = false;
+    plan.apply(|node| {
+        Ok(match node {
+            LogicalPlan::Subquery(_) => TreeNodeRecursion::Jump,
+            _ if node.contains_outer_reference() => {
+                found = true;
+                TreeNodeRecursion::Stop
+            }
+            _ => TreeNodeRecursion::Continue,
+        })
+    })
+    .expect("apply closure is infallible");
+    found
+}
+
 fn can_pullup_over_aggregation(expr: &Expr) -> bool {
     if let Expr::BinaryExpr(BinaryExpr {
         left,
diff --git a/datafusion/optimizer/src/push_down_filter.rs b/datafusion/optimizer/src/push_down_filter.rs
index be0d4c57bb..d059b2ae7d 100644
--- a/datafusion/optimizer/src/push_down_filter.rs
+++ b/datafusion/optimizer/src/push_down_filter.rs
@@ -173,10 +173,14 @@ pub(crate) fn lr_is_preserved(join_type: JoinType) -> (bool, bool) {
         JoinType::Right => (false, true),
         JoinType::Full => (false, false),
         // No columns from the right side of the join can be referenced in output
-        // predicates for semi/anti joins, so whether we specify t/f doesn't matter.
+        // predicates for semi/anti joins. The right side must stay `false`:
+        // `PullUpCorrelatedExpr` uses it to refuse to pull a correlated filter
+        // out of a side that the join does not output.
         JoinType::LeftSemi | JoinType::LeftAnti | JoinType::LeftMark => (true, false),
         // No columns from the left side of the join can be referenced in output
-        // predicates for semi/anti joins, so whether we specify t/f doesn't matter.
+        // predicates for semi/anti joins. The left side must stay `false`:
+        // `PullUpCorrelatedExpr` uses it to refuse to pull a correlated filter
+        // out of a side that the join does not output.
         JoinType::RightSemi | JoinType::RightAnti | JoinType::RightMark => (false, true),
     }
 }
diff --git a/datafusion/sqllogictest/test_files/lateral_join.slt b/datafusion/sqllogictest/test_files/lateral_join.slt
index cae3e67153..02d4d9f0ea 100644
--- a/datafusion/sqllogictest/test_files/lateral_join.slt
+++ b/datafusion/sqllogictest/test_files/lateral_join.slt
@@ -739,6 +739,20 @@ FROM t1, LATERAL (
 ) AS sub
 ORDER BY t1.id;
 
+# --- Correlated filter on the nullable side of an outer join ---
+# https://github.com/apache/datafusion/issues/25507
+# Pulling `t2.t1_id = t1.id` above the LEFT JOIN would drop the t3 rows that
+# have no match instead of extending them with NULLs.
+# Expected result once supported: every t3 row for every t1 row (9 rows),
+# with y set only where t2.t1_id = t1.id.
+statement error OuterReferenceColumn
+SELECT t1.id, sub.x, sub.y
+FROM t1, LATERAL (
+    SELECT t3.id AS x, t2.t1_id AS y
+    FROM t3 LEFT JOIN (SELECT * FROM t2 WHERE t2.t1_id = t1.id) AS t2 ON t3.t2_id = t2.id
+) AS sub
+ORDER BY t1.id, sub.x;
+
 # --- Implicit LATERAL (comma without LATERAL keyword) ---
 # DuckDB auto-detects lateral correlation; DataFusion requires
 # the explicit LATERAL keyword.
diff --git a/datafusion/sqllogictest/test_files/subquery.slt b/datafusion/sqllogictest/test_files/subquery.slt
index f383f66176..d27c244e0d 100644
--- a/datafusion/sqllogictest/test_files/subquery.slt
+++ b/datafusion/sqllogictest/test_files/subquery.slt
@@ -2848,3 +2848,177 @@ DROP TABLE gs_outer;
 
 statement ok
 DROP TABLE gs_inner;
+
+# Regression test for #25507: a correlated filter below the side of an outer
+# join that the join fills with NULLs must not be pulled above the join. The
+# filter decides which rows of the other side are unmatched, so once it is
+# above the join the rows that get NULLs are different.
+statement ok
+CREATE TABLE oj_outer(k INT) AS VALUES (1), (5);
+
+statement ok
+CREATE TABLE oj_a(id INT) AS VALUES (1), (2);
+
+statement ok
+CREATE TABLE oj_b(id INT, y INT) AS VALUES (1, 1), (2, 2);
+
+statement ok
+set datafusion.explain.logical_plan_only = true;
+
+# The correlated filter is on the right side of a LEFT JOIN, so the subquery
+# stays correlated.
+query TT
+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;
+----
+logical_plan
+01)Projection: oj_outer.k, EXISTS (<subquery>) AS e
+02)--Subquery:
+03)----Projection: Int64(1)
+04)------Filter: b.y IS NULL
+05)--------Left Join: oj_a.id = b.id
+06)----------TableScan: oj_a
+07)----------SubqueryAlias: b
+08)------------Projection: oj_b.id, oj_b.y
+09)--------------Filter: oj_b.y = outer_ref(oj_outer.k)
+10)----------------TableScan: oj_b
+11)--TableScan: oj_outer projection=[k]
+
+# It errors rather than returning wrong results. The right answer is
+# `(1, true), (5, true)`.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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;
+
+# The same for IN. The right answer is `(1, true), (5, NULL)`.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression InSubquery
+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;
+
+# And for EXISTS and NOT EXISTS in WHERE. `oj_a` is never empty, so the right
+# answers are every row and no row.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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);
+
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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);
+
+# And for a scalar subquery. The right answer is `(1, 1), (5, 2)`.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression ScalarSubquery
+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;
+
+# The left side of a RIGHT JOIN, and either side of a FULL JOIN.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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;
+
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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;
+
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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;
+
+# The filter can sit deeper below the nullable side, here under an inner join.
+statement error DataFusion error: This feature is not implemented: Physical plan does not support logical expression Exists
+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;
+
+# A correlated filter on the preserved side of a LEFT JOIN is still pulled up.
+query TT
+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;
+----
+logical_plan
+01)Projection: oj_outer.k, __correlated_sq_1.mark AS e
+02)--LeftMark Join: oj_outer.k = __correlated_sq_1.id
+03)----TableScan: oj_outer projection=[k]
+04)----SubqueryAlias: __correlated_sq_1
+05)------Projection: a.id
+06)--------Filter: oj_b.y IS NULL
+07)----------Projection: a.id, oj_b.y
+08)------------Left Join: a.id = oj_b.id
+09)--------------SubqueryAlias: a
+10)----------------TableScan: oj_a projection=[id]
+11)--------------TableScan: oj_b projection=[id, y]
+
+query IB
+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;
+----
+1 true
+5 false
+
+# So is one on the preserved side of a RIGHT JOIN.
+query IB
+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;
+----
+1 true
+5 false
+
+# And one on either side of an inner join.
+query TT
+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;
+----
+logical_plan
+01)Projection: oj_outer.k, __correlated_sq_1.mark AS e
+02)--LeftMark Join: oj_outer.k = __correlated_sq_1.y
+03)----TableScan: oj_outer projection=[k]
+04)----SubqueryAlias: __correlated_sq_1
+05)------Projection: b.y
+06)--------RightSemi Join: oj_a.id = b.id
+07)----------TableScan: oj_a projection=[id]
+08)----------SubqueryAlias: b
+09)------------TableScan: oj_b projection=[id, y]
+
+query IB
+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;
+----
+1 true
+5 false
+
+# A correlated filter above the outer join is pulled up as before, even when it
+# reads a column of the nullable side.
+query TT
+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);
+----
+logical_plan
+01)LeftSemi Join: oj_outer.k = __correlated_sq_1.y
+02)--TableScan: oj_outer projection=[k]
+03)--SubqueryAlias: __correlated_sq_1
+04)----Projection: oj_b.y
+05)------Left Join: oj_a.id = oj_b.id
+06)--------TableScan: oj_a projection=[id]
+07)--------TableScan: oj_b projection=[id, y]
+
+query I
+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;
+----
+1
+
+# A null-rejecting filter above the outer join makes it an inner join, so the
+# subquery is still decorrelated (in a later optimizer pass).
+query TT
+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;
+----
+logical_plan
+01)Projection: oj_outer.k, __correlated_sq_2.mark AS e
+02)--LeftMark Join: oj_outer.k = __correlated_sq_2.y
+03)----TableScan: oj_outer projection=[k]
+04)----SubqueryAlias: __correlated_sq_2
+05)------Projection: b.y
+06)--------RightSemi Join: oj_a.id = b.id
+07)----------TableScan: oj_a projection=[id]
+08)----------SubqueryAlias: b
+09)------------Filter: oj_b.y > Int32(0)
+10)--------------TableScan: oj_b projection=[id, y]
+
+query IB
+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;
+----
+1 true
+5 false
+
+statement ok
+RESET datafusion.explain.logical_plan_only;
+
+statement ok
+DROP TABLE oj_outer;
+
+statement ok
+DROP TABLE oj_a;
+
+statement ok
+DROP TABLE oj_b;


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@datafusion.apache.org
For additional commands, e-mail: commits-help@datafusion.apache.org