Skip to content

Commit a74ed66

Browse files
committed
Replace max_keys with binaryHeap
1 parent 4530bba commit a74ed66

1 file changed

Lines changed: 30 additions & 37 deletions

File tree

  • datafusion/physical-plan/src/topk

‎datafusion/physical-plan/src/topk/mod.rs‎

Lines changed: 30 additions & 37 deletions
Original file line numberDiff line numberDiff line change
@@ -1819,14 +1819,13 @@ impl PartitionedTopKRank {
18191819
/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
18201820
struct DenseRankPartitionState {
18211821
groups: HashMap<Vec<u8>, Vec<TieEntry>>,
1822-
/// Cached admission boundary: the largest tracked ob value once
1823-
/// `groups` is full. A `HashMap` is unordered, so finding it otherwise
1824-
/// costs an O(K) scan of the keys on *every* new distinct ob value —
1825-
/// O(N·K) overall on mostly-distinct input. Caching makes the common
1826-
/// "new ob is worse than the boundary → drop" path O(1); the O(K) scan
1827-
/// is paid only when the cache is stale (`None`) — after a fill or an
1828-
/// eviction changes the key set.
1829-
max_key: Option<Vec<u8>>,
1822+
/// The same keys as `groups`, in a max-heap: the admission boundary
1823+
/// (the largest tracked ob value) is an O(1) `peek()` check, and
1824+
/// admission / removal are O(log K).
1825+
///
1826+
/// INVARIANT: `keys` and `groups.keys()` hold the same set. Every
1827+
/// insertion into / removal from `groups` must mirror into `keys`.
1828+
keys: BinaryHeap<Vec<u8>>,
18301829
}
18311830

18321831
impl DenseRankPartitionState {
@@ -1847,7 +1846,11 @@ impl DenseRankPartitionState {
18471846
.sum::<usize>()
18481847
})
18491848
.sum();
1850-
table_overhead + contents + self.max_key.as_ref().map_or(0, |k| k.capacity())
1849+
// `keys` duplicates every key's bytes; charge for them plus the
1850+
// heap's backing Vec (one `Vec<u8>` slot per reserved element).
1851+
let keys_overhead: usize = self.keys.capacity() * size_of::<Vec<u8>>()
1852+
+ self.keys.iter().map(|k| k.capacity()).sum::<usize>();
1853+
table_overhead + contents + keys_overhead
18511854
}
18521855
}
18531856

@@ -1878,8 +1881,8 @@ impl DenseRankPartitionState {
18781881
/// - `ob_key` new, `state.groups.len() < k` → insert the run as a new
18791882
/// group.
18801883
/// - `ob_key` new, `state.groups.len() == k` → the largest tracked ob
1881-
/// value is the admission boundary, cached in `max_key` (recomputed via
1882-
/// an O(K) scan of `state.groups.keys()` only when the cache is stale):
1884+
/// value is the admission boundary, read from the `state.keys` max-heap
1885+
/// in O(1):
18831886
/// - `ob_key < max` → remove the max key (evict the entire max-key
18841887
/// group — up to many rows) and insert the run. The evicted group's
18851888
/// row count is added to the `row_replacements` metric.
@@ -2033,7 +2036,7 @@ impl PartitionedTopKDenseRank {
20332036
.entry(pk)
20342037
.or_insert_with(|| DenseRankPartitionState {
20352038
groups: HashMap::new(),
2036-
max_key: None,
2039+
keys: BinaryHeap::with_capacity(k),
20372040
});
20382041

20392042
// Bucket by ob key. `ob_runs` is a reused scratch map (taken
@@ -2063,6 +2066,7 @@ impl PartitionedTopKDenseRank {
20632066

20642067
// Case B: new ob, room available.
20652068
if state.groups.len() < k {
2069+
state.keys.push(ob_key.clone());
20662070
state.groups.insert(
20672071
ob_key,
20682072
vec![TieEntry {
@@ -2071,34 +2075,23 @@ impl PartitionedTopKDenseRank {
20712075
batch_bytes: input_batch_bytes,
20722076
}],
20732077
);
2074-
// A new distinct key may raise the boundary; drop the
2075-
// cached max so it is recomputed on the next Case C.
2076-
state.max_key = None;
20772078
continue;
20782079
}
20792080

20802081
// Case C: new ob, at K distinct keys. The largest tracked
2081-
// ob value is the admission boundary; it is cached in
2082-
// `max_key` and recomputed via an O(K) scan only when the
2083-
// cache is stale, so the common "ob >= max → drop" path is
2084-
// O(1). Scoped so the immutable borrow ends before mutation.
2085-
if state.max_key.is_none() {
2086-
state.max_key = state.groups.keys().max().cloned();
2087-
}
2088-
let is_smaller = state
2089-
.max_key
2090-
.as_deref()
2091-
.map(|max_key| ob_key.as_slice() < max_key)
2092-
.expect("state.groups has k >= 1 keys");
2093-
2094-
if is_smaller {
2095-
// Evict the entire max-key group and drop the cached
2096-
// max (recomputed on the next Case C).
2097-
let evicted_key = state.max_key.take().expect("max key present");
2098-
let evicted =
2099-
state.groups.remove(&evicted_key).expect("max key present");
2082+
// ob value is the admission boundary.
2083+
let max_key = state.keys.peek().expect("state.groups has k >= 1 keys");
2084+
if ob_key.as_slice() < max_key.as_slice() {
2085+
// Evict the entire max-key group, from both the map
2086+
// and its ordered mirror.
2087+
let evicted_key = state.keys.pop().expect("max key present");
2088+
let evicted = state
2089+
.groups
2090+
.remove(&evicted_key)
2091+
.expect("keys mirrors groups");
21002092
replacements +=
21012093
evicted.iter().map(|e| e.row_indices.len()).sum::<usize>();
2094+
state.keys.push(ob_key.clone());
21022095
state.groups.insert(
21032096
ob_key,
21042097
vec![TieEntry {
@@ -2157,10 +2150,10 @@ impl PartitionedTopKDenseRank {
21572150
let mut coalescer = BatchCoalescer::new(Arc::clone(&schema), batch_size);
21582151

21592152
for pk in sorted_pks {
2160-
let DenseRankPartitionState { groups, max_key: _ } =
2153+
let DenseRankPartitionState { groups, keys: _ } =
21612154
states.remove(&pk).expect("key from states.keys()");
2162-
// HashMap is unordered — sort the <= K distinct ob keys so
2163-
// rows emit ascending (byte-comparable encoding == sort order).
2155+
// Sort the <= K distinct ob keys so rows emit ascending
2156+
// (byte-comparable encoding == sort order).
21642157
let mut sorted_obs: Vec<(Vec<u8>, Vec<TieEntry>)> =
21652158
groups.into_iter().collect();
21662159
sorted_obs.sort_by(|a, b| a.0.cmp(&b.0));

0 commit comments

Comments
 (0)