Skip to content

Commit f800da5

Browse files
authored
perf: emit unmatched build rows in batch_size chunks in HashJoinExec (apache#25028)
## Which issue does this PR close? - Related to apache#24768 (bounded-memory hash join) and apache#18942 (hash join operator optimizations); no dedicated issue. ## Rationale for this change For join types that emit build-side rows after the probe side is exhausted (`Left`, `Full`, `LeftAnti`, `LeftSemi`, `LeftMark`), `HashJoinExec` computed the final indices over the *whole* build side and materialized them as **one** `RecordBatch` before handing it to the output coalescer. That batch is not bounded by `batch_size`, and it is not covered by the memory reservation. Worse, `LimitedBatchCoalescer` configures arrow's `BatchCoalescer` with `biggest_coalesce_batch_size = batch_size / 2`, which passes any larger batch through untouched. So a `LEFT ANTI` join over a 10M-row build side with few matches emitted a single ~10M-row batch downstream, regardless of `datafusion.execution.batch_size`. `NestedLoopJoinExec` already emits its unmatched build rows in `batch_size` chunks; this PR brings `HashJoinExec` in line. ## What changes are included in this PR? - `HashJoinStream` gets a new state, `EmitUnmatchedBuildRows`, entered from `ExhaustedProbeSide` by the last probe partition. It holds a `BooleanBuffer` snapshot of the visited bitmap (taken once, after every partition reported completion, so the lock is not held while emitting) and a cursor. - `next_final_indices_chunk` scans the snapshot from the cursor and returns at most `batch_size` final indices per call (`LeftMark` emits every row, so its chunks are plain ranges). Null-aware `LeftAnti`/`LeftMark` post-processing and `fetch` handling are unchanged and now run per chunk. - `input_batches` is still bumped once for the final phase and `input_rows` once per chunk, so metric values are identical to before. - `get_final_indices_from_bit_map` / `get_final_indices_from_shared_bitmap` in `joins/utils.rs` had no other callers and are removed. - New benchmark cases in `hash_join_semi_anti.rs` with a 1M-row build side and a 100K-row probe side (`left_semi_build1m_h10`, `left_anti_build1m_h10`, `left_build1m_h10`). Benchmark (this branch vs. `main`, Apple Silicon, `cargo bench --bench hash_join_semi_anti -- build1m`): | case | main | this PR | change | |---|---|---|---| | left_semi_build1m_h10 | 2.05 ms | 1.97 ms | -4% | | left_anti_build1m_h10 | 6.21 ms | 4.75 ms | -24% | | left_build1m_h10 | 7.37 ms | 6.79 ms | -8% | Peak RSS of the `left_anti_build1m_h10` bench binary: ~369 MB on `main` vs ~160 MB on this branch (`/usr/bin/time -l`, 1M build rows, 900K unmatched). ## Are these changes tested? - New `join_emits_final_build_rows_in_batch_size_chunks` test (Left/Full/LeftAnti/LeftSemi/LeftMark × batch sizes 1/7/8192 × perfect-hash-join on/off) asserts the output rows and that every output batch respects `batch_size`. On `main` 14 of its 30 cases fail the batch-size assertion. - New `join_fetch_stops_final_build_rows_mid_chunk` test checks a `fetch` that is reached in the middle of the final rows. - Existing hash join unit tests (493), join sqllogictests (`joins`, `join_limit_pushdown`, `join_disable_repartition_joins`, `subquery`), and the core join fuzz tests pass. ## Are there any user-facing changes? No result changes. Output batches of the affected join types are now bounded by `batch_size` instead of arriving as one batch holding every unmatched build row.
1 parent 2a42140 commit f800da5

4 files changed

Lines changed: 374 additions & 77 deletions

File tree

‎datafusion/physical-plan/benches/hash_join_semi_anti.rs‎

Lines changed: 59 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -380,6 +380,65 @@ fn bench_hash_join_semi_anti(c: &mut Criterion) {
380380
});
381381
}
382382

