Skip to content

Commit a79a694

Browse files
abp002jayzhan211
andauthored
fix: drop build rows with a dictionary NULL key in null-aware anti joins (apache#26578)
## Which issue does this PR close? - Closes apache#26568. ## Rationale for this change `x NOT IN (subquery)` keeps a build row whose key is a dictionary entry pointing at a NULL value. `NULL NOT IN (5, 6)` is UNKNOWN, so the row should be dropped, as it is when the key is a physical NULL. ## What changes are included in this PR? The final step of the uncorrelated null-aware `LeftAnti` join now checks the logical nulls of the build key instead of `is_null`. They are computed once with the build side, reusing what apache#25693 added for `LeftMark`, so the field and its getter are renamed to `null_aware_build_key_nulls`. ## What is the testing strategy for this PR? New `test_null_aware_left_anti_build_logical_null` with the case from the issue. It fails without the fix. ## Are there any user-facing changes? No. Co-authored-by: Alejandro Borrego <[email protected]> Co-authored-by: Jay Zhan <[email protected]>
1 parent ebf4858 commit a79a694

2 files changed

Lines changed: 91 additions & 15 deletions

File tree

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

Lines changed: 84 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -357,11 +357,12 @@ struct JoinBuildData {
357357
/// `build_side_has_null` were computed from the original keys in
358358
/// `collect_left_input`.
359359
values: Vec<ArrayRef>,
360-
/// Logical nulls of the scalar key for uncorrelated null-aware `LeftMark`.
360+
/// Logical nulls of the scalar key for uncorrelated null-aware `LeftMark`
361+
/// and `LeftAnti`.
361362
///
362363
/// Computed once while collecting the build side because dictionary
363364
/// logical-null discovery can scan nested dictionary values.
364-
left_mark_build_key_nulls: Option<NullBuffer>,
365+
null_aware_build_key_nulls: Option<NullBuffer>,
365366
/// Bounds computed from the build side; absent for an empty partition.
366367
bounds: Option<PartitionBounds>,
367368
/// IN-list values or a hash-table reference used for filter pushdown.
@@ -438,8 +439,8 @@ impl JoinLeftData {
438439
&self.build.values
439440
}
440441

441-
pub(super) fn left_mark_build_key_nulls(&self) -> Option<&NullBuffer> {
442-
self.build.left_mark_build_key_nulls.as_ref()
442+
pub(super) fn null_aware_build_key_nulls(&self) -> Option<&NullBuffer> {
443+
self.build.null_aware_build_key_nulls.as_ref()
443444
}
444445

445446
/// returns a reference to the visited indices bitmap
@@ -3647,20 +3648,25 @@ fn build_in_memory(
36473648
&& !left_values.is_empty()
36483649
&& left_values[0].logical_null_count() > 0;
36493650

3650-
let left_mark_build_key_nulls = if matches!(
3651+
let null_aware_build_key_nulls = if matches!(
36513652
null_aware,
3652-
Some(NullAwareMode::LeftMark {
3653-
correlated: false,
3654-
..
3655-
})
3653+
Some(
3654+
NullAwareMode::LeftMark {
3655+
correlated: false,
3656+
..
3657+
} | NullAwareMode::LeftAnti {
3658+
correlated: false,
3659+
..
3660+
}
3661+
)
36563662
) {
36573663
left_values[0]
36583664
.logical_nulls()
36593665
.filter(|nulls| nulls.null_count() > 0)
36603666
} else {
36613667
None
36623668
};
3663-
if let Some(nulls) = &left_mark_build_key_nulls {
3669+
if let Some(nulls) = &null_aware_build_key_nulls {
36643670
// `logical_nulls` reuses an array's physical null buffer when it can.
36653671
// Only charge newly materialized buffers, such as dictionary logical
36663672
// nulls, because the build batch's buffers were reserved above.
@@ -3692,7 +3698,7 @@ fn build_in_memory(
36923698
map,
36933699
batch,
36943700
values: normalized_values,
3695-
left_mark_build_key_nulls,
3701+
null_aware_build_key_nulls,
36963702
bounds,
36973703
membership,
36983704
reservation,
@@ -10549,6 +10555,73 @@ mod tests {
1054910555
Ok(())
1055010556
}
1055110557

10558+
/// The build side counterpart of
10559+
/// [`test_null_aware_left_anti_probe_logical_null`]: `NULL NOT IN (5, 6)`
10560+
/// is UNKNOWN, so the build row whose key points at a NULL dictionary
10561+
/// value is dropped.
10562+
#[apply(hash_join_exec_configs)]
10563+
#[tokio::test]
10564+
async fn test_null_aware_left_anti_build_logical_null(
10565+
batch_size: usize,
10566+
) -> Result<()> {
10567+
let task_ctx = prepare_task_ctx(batch_size, false);
10568+
10569+
let left = build_table_dict_key(
10570+
"c1",
10571+
vec![Some(1), None, Some(2)],
10572+
vec![0, 1, 2],
10573+
"dummy",
10574+
vec![Some(10), Some(0), Some(20)],
10575+
);
10576+
let left_key = left
10577+
.execute(0, Arc::clone(&task_ctx))?
10578+
.next()
10579+
.await
10580+
.unwrap()?;
10581+
assert_eq!(left_key.column(0).null_count(), 0);
10582+
assert_eq!(left_key.column(0).logical_null_count(), 1);
10583+
10584+
let right = build_table_dict_key(
10585+
"c2",
10586+
vec![Some(5), Some(6)],
10587+
vec![0, 1],
10588+
"dummy",
10589+
vec![Some(50), Some(60)],
10590+
);
10591+
10592+
let on = vec![(
10593+
Arc::new(Column::new_with_schema("c1", &left.schema())?) as _,
10594+
Arc::new(Column::new_with_schema("c2", &right.schema())?) as _,
10595+
)];
10596+
10597+
let join = HashJoinExec::try_new(
10598+
left,
10599+
right,
10600+
on,
10601+
None,
10602+
&JoinType::LeftAnti,
10603+
None,
10604+
PartitionMode::CollectLeft,
10605+
NullEquality::NullEqualsNothing,
10606+
true,
10607+
)?;
10608+
10609+
let stream = join.execute(0, task_ctx)?;
10610+
let batches = common::collect(stream).await?;
10611+
10612+
allow_duplicates! {
10613+
assert_snapshot!(batches_to_sort_string(&batches), @r"
10614+
+----+-------+
10615+
| c1 | dummy |
10616+
+----+-------+
10617+
| 1 | 10 |
10618+
| 2 | 20 |
10619+
+----+-------+
10620+
");
10621+
}
10622+
Ok(())
10623+
}
10624+
1055210625
/// A dictionary key that points to a NULL dictionary value is a NULL build
1055310626
/// key even when the dictionary key bitmap itself has no NULLs.
1055410627
#[apply(hash_join_exec_configs)]

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

Lines changed: 7 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -1379,12 +1379,15 @@ fn null_aware_left_anti_final_indices(
13791379
if !probe_summary.non_empty {
13801380
return (left_side, right_side);
13811381
}
1382-
// null_aware validation ensures a single join key
1383-
let build_key_column = &left_data.values()[0];
1382+
// Logical nulls, so that a dictionary key pointing at a NULL value counts
1383+
// as a NULL build key. Computed once with the build side.
1384+
let Some(build_key_nulls) = left_data.null_aware_build_key_nulls() else {
1385+
return (left_side, right_side);
1386+
};
13841387
let left_side = UInt64Array::from_iter_values(left_side.iter().filter_map(|idx| {
13851388
let idx =
13861389
idx.expect("LeftAnti final indices should always contain build-side rows");
1387-
(!build_key_column.is_null(idx as usize)).then_some(idx)
1390+
(!build_key_nulls.is_null(idx as usize)).then_some(idx)
13881391
}));
13891392
let right_side = UInt32Array::new_null(left_side.len());
13901393
(left_side, right_side)
@@ -1406,7 +1409,7 @@ fn null_aware_left_mark_column(
14061409
let build_key_nulls = if correlated {
14071410
None
14081411
} else {
1409-
left_data.left_mark_build_key_nulls()
1412+
left_data.null_aware_build_key_nulls()
14101413
};
14111414
build_null_aware_left_mark_column(
14121415
left_side,

0 commit comments

Comments
 (0)