Jefffrey commented on code in PR #24419:
URL: https://github.com/apache/datafusion/pull/24419#discussion_r3826613809
##########
datafusion/functions-aggregate/src/percentile_cont.rs:
##########
@@ -816,6 +872,139 @@ where
}
}
+/// A trait to abstract interpolation logic for percentile calculation
+/// for floats and decimals.
+trait PercentileInterpolator<T: ArrowNumericType>: Debug + Sync + Send {
+ fn interpolate(
+ lower: T::Native,
+ upper: T::Native,
+ fraction: f64,
+ ) -> Result<T::Native>;
+}
+
+#[derive(Debug)]
+struct FloatInterpolator;
+
+/// Precision multiplier for floating-point linear interpolation calculations.
+///
+/// This value of 1,000,000 was chosen to balance precision with overflow
safety:
+/// - Provides 6 decimal places of precision for the fractional component
+/// - Small enough to avoid overflow when multiplied with typical numeric
values
+/// - Sufficient precision for most statistical applications
+///
+/// The interpolation formula: `lower + (upper - lower) * fraction`
+/// is computed as: `lower + ((upper - lower) * (fraction * PRECISION)) /
PRECISION`
+/// to avoid floating-point operations on integer types while maintaining
precision.
+///
+/// The interpolation arithmetic for floats is performed in f64 and then cast
back to the
+/// native type to avoid overflowing Float16 intermediates.
+const FLOAT_INTERPOLATION_PRECISION: f64 = 1_000_000.0;
+
+impl<T> PercentileInterpolator<T> for FloatInterpolator
+where
+ T: ArrowNumericType,
+ T::Native: AsPrimitive<f64>,
+ f64: AsPrimitive<T::Native>,
+{
+ fn interpolate(
+ lower: T::Native,
+ upper: T::Native,
+ fraction: f64,
+ ) -> Result<T::Native> {
+ // Linear interpolation.
+ // We compute a quantized interpolation weight using
`FLOAT_INTERPOLATION_PRECISION` because:
+ // 1. Both values come from the input data, so (upper - lower) is
bounded by the value range
+ // 2. fraction is between 0 and 1; quantizing it provides stable,
predictable results
+ // 3. The result is guaranteed to be between lower_value and
upper_value (modulo cast rounding)
+ // 4. Arithmetic is performed in f64 and cast back to avoid
overflowing Float16 intermediates
+ let scaled = (fraction * FLOAT_INTERPOLATION_PRECISION) as usize;
+ let weight = scaled as f64 / FLOAT_INTERPOLATION_PRECISION;
+
+ let lower_f: f64 = lower.as_();
+ let upper_f: f64 = upper.as_();
+ let interpolated_f = lower_f + (upper_f - lower_f) * weight;
+ Ok(interpolated_f.as_())
+ }
+}
+
+#[derive(Debug)]
+struct DecimalInterpolator;
+
+/// Precision multiplier for decimal linear interpolation calculations.
+fn deduce_interpolation_precision<T: DecimalType>() -> usize {
Review Comment:
i mainly ask since i had codex check some of the math and it mentioned some
edge cases where the wrong value can be returned, for example:
```sql
> SELECT percentile_cont(0.00009) WITHIN GROUP (ORDER BY v)
FROM (VALUES (arrow_cast(0, 'Decimal32(9,0)')), (arrow_cast(999999999,
'Decimal32(9,0)'))) as t (v);
+---------------------------------------------------------------------+
| percentile_cont(Float64(0.00009)) WITHIN GROUP [t.v ASC NULLS LAST] |
+---------------------------------------------------------------------+
| 0 |
+---------------------------------------------------------------------+
1 row(s) fetched.
Elapsed 0.010 seconds.
```
for reference, if done on float:
```sql
> SELECT percentile_cont(0.00009) WITHIN GROUP (ORDER BY v)
FROM (VALUES (0), (999999999)) as t (v);
+---------------------------------------------------------------------+
| percentile_cont(Float64(0.00009)) WITHIN GROUP [t.v ASC NULLS LAST] |
+---------------------------------------------------------------------+
| 89999.99991 |
+---------------------------------------------------------------------+
1 row(s) fetched.
Elapsed 0.010 seconds.
```
i havent looked too closely at the interpolation maths, but i wonder if this
is something we should try fix if possible? or can do in followup
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
