Skip to content

Commit 9926d75

Browse files
adriangbclaude
andcommitted
test: correlated NOT IN with a non-equality correlation
Adds sqllogictest regression tests for apache#25336 (expected results checked with DuckDB and PostgreSQL) and HashJoinExec unit tests for null-aware LeftAnti and LeftMark joins that have a join filter and no scope keys. Co-Authored-By: Claude Opus 5 <[email protected]>
1 parent 61ce306 commit 9926d75

3 files changed

Lines changed: 434 additions & 0 deletions

File tree

‎datafusion/physical-plan/src/joins/hash_join/exec.rs‎

Lines changed: 145 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -9158,6 +9158,151 @@ mod tests {
91589158
Ok(())
91599159
}
91609160

9161+
/// `left.z > right.z` over the second column of two-column tables: the
9162+
/// non-equality correlation of
9163+
/// `id NOT IN (SELECT r.id FROM r WHERE r.z < l.z)`.
9164+
fn prepare_second_column_gt_filter() -> JoinFilter {
9165+
let column_indices = vec![
9166+
ColumnIndex {
9167+
index: 1,
9168+
side: JoinSide::Left,
9169+
},
9170+
ColumnIndex {
9171+
index: 1,
9172+
side: JoinSide::Right,
9173+
},
9174+
];
9175+
let intermediate_schema = Schema::new(vec![
9176+
Field::new("z", DataType::Int32, true),
9177+
Field::new("z", DataType::Int32, true),
9178+
]);
9179+
let filter_expression = Arc::new(BinaryExpr::new(
9180+
Arc::new(Column::new("z", 0)),
9181+
Operator::Gt,
9182+
Arc::new(Column::new("z", 1)),
9183+
)) as Arc<dyn PhysicalExpr>;
9184+
9185+
JoinFilter::new(
9186+
filter_expression,
9187+
column_indices,
9188+
Arc::new(intermediate_schema),
9189+
)
9190+
}
9191+
9192+
/// Build and probe sides of a null-aware join whose only correlation is
9193+
/// the non-equality filter from [`prepare_second_column_gt_filter`].
9194+
///
9195+
/// For each build row, the probe rows with a smaller `z` form its
9196+
/// subquery result:
9197+
/// - `(1, 10)` and `(2, 20)`: `{1, NULL}`
9198+
/// - `(NULL, 30)`: `{1, NULL}`
9199+
/// - `(4, 40)`: `{1, 4, NULL}`
9200+
/// - `(NULL, 1)` and `(5, 1)`: empty
9201+
///
9202+
/// The probe row `(NULL, 50)` never passes the filter.
9203+
fn build_null_aware_filter_only_inputs()
9204+
-> (Arc<dyn ExecutionPlan>, Arc<dyn ExecutionPlan>, JoinOn) {
9205+
let left = build_table_two_cols(
9206+
("id", &vec![Some(1), Some(2), None, Some(4), None, Some(5)]),
9207+
(
9208+
"z",
9209+
&vec![Some(10), Some(20), Some(30), Some(40), Some(1), Some(1)],
9210+
),
9211+
);
9212+
let right = build_table_two_cols(
9213+
("id", &vec![Some(1), None, Some(4), None]),
9214+
("z", &vec![Some(5), Some(50), Some(35), Some(2)]),
9215+
);
9216+
let on = vec![(
9217+
Arc::new(Column::new_with_schema("id", &left.schema()).unwrap()) as _,
9218+
Arc::new(Column::new_with_schema("id", &right.schema()).unwrap()) as _,
9219+
)];
9220+
(left, right, on)
9221+
}
9222+
9223+
/// Null-aware `LeftAnti` with a join filter and no correlation scope keys.
9224+
///
9225+
/// A NULL on either side only makes `NOT IN` UNKNOWN for the build rows
9226+
/// where the filter keeps the NULL, so the NULLs must not remove every row.
9227+
#[apply(hash_join_exec_configs)]
9228+
#[tokio::test]
9229+
async fn test_null_aware_left_anti_filter_only(batch_size: usize) -> Result<()> {
9230+
let task_ctx = prepare_task_ctx(batch_size, false);
9231+
let (left, right, on) = build_null_aware_filter_only_inputs();
9232+
9233+
let join = HashJoinExec::try_new(
9234+
left,
9235+
right,
9236+
on,
9237+
Some(prepare_second_column_gt_filter()),
9238+
&JoinType::LeftAnti,
9239+
None,
9240+
PartitionMode::CollectLeft,
9241+
NullEquality::NullEqualsNothing,
9242+
true,
9243+
)?;
9244+
9245+
let stream = join.execute(0, task_ctx)?;
9246+
let batches = common::collect(stream).await?;
9247+
9248+
// Only the rows with an empty subquery result are TRUE.
9249+
allow_duplicates! {
9250+
assert_snapshot!(batches_to_sort_string(&batches), @r"
9251+
+----+---+
9252+
| id | z |
9253+
+----+---+
9254+
| | 1 |
9255+
| 5 | 1 |
9256+
+----+---+
9257+
");
9258+
}
9259+
9260+
Ok(())
9261+
}
9262+
9263+
/// Null-aware `LeftMark` with a join filter and no correlation scope keys.
9264+
#[apply(hash_join_exec_configs)]
9265+
#[tokio::test]
9266+
async fn test_null_aware_left_mark_filter_only(batch_size: usize) -> Result<()> {
9267+
let task_ctx = prepare_task_ctx(batch_size, false);
9268+
let (left, right, on) = build_null_aware_filter_only_inputs();
9269+
9270+
let join = HashJoinExec::try_new(
9271+
left,
9272+
right,
9273+
on,
9274+
Some(prepare_second_column_gt_filter()),
9275+
&JoinType::LeftMark,
9276+
None,
9277+
PartitionMode::CollectLeft,
9278+
NullEquality::NullEqualsNothing,
9279+
true,
9280+
)?;
9281+
9282+
let stream = join.execute(0, task_ctx)?;
9283+
let batches = common::collect(stream).await?;
9284+
9285+
// `(1, 10)` and `(4, 40)` match (true); `(2, 20)` and `(NULL, 30)`
9286+
// keep the NULL probe row (UNKNOWN); `(NULL, 1)` and `(5, 1)` have an
9287+
// empty subquery result (false).
9288+
allow_duplicates! {
9289+
assert_snapshot!(batches_to_sort_string(&batches), @r"
9290+
+----+----+-------+
9291+
| id | z | mark |
9292+
+----+----+-------+
9293+
| | 1 | false |
9294+
| | 30 | |
9295+
| 1 | 10 | true |
9296+
| 2 | 20 | |
9297+
| 4 | 40 | true |
9298+
| 5 | 1 | false |
9299+
+----+----+-------+
9300+
");
9301+
}
9302+
9303+
Ok(())
9304+
}
9305+
91619306
#[test]
91629307
fn test_lr_is_preserved() {
91639308
assert_eq!(lr_is_preserved(JoinType::Inner), (true, true));

‎datafusion/sqllogictest/test_files/null_aware_anti_join.slt‎

Lines changed: 165 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -666,3 +666,168 @@ DROP TABLE naconst_t1;
666666

667667
statement ok
668668
DROP TABLE naconst_t2;
669+
670+
## Correlated NOT IN with a non-equality correlation
671+
## https://github.com/apache/datafusion/issues/25336
672+
#############
673+
674+
# The non-equality correlation stays behind as a residual join filter. A NULL
675+
# subquery value only makes NOT IN UNKNOWN for the outer rows where the
676+
# residual keeps that NULL row. Expected results are verified with DuckDB and
677+
# PostgreSQL.
678+
679+
statement ok
680+
CREATE TABLE nai_res_t1(id INT, z INT) AS VALUES (1,10), (2,20), (NULL,30), (4,40);
681+
682+
statement ok
683+
CREATE TABLE nai_res_t2(id INT, z INT) AS VALUES (1,5), (NULL,50);
684+
685+
# The NULL row (z = 50) never passes `t2.z < t1.z`, so it does not affect the result.
686+
query I
687+
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;
688+
----
689+
2
690+
4
691+
692+
query I
693+
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;
694+
----
695+
2
696+
4
697+
698+
query I
699+
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;
700+
----
701+
1
702+
703+
# Uncorrelated residuals are pushed into the subquery.
704+
query I
705+
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;
706+
----
707+
2
708+
4
709+
710+
query I
711+
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;
712+
----
713+
714+
# The NULL row passes `t2.z > t1.z` for every outer row, so every row is UNKNOWN.
715+
query I
716+
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;
717+
----
718+
719+
statement ok
720+
CREATE TABLE nai_res_outer(id INT, z INT, g INT) AS VALUES
721+
(1, 10, 1),
722+
(2, 20, 1),
723+
(NULL, 30, 1),
724+
(4, 40, 2),
725+
(NULL, 1, 2),
726+
(5, 1, 3);
727+
728+
statement ok
729+
CREATE TABLE nai_res_inner(id INT, z INT, g INT) AS VALUES
730+
(1, 5, 1),
731+
(NULL, 50, 1),
732+
(4, 35, 2),
733+
(NULL, 2, 2);
734+
735+
# Per outer row, the residual decides which inner rows (NULL or not) are in
736+
# the subquery. A NULL outer value is TRUE only when that set is empty.
737+
query II rowsort
738+
SELECT id, z FROM nai_res_outer
739+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z);
740+
----
741+
5 1
742+
NULL 1
743+
744+
query II rowsort
745+
SELECT id, z FROM nai_res_outer
746+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z > nai_res_outer.z);
747+
----
748+
749+
query II rowsort
750+
SELECT id, z FROM nai_res_outer
751+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z AND i.z > 3);
752+
----
753+
2 20
754+
5 1
755+
NULL 1
756+
757+
query II rowsort
758+
SELECT id, z FROM nai_res_outer
759+
WHERE id + 0 NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z);
760+
----
761+
5 1
762+
NULL 1
763+
764+
# The residual references the subquery value itself.
765+
query II rowsort
766+
SELECT id, z FROM nai_res_outer
767+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.id + i.z > nai_res_outer.z);
768+
----
769+
1 10
770+
2 20
771+
4 40
772+
5 1
773+
774+
# Equality and non-equality correlation together.
775+
query II rowsort
776+
SELECT id, z FROM nai_res_outer
777+
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);
778+
----
779+
2 20
780+
5 1
781+
NULL 1
782+
783+
# Equality correlation only.
784+
query II rowsort
785+
SELECT id, z FROM nai_res_outer
786+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.g = nai_res_outer.g);
787+
----
788+
5 1
789+
790+
# NOT EXISTS uses two-valued logic and must not change.
791+
query II rowsort
792+
SELECT id, z FROM nai_res_outer
793+
WHERE NOT EXISTS (SELECT 1 FROM nai_res_inner i WHERE i.id = nai_res_outer.id AND i.z < nai_res_outer.z);
794+
----
795+
2 20
796+
5 1
797+
NULL 1
798+
NULL 30
799+
800+
# Output batches of one row split the unmatched build rows and the candidate
801+
# pairs checked against the residual filter into many chunks.
802+
statement ok
803+
SET datafusion.execution.batch_size = 1;
804+
805+
query II rowsort
806+
SELECT id, z FROM nai_res_outer
807+
WHERE id NOT IN (SELECT i.id FROM nai_res_inner i WHERE i.z < nai_res_outer.z);
808+
----
809+
5 1
810+
NULL 1
811+
812+
query II rowsort
813+
SELECT id, z FROM nai_res_outer
814+
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);
815+
----
816+
2 20
817+
5 1
818+
NULL 1
819+
820+
statement ok
821+
RESET datafusion.execution.batch_size;
822+
823+
statement ok
824+
DROP TABLE nai_res_t1;
825+
826+
statement ok
827+
DROP TABLE nai_res_t2;
828+
829+
statement ok
830+
DROP TABLE nai_res_outer;
831+
832+
statement ok
833+
DROP TABLE nai_res_inner;

0 commit comments

Comments
 (0)