avantgardnerio commented on code in PR #2294:
URL:
https://github.com/apache/datafusion-ballista/pull/2294#discussion_r3786726118
##########
ballista/core/src/kll.rs:
##########
@@ -477,15 +539,37 @@ 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> {
+ let total_weight = self.count();
+ if total_weight == 0 {
+ return None;
+ }
+ if rank == 0 {
+ return self.min.as_ref();
+ }
+ if rank >= total_weight {
+ return self.max.as_ref();
+ }
Review Comment:
> `at_rank` allocates and sorts the ~3k retained pairs per call, so
`cuts(P)` is O(P · m log m)
Correct, and left as is. The bench module doc carries the reason: at N=1M,
P=64, K=64 cuts, merge and quantile are 3+ orders of magnitude cheaper than
ingest, so this is not where the time goes. If a consumer ever calls `cuts` per
batch rather than per stage that changes, and the fix is to sort the pairs once
per `cuts` call instead of once per cut.
--
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]
