Skip to content

Commit 801b017

Browse files
authored
perf: normalize float hash join build keys once (apache#25972)
## Which issue does this PR close? - Follow-up to apache#25658, from @jayzhan211's review there. No separate issue. This branch is stacked on apache#25658, so until that merges the diff here includes its commits. Only the last commit is new. ## Rationale for this change Hash joins on float keys get much slower as the build side grows. The comparator that checks key equality is built once per probe batch, and building it rewrites `-0.0` to `+0.0` across the whole build key column so that `-0.0 = 0.0` holds. That scan repeats for every probe batch even though the build side never changes, so a float-key join costs build rows times probe batches, while the same join on integer keys does not. ## What changes are included in this PR? - `collect_left_input` normalizes the build key columns once and keeps the result as the join's build keys. The in-list and bounds dynamic filters and the build-side null check still read the original keys, which they already did before this point. - A rewritten copy is only made when a column actually holds `-0.0`; otherwise the stored key shares the original buffer. Any copy is charged to the build-side memory reservation. - `JoinKeyComparator::new_with_normalized_left` and `equal_rows_arr_with_normalized_left` skip the build-side pass. Hash join's lookup uses them; sort-merge, piecewise merge, ASOF and symmetric hash joins keep the existing behavior. The query from the review, TPC-H SF1, `target_partitions = 1`, `HashJoinExec` `join_time`, median of five interleaved runs: ```sql SELECT count(*) FROM (SELECT l_orderkey AS k, CAST(l_quantity AS DOUBLE) AS q FROM lineitem WHERE l_orderkey < 1500000) b JOIN (SELECT l_orderkey AS k, CAST(l_quantity AS DOUBLE) AS q FROM lineitem) p ON b.k = p.k AND b.q = p.q; ``` | keys | before | after | |---|---|---| | `(BIGINT, DOUBLE)` | 96.4 ms | 25.7 ms | | `(BIGINT, BIGINT)` control | 24.9 ms | 24.8 ms | ## What is the testing strategy for this PR? New tests: - `join_key_comparator_with_normalized_left_skips_left_normalization` in `joins/utils.rs` pins the new constructor's contract. - `collect_left_input_stores_normalized_float_keys` checks that Float64 and Float32 build keys are stored with `+0.0` while the batch keeps `-0.0`, that no copy is made without `-0.0`, and that the copy is charged to the reservation. - `join_inner_single_float_key_negative_zero` covers a single float key with `-0.0` and `+0.0` on both sides, over batch sizes and both null equality modes. - `test_null_aware_left_anti_float_scope_negative_zero` covers both null-aware scope lookups with float scope keys. `join_inner_multi_key_float_zero_and_nulls_across_chunks` and the existing join tests and `joins`, `null_aware` and `subquery` sqllogictest files pass unchanged. ## Are there any user-facing changes? No.
1 parent cae7c61 commit 801b017

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
@@ -82,6 +82,7 @@ use datafusion_common::tree_node::{Transformed, TreeNode, TreeNodeRecursion};
8282
use datafusion_common::utils::memory::{
8383
RecordBatchMemoryCounter, estimate_memory_size, get_record_batch_memory_size,
8484
};
85+
use datafusion_common::utils::normalize_float_zero;
8586
use datafusion_common::{
8687
JoinSide, JoinType, NullEquality, Result, assert_or_internal_err, internal_err,
8788
plan_err, project_schema,
@@ -299,7 +300,11 @@ struct JoinBuildData {
299300
map: Arc<Map>,
300301
/// The input rows for the build side.
301302
batch: RecordBatch,
302-
/// Evaluated build-side key expressions.
303+
/// Evaluated build-side key expressions, with float `-0.0` rewritten to
304+
/// `+0.0` so probe batches can compare against them without scanning the
305+
/// build side again. The dynamic filters (`bounds`, `membership`) and
306+
/// `build_side_has_null` were computed from the original keys in
307+
/// `collect_left_input`.
303308
values: Vec<ArrayRef>,
304309
/// Bounds computed from the build side; absent for an empty partition.
305310
bounds: Option<PartitionBounds>,
@@ -370,7 +375,9 @@ impl JoinLeftData {
370375
!self.map().is_empty()
371376
}
372377

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

3218+
// Rewrite float `-0.0` to `+0.0` once here, so the per probe batch key
3219+
// comparison does not rescan the build side. Arrays without `-0.0`, and
3220+
// non-float keys, are shared rather than copied.
3221+
let normalized_values: Vec<ArrayRef> =
3222+
left_values.iter().map(normalize_float_zero).collect();
3223+
32113224
// Join keys that are plain columns share the buffers of `batch`, any other
32123225
// expression evaluates to new arrays that are kept for the whole join.
3226+
// The same goes for normalized keys: only a rewritten copy adds memory.
32133227
let mut key_counter = RecordBatchMemoryCounter::new();
32143228
key_counter.count_batch(&batch);
32153229
let keys_size = left_values
32163230
.iter()
3231+
.chain(&normalized_values)
32173232
.map(|values| key_counter.count_array(values.as_ref()))
32183233
.sum::<usize>();
32193234
reservation.try_grow(keys_size)?;
@@ -3276,7 +3291,7 @@ async fn collect_left_input(
32763291
let build_indices = UInt64Array::from_iter_values(
32773292
null_mask.values().set_indices().map(|i| i as u64),
32783293
);
3279-
let scope_values = left_values[1..]
3294+
let scope_values = normalized_values[1..]
32803295
.iter()
32813296
.map(|values| Ok(arrow::compute::filter(values.as_ref(), &null_mask)?))
32823297
.collect::<Result<Vec<_>>>()?;
@@ -3399,7 +3414,7 @@ async fn collect_left_input(
33993414
build: Arc::new(JoinBuildData {
34003415
map,
34013416
batch,
3402-
values: left_values,
3417+
values: normalized_values,
34033418
bounds,
34043419
membership,
34053420
reservation,
@@ -3488,11 +3503,11 @@ mod tests {
34883503

34893504
use arrow::array::{
34903505
Array, ArrayRef, AsArray, BinaryViewArray, Date32Array, DictionaryArray,
3491-
Float64Array, Int32Array, Int64Array, StringArray, StringViewArray, StructArray,
3492-
UInt32Array, UInt64Array,
3506+
Float32Array, Float64Array, Int32Array, Int64Array, StringArray, StringViewArray,
3507+
StructArray, UInt32Array, UInt64Array,
34933508
};
34943509
use arrow::buffer::NullBuffer;
3495-
use arrow::datatypes::{DataType, Field, Int32Type};
3510+
use arrow::datatypes::{DataType, Field, Float32Type, Float64Type, Int32Type};
34963511
use datafusion_common::hash_utils::create_hashes;
34973512
use datafusion_common::stats::Precision;
34983513
use datafusion_common::test_util::{batches_to_sort_string, batches_to_string};
@@ -4257,6 +4272,165 @@ mod tests {
42574272
Ok(())
42584273
}
42594274

4275+
/// Collects a single-column build side keyed on that column.
4276+
async fn collect_float_build(
4277+
keys: ArrayRef,
4278+
) -> Result<(JoinLeftData, BuildProbeJoinMetrics)> {
4279+
let schema = Arc::new(Schema::new(vec![Field::new(
4280+
"f",
4281+
keys.data_type().clone(),
4282+
true,
4283+
)]));
4284+
let batch = RecordBatch::try_new(Arc::clone(&schema), vec![keys])?;
4285+
let exec = TestMemoryExec::try_new_exec(&[vec![batch]], schema, None)?;
4286+
let stream = exec.execute(0, Arc::new(TaskContext::default()))?;
4287+
let pool: Arc<dyn MemoryPool> = Arc::new(UnboundedMemoryPool::default());
4288+
let metrics = BuildProbeJoinMetrics::new(0, &ExecutionPlanMetricsSet::new());
4289+
let on_left: Vec<PhysicalExprRef> = vec![Arc::new(Column::new("f", 0))];
4290+
let left_data = collect_left_input(
4291+
RandomState::with_seed(0),
4292+
stream,
4293+
on_left,
4294+
metrics.clone(),
4295+
MemoryConsumer::new("HashJoinInput").register(&pool),
4296+
false,
4297+
1,
4298+
false,
4299+
Arc::new(ConfigOptions::default()),
4300+
NullEquality::NullEqualsNothing,
4301+
None,
4302+
Count::new(),
4303+
BuildMode::Ordinary,
4304+
)
4305+
.await?;
4306+
Ok((left_data, metrics))
4307+
}
4308+
4309+
/// The stored build keys have `-0.0` rewritten to `+0.0`, while the build
4310+
/// batch keeps the original value. The rewritten copy is charged to the
4311+
/// build memory, and keys without `-0.0` are shared with the batch.
4312+
#[tokio::test]
4313+
async fn collect_left_input_stores_normalized_float_keys() -> Result<()> {
4314+
let (with_neg_zero, neg_metrics) =
4315+
collect_float_build(Arc::new(Float64Array::from(vec![-0.0, 1.0]))).await?;
4316+
let stored = with_neg_zero.values()[0].as_primitive::<Float64Type>();
4317+
assert_eq!(stored.value(0).to_bits(), 0.0_f64.to_bits());
4318+
assert_eq!(stored.value(1), 1.0);
4319+
let original = with_neg_zero
4320+
.batch()
4321+
.column(0)
4322+
.as_primitive::<Float64Type>();
4323+
assert_eq!(original.value(0).to_bits(), (-0.0_f64).to_bits());
4324+
4325+
let (without_neg_zero, pos_metrics) =
4326+
collect_float_build(Arc::new(Float64Array::from(vec![0.0, 1.0]))).await?;
4327+
assert!(Arc::ptr_eq(
4328+
&without_neg_zero.values()[0],
4329+
without_neg_zero.batch().column(0)
4330+
));
4331+
4332+
// Both builds are the same shape, so they differ only by the copy.
4333+
assert_eq!(
4334+
neg_metrics.build_mem_used.value(),
4335+
pos_metrics.build_mem_used.value() + stored.values().inner().capacity()
4336+
);
4337+
4338+
let (f32_build, _) =
4339+
collect_float_build(Arc::new(Float32Array::from(vec![-0.0_f32, 1.0])))
4340+
.await?;
4341+
let stored = f32_build.values()[0].as_primitive::<Float32Type>();
4342+
assert_eq!(stored.value(0).to_bits(), 0.0_f32.to_bits());
4343+
let original = f32_build.batch().column(0).as_primitive::<Float32Type>();
4344+
assert_eq!(original.value(0).to_bits(), (-0.0_f32).to_bits());
4345+
Ok(())
4346+
}
4347+
4348+
/// A single Float64 key takes the general comparator path. Build and
4349+
/// probe both hold `-0.0` and `0.0`, which must all match each other,
4350+
/// while the output keeps each side's original sign.
4351+
#[rstest]
4352+
#[tokio::test]
4353+
async fn join_inner_single_float_key_negative_zero(
4354+
#[values(8192, 1)] batch_size: usize,
4355+
#[values(NullEquality::NullEqualsNothing, NullEquality::NullEqualsNull)]
4356+
null_equality: NullEquality,
4357+
) -> Result<()> {
4358+
let task_ctx = prepare_task_ctx(batch_size, false);
4359+
4360+
let table = |suffix: &str,
4361+
f: Vec<Option<f64>>,
4362+
v: Vec<i32>|
4363+
-> Result<Arc<dyn ExecutionPlan>> {
4364+
let schema = Arc::new(Schema::new(vec![
4365+
Field::new(format!("f{suffix}"), DataType::Float64, true),
4366+
Field::new(format!("v{suffix}"), DataType::Int32, true),
4367+
]));
4368+
let batch = RecordBatch::try_new(
4369+
Arc::clone(&schema),
4370+
vec![
4371+
Arc::new(Float64Array::from(f)),
4372+
Arc::new(Int32Array::from(v)),
4373+
],
4374+
)?;
4375+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None)
4376+
.map(|exec| exec as _)
4377+
};
4378+
4379+
let left = table(
4380+
"1",
4381+
vec![Some(-0.0), Some(0.0), Some(1.5), None],
4382+
vec![10, 11, 12, 13],
4383+
)?;
4384+
let right = table(
4385+
"2",
4386+
vec![Some(0.0), Some(-0.0), Some(1.5), None],
4387+
vec![20, 21, 22, 23],
4388+
)?;
4389+
let on = vec![(
4390+
Arc::new(Column::new_with_schema("f1", &left.schema())?) as _,
4391+
Arc::new(Column::new_with_schema("f2", &right.schema())?) as _,
4392+
)];
4393+
4394+
let (_, batches, _) =
4395+
join_collect(left, right, on, &JoinType::Inner, null_equality, task_ctx)
4396+
.await?;
4397+
4398+
// The NULL keys only pair up when NULL equals NULL.
4399+
allow_duplicates! {
4400+
match null_equality {
4401+
NullEquality::NullEqualsNothing => {
4402+
assert_snapshot!(batches_to_sort_string(&batches), @r"
4403+
+------+----+------+----+
4404+
| f1 | v1 | f2 | v2 |
4405+
+------+----+------+----+
4406+
| -0.0 | 10 | -0.0 | 21 |
4407+
| -0.0 | 10 | 0.0 | 20 |
4408+
| 0.0 | 11 | -0.0 | 21 |
4409+
| 0.0 | 11 | 0.0 | 20 |
4410+
| 1.5 | 12 | 1.5 | 22 |
4411+
+------+----+------+----+
4412+
");
4413+
}
4414+
NullEquality::NullEqualsNull => {
4415+
assert_snapshot!(batches_to_sort_string(&batches), @r"
4416+
+------+----+------+----+
4417+
| f1 | v1 | f2 | v2 |
4418+
+------+----+------+----+
4419+
| | 13 | | 23 |
4420+
| -0.0 | 10 | -0.0 | 21 |
4421+
| -0.0 | 10 | 0.0 | 20 |
4422+
| 0.0 | 11 | -0.0 | 21 |
4423+
| 0.0 | 11 | 0.0 | 20 |
4424+
| 1.5 | 12 | 1.5 | 22 |
4425+
+------+----+------+----+
4426+
");
4427+
}
4428+
}
4429+
}
4430+
4431+
Ok(())
4432+
}
4433+
42604434
/// Two probe batches carry different multi-column keys at the same row
42614435
/// positions. Each batch has to be compared against its own key arrays;
42624436
/// a comparator left over from the first batch would drop the second
@@ -10425,6 +10599,96 @@ mod tests {
1042510599
Ok(())
1042610600
}
1042710601

10602+
/// Correlated null-aware `LeftAnti` whose two scope keys are Float64, with
10603+
/// `-0.0` on the build side and `0.0` on the probe side. Both scopes must
10604+
/// still match in every direction: the full key lookup, NULL probe values
10605+
/// against all build rows, and NULL build values against the probe rows.
10606+
#[apply(hash_join_exec_configs)]
10607+
#[tokio::test]
10608+
async fn test_null_aware_left_anti_float_scope_negative_zero(
10609+
batch_size: usize,
10610+
) -> Result<()> {
10611+
let task_ctx = prepare_task_ctx(batch_size, false);
10612+
10613+
fn table(
10614+
id: Vec<Option<i32>>,
10615+
g1: Vec<f64>,
10616+
g2: Vec<f64>,
10617+
) -> Arc<dyn ExecutionPlan> {
10618+
let schema = Arc::new(Schema::new(vec![
10619+
Field::new("id", DataType::Int32, true),
10620+
Field::new("g1", DataType::Float64, true),
10621+
Field::new("g2", DataType::Float64, true),
10622+
]));
10623+
let batch = RecordBatch::try_new(
10624+
Arc::clone(&schema),
10625+
vec![
10626+
Arc::new(Int32Array::from(id)),
10627+
Arc::new(Float64Array::from(g1)),
10628+
Arc::new(Float64Array::from(g2)),
10629+
],
10630+
)
10631+
.unwrap();
10632+
TestMemoryExec::try_new_exec(&[vec![batch]], schema, None).unwrap()
10633+
}
10634+
10635+
let left = table(
10636+
vec![Some(1), Some(3), None, Some(4), Some(5), None, Some(6)],
10637+
vec![-0.0, -0.0, -0.0, 2.0, -0.0, 3.0, 2.0],
10638+
vec![1.0, 1.0, 1.0, -0.0, -0.0, -0.0, 1.0],
10639+
);
10640+
let right = table(
10641+
vec![Some(1), Some(2), None, Some(7)],
10642+
vec![0.0, 0.0, 2.0, 2.0],
10643+
vec![1.0, 1.0, 0.0, 1.0],
10644+
);
10645+
10646+
let on = ["id", "g1", "g2"]
10647+
.into_iter()
10648+
.map(|name| {
10649+
Ok((
10650+
Arc::new(Column::new_with_schema(name, &left.schema())?) as _,
10651+
Arc::new(Column::new_with_schema(name, &right.schema())?) as _,
10652+
))
10653+
})
10654+
.collect::<Result<JoinOn>>()?;
10655+
10656+
let join = HashJoinExec::try_new(
10657+
left,
10658+
right,
10659+
on,
10660+
None,
10661+
&JoinType::LeftAnti,
10662+
None,
10663+
PartitionMode::CollectLeft,
10664+
NullEquality::NullEqualsNothing,
10665+
true,
10666+
)?;
10667+
10668+
let stream = join.execute(0, task_ctx)?;
10669+
let batches = common::collect(stream).await?;
10670+
10671+
// Scope (0, 1) holds 1 and 2: `1` matches and is dropped, `3` is kept,
10672+
// and the NULL build value there is UNKNOWN. Scope (2, 0) holds a
10673+
// NULL probe value, so `4` is UNKNOWN. Scopes (0, 0) and (3, 0) are
10674+
// empty, so `5` and the NULL build value in (3, 0) are kept. Scope
10675+
// (2, 1) holds only 7, so `6` is kept.
10676+
allow_duplicates! {
10677+
assert_snapshot!(batches_to_sort_string(&batches), @r"
10678+
+----+------+------+
10679+
| id | g1 | g2 |
10680+
+----+------+------+
10681+
| | 3.0 | -0.0 |
10682+
| 3 | -0.0 | 1.0 |
10683+
| 5 | -0.0 | -0.0 |
10684+
| 6 | 2.0 | 1.0 |
10685+
+----+------+------+
10686+
");
10687+
}
10688+
10689+
Ok(())
10690+
}
10691+
1042810692
#[test]
1042910693
fn test_lr_is_preserved() {
1043010694
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)