This is an automated email from the ASF dual-hosted git repository.
tisonkun pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/datasketches-rust.git
The following commit(s) were added to refs/heads/main by this push:
new 6d62125 perf(kll): binary search sorted levels in rank queries (#308)
6d62125 is described below
commit 6d62125bad9ff1f26e1603f22eb7ca6c190f0d80
Author: Xuanwo <[email protected]>
AuthorDate: Tue Oct 27 18:06:56 2026 +0800
perf(kll): binary search sorted levels in rank queries (#308)
Co-authored-by: tison <[email protected]>
---
CHANGELOG.md | 1 +
datasketches/src/kll/sketch.rs | 45 ++++++++++++++++++++++---------
tests-integration/tests/kll_test/query.rs | 9 +++++++
3 files changed, 43 insertions(+), 12 deletions(-)
diff --git a/CHANGELOG.md b/CHANGELOG.md
index 90a93c4..53a9971 100644
--- a/CHANGELOG.md
+++ b/CHANGELOG.md
@@ -6,6 +6,7 @@ All significant changes to this project will be documented in
this file.
### Improvements
+* `KllSketch::rank` is faster for repeated queries on compacted sketches.
* `TDigest` and `TDigestMut` CDF and PMF batches are faster for many split
points; batches with sparse split points keep the original binary-search
behavior.
* `BloomFilter::insert` is faster for streams of new items when multiple
hashes are configured.
diff --git a/datasketches/src/kll/sketch.rs b/datasketches/src/kll/sketch.rs
index f90a07d..17e13cc 100644
--- a/datasketches/src/kll/sketch.rs
+++ b/datasketches/src/kll/sketch.rs
@@ -212,20 +212,24 @@ impl<T: Clone + Ord> KllSketch<T> {
if self.is_empty() {
return None;
}
- let inclusive = criteria == SearchCriteria::Inclusive;
- let mut weight = 0u64;
+ // Keep a direct scan to preserve query latency for small exact
sketches.
+ if let [items] = self.levels.as_slice() {
+ let count = count_rank_linear(items, item, criteria);
+ return Some(count as f64 / self.n as f64);
+ }
+
+ let mut rank_weight = 0u64;
for (level, items) in self.levels.iter().enumerate() {
- let count = items
- .iter()
- .filter(|retained| match (*retained).cmp(item) {
- Ordering::Less => true,
- Ordering::Equal => inclusive,
- Ordering::Greater => false,
- })
- .count() as u64;
- weight += count << level;
+ // Higher levels are always sorted; level zero may be an unsorted
update buffer.
+ let is_sorted = level > 0 || self.is_level_zero_sorted;
+ let count = if is_sorted {
+ count_rank_sorted(items, item, criteria)
+ } else {
+ count_rank_linear(items, item, criteria)
+ };
+ rank_weight += (count as u64) << level;
}
- Some(weight as f64 / self.n as f64)
+ Some(rank_weight as f64 / self.n as f64)
}
/// Returns the quantile for the given normalized rank.
@@ -920,6 +924,23 @@ impl<T: Clone + Ord> KllSketch<T> {
}
}
+fn count_rank_linear<T: Ord>(items: &[T], item: &T, criteria: SearchCriteria)
-> usize {
+ items
+ .iter()
+ .filter(|retained| match criteria {
+ SearchCriteria::Inclusive => *retained <= item,
+ SearchCriteria::Exclusive => *retained < item,
+ })
+ .count()
+}
+
+fn count_rank_sorted<T: Ord>(items: &[T], item: &T, criteria: SearchCriteria)
-> usize {
+ items.partition_point(|retained| match criteria {
+ SearchCriteria::Inclusive => retained <= item,
+ SearchCriteria::Exclusive => retained < item,
+ })
+}
+
fn normalized_rank_error(k: u16, pmf: bool) -> f64 {
let k = k as f64;
if pmf {
diff --git a/tests-integration/tests/kll_test/query.rs
b/tests-integration/tests/kll_test/query.rs
index aa303e3..ade962e 100644
--- a/tests-integration/tests/kll_test/query.rs
+++ b/tests-integration/tests/kll_test/query.rs
@@ -168,6 +168,15 @@ fn inclusive_and_exclusive_semantics_cover_duplicates() {
sketch.quantile(0.5, SearchCriteria::Exclusive).unwrap(),
Some(2)
);
+
+ // Equal values make the expected ranks independent of compaction sampling.
+ let mut compacted = KllSketch::<i64>::new(8).unwrap();
+ for _ in 0..9 {
+ compacted.update(1);
+ }
+ assert!(compacted.is_estimation_mode());
+ assert_eq!(compacted.rank(&1, SearchCriteria::Exclusive), Some(0.0));
+ assert_eq!(compacted.rank(&1, SearchCriteria::Inclusive), Some(1.0));
}
#[test]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
