avantgardnerio commented on code in PR #2294:
URL:
https://github.com/apache/datafusion-ballista/pull/2294#discussion_r3786994155
##########
ballista/core/src/kll.rs:
##########
@@ -477,15 +544,50 @@ impl<T: Ord + Clone> KllSketch<T> {
if q == 1.0 {
return self.max.as_ref();
}
- let total_weight: u64 = self
- .levels
- .iter()
- .enumerate()
- .map(|(h, level)| (1u64 << h) * level.len() as u64)
- .sum();
+ let total_weight = self.count();
if total_weight == 0 {
return None;
}
+ self.at_rank((q * total_weight as f64) as u64)
+ }
+
+ /// Return the item at `rank`, counting cumulative weight from the
+ /// smallest item up. `None` if the sketch is empty.
+ ///
+ /// Semantics: the smallest retained item whose cumulative weight is at
+ /// least `rank`. Ranks at or beyond the ends give the tracked extremes,
+ /// which bypass the compactor so coin-flip history can't move them.
+ ///
+ /// This is the primitive [`Self::quantile`] is expressed in, and the
+ /// one to prefer whenever the caller already knows the rank it wants.
+ /// Converting a known rank into a fraction and back loses it: for 99
+ /// items, rank 59 becomes `59/99`, and multiplying that back by 99
+ /// yields `58.999…`, which truncates to 58. Callers that adjust a rank
+ /// — stepping over a run of NULLs, say — must stay in integers.
+ pub fn at_rank(&self, rank: u64) -> Option<&T> {
+ self.at_ranks(&[rank]).into_iter().next().flatten()
+ }
+
+ /// Answer several ranks against one pass over the retained items,
+ /// returning one answer per entry of `ranks`, positionally.
+ ///
+ /// Semantics per rank are [`Self::at_rank`]'s exactly. The difference is
+ /// cost: resolving a rank means materializing every retained item with
+ /// its level weight and sorting them, and that work does not depend on
+ /// the rank. Asking one at a time repeats it per rank, which makes
+ /// `cuts` over P partitions P-1 sorts of the whole retained set. Here it
+ /// happens once.
+ ///
+ /// `ranks` may be in any order; the answers come back in the order
+ /// asked. Internally they are walked smallest-first so a single
+ /// cumulative sweep serves all of them.
+ pub fn at_ranks(&self, ranks: &[u64]) -> Vec<Option<&T>> {
Review Comment:
> `at_rank` allocates and sorts the ~3k retained pairs per call, so
`cuts(P)` is O(P · m log m)
> Negligible against ingest, and pre-existing in shape.
Benched it rather than taking that on faith, and it was not negligible.
`runtime_stats_cuts` is new and measures cut extraction against the ingest that
built the sketch:
| n | `cuts(64)` | `cuts(256)` |
|---|---|---|
| 100K | 30% of ingest | 123% of ingest |
| 1M | 1.7% of ingest | 6.8% of ingest |
It scales the wrong way too: a smaller stage has less ingest to hide the
sorts behind, so `cuts(256)` at 100K cost more than building the sketch did.
`KllSketch::at_ranks` now resolves a whole batch against one sorted pass,
and `SortKeySketch::cuts` makes a single call. At n=1M that takes `cuts(256)`
from 1.13 ms to 16.6 µs and `cuts(64)` from 279 µs to 7.56 µs, leaving cut
extraction at 0.045% of ingest. The P-dependence is close to flat now, since
only the scatter over the answers grows with P.
--
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]
