xiangfu0 commented on code in PR #19015:
URL: https://github.com/apache/pinot/pull/19015#discussion_r3636311912
##########
pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/PercentileTDigestAccumulator.java:
##########
@@ -438,62 +544,113 @@ public double quantile(double quantile) {
}
double index = quantile * _totalWeight;
- if (index < _centroidWeights[0] / 2.0) {
- return _min + 2.0 * index / _centroidWeights[0] * (_centroidMeans[0] -
_min);
+ if (index < 1.0) {
+ return _min;
+ }
+ if (_centroidWeights[0] > 1.0 && index < _centroidWeights[0] / 2.0) {
+ return _min + (index - 1.0) / (_centroidWeights[0] / 2.0 - 1.0) *
(_centroidMeans[0] - _min);
}
- double weightSoFar = _centroidWeights[0] / 2.0;
int lastIndex = _numCentroids - 1;
+ if (index > _totalWeight - 1.0) {
+ return _max;
+ }
+ if (_centroidWeights[lastIndex] > 1.0
+ && _totalWeight - index <= _centroidWeights[lastIndex] / 2.0) {
+ return _max - (_totalWeight - index - 1.0) /
(_centroidWeights[lastIndex] / 2.0 - 1.0)
+ * (_max - _centroidMeans[lastIndex]);
+ }
+
+ double weightSoFar = _centroidWeights[0] / 2.0;
for (int i = 0; i < lastIndex; i++) {
double halfWeight = (_centroidWeights[i] + _centroidWeights[i + 1]) /
2.0;
if (weightSoFar + halfWeight > index) {
- double leftWeight = index - weightSoFar;
- double rightWeight = weightSoFar + halfWeight - index;
+ double leftUnitWeight = 0.0;
+ if (_centroidWeights[i] == 1.0) {
+ if (index - weightSoFar < 0.5) {
+ return _centroidMeans[i];
+ }
+ leftUnitWeight = 0.5;
+ }
+ double rightUnitWeight = 0.0;
+ if (_centroidWeights[i + 1] == 1.0) {
+ if (weightSoFar + halfWeight - index <= 0.5) {
+ return _centroidMeans[i + 1];
+ }
+ rightUnitWeight = 0.5;
+ }
+ double leftWeight = index - weightSoFar - leftUnitWeight;
+ double rightWeight = weightSoFar + halfWeight - index -
rightUnitWeight;
return weightedAverage(_centroidMeans[i], rightWeight,
_centroidMeans[i + 1], leftWeight);
}
weightSoFar += halfWeight;
}
- double leftWeight = index - _totalWeight - _centroidWeights[lastIndex] /
2.0;
- double rightWeight = _centroidWeights[lastIndex] / 2.0 - leftWeight;
- return weightedAverage(_centroidMeans[lastIndex], leftWeight, _max,
rightWeight);
+ double weightToMax = index - _totalWeight - _centroidWeights[lastIndex] /
2.0;
+ double weightFromLastCentroid = _centroidWeights[lastIndex] / 2.0 -
weightToMax;
+ return weightedAverage(_centroidMeans[lastIndex], weightToMax, _max,
weightFromLastCentroid);
}
private static double weightedAverage(double firstValue, double firstWeight,
double secondValue,
double secondWeight) {
if (firstValue > secondValue) {
return weightedAverage(secondValue, secondWeight, firstValue,
firstWeight);
}
+ if (firstWeight == 0.0) {
+ return secondValue;
+ }
+ if (secondWeight == 0.0 || firstValue == secondValue) {
+ return firstValue;
+ }
+ if (!Double.isFinite(firstValue)) {
+ return firstValue;
+ }
+ if (!Double.isFinite(secondValue)) {
+ return secondValue;
+ }
double average = (firstValue * firstWeight + secondValue * secondWeight) /
(firstWeight + secondWeight);
return Math.max(firstValue, Math.min(average, secondValue));
}
@Override
public Collection<Centroid> centroids() {
- return toTDigest().centroids();
+ compress();
+ List<Centroid> centroids = new ArrayList<>(_numCentroids);
+ for (int i = 0; i < _numCentroids; i++) {
+ centroids.add(Centroid.createWeighted(_centroidMeans[i],
Math.toIntExact((long) _centroidWeights[i]), null));
+ }
Review Comment:
Fixed in 5917db8 — `centroids()` now narrows with a plain `(int)` cast,
matching the library. Added
`testCentroidsSaturateWeightExceedingIntegerMaxValue`.
The underlying reason differs from the description, though: `Centroid` in
t-digest 3.3 stores the count as an `int`, not a `long` (`public int count()`,
`createWeighted(double, int, Iterable)`), so a weight above `Integer.MAX_VALUE`
cannot be represented at all. The actual divergence was the narrowing strategy:
`MergingDigest.centroids()` uses a plain `(int)` cast (`d2i`), which saturates
at `Integer.MAX_VALUE`, whereas this code used `Math.toIntExact`, which throws
`ArithmeticException`. Saturating now matches `MergingDigest` exactly.
##########
pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/PercentileTDigestAccumulator.java:
##########
@@ -429,7 +534,8 @@ public double quantile(double quantile) {
if (quantile < 0.0 || quantile > 1.0) {
throw new IllegalArgumentException("q should be in [0,1], got " +
quantile);
}
Review Comment:
Fixed in 5917db8. `quantile()` now rejects `NaN` using the same guard and
message as `NonFiniteAwareTDigest.quantile()`, so the two digest
implementations in this PR agree. Added `testQuantileRejectsNaN`.
One correction for the record: t-digest 3.3's own `MergingDigest.quantile()`
uses the same `q < 0 || q > 1` guard and therefore also lets `NaN` through
(verified in the 3.3 bytecode: `dcmpg`/`iflt` then `dcmpl`/`ifle`, both of
which fall through for `NaN`). So this change makes the accumulator *stricter*
than the library rather than restoring library behavior — consistency with
`NonFiniteAwareTDigest` is the intended contract here.
--
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]
