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: [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]
