Skip to content

Commit 3bc2308

Browse files
committed
fix: cache logical null scans in null-aware joins
1 parent 4d50daa commit 3bc2308

3 files changed

Lines changed: 134 additions & 28 deletions

File tree

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

Lines changed: 108 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -70,6 +70,7 @@ use crate::{
7070
};
7171

7272
use arrow::array::{Array, ArrayRef, BooleanBufferBuilder, UInt64Array};
73+
use arrow::buffer::NullBuffer;
7374
use arrow::compute::concat_batches;
7475
use arrow::datatypes::SchemaRef;
7576
use arrow::record_batch::RecordBatch;
@@ -304,6 +305,11 @@ pub(super) struct JoinLeftData {
304305
batch: RecordBatch,
305306
/// The build side on expressions values
306307
values: Vec<ArrayRef>,
308+
/// Logical nulls of the scalar key for uncorrelated null-aware `LeftMark`.
309+
///
310+
/// Computed once while collecting the build side because dictionary
311+
/// logical-null discovery can scan nested dictionary values.
312+
left_mark_build_key_nulls: Option<NullBuffer>,
307313
/// Shared bitmap builder for visited left indices
308314
visited_indices_bitmap: SharedBitmapBuilder,
309315
/// Shared bitmap builder for null marks
@@ -368,6 +374,10 @@ impl JoinLeftData {
368374
&self.values
369375
}
370376

377+
pub(super) fn left_mark_build_key_nulls(&self) -> Option<&NullBuffer> {
378+
self.left_mark_build_key_nulls.as_ref()
379+
}
380+
371381
/// returns a reference to the visited indices bitmap
372382
pub(super) fn visited_indices_bitmap(&self) -> &SharedBitmapBuilder {
373383
&self.visited_indices_bitmap
@@ -3138,12 +3148,37 @@ async fn collect_left_input(
31383148
&& !left_values.is_empty()
31393149
&& left_values[0].logical_null_count() > 0;
31403150

3151+
let left_mark_build_key_nulls = if matches!(
3152+
null_aware,
3153+
Some(NullAwareMode::LeftMark { correlated: false })
3154+
) {
3155+
left_values[0]
3156+
.logical_nulls()
3157+
.filter(|nulls| nulls.null_count() > 0)
3158+
} else {
3159+
None
3160+
};
3161+
if let Some(nulls) = &left_mark_build_key_nulls {
3162+
// `logical_nulls` reuses an array's physical null buffer when it can.
3163+
// Only charge newly materialized buffers, such as dictionary logical
3164+
// nulls, because the build batch's buffers were reserved above.
3165+
let reuses_input_buffer = left_values[0]
3166+
.nulls()
3167+
.is_some_and(|input| input.inner().ptr_eq(nulls.inner()));
3168+
if !reuses_input_buffer {
3169+
let retained_size = nulls.buffer().capacity();
3170+
reservation.try_grow(retained_size)?;
3171+
metrics.build_mem_used.add(retained_size);
3172+
}
3173+
}
3174+
31413175
let data = JoinLeftData {
31423176
map,
31433177
null_aware_scope_map,
31443178
null_value_build_rows,
31453179
batch,
31463180
values: left_values,
3181+
left_mark_build_key_nulls,
31473182
visited_indices_bitmap: Mutex::new(visited_indices_bitmap),
31483183
null_indices_bitmap: Mutex::new(null_indices_bitmap),
31493184
probe_completion: ProbeCompletion::new(probe_threads_count),
@@ -9186,6 +9221,79 @@ mod tests {
91869221
Ok(())
91879222
}
91889223

9224+
fn build_single_column_table(name: &str, array: ArrayRef) -> Arc<dyn ExecutionPlan> {
9225+
let schema = Arc::new(Schema::new(vec![Field::new(
9226+
name,
9227+
array.data_type().clone(),
9228+
true,
9229+
)]));
9230+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![array]).unwrap();
9231+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None).unwrap()
9232+
}
9233+
9234+
fn nested_dictionary_array(
9235+
leaf_values: Vec<Option<i32>>,
9236+
inner_keys: Vec<i32>,
9237+
outer_keys: Vec<i32>,
9238+
) -> ArrayRef {
9239+
let leaf_values: ArrayRef = Arc::new(Int32Array::from(leaf_values));
9240+
let inner_keys = Int32Array::from(inner_keys);
9241+
let inner_values: ArrayRef =
9242+
Arc::new(DictionaryArray::<Int32Type>::new(inner_keys, leaf_values));
9243+
Arc::new(DictionaryArray::<Int32Type>::new(
9244+
Int32Array::from(outer_keys),
9245+
inner_values,
9246+
))
9247+
}
9248+
9249+
/// A nested dictionary's logical null bitmap must be computed once for the
9250+
/// complete build key and remain indexed by the original build row.
9251+
#[apply(hash_join_exec_configs)]
9252+
#[tokio::test]
9253+
async fn test_null_aware_left_mark_nested_dictionary_logical_null(
9254+
batch_size: usize,
9255+
) -> Result<()> {
9256+
let task_ctx = prepare_task_ctx(batch_size, false);
9257+
let left_key = nested_dictionary_array(
9258+
vec![Some(1), None, Some(4)],
9259+
vec![0, 1, 2],
9260+
vec![0, 1, 2],
9261+
);
9262+
assert_eq!(left_key.logical_null_count(), 1);
9263+
let left = build_single_column_table("c1", left_key);
9264+
let right = build_single_column_table(
9265+
"c2",
9266+
nested_dictionary_array(
9267+
vec![Some(1), Some(2), Some(3)],
9268+
vec![0, 1, 2],
9269+
vec![0, 1, 2],
9270+
),
9271+
);
9272+
let on = vec![(
9273+
Arc::new(Column::new_with_schema("c1", &left.schema())?) as _,
9274+
Arc::new(Column::new_with_schema("c2", &right.schema())?) as _,
9275+
)];
9276+
let join = HashJoinExec::try_new(
9277+
left,
9278+
right,
9279+
on,
9280+
None,
9281+
&JoinType::LeftMark,
9282+
None,
9283+
PartitionMode::CollectLeft,
9284+
NullEquality::NullEqualsNothing,
9285+
true,
9286+
)?;
9287+
9288+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
9289+
let marks = batches
9290+
.iter()
9291+
.flat_map(|batch| batch.column(batch.num_columns() - 1).as_boolean().iter())
9292+
.collect::<Vec<_>>();
9293+
assert_eq!(marks, vec![Some(true), None, Some(false)]);
9294+
Ok(())
9295+
}
9296+
91899297
/// Scalar correlated null-aware left mark join where only the build side's
91909298
/// value key contains NULL.
91919299
///

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

Lines changed: 16 additions & 15 deletions
Original file line numberDiff line numberDiff line change
@@ -1248,14 +1248,19 @@ fn null_aware_skip_probe_batch(
12481248
| NullAwareMode::LeftMark { correlated: true } => false,
12491249
NullAwareMode::LeftAnti { correlated: false }
12501250
| NullAwareMode::LeftMark { correlated: false } => {
1251-
// `on[0]` is the `NOT IN` value key for both modes.
1252-
let probe_key_column = &state.values[0];
12531251
let is_anti = matches!(mode, NullAwareMode::LeftAnti { .. });
1254-
let probe_has_null = probe_key_column.logical_null_count() > 0;
1255-
// Only batches with rows count: `NULL NOT IN (empty)` is TRUE.
1256-
left_data.record_probe_batch(state.batch.num_rows() > 0, probe_has_null);
1252+
if state.offset == (0, None) {
1253+
// `on[0]` is the `NOT IN` value key for both modes. A probe
1254+
// batch may resume lookup many times, but its summary is
1255+
// invariant and only needs to be computed once.
1256+
let probe_has_null = state.values[0].logical_null_count() > 0;
1257+
// Only batches with rows count: `NULL NOT IN (empty)` is TRUE.
1258+
left_data.record_probe_batch(state.batch.num_rows() > 0, probe_has_null);
1259+
}
12571260
// Best-effort early exit; the final stage re-checks the flag
1258-
// through `report_probe_completed`.
1261+
// through `report_probe_completed`. Keep this outside the first-
1262+
// chunk guard so a sibling partition can stop an anti join between
1263+
// resumed lookups.
12591264
is_anti && left_data.probe_side_has_null_hint()
12601265
}
12611266
}
@@ -1345,21 +1350,17 @@ fn null_aware_left_mark_column(
13451350
) -> ArrayRef {
13461351
// Correlated joins precomputed the UNKNOWN decision per build row.
13471352
let null_indices_bitmap = correlated.then(|| left_data.null_indices_bitmap().lock());
1348-
// `LeftMark` final indices are a contiguous chunk of build rows. Limit the
1349-
// potentially allocating dictionary logical-null computation to this chunk;
1350-
// correlated joins already carry the answer in `null_indices_bitmap`.
1351-
let build_key_nulls = if correlated || left_side.is_empty() {
1353+
// Uncorrelated joins use the logical-null bitmap computed once with the
1354+
// build side. Correlated joins carry the answer in `null_indices_bitmap`.
1355+
let build_key_nulls = if correlated {
13521356
None
13531357
} else {
1354-
let start = left_side.value(0) as usize;
1355-
left_data.values()[0]
1356-
.slice(start, left_side.len())
1357-
.logical_nulls()
1358+
left_data.left_mark_build_key_nulls()
13581359
};
13591360
build_null_aware_left_mark_column(
13601361
left_side,
13611362
right_side,
1362-
build_key_nulls.as_ref(),
1363+
build_key_nulls,
13631364
null_indices_bitmap.as_deref(),
13641365
probe_summary.has_null,
13651366
probe_summary.non_empty,

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

Lines changed: 10 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -1381,8 +1381,7 @@ pub(crate) fn build_batch_from_indices(
13811381
/// For correlated scalar `NOT IN`, `null_indices_bitmap` carries the same UNKNOWN
13821382
/// decision per build row, scoped by the correlated equality keys.
13831383
///
1384-
/// When present, `build_key_nulls` is aligned with the output rows in
1385-
/// `build_indices`, rather than indexed by the original build row number.
1384+
/// When present, `build_key_nulls` is indexed by the original build row number.
13861385
///
13871386
/// This is the helper equivalent of the paper's "null bucket" and `hadNull` handling.
13881387
/// It is intentionally scoped to scalar null-aware mark joins.
@@ -1397,27 +1396,25 @@ pub(crate) fn build_null_aware_left_mark_column(
13971396
// Whether an unmatched build row's mark is NULL (UNKNOWN) instead of FALSE:
13981397
// correlated joins precomputed this per row in `null_indices_bitmap`; the
13991398
// uncorrelated rules are cases 1-4 in the doc above.
1400-
let unmatched_mark_is_null =
1401-
|build_idx: usize, output_idx: usize| match null_indices_bitmap {
1402-
Some(bitmap) => bitmap.get_bit(build_idx),
1403-
None if build_key_nulls.is_some_and(|nulls| nulls.is_null(output_idx)) => {
1404-
probe_side_non_empty
1405-
}
1406-
None => probe_side_has_null,
1407-
};
1399+
let unmatched_mark_is_null = |build_idx: usize| match null_indices_bitmap {
1400+
Some(bitmap) => bitmap.get_bit(build_idx),
1401+
None if build_key_nulls.is_some_and(|nulls| nulls.is_null(build_idx)) => {
1402+
probe_side_non_empty
1403+
}
1404+
None => probe_side_has_null,
1405+
};
14081406

14091407
let marks: BooleanArray = build_indices
14101408
.iter()
14111409
.zip(probe_indices.iter())
1412-
.enumerate()
1413-
.map(|(output_idx, (build_idx, probe_idx))| {
1410+
.map(|(build_idx, probe_idx)| {
14141411
if probe_idx.is_some() {
14151412
return Some(true);
14161413
}
14171414
let build_idx = build_idx
14181415
.expect("LeftMark final indices should always contain build-side rows")
14191416
as usize;
1420-
if unmatched_mark_is_null(build_idx, output_idx) {
1417+
if unmatched_mark_is_null(build_idx) {
14211418
None
14221419
} else {
14231420
Some(false)

0 commit comments

Comments
 (0)