383+
// =========================================================================
384+
// Build-side output benchmarks (LeftSemi / LeftAnti / Left)
385+
// =========================================================================
386+
//
387+
// These join types emit build-side rows only after the probe side is
388+
// exhausted, so they exercise the final "unmatched build rows" emission.
389+
// Build side: 1M rows, Probe side: 100K rows, so most build rows stay
390+
// unmatched and the final emission dominates.
391+
let large_build_rows = 1_000_000;
392+
let small_probe_rows = 100_000;
393+
394+
// LeftSemi - 10% of build rows matched -> 100K output rows
395+
{
396+
let left_batches = build_batches(large_build_rows, large_build_rows, 0, &s);
397+
let right_batches = build_batches(small_probe_rows, small_probe_rows, 0, &s);
398+
group.bench_function(
399+
BenchmarkId::new("left_semi_build1m_h10", small_probe_rows),
400+
|b| {
401+
b.iter(|| {
402+
let left = make_exec(&left_batches, &s);
403+
let right = make_exec(&right_batches, &s);
404+
do_hash_join(left, right, JoinType::LeftSemi, &rt)
405+
})
406+
},
407+
);
408+
}
409+
410+
// LeftAnti - 10% of build rows matched -> 900K output rows
411+
{
412+
let left_batches = build_batches(large_build_rows, large_build_rows, 0, &s);
413+
let right_batches = build_batches(small_probe_rows, small_probe_rows, 0, &s);
414+
group.bench_function(
415+
BenchmarkId::new("left_anti_build1m_h10", small_probe_rows),
416+
|b| {
417+
b.iter(|| {
418+
let left = make_exec(&left_batches, &s);
419+
let right = make_exec(&right_batches, &s);
420+
do_hash_join(left, right, JoinType::LeftAnti, &rt)
421+
})
422+
},
423+
);
424+
}
425+
426+
// Left - 10% of build rows matched -> 100K matched + 900K unmatched output rows
427+
{
428+
let left_batches = build_batches(large_build_rows, large_build_rows, 0, &s);
429+
let right_batches = build_batches(small_probe_rows, small_probe_rows, 0, &s);
430+
group.bench_function(
431+
BenchmarkId::new("left_build1m_h10", small_probe_rows),
432+
|b| {
433+
b.iter(|| {
434+
let left = make_exec(&left_batches, &s);
435+
let right = make_exec(&right_batches, &s);
436+
do_hash_join(left, right, JoinType::Left, &rt)
437+
})
438+
},
439+
);
440+
}
441+
383442
group.finish();
384443
}
385444

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

Lines changed: 160 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3041,11 +3041,11 @@ mod tests {
30413041
};
30423042

