Skip to content

Commit db01044

Browse files
committed
perf: normalize float hash join build keys once
The hash join key comparator is built once per probe batch, and each build rewrote -0.0 to +0.0 across the whole build key column. A join on float keys therefore rescanned the build side for every probe batch. Normalize the build keys once in collect_left_input and keep them as the stored build keys. The in-list and bounds dynamic filters and the build null check still read the original keys, and a rewritten copy is charged to the build reservation. Hash join's lookup now uses a comparator that skips the build-side pass; other joins keep the existing behavior. On TPC-H SF1 a (BIGINT, DOUBLE) key join drops from 96 ms to 26 ms of join time, in line with the same join on integer keys.
1 parent 31f5ae6 commit db01044

3 files changed

Lines changed: 413 additions & 12 deletions

File tree

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

Lines changed: 271 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -81,6 +81,7 @@ use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRecursion};
8181
use datafusion_common::utils::memory::{
8282
RecordBatchMemoryCounter, estimate_memory_size, get_record_batch_memory_size,
8383
};
84+
use datafusion_common::utils::normalize_float_zero;
8485
use datafusion_common::{
8586
JoinSide, JoinType, NullEquality, Result, assert_or_internal_err, internal_err,
8687
plan_err, project_schema,
@@ -298,7 +299,11 @@ struct JoinBuildData {
298299
map: Arc<Map>,
299300
/// The input rows for the build side.
300301
batch: RecordBatch,
301-
/// Evaluated build-side key expressions.
302+
/// Evaluated build-side key expressions, with float `-0.0` rewritten to
303+
/// `+0.0` so probe batches can compare against them without scanning the
304+
/// build side again. The dynamic filters (`bounds`, `membership`) and
305+
/// `build_side_has_null` were computed from the original keys in
306+
/// `collect_left_input`.
302307
values: Vec<ArrayRef>,
303308
/// Bounds computed from the build side; absent for an empty partition.
304309
bounds: Option<PartitionBounds>,
@@ -369,7 +374,9 @@ impl JoinLeftData {
369374
!self.map().is_empty()
370375
}
371376

372-
/// returns a reference to the build side expressions values
377+
/// Returns the build side key values, with float `-0.0` already rewritten
378+
/// to `+0.0` for key comparison. The dynamic filters and
379+
/// `build_side_has_null` were derived from the original keys instead.
373380
pub(super) fn values(&self) -> &[ArrayRef] {
374381
&self.build.values
375382
}
@@ -3202,12 +3209,20 @@ async fn collect_left_input(
32023209
(Map::HashMap(hashmap), batch, left_values)
32033210
};
32043211

3212+
// Rewrite float `-0.0` to `+0.0` once here, so the per probe batch key
3213+
// comparison does not rescan the build side. Arrays without `-0.0`, and
3214+
// non-float keys, are shared rather than copied.
3215+
let normalized_values: Vec<ArrayRef> =
3216+
left_values.iter().map(normalize_float_zero).collect();
3217+
32053218
// Join keys that are plain columns share the buffers of `batch`, any other
32063219
// expression evaluates to new arrays that are kept for the whole join.
3220+
// The same goes for normalized keys: only a rewritten copy adds memory.
32073221
let mut key_counter = RecordBatchMemoryCounter::new();
32083222
key_counter.count_batch(&batch);
32093223
let keys_size = left_values
32103224
.iter()
3225+
.chain(&normalized_values)
32113226
.map(|values| key_counter.count_array(values.as_ref()))
32123227
.sum::<usize>();
32133228
reservation.try_grow(keys_size)?;
@@ -3270,7 +3285,7 @@ async fn collect_left_input(
32703285
let build_indices = UInt64Array::from_iter_values(
32713286
null_mask.values().set_indices().map(|i| i as u64),
32723287
);
3273-
let scope_values = left_values[1..]
3288+
let scope_values = normalized_values[1..]
32743289
.iter()
32753290
.map(|values| Ok(arrow::compute::filter(values.as_ref(), &null_mask)?))
32763291
.collect::<Result<Vec<_>>>()?;
@@ -3364,7 +3379,7 @@ async fn collect_left_input(
33643379
build: Arc::new(JoinBuildData {
33653380
map,
33663381
batch,
3367-
values: left_values,
3382+
values: normalized_values,
33683383
bounds,
33693384
membership,
33703385
reservation,
@@ -3452,11 +3467,11 @@ mod tests {
34523467

34533468
use arrow::array::{
34543469
Array, ArrayRef, AsArray, BinaryViewArray, Date32Array, DictionaryArray,
3455-
Float64Array, Int32Array, Int64Array, StringArray, StringViewArray, StructArray,
3456-
UInt32Array, UInt64Array,
3470+
Float32Array, Float64Array, Int32Array, Int64Array, StringArray, StringViewArray,
3471+
StructArray, UInt32Array, UInt64Array,
34573472
};
34583473
use arrow::buffer::NullBuffer;
3459-
use arrow::datatypes::{DataType, Field, Int32Type};
3474+
use arrow::datatypes::{DataType, Field, Float32Type, Float64Type, Int32Type};
34603475
use datafusion_common::hash_utils::create_hashes;
34613476
use datafusion_common::test_util::{batches_to_sort_string, batches_to_string};
34623477
use datafusion_common::{
@@ -4155,6 +4170,165 @@ mod tests {
41554170
Ok(())
41564171
}
41574172

4173+
/// Collects a single-column build side keyed on that column.
4174+
async fn collect_float_build(
4175+
keys: ArrayRef,
4176+
) -> Result<(JoinLeftData, BuildProbeJoinMetrics)> {
4177+
let schema = Arc::new(Schema::new(vec![Field::new(
4178+
"f",
4179+
keys.data_type().clone(),
4180+
true,
4181+
)]));
4182+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![keys])?;
4183+
let exec = TestMemoryExec::try_new_exec(&[vec![batch]], schema, None)?;
4184+
let stream = exec.execute(0, Arc::new(TaskContext::default()))?;
4185+
let pool: Arc<dyn MemoryPool> = Arc::new(UnboundedMemoryPool::default());
4186+
let metrics = BuildProbeJoinMetrics::new(0, &ExecutionPlanMetricsSet::new());
4187+
let on_left: Vec<PhysicalExprRef> = vec![Arc::new(Column::new("f", 0))];
4188+
let left_data = collect_left_input(
4189+
RandomState::with_seed(0),
4190+
stream,
4191+
on_left,
4192+
metrics.clone(),
4193+
MemoryConsumer::new("HashJoinInput").register(&pool),
4194+
false,
4195+
1,
4196+
false,
4197+
Arc::new(ConfigOptions::default()),
4198+
NullEquality::NullEqualsNothing,
4199+
None,
4200+
Count::new(),
4201+
BuildMode::Ordinary,
4202+
)
4203+
.await?;
4204+
Ok((left_data, metrics))
4205+
}
4206+
4207+
/// The stored build keys have `-0.0` rewritten to `+0.0`, while the build
4208+
/// batch keeps the original value. The rewritten copy is charged to the
4209+
/// build memory, and keys without `-0.0` are shared with the batch.
4210+
#[tokio::test]
4211+
async fn collect_left_input_stores_normalized_float_keys() -> Result<()> {
4212+
let (with_neg_zero, neg_metrics) =
4213+
collect_float_build(Arc::new(Float64Array::from(vec![-0.0, 1.0]))).await?;
4214+
let stored = with_neg_zero.values()[0].as_primitive::<Float64Type>();
4215+
assert_eq!(stored.value(0).to_bits(), 0.0_f64.to_bits());
4216+
assert_eq!(stored.value(1), 1.0);
4217+
let original = with_neg_zero
4218+
.batch()
4219+
.column(0)
4220+
.as_primitive::<Float64Type>();
4221+
assert_eq!(original.value(0).to_bits(), (-0.0_f64).to_bits());
4222+
4223+
let (without_neg_zero, pos_metrics) =
4224+
collect_float_build(Arc::new(Float64Array::from(vec![0.0, 1.0]))).await?;
4225+
assert!(Arc::ptr_eq(
4226+
&without_neg_zero.values()[0],
4227+
without_neg_zero.batch().column(0)
4228+
));
4229+
4230+
// Both builds are the same shape, so they differ only by the copy.
4231+
assert_eq!(
4232+
neg_metrics.build_mem_used.value(),
4233+
pos_metrics.build_mem_used.value() + stored.values().inner().capacity()
4234+
);
4235+
4236+
let (f32_build, _) =
4237+
collect_float_build(Arc::new(Float32Array::from(vec![-0.0_f32, 1.0])))
4238+
.await?;
4239+
let stored = f32_build.values()[0].as_primitive::<Float32Type>();
4240+
assert_eq!(stored.value(0).to_bits(), 0.0_f32.to_bits());
4241+
let original = f32_build.batch().column(0).as_primitive::<Float32Type>();
4242+
assert_eq!(original.value(0).to_bits(), (-0.0_f32).to_bits());
4243+
Ok(())
4244+
}
4245+
4246+
/// A single Float64 key takes the general comparator path. Build and
4247+
/// probe both hold `-0.0` and `0.0`, which must all match each other,
4248+
/// while the output keeps each side's original sign.
4249+
#[rstest]
4250+
#[tokio::test]
4251+
async fn join_inner_single_float_key_negative_zero(
4252+
#[values(8192, 1)] batch_size: usize,
4253+
#[values(NullEquality::NullEqualsNothing, NullEquality::NullEqualsNull)]
4254+
null_equality: NullEquality,
4255+
) -> Result<()> {
4256+
let task_ctx = prepare_task_ctx(batch_size, false);
4257+
4258+
let table = |suffix: &str,
4259+
f: Vec<Option<f64>>,
4260+
v: Vec<i32>|
4261+
-> Result<Arc<dyn ExecutionPlan>> {
4262+
let schema = Arc::new(Schema::new(vec![
4263+
Field::new(format!("f{suffix}"), DataType::Float64, true),
4264+
Field::new(format!("v{suffix}"), DataType::Int32, true),
4265+
]));
4266+
let batch = RecordBatch::try_new(
4267+
Arc::clone(&schema),
4268+
vec![
4269+
Arc::new(Float64Array::from(f)),
4270+
Arc::new(Int32Array::from(v)),
4271+
],
4272+
)?;
4273+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None)
4274+
.map(|exec| exec as _)
4275+
};
4276+
4277+
let left = table(
4278+
"1",
4279+
vec![Some(-0.0), Some(0.0), Some(1.5), None],
4280+
vec![10, 11, 12, 13],
4281+
)?;
4282+
let right = table(
4283+
"2",
4284+
vec![Some(0.0), Some(-0.0), Some(1.5), None],
4285+
vec![20, 21, 22, 23],
4286+
)?;
4287+
let on = vec![(
4288+
Arc::new(Column::new_with_schema("f1", &left.schema())?) as _,
4289+
Arc::new(Column::new_with_schema("f2", &right.schema())?) as _,
4290+
)];
4291+
4292+
let (_, batches, _) =
4293+
join_collect(left, right, on, &JoinType::Inner, null_equality, task_ctx)
4294+
.await?;
4295+
4296+
// The NULL keys only pair up when NULL equals NULL.
4297+
allow_duplicates! {
4298+
match null_equality {
4299+
NullEquality::NullEqualsNothing => {
4300+
assert_snapshot!(batches_to_sort_string(&batches), @r"
4301+
+------+----+------+----+
4302+
| f1 | v1 | f2 | v2 |
4303+
+------+----+------+----+
4304+
| -0.0 | 10 | -0.0 | 21 |
4305+
| -0.0 | 10 | 0.0 | 20 |
4306+
| 0.0 | 11 | -0.0 | 21 |
4307+
| 0.0 | 11 | 0.0 | 20 |
4308+
| 1.5 | 12 | 1.5 | 22 |
4309+
+------+----+------+----+
4310+
");
4311+
}
4312+
NullEquality::NullEqualsNull => {
4313+
assert_snapshot!(batches_to_sort_string(&batches), @r"
4314+
+------+----+------+----+
4315+
| f1 | v1 | f2 | v2 |
4316+
+------+----+------+----+
4317+
| | 13 | | 23 |
4318+
| -0.0 | 10 | -0.0 | 21 |
4319+
| -0.0 | 10 | 0.0 | 20 |
4320+
| 0.0 | 11 | -0.0 | 21 |
4321+
| 0.0 | 11 | 0.0 | 20 |
4322+
| 1.5 | 12 | 1.5 | 22 |
4323+
+------+----+------+----+
4324+
");
4325+
}
4326+
}
4327+
}
4328+
4329+
Ok(())
4330+
}
4331+
41584332
/// Two probe batches carry different multi-column keys at the same row
41594333
/// positions. Each batch has to be compared against its own key arrays;
41604334
/// a comparator left over from the first batch would drop the second
@@ -10279,6 +10453,96 @@ mod tests {
1027910453
Ok(())
1028010454
}
1028110455

10456+
/// Correlated null-aware `LeftAnti` whose two scope keys are Float64, with
10457+
/// `-0.0` on the build side and `0.0` on the probe side. Both scopes must
10458+
/// still match in every direction: the full key lookup, NULL probe values
10459+
/// against all build rows, and NULL build values against the probe rows.
10460+
#[apply(hash_join_exec_configs)]
10461+
#[tokio::test]
10462+
async fn test_null_aware_left_anti_float_scope_negative_zero(
10463+
batch_size: usize,
10464+
) -> Result<()> {
10465+
let task_ctx = prepare_task_ctx(batch_size, false);
10466+
10467+
fn table(
10468+
id: Vec<Option<i32>>,
10469+
g1: Vec<f64>,
10470+
g2: Vec<f64>,
10471+
) -> Arc<dyn ExecutionPlan> {
10472+
let schema = Arc::new(Schema::new(vec![
10473+
Field::new("id", DataType::Int32, true),
10474+
Field::new("g1", DataType::Float64, true),
10475+
Field::new("g2", DataType::Float64, true),
10476+
]));
10477+
let batch = RecordBatch::try_new(
10478+
Arc::clone(&schema),
10479+
vec![
10480+
Arc::new(Int32Array::from(id)),
10481+
Arc::new(Float64Array::from(g1)),
10482+
Arc::new(Float64Array::from(g2)),
10483+
],
10484+
)
10485+
.unwrap();
10486+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None).unwrap()
10487+
}
10488+
10489+
let left = table(
10490+
vec![Some(1), Some(3), None, Some(4), Some(5), None, Some(6)],
10491+
vec![-0.0, -0.0, -0.0, 2.0, -0.0, 3.0, 2.0],
10492+
vec![1.0, 1.0, 1.0, -0.0, -0.0, -0.0, 1.0],
10493+
);
10494+
let right = table(
10495+
vec![Some(1), Some(2), None, Some(7)],
10496+
vec![0.0, 0.0, 2.0, 2.0],
10497+
vec![1.0, 1.0, 0.0, 1.0],
10498+
);
10499+
10500+
let on = ["id", "g1", "g2"]
10501+
.into_iter()
10502+
.map(|name| {
10503+
Ok((
10504+
Arc::new(Column::new_with_schema(name, &left.schema())?) as _,
10505+
Arc::new(Column::new_with_schema(name, &right.schema())?) as _,
10506+
))
10507+
})
10508+
.collect::<Result<JoinOn>>()?;
10509+
10510+
let join = HashJoinExec::try_new(
10511+
left,
10512+
right,
10513+
on,
10514+
None,
10515+
&JoinType::LeftAnti,
10516+
None,
10517+
PartitionMode::CollectLeft,
10518+
NullEquality::NullEqualsNothing,
10519+
true,
10520+
)?;
10521+
10522+
let stream = join.execute(0, task_ctx)?;
10523+
let batches = common::collect(stream).await?;
10524+
10525+
// Scope (0, 1) holds 1 and 2: `1` matches and is dropped, `3` is kept,
10526+
// and the NULL build value there is UNKNOWN. Scope (2, 0) holds a
10527+
// NULL probe value, so `4` is UNKNOWN. Scopes (0, 0) and (3, 0) are
10528+
// empty, so `5` and the NULL build value in (3, 0) are kept. Scope
10529+
// (2, 1) holds only 7, so `6` is kept.
10530+
allow_duplicates! {
10531+
assert_snapshot!(batches_to_sort_string(&batches), @r"
10532+
+----+------+------+
10533+
| id | g1 | g2 |
10534+
+----+------+------+
10535+
| | 3.0 | -0.0 |
10536+
| 3 | -0.0 | 1.0 |
10537+
| 5 | -0.0 | -0.0 |
10538+
| 6 | 2.0 | 1.0 |
10539+
+----+------+------+
10540+
");
10541+
}
10542+
10543+
Ok(())
10544+
}
10545+
1028210546
#[test]
1028310547
fn test_lr_is_preserved() {
1028410548
assert_eq!(lr_is_preserved(JoinType::Inner), (true, true));

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

Lines changed: 9 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -33,7 +33,7 @@ use crate::joins::hash_join::shared_bounds::{
3333
PartitionBounds, PartitionBuildData, SharedBuildAccumulator,
3434
};
3535
use crate::joins::utils::{
36-
JoinKeyComparator, OnceFut, equal_rows_arr, matchable_join_keys,
36+
JoinKeyComparator, OnceFut, equal_rows_arr_with_normalized_left, matchable_join_keys,
3737
};
3838
use crate::stream::EmptyRecordBatchStream;
3939
use crate::{
@@ -425,6 +425,11 @@ impl RecordBatchStream for HashJoinStream {
425425
/// Returns build/probe indices satisfying the equality condition, along with
426426
/// (optional) starting point for next iteration.
427427
///
428+
/// `build_side_values` must come from [`JoinLeftData::values()`] (or be
429+
/// derived from it), where float `-0.0` is already rewritten to `+0.0`. The
430+
/// key comparison does not normalize the build side again, so raw build keys
431+
/// holding `-0.0` would fail to match `+0.0` on the probe side.
432+
///
428433
/// # Example
429434
///
430435
/// For `LEFT.b1 = RIGHT.b2`:
@@ -496,7 +501,7 @@ pub(super) fn lookup_join_hashmap(
496501
let probe_indices_unfiltered: UInt32Array =
497502
std::mem::take(probe_indices_buffer).into();
498503

499-
let (build_indices, probe_indices) = equal_rows_arr(
504+
let (build_indices, probe_indices) = equal_rows_arr_with_normalized_left(
500505
&build_indices_unfiltered,
501506
&probe_indices_unfiltered,
502507
build_side_values,
@@ -1568,6 +1573,8 @@ fn mark_null_candidates_for_probe_batch(
15681573
/// Calls `f` with all correlation-scope matches between `build_scope_values`
15691574
/// and `probe_scope_values`, as chunks of at most `batch_size` pairs of
15701575
/// (position in `build_scope_values`, position in `probe_scope_values`).
1576+
/// `build_scope_values` must already be normalized, as for
1577+
/// [`lookup_join_hashmap`].
15711578
#[expect(clippy::too_many_arguments)]
15721579
fn for_each_scope_match(
15731580
scope_map: &dyn JoinHashMapType,

0 commit comments

Comments
 (0)