Skip to content

Commit 44db469

Browse files
neilconwaykosiew
authored andcommitted
perf: Optimize hashing, null-free fast path for percentile_cont, median (apache#23954)
## Which issue does this PR close? - Closes apache#23953 ## Rationale for this change This PR makes three improvements to non-distinct `PercentileContAccumulator` and `MedianAccumulator`, inspired by recent work on `percentile_cont(DISTINCT)` (apache#23946): 1. Switch from SipHash to foldhash for internal hash maps 2. Add a null-free fast path to `update_batch` and `retract_batch` 3. Raise an error if we attempt to retract an unknown value in `retract_batch`, rather than silently ignoring it. Benchmarks: percentile_cont no_nulls window=256 -61.1% (249.0 -> 96.6 us) percentile_cont with_nulls window=256 -59.4% (232.7 -> 94.5 us) percentile_cont no_nulls window=4096 -50.9% (756.3 -> 370.4 us) percentile_cont with_nulls window=4096 -48.2% (552.2 -> 286.2 us) percentile_cont no_nulls window=16384 -47.3% (2.311 -> 1.218 ms) percentile_cont with_nulls window=16384 -42.0% (1.465 -> 0.851 ms) median no_nulls window=256 -62.8% (247.0 -> 92.0 us) median with_nulls window=256 -59.8% (228.8 -> 92.0 us) median no_nulls window=4096 -40.0% (411.4 -> 246.6 us) median with_nulls window=4096 -39.4% (364.4 -> 221.0 us) median no_nulls window=16384 -31.5% (1.107 -> 0.759 ms) median with_nulls window=16384 -32.9% (0.947 -> 0.637 ms) ## What changes are included in this PR? See above. ## Are these changes tested? Yes: existing tests pass, new tests added for the null-free fast path and the improved error handling. ## Are there any user-facing changes? No.
1 parent fb75a61 commit 44db469

2 files changed

Lines changed: 155 additions & 13 deletions

File tree

‎datafusion/functions-aggregate/src/median.rs‎

Lines changed: 83 additions & 5 deletions
Original file line numberDiff line numberDiff line change
@@ -39,10 +39,11 @@ use arrow::datatypes::{
3939
ArrowNativeType, ArrowPrimitiveType, Decimal32Type, Decimal64Type, FieldRef,
4040
};
4141

42+
use datafusion_common::hash_utils::RandomState;
4243
use datafusion_common::types::{NativeType, logical_float64};
4344
use datafusion_common::{
4445
DataFusionError, Result, ScalarValue, assert_eq_or_internal_err, exec_datafusion_err,
45-
internal_datafusion_err,
46+
internal_datafusion_err, internal_err,
4647
};
4748
use datafusion_expr::function::StateFieldsArgs;
4849
use datafusion_expr::{
@@ -288,7 +289,12 @@ impl<T: ArrowNumericType> Accumulator for MedianAccumulator<T> {
288289
"failed to reserve {additional} values for median accumulator: {e}"
289290
)
290291
})?;
291-
self.all_values.extend(values.iter().flatten());
292+
if values.null_count() > 0 {
293+
self.all_values.extend(values.iter().flatten());
294+
} else {
295+
// Fast path: no nulls, so the values buffer can be appended wholesale.
296+
self.all_values.extend_from_slice(values.values());
297+
}
292298
Ok(())
293299
}
294300

@@ -310,11 +316,19 @@ impl<T: ArrowNumericType> Accumulator for MedianAccumulator<T> {
310316
}
311317

312318
fn retract_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
313-
let mut to_remove: HashMap<Hashable<T::Native>, usize> = HashMap::new();
319+
let mut to_remove: HashMap<Hashable<T::Native>, usize, RandomState> =
320+
HashMap::default();
314321

