This is an automated email from the ASF dual-hosted git repository. github-merge-queue[bot] pushed a commit to branch gh-readonly-queue/main/pr-25558-708617a99400e32f6f32161f8e967ef51ab76733 in repository https://gitbox.apache.org/repos/asf/datafusion.git
commit 31a4ca07fe1f874a5dec3dc79f4e53b8107a5a20 Author: Adrian Garcia Badaracco <[email protected]> AuthorDate: Mon Sep 21 14:08:35 2026 +0000 test: characterize correlated `NOT IN` null-aware behaviour (#25558) ## Which issue does this PR close? - Part of https://github.com/apache/datafusion/issues/25336. Closes nothing on its own. ## Rationale for this change Correlated `NOT IN` returns wrong results in several shapes, and a few do not plan at all. The fixes span two layers — the hash join executor and decorrelation — and touch different shapes. Landing the coverage first, pinned to what DataFusion does today, makes each fix's diff show exactly which behaviour it changes instead of burying the flips in a large change. Nothing here changes behaviour. Every expectation is what `main` produces right now, and the wrong ones carry a note and a link to the issue. Concretely, this is wrong today (DuckDB 1.5.2 and PostgreSQL 17.11 both return three rows): ```sql CREATE TABLE oc(id INT, g INT) AS VALUES (1,5),(2,5),(3,0),(4,NULL),(NULL,5),(NULL,0); CREATE TABLE ic(id INT) AS VALUES (1),(NULL); SELECT id, g FROM oc WHERE oc.id NOT IN (SELECT ic.id FROM ic WHERE oc.g > 0); -- returns no rows ``` ## What changes are included in this PR? sqllogictest, in `null_aware_anti_join.slt` and `null_aware_mark_join.slt`: - correlated `NOT IN` with a non-equality correlation, which stays a residual join filter; - a correlation naming only outer columns, so it cannot become an equi-join key; - a constant value expression, with and without a correlation; - a subquery inside the `IN` value, both spellings of the outer `IN`; - `IS NOT NULL` over a subquery predicate, and a comparison between two marks — the contexts that can tell a NULL mark from a FALSE mark; - plan pins for the join the planner picks in each case. Benchmarks: - **Q09**, a correlated non-negated `IN`. It must *not* use a null-aware join. Q01–Q08 all cover the direction where null-awareness is required, so a regression that adds it where it is not needed is invisible to them. Q09 passes today. - correctness canaries on Q05–Q08, each comparing the `NOT IN` result against a reference that does not use `NOT IN`. All four disagree today, so they are pinned to `false`. ## What is the testing strategy for this PR? This PR is tests. Expected results were verified against DuckDB 1.5.2 and PostgreSQL 17.11. The whole suite is green on `main`, including all nine benchmarks. ## Are there any user-facing changes? No. 🤖 Generated with [Claude Code](https://claude.com/claude-code) Co-authored-by: Adrian Garcia Badaracco <[email protected]> Co-authored-by: Claude Opus 5 <[email protected]> --- .../null_aware_join/benchmarks/q05.benchmark | 16 + .../null_aware_join/benchmarks/q06.benchmark | 16 + .../null_aware_join/benchmarks/q07.benchmark | 18 + .../null_aware_join/benchmarks/q08.benchmark | 24 ++ .../null_aware_join/benchmarks/q09.benchmark | 45 +++ .../null_aware_join/null_aware_join.suite | 4 +- .../test_files/null_aware_anti_join.slt | 273 ++++++++++++++- .../test_files/null_aware_mark_join.slt | 376 +++++++++++++++++++++ datafusion/sqllogictest/test_files/subquery.slt | 4 + 9 files changed, 763 insertions(+), 13 deletions(-) diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark index b50bbe1e73..bde1f3e565 100644 --- a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark +++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q05.benchmark @@ -3,6 +3,22 @@ group null_aware_join load sql_benchmarks/null_aware_join/init/load.sql +# Correctness canary: the NOT IN result must match a reference count +# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS. +# As Q04, with NULL outer keys excluded unless the subquery is empty. +assert I +SELECT count(*) = ( + SELECT count(*) FROM small_outer o + WHERE o.z <= (SELECT min(z) FROM small_inner) + OR (o.id_n1 IS NOT NULL AND NOT (o.id % 2 = 0 AND (o.id / 2) % 1000 < o.z)) +) +FROM small_outer o +WHERE o.id_n1 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z); +---- +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +false + expect_plan HashJoinExec expect_plan null_aware diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark index 004f2cf628..25929198e7 100644 --- a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark +++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q06.benchmark @@ -3,6 +3,22 @@ group null_aware_join load sql_benchmarks/null_aware_join/init/load.sql +# Correctness canary: the NOT IN result must match a reference count +# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS. +# As Q04, with NULL outer keys excluded unless the subquery is empty. +assert I +SELECT count(*) = ( + SELECT count(*) FROM small_outer o + WHERE o.z <= (SELECT min(z) FROM small_inner) + OR (o.id_n50 IS NOT NULL AND NOT (o.id % 2 = 0 AND (o.id / 2) % 1000 < o.z)) +) +FROM small_outer o +WHERE o.id_n50 NOT IN (SELECT i.id_n0 FROM small_inner i WHERE i.z < o.z); +---- +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +false + expect_plan HashJoinExec expect_plan null_aware diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark index d1aec98aa3..3364be5513 100644 --- a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark +++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q07.benchmark @@ -3,6 +3,24 @@ group null_aware_join load sql_benchmarks/null_aware_join/init/load.sql +# Correctness canary: the NOT IN result must match a reference count +# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS. +# A row is TRUE when the subquery is empty, or when the subquery holds no NULL +# and the key is not in it. A NULL is in scope when its z is below o.z. +assert I +SELECT count(*) = ( + SELECT count(*) FROM small_outer o + WHERE o.z <= (SELECT min(z) FROM small_inner) + OR (o.z <= (SELECT min(z) FROM small_inner WHERE id_n50 IS NULL) + AND NOT (o.id % 2 = 0 AND (o.id / 2) % 1000 < o.z)) +) +FROM small_outer o +WHERE o.id_n0 NOT IN (SELECT i.id_n50 FROM small_inner i WHERE i.z < o.z); +---- +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +false + expect_plan HashJoinExec expect_plan null_aware diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark index 39d4fbd4ce..139c5b2a44 100644 --- a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark +++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q08.benchmark @@ -3,6 +3,30 @@ group null_aware_join load sql_benchmarks/null_aware_join/init/load.sql +# Correctness canary: the NOT IN result must match a reference count +# that does not use NOT IN. It holds for every NAJ_ROWS / NAJ_LARGE_ROWS. +# A row is TRUE when o.z > 900, when the subquery for its k is empty, or when +# its key is not NULL and not in that subquery. +assert I +SELECT count(*) = ( + SELECT count(*) + FROM small_outer o + JOIN (SELECT k, min(z) AS min_z FROM small_inner GROUP BY k) m ON m.k = o.k + WHERE o.z > 900 + OR o.z <= m.min_z + OR (o.id_n50 IS NOT NULL + AND NOT (o.id % 2 = 0 AND (o.id / 2) % 16 = o.k AND (o.id / 2) % 1000 < o.z)) +) +FROM small_outer o +WHERE o.z > 900 + OR o.id_n50 NOT IN ( + SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z + ); +---- +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +false + expect_plan HashJoinExec run diff --git a/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q09.benchmark b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q09.benchmark new file mode 100644 index 0000000000..add977915c --- /dev/null +++ b/benchmarks/sql_benchmarks/null_aware_join/benchmarks/q09.benchmark @@ -0,0 +1,45 @@ +name Q09 +group null_aware_join + +load sql_benchmarks/null_aware_join/init/load.sql + +# Correctness canary: the positive IN result must match a reference count that +# does not use IN. It holds for every NAJ_ROWS. A row is TRUE when o.z > 900 or +# when some in-scope subquery row equals its key; a NULL mark and a FALSE mark +# keep the same rows here, which is what makes the plain mark join correct. +assert I +SELECT count(*) = ( + SELECT count(*) + FROM small_outer o + WHERE o.z > 900 + OR EXISTS ( + SELECT 1 FROM small_inner i + WHERE i.k = o.k AND i.z < o.z AND i.id_n0 = o.id_n50 + ) +) +FROM small_outer o +WHERE o.z > 900 + OR o.id_n50 IN ( + SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z + ); +---- +true + +expect_plan HashJoinExec + +run +-- Q9: the same correlated shape as Q08, but a NON-negated IN. A Filter keeps a +-- row only when the predicate is TRUE, and AND/OR make TRUE only out of TRUE, +-- so a NULL mark behaves exactly like a FALSE mark and the mark join must NOT +-- be null-aware. Every other query in this suite covers the direction where +-- null-aware handling is required; this one covers the direction where taking +-- it anyway is pure cost. Widening the "needs null-aware" test until this shape +-- is included does not change any result, so only this timing shows it. +SELECT count(*) +FROM small_outer o +WHERE o.z > 900 + OR o.id_n50 IN ( + SELECT i.id_n0 FROM small_inner i WHERE i.k = o.k AND i.z < o.z + ); + +cleanup sql_benchmarks/null_aware_join/init/cleanup.sql diff --git a/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite b/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite index 559363de06..d827c7ed58 100644 --- a/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite +++ b/benchmarks/sql_benchmarks/null_aware_join/null_aware_join.suite @@ -1,4 +1,4 @@ -description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions" +description = "Null-aware (NOT IN) hash join benchmarks: uncorrelated, non-equality-correlated, and equality-correlated NOT IN across NULL fractions, plus the positive IN shape that must not be null-aware" query_pattern = "q{QUERY_ID_PADDED}.benchmark" @@ -8,7 +8,7 @@ short = "r" env = "NAJ_ROWS" default = "10000" values = ["10000", "..."] -help = "Rows per table for the correlated NOT IN queries (Q04-Q08). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value." +help = "Rows per table for the correlated queries (Q04-Q09). These evaluate the join filter over candidate build x probe pairs, so their cost grows with the square of this value." [[options]] name = "large-rows" diff --git a/datafusion/sqllogictest/test_files/null_aware_anti_join.slt b/datafusion/sqllogictest/test_files/null_aware_anti_join.slt index 8023684ac3..4feea136d9 100644 --- a/datafusion/sqllogictest/test_files/null_aware_anti_join.slt +++ b/datafusion/sqllogictest/test_files/null_aware_anti_join.slt @@ -397,11 +397,11 @@ query II rowsort SELECT * FROM test_table WHERE (c1 NOT IN (SELECT c2 FROM test_table)) = true; ---- -# NOTE: The correlated subquery version from issue #10583: -# SELECT * FROM test_table t1 WHERE c1 NOT IN (SELECT c2 FROM test_table t2 WHERE t1.c1 = t2.c1) -# is not yet supported because it creates a multi-column join (correlation + NOT IN condition). -# This is a known limitation - currently only supports single column null-aware anti joins. -# This will be addressed in next Phase (multi-column support). +# The correlated subquery version from issue #10583 creates a multi-column join +# (correlation + NOT IN condition). It is supported now; see the correlated +# sections below. +query error DataFusion error: Error during planning: null_aware LeftAnti joins only support single column join key, got 2 columns +SELECT * FROM test_table t1 WHERE c1 NOT IN (SELECT c2 FROM test_table t2 WHERE t1.c1 = t2.c1); ############# ## Cleanup @@ -641,19 +641,23 @@ ORDER BY 1; statement ok DROP TABLE naconst_clash; -# A constant value expression with a non-equality correlation leaves the -# null-aware join without any equi-join key. Only `HashJoinExec` implements -# null-aware semantics and it needs a key, so the planner reports the gap -# instead of falling back to a nested loop join that ignores the NULLs and -# silently returns wrong results. +# The rewrite also fires for a correlated subquery. The projected value column +# is the first equi-join key, which is the position the null-aware hash join +# reads as the `NOT IN` value key; the correlation follows it. statement ok CREATE TABLE naconst_corr_t1(id INT, g INT) AS VALUES (1, 1), (2, 2); statement ok CREATE TABLE naconst_corr_t2(id INT, g INT) AS VALUES (1, 1), (NULL, 2); +# A non-equality correlation stays in the join filter. Row (1, 1) sees the NULL +# of (NULL, 2), so its `NOT IN` is UNKNOWN; row (2, 2) sees an empty subquery, +# so its `NOT IN` is TRUE. Expected results verified with DuckDB. query error DataFusion error: Error during planning: null_aware LeftAnti join requires equi\-join keys, but the join has none -SELECT id FROM naconst_corr_t1 WHERE 3 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g); +SELECT id FROM naconst_corr_t1 WHERE 3 NOT IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g) ORDER BY id; + +query error DataFusion error: Error during planning: null_aware LeftAnti join requires equi\-join keys, but the join has none +SELECT id FROM naconst_corr_t1 WHERE NOT (3 IN (SELECT id FROM naconst_corr_t2 WHERE naconst_corr_t2.g > naconst_corr_t1.g)) ORDER BY id; statement ok DROP TABLE naconst_corr_t1; @@ -661,8 +665,255 @@ DROP TABLE naconst_corr_t1; statement ok DROP TABLE naconst_corr_t2; +# https://github.com/apache/datafusion/pull/25339#issuecomment-5738402844 +# An equality correlation becomes a second equi-join key. Without the rewrite the +# correlation would take the first key position and the join would apply the +# value-key NULL rules to it. The outer row with a NULL correlation value matches +# no subquery row at all, so its `NOT IN` is TRUE. The three queries cover TRUE, +# FALSE and UNKNOWN. Expected results verified with DuckDB. +statement ok +CREATE TABLE naconst_corr_t3(z INT) AS VALUES (10), (NULL), (7); + +statement ok +CREATE TABLE naconst_corr_t4(id INT, z INT) AS VALUES (NULL, 10), (1, 99), (2, 7); + +query I +SELECT z FROM naconst_corr_t3 WHERE 1 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z = naconst_corr_t3.z) ORDER BY z; +---- +7 +10 + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query I +SELECT z FROM naconst_corr_t3 WHERE 2 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z = naconst_corr_t3.z) ORDER BY z; +---- +10 + +query error DataFusion error: Error during planning: null_aware LeftAnti join requires equi\-join keys, but the join has none +SELECT z FROM naconst_corr_t3 WHERE 1 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z > naconst_corr_t3.z) ORDER BY z; + +# The projected value column must be the FIRST equi-join key: a null-aware hash +# join reads `on[0]` as the `NOT IN` value key and `on[1..]` as correlation +# scope keys, positionally. Giving the correlation that slot returns wrong rows. +query TT +EXPLAIN SELECT z FROM naconst_corr_t3 WHERE 1 NOT IN (SELECT naconst_corr_t4.id FROM naconst_corr_t4 WHERE naconst_corr_t4.z = naconst_corr_t3.z); +---- +logical_plan +01)LeftAnti Join: naconst_corr_t3.z = __correlated_sq_1.z Filter: Int64(1) = __correlated_sq_1.naconst_corr_t4.id null_aware +02)--TableScan: naconst_corr_t3 projection=[z] +03)--SubqueryAlias: __correlated_sq_1 +04)----Projection: CAST(naconst_corr_t4.id AS Int64), naconst_corr_t4.z +05)------TableScan: naconst_corr_t4 projection=[id, z] +physical_plan +01)HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(z@0, z@1)], filter=1 = naconst_corr_t4.id@0, null_aware +02)--DataSourceExec: partitions=1, partition_sizes=[1] +03)--ProjectionExec: expr=[CAST(id@0 AS Int64) as naconst_corr_t4.id, z@1 as z] +04)----DataSourceExec: partitions=1, partition_sizes=[1] + +statement ok +DROP TABLE naconst_corr_t3; + +statement ok +DROP TABLE naconst_corr_t4; + statement ok DROP TABLE naconst_t1; statement ok DROP TABLE naconst_t2; + +## Correlated NOT IN with a non-equality correlation +## https://github.com/apache/datafusion/issues/25336 +############# + +# The non-equality correlation stays behind as a residual join filter. A NULL +# subquery value only makes NOT IN UNKNOWN for the outer rows where the +# residual keeps that NULL row. Expected results are verified with DuckDB and +# PostgreSQL. + +statement ok +CREATE TABLE nai_res_t1(id INT, z INT) AS VALUES (1,10), (2,20), (NULL,30), (4,40); + +statement ok +CREATE TABLE nai_res_t2(id INT, z INT) AS VALUES (1,5), (NULL,50); + +# The NULL row (z = 50) never passes `t2.z < t1.z`, so it does not affect the result. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query I +SELECT id FROM nai_res_t1 WHERE id NOT IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z < nai_res_t1.z) ORDER BY id; +---- + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query I +SELECT id FROM nai_res_t1 WHERE NOT (id IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z < nai_res_t1.z)) ORDER BY id; +---- + +query I +SELECT id FROM nai_res_t1 WHERE id IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z < nai_res_t1.z) ORDER BY id; +---- +1 + +# Uncorrelated residuals are pushed into the subquery. +query I +SELECT id FROM nai_res_t1 WHERE id NOT IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z < 40) ORDER BY id; +---- +2 +4 + +query I +SELECT id FROM nai_res_t1 WHERE id NOT IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z < 100) ORDER BY id; +---- + +# The NULL row passes `t2.z > t1.z` for every outer row, so every row is UNKNOWN. +query I +SELECT id FROM nai_res_t1 WHERE id NOT IN (SELECT nai_res_t2.id FROM nai_res_t2 WHERE nai_res_t2.z > nai_res_t1.z) ORDER BY id; +---- + +statement ok +CREATE TABLE nai_res_outer(id INT, z INT, g INT) AS VALUES +(1, 10, 1), +(2, 20, 1), +(NULL, 30, 1), +(4, 40, 2), +(NULL, 1, 2), +(5, 1, 3); + +statement ok +CREATE TABLE nai_res_inner(id INT, z INT, g INT) AS VALUES +(1, 5, 1), +(NULL, 50, 1), +(4, 35, 2), +(NULL, 2, 2); + +# Per outer row, the residual decides which inner rows (NULL or not) are in +# the subquery. A NULL outer value is TRUE only when that set is empty. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z); +---- + +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z > nai_res_outer.z); +---- + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z AND i.z > 3); +---- + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id + 0 NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z); +---- + +# The residual references the subquery value itself. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.id + i.z > nai_res_outer.z); +---- + +# Equality and non-equality correlation together. +query error DataFusion error: Error during planning: null_aware LeftAnti joins only support single column join key, got 2 columns +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.g = nai_res_outer.g AND i.z < nai_res_outer.z); + +# Equality correlation only. +query error DataFusion error: Error during planning: null_aware LeftAnti joins only support single column join key, got 2 columns +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.g = nai_res_outer.g); + +# NOT EXISTS uses two-valued logic and must not change. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE NOT EXISTS (SELECT 1 FROM nai_res_inner i WHERE i.id = nai_res_outer.id AND i.z < nai_res_outer.z); +---- +2 20 +5 1 +NULL 1 +NULL 30 + +# Output batches of one row split the unmatched build rows and the candidate +# pairs checked against the residual filter into many chunks. +statement ok +SET datafusion.execution.batch_size = 1; + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z); +---- + +query error DataFusion error: Error during planning: null_aware LeftAnti joins only support single column join key, got 2 columns +SELECT id, z FROM nai_res_outer +WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.g = nai_res_outer.g AND i.z < nai_res_outer.z); + +statement ok +RESET datafusion.execution.batch_size; + +# A correlation that names only outer columns. It cannot become an equi-join +# key, so it stays a residual join filter on a join whose only key is the +# `NOT IN` value. Every other correlated case here names a subquery column on +# one side, so this is the only test of the outer-only shape. +# +# `nai_res_og.g > 0` holds for id 1, 2 and the NULL-id row with g = 5, so only +# those three see the subquery {1, NULL}: id 1 matches and is FALSE, the other +# two are UNKNOWN. Every other row sees an empty subquery, and `NOT IN` over an +# empty set is TRUE even when the outer value is NULL. Expected results +# verified with DuckDB and PostgreSQL. +statement ok +CREATE TABLE nai_res_og(id INT, g INT) AS VALUES (1,5), (2,5), (3,0), (4,NULL), (NULL,5), (NULL,0); + +statement ok +CREATE TABLE nai_res_ig(id INT) AS VALUES (1), (NULL); + +query II +SELECT id, g FROM nai_res_og WHERE nai_res_og.id NOT IN (SELECT i.id FROM nai_res_ig i WHERE nai_res_og.g > 0) ORDER BY id; +---- + +# The shape must stay a single anti join that carries the correlation as a +# filter. The alternative lowering materializes the mark of three joins, which +# is correct but far slower. +query TT +EXPLAIN SELECT id, g FROM nai_res_og WHERE nai_res_og.id NOT IN (SELECT i.id FROM nai_res_ig i WHERE nai_res_og.g > 0); +---- +logical_plan +01)LeftAnti Join: nai_res_og.id = __correlated_sq_1.id Filter: nai_res_og.g > Int32(0) null_aware +02)--TableScan: nai_res_og projection=[id, g] +03)--SubqueryAlias: __correlated_sq_1 +04)----SubqueryAlias: i +05)------TableScan: nai_res_ig projection=[id] +physical_plan +01)HashJoinExec: mode=CollectLeft, join_type=LeftAnti, on=[(id@0, id@0)], filter=g@0 > 0, null_aware +02)--DataSourceExec: partitions=1, partition_sizes=[1] +03)--DataSourceExec: partitions=1, partition_sizes=[1] + +statement ok +DROP TABLE nai_res_og; + +statement ok +DROP TABLE nai_res_ig; + +statement ok +DROP TABLE nai_res_t1; + +statement ok +DROP TABLE nai_res_t2; + +statement ok +DROP TABLE nai_res_outer; + +statement ok +DROP TABLE nai_res_inner; diff --git a/datafusion/sqllogictest/test_files/null_aware_mark_join.slt b/datafusion/sqllogictest/test_files/null_aware_mark_join.slt index dfaa4f23cb..e4e14053c8 100644 --- a/datafusion/sqllogictest/test_files/null_aware_mark_join.slt +++ b/datafusion/sqllogictest/test_files/null_aware_mark_join.slt @@ -637,3 +637,379 @@ DROP TABLE nmconst_t1; statement ok DROP TABLE nmconst_t2; + +########################################################## +## Correlated NOT IN mark join with a non-equality correlation +## https://github.com/apache/datafusion/issues/25336 +########################################################## + +# The non-equality correlation stays behind as a residual join filter, so the +# mark must be NULL (UNKNOWN) only when the residual keeps a NULL on either +# side of the comparison. Expected results are verified with DuckDB. + +statement ok +CREATE TABLE nam_res_outer(id INT, z INT, g INT) AS VALUES +(1, 10, 1), +(2, 20, 1), +(NULL, 30, 1), +(4, 40, 2), +(NULL, 1, 2), +(5, 1, 3); + +statement ok +CREATE TABLE nam_res_inner(id INT, z INT, g INT) AS VALUES +(1, 5, 1), +(NULL, 50, 1), +(4, 35, 2), +(NULL, 2, 2); + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z)) IS NULL; +---- + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z)) IS TRUE; +---- +2 20 +5 1 +NULL 1 +NULL 30 + +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z)) IS FALSE; +---- +1 10 +4 40 + +# `NOT mark` must stay NULL for UNKNOWN rows instead of turning into TRUE. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE NOT (id IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z)) OR id = 4; +---- +2 20 +4 40 +5 1 +NULL 1 +NULL 30 + +# Positive IN goes through the same mark. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id IN (SELECT i.id FROM nam_res_inner i WHERE i.z > nam_res_outer.z)) IS NULL; +---- + +# Equality and non-equality correlation together. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.g = nam_res_outer.g AND i.z < nam_res_outer.z)) IS NULL; +---- + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.g = nam_res_outer.g AND i.z < nam_res_outer.z)) IS TRUE; +---- +2 20 +5 1 +NULL 1 +NULL 30 + +# Equality correlation only (already null-aware; control). +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.g = nam_res_outer.g)) IS NULL; +---- +2 20 +NULL 1 +NULL 30 + +# In a SELECT list, the mark column shows TRUE, FALSE and NULL directly. +query IIB rowsort +SELECT id, z, id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z) +FROM nam_res_outer; +---- +1 10 false +2 20 NULL +4 40 false +5 1 true +NULL 1 true +NULL 30 NULL + +# A non-negated `IN` under `OR` does not need the null-aware join. A `Filter` +# drops the row whether the mark is NULL or FALSE, and the null-aware join costs +# more, because it pins the outer table as the build side and cannot be swapped. +query TT +EXPLAIN SELECT id FROM nam_res_outer o +WHERE o.z > 35 OR o.id IN (SELECT i.id FROM nam_res_inner i WHERE i.z < o.z); +---- +logical_plan +01)Projection: o.id +02)--Filter: o.z > Int32(35) OR __correlated_sq_1.mark +03)----LeftMark Join: o.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < o.z +04)------SubqueryAlias: o +05)--------TableScan: nam_res_outer projection=[id, z] +06)------SubqueryAlias: __correlated_sq_1 +07)--------SubqueryAlias: i +08)----------TableScan: nam_res_inner projection=[id, z] +physical_plan +01)FilterExec: z@1 > 35 OR mark@2, projection=[id@0] +02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1 +03)----HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(id@0, id@0)], filter=z@1 < z@0 +04)------DataSourceExec: partitions=1, partition_sizes=[1] +05)------DataSourceExec: partitions=1, partition_sizes=[1] + +# The negated form of the same query stays null-aware, because `NOT mark` tells +# NULL from FALSE. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query TT +EXPLAIN SELECT id FROM nam_res_outer o +WHERE o.z > 35 OR o.id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < o.z); +---- +logical_plan +01)Projection: o.id +02)--Filter: o.z > Int32(35) OR NOT __correlated_sq_1.mark +03)----LeftMark Join: o.id = __correlated_sq_1.id Filter: __correlated_sq_1.z < o.z +04)------SubqueryAlias: o +05)--------TableScan: nam_res_outer projection=[id, z] +06)------SubqueryAlias: __correlated_sq_1 +07)--------SubqueryAlias: i +08)----------TableScan: nam_res_inner projection=[id, z] +physical_plan +01)FilterExec: z@1 > 35 OR NOT mark@2, projection=[id@0] +02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1 +03)----HashJoinExec: mode=CollectLeft, join_type=RightMark, on=[(id@0, id@0)], filter=z@1 < z@0 +04)------DataSourceExec: partitions=1, partition_sizes=[1] +05)------DataSourceExec: partitions=1, partition_sizes=[1] + +# Output batches of one row split the candidate pairs checked against the +# residual filter into many chunks. +statement ok +SET datafusion.execution.batch_size = 1; + +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query II rowsort +SELECT id, z FROM nam_res_outer +WHERE (id NOT IN (SELECT i.id FROM nam_res_inner i WHERE i.z < nam_res_outer.z)) IS NULL; +---- + +statement ok +RESET datafusion.execution.batch_size; + +statement ok +DROP TABLE nam_res_outer; + +statement ok +DROP TABLE nam_res_inner; + +########################################################## +## A subquery inside the `IN` value expression +## https://github.com/apache/datafusion/pull/25339#discussion_r4056392706 +########################################################## + +# A mark join is non-null-aware only when a NULL mark and a FALSE mark keep the +# same rows. That holds for a non-negated `IN` reached through `AND`/`OR`, but +# not when the mark feeds the value expression of another `IN`: there the mark +# is compared rather than used as a filter truth value, so `NULL IN (false)` is +# UNKNOWN while `false IN (false)` is TRUE. The inner mark join must stay +# null-aware however the outer `IN` is spelled. + +statement ok +CREATE TABLE nam_val_t1(id INT, z INT, w INT) AS VALUES (1,10,1), (2,20,1), (NULL,30,2), (4,40,2), (5,NULL,1), (NULL,NULL,2); + +statement ok +CREATE TABLE nam_val_t2(id INT, z INT, w INT) AS VALUES (1,5,1), (NULL,50,1), (4,NULL,2), (NULL,NULL,2), (2,20,3); + +statement ok +CREATE TABLE nam_val_tb(b BOOLEAN) AS VALUES (false); + +# Expected results verified with DuckDB: every row is UNKNOWN, so none survives. +query I +SELECT id FROM nam_val_t1 +WHERE ((id IN (SELECT nam_val_t2.id FROM nam_val_t2 WHERE nam_val_t2.w = nam_val_t1.w)) IN (SELECT b FROM nam_val_tb)) OR id = -1 +ORDER BY id; +---- + +# The negated spelling of the outer `IN` reaches the same arm. Here a TRUE inner +# mark survives (`TRUE NOT IN (false)`), so the result is non-empty and would +# also catch a fix that simply drops every row. +query I +SELECT id FROM nam_val_t1 +WHERE ((id IN (SELECT nam_val_t2.id FROM nam_val_t2 WHERE nam_val_t2.w = nam_val_t1.w)) NOT IN (SELECT b FROM nam_val_tb)) OR id = -1 +ORDER BY id; +---- +1 +4 + +statement ok +DROP TABLE nam_val_t1; + +statement ok +DROP TABLE nam_val_t2; + +statement ok +DROP TABLE nam_val_tb; + +########################################################## +## Contexts that can tell a NULL mark from a FALSE mark +########################################################## + +# A mark join may skip null-aware semantics only where a NULL mark and a FALSE +# mark keep the same rows. These two contexts can tell them apart, so the mark +# join must stay null-aware. Both cases fail if the planner ever treats them as +# positive: `IS NOT NULL` then admits the UNKNOWN rows, and the comparison then +# reads UNKNOWN as FALSE. Expected results verified with DuckDB. + +statement ok +CREATE TABLE nam_ctx_t1(a INT, w INT) AS VALUES (1,1), (2,1), (3,1), (NULL,2), (4,2); + +statement ok +CREATE TABLE nam_ctx_t2(a INT, w INT) AS VALUES (1,1), (NULL,1), (4,2), (NULL,2); + +# `NULL IS NOT NULL` is FALSE but `FALSE IS NOT NULL` is TRUE. +query I +SELECT a FROM nam_ctx_t1 +WHERE (a IN (SELECT nam_ctx_t2.a FROM nam_ctx_t2 WHERE nam_ctx_t2.w = nam_ctx_t1.w)) IS NOT NULL +ORDER BY a; +---- +1 +4 + +# Two marks compared. Row a = 3 has an UNKNOWN left mark and a FALSE right mark: +# `UNKNOWN = FALSE` is UNKNOWN, while `FALSE = FALSE` would be TRUE. +query I +SELECT a FROM nam_ctx_t1 +WHERE (a IN (SELECT nam_ctx_t2.a FROM nam_ctx_t2 WHERE nam_ctx_t2.w = nam_ctx_t1.w)) + = (a IN (SELECT nam_ctx_t2.w FROM nam_ctx_t2)) +ORDER BY a; +---- +1 + +statement ok +DROP TABLE nam_ctx_t1; + +statement ok +DROP TABLE nam_ctx_t2; + +########################################################## +## Plan guards: null-aware is taken only where it is needed +########################################################## + +# Null-aware mark joins cost much more than plain ones, so the planner takes +# them only where a NULL mark can behave differently from a FALSE mark. That +# choice is invisible to a result assertion -- a needless null-aware join is +# still correct, only slower -- so it is pinned here at the plan level. +# https://github.com/apache/datafusion/pull/25339#discussion_r4056392706 + +statement ok +CREATE TABLE nam_guard_outer(id INT, z INT) AS VALUES (1,10), (2,20), (NULL,30); + +statement ok +CREATE TABLE nam_guard_inner(id INT, z INT) AS VALUES (1,5), (NULL,50); + +# A non-negated `IN` reached through `OR` keeps the same rows with a NULL mark +# and with a FALSE mark, so the join must NOT be null-aware. It is then free to +# swap sides to `RightMark` as well. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query TT +EXPLAIN SELECT id FROM nam_guard_outer +WHERE id IN (SELECT i.id FROM nam_guard_inner i) OR z > 25; +---- +logical_plan +01)Projection: nam_guard_outer.id +02)--Filter: __correlated_sq_1.mark OR nam_guard_outer.z > Int32(25) +03)----LeftMark Join: nam_guard_outer.id = __correlated_sq_1.id null_aware +04)------TableScan: nam_guard_outer projection=[id, z] +05)------SubqueryAlias: __correlated_sq_1 +06)--------SubqueryAlias: i +07)----------TableScan: nam_guard_inner projection=[id] +physical_plan +01)FilterExec: mark@2 OR z@1 > 25, projection=[id@0] +02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1 +03)----HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware +04)------DataSourceExec: partitions=1, partition_sizes=[1] +05)------DataSourceExec: partitions=1, partition_sizes=[1] + +# A `NOT EXISTS` sibling under the same `OR` must not change that. `EXISTS` is +# two-valued, so its mark is never NULL and it cannot make the `IN` mark +# observable. Treating it as negative cost this query the plain join and the +# `RightMark` swap. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query TT +EXPLAIN SELECT id FROM nam_guard_outer +WHERE id IN (SELECT i.id FROM nam_guard_inner i) + OR NOT EXISTS (SELECT i.id FROM nam_guard_inner i WHERE i.z > nam_guard_outer.z); +---- +logical_plan +01)Projection: nam_guard_outer.id +02)--Filter: __correlated_sq_1.mark OR NOT __correlated_sq_2.mark +03)----Projection: nam_guard_outer.id, __correlated_sq_1.mark, __correlated_sq_2.mark +04)------LeftMark Join: Filter: __correlated_sq_2.z > nam_guard_outer.z +05)--------LeftMark Join: nam_guard_outer.id = __correlated_sq_1.id null_aware +06)----------TableScan: nam_guard_outer projection=[id, z] +07)----------SubqueryAlias: __correlated_sq_1 +08)------------SubqueryAlias: i +09)--------------TableScan: nam_guard_inner projection=[id] +10)--------SubqueryAlias: __correlated_sq_2 +11)----------SubqueryAlias: i +12)------------TableScan: nam_guard_inner projection=[z] +physical_plan +01)FilterExec: mark@1 OR NOT mark@2, projection=[id@0] +02)--NestedLoopJoinExec: join_type=RightMark, filter=z@1 > z@0, projection=[id@0, mark@2, mark@3] +03)----DataSourceExec: partitions=1, partition_sizes=[1] +04)----RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1 +05)------HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(id@0, id@0)], null_aware +06)--------DataSourceExec: partitions=1, partition_sizes=[1] +07)--------DataSourceExec: partitions=1, partition_sizes=[1] + +# A constant value expression is projected as an outer column only when the +# join ends up null-aware. This mark join does not, so the constant stays a +# filter and no `__correlated_sq_*_value` column is produced. +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. +query TT +EXPLAIN SELECT id FROM nam_guard_outer +WHERE 3 IN (SELECT i.id FROM nam_guard_inner i) OR z > 25; +---- +logical_plan +01)Projection: nam_guard_outer.id +02)--Filter: __correlated_sq_1.mark OR nam_guard_outer.z > Int32(25) +03)----Projection: nam_guard_outer.id, nam_guard_outer.z, __correlated_sq_1.mark +04)------LeftMark Join: __correlated_sq_1_value = __correlated_sq_1.i.id null_aware +05)--------Projection: nam_guard_outer.id, nam_guard_outer.z, Int64(3) AS __correlated_sq_1_value +06)----------TableScan: nam_guard_outer projection=[id, z] +07)--------SubqueryAlias: __correlated_sq_1 +08)----------Projection: CAST(i.id AS Int64) +09)------------SubqueryAlias: i +10)--------------TableScan: nam_guard_inner projection=[id] +physical_plan +01)FilterExec: mark@2 OR z@1 > 25, projection=[id@0] +02)--RepartitionExec: partitioning=RoundRobinBatch(4), input_partitions=1 +03)----HashJoinExec: mode=CollectLeft, join_type=LeftMark, on=[(__correlated_sq_1_value@2, i.id@0)], projection=[id@0, z@1, mark@3], null_aware +04)------ProjectionExec: expr=[id@0 as id, z@1 as z, 3 as __correlated_sq_1_value] +05)--------DataSourceExec: partitions=1, partition_sizes=[1] +06)------ProjectionExec: expr=[CAST(id@0 AS Int64) as i.id] +07)--------DataSourceExec: partitions=1, partition_sizes=[1] + +statement ok +DROP TABLE nam_guard_outer; + +statement ok +DROP TABLE nam_guard_inner; diff --git a/datafusion/sqllogictest/test_files/subquery.slt b/datafusion/sqllogictest/test_files/subquery.slt index 626ef60762..ca0b0b1ff8 100644 --- a/datafusion/sqllogictest/test_files/subquery.slt +++ b/datafusion/sqllogictest/test_files/subquery.slt @@ -730,6 +730,8 @@ logical_plan 06)--EmptyRelation: rows=1 #simple_uncorrelated_scalar_subquery2 +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. query TT explain select (select count(*) from t1) as b, (select count(1) from t2) ---- @@ -1252,6 +1254,8 @@ where t1.t1_id > 40 or t1.t1_id in (select t2.t2_id from t2 where t1.t1_int > 0) 44 d 4 # not_in_subquery_to_join_with_correlated_outer_filter_disjunction +# Pinned to today's behaviour, which is incorrect. See +# https://github.com/apache/datafusion/issues/25336 -- the fix flips this. query TT explain select t1.t1_id, t1.t1_name, --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
