You are viewing a plain text version of this content. The canonical link for it is here.

Posted to commits@pinot.apache.org by "xiangfu0 (via GitHub)" <gi...@apache.org> on 2026/07/15 18:42:02 UTC

[PR] [core] Optimize exact and TDigest percentile aggregation [pinot]

xiangfu0 opened a new pull request, #18996:
URL: https://github.com/apache/pinot/pull/18996

   ## Summary
   
   - replace exact-percentile full sorting with an introspective three-way rank selector
   - batch raw TDigest values and linearly merge them with sorted centroids instead of repeatedly indirect-sorting old centroids
   - normalize optimized TDigest state to the existing `MergingDigest` intermediate representation
   - add deterministic 100-million-row JMH benchmarks, correctness coverage, sample queries, and reproduction instructions
   
   ## Why
   
   Exact percentile previously sorted every retained value even though a query needs only one rank, making extraction
   `O(n log n)`. TDigest 3.2 profiling showed most raw aggregation time in its indirect quicksort/insertion-sort path,
   which re-sorts existing centroids whenever the input buffer is compressed.
   
   The exact path now uses three-way introselect with median/ninther pivoting and a bounded sort fallback. The TDigest path
   sorts only small primitive-double batches, linearly merges them with already-sorted centroids, and applies the same
   weight-limit rule as `MergingDigest`.
   
   There are no query, table configuration, intermediate serialization, or distributed merge changes. Group-by, serialized
   BYTES, and star-tree TDigest aggregation paths remain unchanged.
   
   ## Benchmark results
   
   Single-thread JMH 1.37 on an Apple M4 Pro with 24 GiB RAM and OpenJDK 21.0.10. Each workload processes 100 million
   deterministic doubles in 10,000-row Pinot blocks, with 2 forks and 5 measurements per fork.
   
   | Workload | Baseline | Optimized | Latency reduction | Speedup |
   |---|---:|---:|---:|---:|
   | Exact P75, fresh holder | 7,710.804 ms/op | 764.626 ms/op | 90.084% | 10.084x |
   | Exact P75, reused holder | 7,499.571 ms/op | 707.555 ms/op | 90.565% | 10.599x |
   | Exact P75 extraction | 7,448.796 ms/op | 618.253 ms/op | 91.700% | 12.048x |
   | TDigest P75 aggregation | 5,677.240 ms/op | 2,569.679 ms/op | 54.737% | 2.209x |
   
   Exact results match a fully sorted oracle bit-for-bit. Optimized TDigest P75 was `0.7499280847` versus exact
   `0.7499315464`, an absolute error of `0.0000034617`. These are aggregation-function measurements, not distributed
   end-to-end query latency.
   
   Full commands and sample SQL are recorded in
   `pinot-perf/benchmark-results/percentile-aggregation-100m-results.md`.
   
   ## Validation
   
   - `./mvnw spotless:apply -pl pinot-core,pinot-perf`
   - `./mvnw license:format -pl pinot-core,pinot-perf`
   - `./mvnw checkstyle:check -pl pinot-core,pinot-perf`
   - `./mvnw license:check -pl pinot-core,pinot-perf`
   - `./mvnw test-compile -pl pinot-core,pinot-perf -am -Dmaven.compiler.showDeprecation=true -Dmaven.compiler.showWarnings=true '-Dmaven.compiler.compilerArgs=-Xlint:all'`
   - `./mvnw -pl pinot-core -Dtest=PercentileAggregationFunctionTest,PercentileTDigestAggregationFunctionTest,InterSegmentAggregationMultiValueRawQueriesTest test` — 90 tests passed
   - broader TDigest query, MV, serialization, and star-tree suite — 42 tests passed
   


-- 
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: commits-unsubscribe@pinot.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org

Re: [PR] [core] Optimize exact and TDigest percentile aggregation, including StarTree group-by [pinot]

Posted by "Copilot (via GitHub)" <gi...@apache.org>.

Copilot commented on code in PR #18996:
URL: https://github.com/apache/pinot/pull/18996#discussion_r3591440895


##########
pinot-core/src/main/java/org/apache/pinot/core/query/aggregation/function/PercentileTDigestAggregationFunction.java:
##########
@@ -215,15 +205,9 @@ public void aggregateGroupByMV(int length, int[][] groupKeysArray, GroupByResult
       byte[][] bytesValues = blockValSet.getBytesValuesSV();
       forEachNotNull(length, blockValSet, (from, to) -> {
         for (int i = from; i < to; i++) {
-          TDigest value = ObjectSerDeUtils.TDIGEST_SER_DE.deserialize(bytesValues[i]);
           for (int groupKey : groupKeysArray[i]) {
-            TDigest tDigest = groupByResultHolder.getResult(groupKey);
-            if (tDigest != null) {
-              tDigest.add(value);
-            } else {
-              // Create a new TDigest for the group
-              groupByResultHolder.setValueForKey(groupKey, ObjectSerDeUtils.TDIGEST_SER_DE.deserialize(bytesValues[i]));
-            }
+            getSerializedAccumulator(groupByResultHolder, groupKey, bytesValues[i])
+                .addSerializedTDigest(bytesValues[i]);
           }

Review Comment:
   In the BYTES + group-by-MV path, the same serialized TDigest is parsed once per group key (`addSerializedTDigest(bytesValues[i])` inside the inner `for (int groupKey : groupKeysArray[i])`). This is a regression vs. the previous implementation that deserialized once per row and re-used the decoded representation across all group keys for that row. For multi-value group-bys with many keys per row, this can reintroduce significant per-row overhead and undermine the intended allocation/CPU savings of the serialized merge path.
   
   Consider decoding the serialized digest once per row and reusing the decoded centroids when merging into multiple groups (e.g., add an accumulator API that accepts already-decoded centroid arrays / a shared decode buffer, or a helper that decodes into temporary primitive arrays once and then merges them into each group accumulator).



-- 
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: commits-unsubscribe@pinot.apache.org

For queries about this service, please contact Infrastructure at:
users@infra.apache.org


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@pinot.apache.org
For additional commands, e-mail: commits-help@pinot.apache.org