315322
let arr = values[0].as_primitive::<T>();
316-
for value in arr.iter().flatten() {
317-
*to_remove.entry(Hashable(value)).or_default() += 1;
323+
if arr.null_count() > 0 {
324+
for value in arr.iter().flatten() {
325+
*to_remove.entry(Hashable(value)).or_default() += 1;
326+
}
327+
} else {
328+
// Fast path: no nulls, so skip the per-element validity check.
329+
for value in arr.values().iter() {
330+
*to_remove.entry(Hashable(*value)).or_default() += 1;
331+
}
318332
}
319333

320334
let mut i = 0;
@@ -335,6 +349,15 @@ impl<T: ArrowNumericType> Accumulator for MedianAccumulator<T> {
335349
i += 1;
336350
}
337351
}
352+
353+
// Retracting values that are not tracked means the accumulator state
354+
// has diverged from the window frame; continuing would silently
355+
// produce wrong results, so surface it as an error.
356+
if !to_remove.is_empty() {
357+
return internal_err!(
358+
"median retract_batch: retracted value(s) not present in the window"
359+
);
360+
}
338361
Ok(())
339362
}
340363

@@ -627,3 +650,58 @@ fn calculate_median<T: ArrowNumericType>(values: &mut [T::Native]) -> Option<T::
627650
Some(*median)
628651
}
629652
}
653+
654+
#[cfg(test)]
655+
mod tests {
656+
use super::*;
657+
use arrow::array::Float64Array;
658+
659+
fn median_accumulator() -> MedianAccumulator<Float64Type> {
660+
MedianAccumulator {
661+
data_type: DataType::Float64,
662+
all_values: vec![],
663+
}
664+
}
665+
666+
#[test]
667+
fn retract_batch_errors_on_untracked_value() {
668+
let mut acc = median_accumulator();
669+
let values: ArrayRef = Arc::new(Float64Array::from(vec![1.0, 2.0]));
670+
acc.update_batch(std::slice::from_ref(&values)).unwrap();
671+
672+
let retract: ArrayRef = Arc::new(Float64Array::from(vec![3.0]));
673+
let err = acc
674+
.retract_batch(std::slice::from_ref(&retract))
675+
.unwrap_err()
676+
.to_string();
677+
assert!(
678+
err.contains("not present in the window"),
679+
"unexpected error: {err}"
680+
);
681+
}
682+
683+
#[test]
684+
fn update_batch_with_and_without_nulls_agree() {
685+
// The null-free fast path must accumulate the same values as the
686+
// general path.
687+
let dense: ArrayRef = Arc::new(Float64Array::from(vec![1.0, 2.0, 3.0]));
688+
let sparse: ArrayRef = Arc::new(Float64Array::from(vec![
689+
Some(1.0),
690+
None,
691+
Some(2.0),
692+
None,
693+
Some(3.0),
694+
]));
695+
696+
let mut dense_acc = median_accumulator();
697+
dense_acc
698+
.update_batch(std::slice::from_ref(&dense))
699+
.unwrap();
700+
let mut sparse_acc = median_accumulator();
701+
sparse_acc
702+
.update_batch(std::slice::from_ref(&sparse))
703+
.unwrap();
704+
705+
assert_eq!(dense_acc.all_values, sparse_acc.all_values);
706+
}
707+
}

‎datafusion/functions-aggregate/src/percentile_cont.rs‎

Lines changed: 72 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -429,7 +429,12 @@ where
429429
"failed to reserve {additional} values for percentile_cont accumulator: {e}"
430430
)
431431
})?;
432-
self.all_values.extend(values.iter().flatten());
432+
if values.null_count() > 0 {
433+
self.all_values.extend(values.iter().flatten());
434+
} else {
435+
// Fast path: no nulls, so the values buffer can be appended wholesale.
436+
self.all_values.extend_from_slice(values.values());
437+
}
433438
Ok(())
434439
}
435440

@@ -449,11 +454,19 @@ where
449454
}
450455