30433043
use arrow::array::{
3044-
Array, ArrayRef, Date32Array, DictionaryArray, Int32Array, Int64Array,
3044+
Array, ArrayRef, AsArray, Date32Array, DictionaryArray, Int32Array, Int64Array,
30453045
StructArray, UInt32Array, UInt64Array,
30463046
};
30473047
use arrow::buffer::NullBuffer;
3048-
use arrow::datatypes::{DataType, Field};
3048+
use arrow::datatypes::{DataType, Field, Int32Type};
30493049
use datafusion_common::hash_utils::create_hashes;
30503050
use datafusion_common::test_util::{batches_to_sort_string, batches_to_string};
30513051
use datafusion_common::{
@@ -4127,6 +4127,164 @@ mod tests {
41274127
return Ok(());
41284128
}
41294129

4130+
/// Build side keyed `0..num_build_rows`, probe side holding only
4131+
/// `matched_keys`, joined on the key column.
4132+
fn final_build_rows_inputs(
4133+
num_build_rows: i32,
4134+
matched_keys: &[i32],
4135+
) -> (Arc<dyn ExecutionPlan>, Arc<dyn ExecutionPlan>, JoinOn) {
4136+
let build_keys: Vec<i32> = (0..num_build_rows).collect();
4137+
let probe_keys = matched_keys.to_vec();
4138+
let left = build_table(
4139+
("a1", &build_keys),
4140+
("b1", &build_keys),
4141+
("c1", &build_keys),
4142+
);
4143+
let right = build_table(
4144+
("a2", &probe_keys),
4145+
("b2", &probe_keys),
4146+
("c2", &probe_keys),
4147+
);
4148+
let on = vec![(
4149+
Arc::new(Column::new_with_schema("b1", &left.schema()).unwrap()) as _,
4150+
Arc::new(Column::new_with_schema("b2", &right.schema()).unwrap()) as _,
4151+
)];
4152+
(left, right, on)
4153+
}
4154+
4155+
/// Returns the sorted `(a1, matched)` pairs of the joined output, where
4156+
/// `matched` is read from the mark column for `LeftMark`, from the
4157+
/// presence of probe-side data for `Left`/`Full`, and is `None` for
4158+
/// existence joins whose output carries no match information.
4159+
fn build_rows_with_match_flag(batches: &[RecordBatch]) -> Vec<(i32, Option<bool>)> {
4160+
let mut rows = vec![];
4161+
for batch in batches {
4162+
let a1 = batch
4163+
.column_by_name("a1")
4164+
.unwrap()
4165+
.as_primitive::<Int32Type>();
4166+
let matched: Vec<Option<bool>> = match batch.column_by_name("mark") {
4167+
Some(mark) => mark.as_boolean().iter().collect(),
4168+
None => match batch.column_by_name("a2") {
4169+
Some(a2) => (0..a2.len()).map(|i| Some(a2.is_valid(i))).collect(),
4170+
None => vec![None; batch.num_rows()],
4171+
},
4172+
};
4173+
rows.extend(a1.values().iter().copied().zip(matched));
4174+
}
4175+
rows.sort_unstable();
4176+
rows
4177+
}
4178+
4179+
/// The `(a1, matched)` pairs a join of [`final_build_rows_inputs`] must
4180+
/// produce, in the format of [`build_rows_with_match_flag`].
4181+
fn expected_final_build_rows(
4182+
join_type: JoinType,
4183+
num_build_rows: i32,
4184+
matched_keys: &[i32],
4185+
) -> Vec<(i32, Option<bool>)> {
4186+
(0..num_build_rows)
4187+
.filter_map(|key| {
4188+
let matched = matched_keys.contains(&key);
4189+
match join_type {
4190+
JoinType::LeftSemi => matched.then_some((key, None)),
4191+
JoinType::LeftAnti => (!matched).then_some((key, None)),
4192+
_ => Some((key, Some(matched))),
4193+
}
4194+
})
4195+
.collect()
4196+
}
4197+
4198+
/// The final build-side rows (unmatched rows, or matched rows for
4199+
/// `LeftSemi`) must be emitted in chunks bounded by `batch_size` instead
4200+
/// of one batch over the whole build side.
4201+
#[rstest]
4202+
#[tokio::test]
4203+
async fn join_emits_final_build_rows_in_batch_size_chunks(
4204+
#[values(
4205+
JoinType::Left,
4206+
JoinType::Full,
4207+
JoinType::LeftAnti,
4208+
JoinType::LeftSemi,
4209+
JoinType::LeftMark
4210+
)]
4211+
join_type: JoinType,
4212+
#[values(1, 7, 8192)] batch_size: usize,
4213+
#[values(true, false)] use_perfect_hash_join_as_possible: bool,
4214+
) -> Result<()> {
4215+
let task_ctx = prepare_task_ctx(batch_size, use_perfect_hash_join_as_possible);
4216+
let num_build_rows = 100;
4217+
let matched_keys = [3, 50, 97];
4218+
let (left, right, on) = final_build_rows_inputs(num_build_rows, &matched_keys);
4219+
4220+
let (_, batches, metrics) = join_collect(
4221+
left,
4222+
right,
4223+
on,
4224+
&join_type,
4225+
NullEquality::NullEqualsNothing,
4226+
task_ctx,
4227+
)
4228+
.await?;
4229+
assert_phj_used(&metrics, use_perfect_hash_join_as_possible);
4230+
4231+
let expected =
4232+
expected_final_build_rows(join_type, num_build_rows, &matched_keys);
4233+
assert_eq!(build_rows_with_match_flag(&batches), expected);
4234+
4235+
for batch in &batches {
4236+
assert!(
4237+
batch.num_rows() <= batch_size,
4238+
"{join_type} join emitted a batch of {} rows with batch_size {batch_size}",
4239+
batch.num_rows()
4240+
);
4241+
}
4242+
assert!(
4243+
batches.len() >= expected.len().div_ceil(batch_size),
4244+
"{join_type} join emitted {} batches for {} rows with batch_size {batch_size}",
4245+
batches.len(),
4246+
expected.len()
4247+
);
4248+
4249+
Ok(())
4250+
}
4251+
4252+
/// A `fetch` limit that is reached in the middle of the final build-side
4253+
/// rows stops the emission at exactly `fetch` rows.
4254+
#[rstest]
4255+
#[tokio::test]
4256+
async fn join_fetch_stops_final_build_rows_mid_chunk(
4257+
#[values(JoinType::Left, JoinType::LeftAnti, JoinType::LeftMark)]
4258+
join_type: JoinType,
4259+
) -> Result<()> {
4260+
let batch_size = 7;
4261+
let fetch = 20;
4262+
let num_build_rows = 100;
4263+
let matched_keys = [3, 50, 97];
4264+
let task_ctx = prepare_task_ctx(batch_size, false);
4265+
let (left, right, on) = final_build_rows_inputs(num_build_rows, &matched_keys);
4266+
4267+
let join = HashJoinExecBuilder::new(left, right, on, join_type)
4268+
.with_partition_mode(PartitionMode::CollectLeft)
4269+
.with_fetch(Some(fetch))
4270+
.build()?;
4271+
let batches = common::collect(join.execute(0, task_ctx)?).await?;
4272+
4273+
let num_rows: usize = batches.iter().map(|b| b.num_rows()).sum();
4274+
assert_eq!(num_rows, fetch);
4275+
for batch in &batches {
4276+
assert!(batch.num_rows() <= batch_size);
4277+
}
4278+
// Every emitted row is a genuine join result row.
4279+
let expected =
4280+
expected_final_build_rows(join_type, num_build_rows, &matched_keys);
4281+
for row in build_rows_with_match_flag(&batches) {
4282+
assert!(expected.contains(&row), "unexpected output row {row:?}");
4283+
}
4284+
4285+
Ok(())
4286+
}
4287+
41304288
#[apply(hash_join_exec_configs)]
41314289
#[tokio::test]
41324290
async fn join_full_multi_batch(

0 commit comments

Comments
 (0)