Skip to content

Commit e1f8393

Browse files
viiryaOmega359
authored andcommitted
fix: handle dictionary nulls in null-aware left mark joins (apache#25693)
## Which issue does this PR close? - Closes apache#25691. ## Rationale for this change Null-aware `LeftMark` joins use physical null checks for dictionary keys. They miss valid dictionary keys that point to `NULL` dictionary values and return `FALSE` marks where SQL three-valued logic requires `NULL`. ## What changes are included in this PR? Null-aware `LeftMark` joins now use Arrow's logical-null APIs on both probe and build keys. The build-side logical-null bitmap is computed once during build collection, retained with memory accounting, and reused by final output chunks. Probe-side null summaries are computed once per input batch even when hash lookup resumes across several chunks. Correlated joins continue using their precomputed per-row null bitmap. ## What is the testing strategy for this PR? The diff adds three `HashJoinExec` test functions covering logical dictionary nulls on the build and probe sides, including nested dictionary build keys. `#[apply(hash_join_exec_configs)]` expands each function across five batch sizes, so Cargo reports 15 new test instances. The probe-side function also checks both probe-partition completion orders inside each instance. Ablation testing confirmed that the original build- and probe-side functions fail at every batch size without the correctness fix. With the fix, all 109 null-aware tests and the complete 2,409-test `datafusion-physical-plan` all-features suite pass. For 524,288-row debug diagnostics, bounding the original flat-dictionary scan reduced runtime from about 693ms to 141ms. The follow-up nested-dictionary diagnostic dropped from about 561ms to 177ms, and the oversized resumed-probe diagnostic dropped from about 1.29s to 910ms. ## Are there any user-facing changes? Null-aware mark joins over dictionary-encoded keys now return the correct nullable marks. There are no public API changes.
1 parent 9bc5cd9 commit e1f8393

3 files changed

Lines changed: 254 additions & 14 deletions

File tree

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

Lines changed: 229 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -358,6 +358,11 @@ struct JoinBuildData {
358358
/// `build_side_has_null` were computed from the original keys in
359359
/// `collect_left_input`.
360360
values: Vec<ArrayRef>,
361+
/// Logical nulls of the scalar key for uncorrelated null-aware `LeftMark`.
362+
///
363+
/// Computed once while collecting the build side because dictionary
364+
/// logical-null discovery can scan nested dictionary values.
365+
left_mark_build_key_nulls: Option<NullBuffer>,
361366
/// Bounds computed from the build side; absent for an empty partition.
362367
bounds: Option<PartitionBounds>,
363368
/// IN-list values or a hash-table reference used for filter pushdown.
@@ -438,6 +443,10 @@ impl JoinLeftData {
438443
&self.build.values
439444
}
440445

446+
pub(super) fn left_mark_build_key_nulls(&self) -> Option<&NullBuffer> {
447+
self.build.left_mark_build_key_nulls.as_ref()
448+
}
449+
441450
/// returns a reference to the visited indices bitmap
442451
pub(super) fn visited_indices_bitmap(&self) -> &SharedBitmapBuilder {
443452
&self.visited_indices_bitmap
@@ -3586,6 +3595,33 @@ async fn collect_left_input(
35863595
&& !left_values.is_empty()
35873596
&& left_values[0].logical_null_count() > 0;
35883597

3598+
let left_mark_build_key_nulls = if matches!(
3599+
null_aware,
3600+
Some(NullAwareMode::LeftMark {
3601+
correlated: false,
3602+
..
3603+
})
3604+
) {
3605+
left_values[0]
3606+
.logical_nulls()
3607+
.filter(|nulls| nulls.null_count() > 0)
3608+
} else {
3609+
None
3610+
};
3611+
if let Some(nulls) = &left_mark_build_key_nulls {
3612+
// `logical_nulls` reuses an array's physical null buffer when it can.
3613+
// Only charge newly materialized buffers, such as dictionary logical
3614+
// nulls, because the build batch's buffers were reserved above.
3615+
let reuses_input_buffer = left_values[0]
3616+
.nulls()
3617+
.is_some_and(|input| input.inner().ptr_eq(nulls.inner()));
3618+
if !reuses_input_buffer {
3619+
let retained_size = nulls.buffer().capacity();
3620+
reservation.try_grow(retained_size)?;
3621+
metrics.build_mem_used.add(retained_size);
3622+
}
3623+
}
3624+
35893625
if prepared {
35903626
drop(batches);
35913627
// Prepared keys are direct columns. IN-list arrays share these batch
@@ -3635,6 +3671,7 @@ async fn collect_left_input(
36353671
integer_prefilter,
36363672
batch,
36373673
values: normalized_values,
3674+
left_mark_build_key_nulls,
36383675
bounds,
36393676
membership,
36403677
reservation,
@@ -9695,6 +9732,59 @@ mod tests {
96959732
Ok(())
96969733
}
96979734

9735+
/// The dictionary counterpart of
9736+
/// [`test_null_aware_left_mark_probe_null_in_other_partition`], where the
9737+
/// probe NULL exists in a dictionary value instead of the key bitmap.
9738+
#[apply(hash_join_exec_configs)]
9739+
#[tokio::test]
9740+
async fn test_null_aware_left_mark_probe_logical_null_in_other_partition(
9741+
batch_size: usize,
9742+
) -> Result<()> {
9743+
let task_ctx = prepare_task_ctx(batch_size, false);
9744+
9745+
for order in [[0, 1], [1, 0]] {
9746+
let left = build_table_dict_key(
9747+
"c1",
9748+
vec![Some(1), Some(4)],
9749+
vec![0, 1],
9750+
"dummy",
9751+
vec![Some(10), Some(40)],
9752+
);
9753+
let right = build_two_partition_dict_probe_with_logical_null_in_partition_0();
9754+
9755+
let on = vec![(
9756+
Arc::new(Column::new_with_schema("c1", &left.schema())?) as _,
9757+
Arc::new(Column::new_with_schema("c2", &right.schema())?) as _,
9758+
)];
9759+
9760+
let join = HashJoinExec::try_new(
9761+
left,
9762+
right,
9763+
on,
9764+
None,
9765+
&JoinType::LeftMark,
9766+
None,
9767+
PartitionMode::CollectLeft,
9768+
NullEquality::NullEqualsNothing,
9769+
true,
9770+
)?;
9771+
9772+
let batches = collect_partitions_in_order(&join, &order, &task_ctx).await?;
9773+
9774+
allow_duplicates! {
9775+
assert_snapshot!(batches_to_sort_string(&batches), @r"
9776+
+----+-------+------+
9777+
| c1 | dummy | mark |
9778+
+----+-------+------+
9779+
| 1 | 10 | true |
9780+
| 4 | 40 | |
9781+
+----+-------+------+
9782+
");
9783+
}
9784+
}
9785+
Ok(())
9786+
}
9787+
96989788
/// Test null-aware anti join when build side (left) contains NULL keys
96999789
/// Expected: rows with NULL keys should not be output
97009790
#[apply(hash_join_exec_configs)]
@@ -10615,6 +10705,145 @@ mod tests {
1061510705
Ok(())
1061610706
}
1061710707

10708+
/// A dictionary key that points to a NULL dictionary value is a NULL build
10709+
/// key even when the dictionary key bitmap itself has no NULLs.
10710+
#[apply(hash_join_exec_configs)]
10711+
#[tokio::test]
10712+
async fn test_null_aware_left_mark_build_logical_null(
10713+
batch_size: usize,
10714+
) -> Result<()> {
10715+
let task_ctx = prepare_task_ctx(batch_size, false);
10716+
10717+
let left = build_table_dict_key(
10718+
"c1",
10719+
vec![Some(1), None, Some(4)],
10720+
vec![0, 1, 2],
10721+
"dummy",
10722+
vec![Some(10), Some(0), Some(40)],
10723+
);
10724+
let left_key = left
10725+
.execute(0, Arc::clone(&task_ctx))?
10726+
.next()
10727+
.await
10728+
.unwrap()?;
10729+
assert_eq!(left_key.column(0).null_count(), 0);
10730+
assert_eq!(left_key.column(0).logical_null_count(), 1);
10731+
10732+
let right = build_table_dict_key(
10733+
"c2",
10734+
vec![Some(1), Some(2), Some(3)],
10735+
vec![0, 1, 2],
10736+
"dummy",
10737+
vec![Some(100), Some(200), Some(300)],
10738+
);
10739+
10740+
let on = vec![(
10741+
Arc::new(Column::new_with_schema("c1", &left.schema())?) as _,
10742+
Arc::new(Column::new_with_schema("c2", &right.schema())?) as _,
10743+
)];
10744+
10745+
let join = HashJoinExec::try_new(
10746+
left,
10747+
right,
10748+
on,
10749+
None,
10750+
&JoinType::LeftMark,
10751+
None,
10752+
PartitionMode::CollectLeft,
10753+
NullEquality::NullEqualsNothing,
10754+
true,
10755+
)?;
10756+
10757+
let stream = join.execute(0, task_ctx)?;
10758+
let batches = common::collect(stream).await?;
10759+
10760+
allow_duplicates! {
10761+
assert_snapshot!(batches_to_sort_string(&batches), @r"
10762+
+----+-------+-------+
10763+
| c1 | dummy | mark |
10764+
+----+-------+-------+
10765+
| | 0 | |
10766+
| 1 | 10 | true |
10767+
| 4 | 40 | false |
10768+
+----+-------+-------+
10769+
");
10770+
}
10771+
Ok(())
10772+
}
10773+
10774+
fn build_single_column_table(name: &str, array: ArrayRef) -> Arc<dyn ExecutionPlan> {
10775+
let schema = Arc::new(Schema::new(vec![Field::new(
10776+
name,
10777+
array.data_type().clone(),
10778+
true,
10779+
)]));
10780+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![array]).unwrap();
10781+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None).unwrap()
10782+
}
10783+
10784+
fn nested_dictionary_array(
10785+
leaf_values: Vec<Option<i32>>,
10786+
inner_keys: Vec<i32>,
10787+
outer_keys: Vec<i32>,
10788+
) -> ArrayRef {
10789+
let leaf_values: ArrayRef = Arc::new(Int32Array::from(leaf_values));
10790+
let inner_keys = Int32Array::from(inner_keys);
10791+
let inner_values: ArrayRef =
10792+
Arc::new(DictionaryArray::<Int32Type>::new(inner_keys, leaf_values));
10793+
Arc::new(DictionaryArray::<Int32Type>::new(
10794+
Int32Array::from(outer_keys),
10795+
inner_values,
10796+
))
10797+
}
10798+
10799+
/// A nested dictionary's logical null bitmap must be computed once for the
10800+
/// complete build key and remain indexed by the original build row.
10801+
#[apply(hash_join_exec_configs)]
10802+
#[tokio::test]
10803+
async fn test_null_aware_left_mark_nested_dictionary_logical_null(
10804+
batch_size: usize,
10805+
) -> Result<()> {
10806+
let task_ctx = prepare_task_ctx(batch_size, false);
10807+
let left_key = nested_dictionary_array(
10808+
vec![Some(1), None, Some(4)],
10809+
vec![0, 1, 2],
10810+
vec![0, 1, 2],
10811+
);
10812+
assert_eq!(left_key.logical_null_count(), 1);
10813+
let left = build_single_column_table("c1", left_key);
10814+
let right = build_single_column_table(
10815+
"c2",
10816+
nested_dictionary_array(
10817+
vec![Some(1), Some(2), Some(3)],
10818+
vec![0, 1, 2],
10819+
vec![0, 1, 2],
10820+
),
10821+
);
10822+
let on = vec![(
10823+
Arc::new(Column::new_with_schema("c1", &left.schema())?) as _,
10824+
Arc::new(Column::new_with_schema("c2", &right.schema())?) as _,
10825+
)];
10826+
let join = HashJoinExec::try_new(
10827+
left,
10828+
right,
10829+
on,
10830+
None,
10831+
&JoinType::LeftMark,
10832+
None,
10833+
PartitionMode::CollectLeft,
10834+
NullEquality::NullEqualsNothing,
10835+
true,
10836+
)?;
10837+
10838+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
10839+
let marks = batches
10840+
.iter()
10841+
.flat_map(|batch| batch.column(batch.num_columns() - 1).as_boolean().iter())
10842+
.collect::<Vec<_>>();
10843+
assert_eq!(marks, vec![Some(true), None, Some(false)]);
10844+
Ok(())
10845+
}
10846+
1061810847
/// Scalar correlated null-aware left mark join where only the build side's
1061910848
/// value key contains NULL.
1062010849
///

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

Lines changed: 19 additions & 12 deletions
Original file line numberDiff line numberDiff line change
@@ -1346,18 +1346,19 @@ fn null_aware_skip_probe_batch(
13461346
| NullAwareMode::LeftMark {
13471347
correlated: false, ..
13481348
} => {
1349-
// `on[0]` is the `NOT IN` value key for both modes.
1350-
let probe_key_column = &state.values[0];
13511349
let is_anti = matches!(mode, NullAwareMode::LeftAnti { .. });
1352-
let probe_has_null = if is_anti {
1353-
probe_key_column.logical_null_count() > 0
1354-
} else {
1355-
probe_key_column.null_count() > 0
1356-
};
1357-
// Only batches with rows count: `NULL NOT IN (empty)` is TRUE.
1358-
left_data.record_probe_batch(state.batch.num_rows() > 0, probe_has_null);
1350+
if state.offset == (0, None) {
1351+
// `on[0]` is the `NOT IN` value key for both modes. A probe
1352+
// batch may resume lookup many times, but its summary is
1353+
// invariant and only needs to be computed once.
1354+
let probe_has_null = state.values[0].logical_null_count() > 0;
1355+
// Only batches with rows count: `NULL NOT IN (empty)` is TRUE.
1356+
left_data.record_probe_batch(state.batch.num_rows() > 0, probe_has_null);
1357+
}
13591358
// Best-effort early exit; the final stage re-checks the flag
1360-
// through `report_probe_completed`.
1359+
// through `report_probe_completed`. Keep this outside the first-
1360+
// chunk guard so a sibling partition can stop an anti join between
1361+
// resumed lookups.
13611362
is_anti && left_data.probe_side_has_null_hint()
13621363
}
13631364
}
@@ -1445,13 +1446,19 @@ fn null_aware_left_mark_column(
14451446
left_side: &UInt64Array,
14461447
right_side: &UInt32Array,
14471448
) -> ArrayRef {
1448-
let build_key_column = &left_data.values()[0];
14491449
// Correlated joins precomputed the UNKNOWN decision per build row.
14501450
let null_indices_bitmap = correlated.then(|| left_data.null_indices_bitmap().lock());
1451+
// Uncorrelated joins use the logical-null bitmap computed once with the
1452+
// build side. Correlated joins carry the answer in `null_indices_bitmap`.
1453+
let build_key_nulls = if correlated {
1454+
None
1455+
} else {
1456+
left_data.left_mark_build_key_nulls()
1457+
};
14511458
build_null_aware_left_mark_column(
14521459
left_side,
14531460
right_side,
1454-
build_key_column.as_ref(),
1461+
build_key_nulls,
14551462
null_indices_bitmap.as_deref(),
14561463
probe_summary.has_null,
14571464
probe_summary.non_empty,

‎datafusion/physical-plan/src/joins/utils.rs‎

Lines changed: 6 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1389,12 +1389,14 @@ pub(crate) fn build_batch_from_indices(
13891389
/// For correlated scalar `NOT IN`, `null_indices_bitmap` carries the same UNKNOWN
13901390
/// decision per build row, scoped by the correlated equality keys.
13911391
///
1392+
/// When present, `build_key_nulls` is indexed by the original build row number.
1393+
///
13921394
/// This is the helper equivalent of the paper's "null bucket" and `hadNull` handling.
13931395
/// It is intentionally scoped to scalar null-aware mark joins.
13941396
pub(crate) fn build_null_aware_left_mark_column(
13951397
build_indices: &UInt64Array,
13961398
probe_indices: &UInt32Array,
1397-
build_key_column: &dyn Array,
1399+
build_key_nulls: Option<&NullBuffer>,
13981400
null_indices_bitmap: Option<&BooleanBufferBuilder>,
13991401
probe_side_has_null: bool,
14001402
probe_side_non_empty: bool,
@@ -1404,7 +1406,9 @@ pub(crate) fn build_null_aware_left_mark_column(
14041406
// uncorrelated rules are cases 1-4 in the doc above.
14051407
let unmatched_mark_is_null = |build_idx: usize| match null_indices_bitmap {
14061408
Some(bitmap) => bitmap.get_bit(build_idx),
1407-
None if build_key_column.is_null(build_idx) => probe_side_non_empty,
1409+
None if build_key_nulls.is_some_and(|nulls| nulls.is_null(build_idx)) => {
1410+
probe_side_non_empty
1411+
}
14081412
None => probe_side_has_null,
14091413
};
14101414

0 commit comments

Comments
 (0)