451456
fn retract_batch(&mut self, values: &[ArrayRef]) -> Result<()> {
452-
let mut to_remove: HashMap<Hashable<T::Native>, usize> = HashMap::new();
457+
let mut to_remove: HashMap<Hashable<T::Native>, usize, RandomState> =
458+
HashMap::default();
453459

454460
let arr = values[0].as_primitive::<T>();
455-
for value in arr.iter().flatten() {
456-
*to_remove.entry(Hashable(value)).or_default() += 1;
461+
if arr.null_count() > 0 {
462+
for value in arr.iter().flatten() {
463+
*to_remove.entry(Hashable(value)).or_default() += 1;
464+
}
465+
} else {
466+
// Fast path: no nulls, so skip the per-element validity check.
467+
for value in arr.values().iter() {
468+
*to_remove.entry(Hashable(*value)).or_default() += 1;
469+
}
457470
}
458471

459472
let mut i = 0;
@@ -474,6 +487,15 @@ where
474487
i += 1;
475488
}
476489
}
490+
491+
// Retracting values that are not tracked means the accumulator state
492+
// has diverged from the window frame; continuing would silently
493+
// produce wrong results, so surface it as an error.
494+
if !to_remove.is_empty() {
495+
return internal_err!(
496+
"percentile_cont retract_batch: retracted value(s) not present in the window"
497+
);
498+
}
477499
Ok(())
478500
}
479501

@@ -876,18 +898,60 @@ where
876898

877899
#[cfg(test)]
878900
mod tests {
879-
use super::calculate_percentile;
901+
use super::*;
902+
use arrow::array::Float64Array;
880903
use half::f16;
881904

905+
#[test]
906+
fn retract_batch_errors_on_untracked_value() {
907+
let mut acc = PercentileContAccumulator::<Float64Type>::new(0.5);
908+
let values: ArrayRef = Arc::new(Float64Array::from(vec![1.0, 2.0]));
909+
acc.update_batch(std::slice::from_ref(&values)).unwrap();
910+
911+
let retract: ArrayRef = Arc::new(Float64Array::from(vec![3.0]));
912+
let err = acc
913+
.retract_batch(std::slice::from_ref(&retract))
914+
.unwrap_err()
915+
.to_string();
916+
assert!(
917+
err.contains("not present in the window"),
918+
"unexpected error: {err}"
919+
);
920+
}
921+
922+
#[test]
923+
fn update_batch_with_and_without_nulls_agree() {
924+
// The null-free fast path must accumulate the same values as the
925+
// general path.
926+
let dense: ArrayRef = Arc::new(Float64Array::from(vec![1.0, 2.0, 3.0]));
927+
let sparse: ArrayRef = Arc::new(Float64Array::from(vec![
928+
Some(1.0),
929+
None,
930+
Some(2.0),
931+
None,
932+
Some(3.0),
933+
]));
934+
935+
let mut dense_acc = PercentileContAccumulator::<Float64Type>::new(0.5);
936+
dense_acc
937+
.update_batch(std::slice::from_ref(&dense))
938+
.unwrap();
939+
let mut sparse_acc = PercentileContAccumulator::<Float64Type>::new(0.5);
940+
sparse_acc
941+
.update_batch(std::slice::from_ref(&sparse))
942+
.unwrap();
943+
944+
assert_eq!(dense_acc.all_values, sparse_acc.all_values);
945+
}
946+
882947
#[test]
883948
fn f16_interpolation_does_not_overflow_to_nan() {
884949
// Regression test for https://github.com/apache/datafusion/issues/18945
885950
// Interpolating between 0 and the max finite f16 value previously overflowed
886951
// intermediate f16 computations and produced NaN.
887952
let mut values = vec![f16::from_f32(0.0), f16::from_f32(65504.0)];
888-
let result =
889-
calculate_percentile::<arrow::datatypes::Float16Type>(&mut values, 0.5)
890-
.expect("non-empty input");
953+
let result = calculate_percentile::<Float16Type>(&mut values, 0.5)
954+
.expect("non-empty input");
891955
let result_f = result.to_f32();
892956
assert!(
893957
!result_f.is_nan(),

0 commit comments

Comments
 (0)