You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
Commit 871058c
Browse filesBrowse the repository at this point in the historyBrowse files
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]>
Copy file name to clipboardExpand all lines: datafusion/sqllogictest/test_files/subquery.slt
+174Lines changed: 174 additions & 0 deletions
Original file line number
Diff line number
Diff line change
@@ -2848,3 +2848,177 @@ DROP TABLE gs_outer;
2848
2848
2849
2849
statement ok
2850
2850
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
# 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
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
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);
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
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;
0 commit comments