@@ -1819,14 +1819,13 @@ impl PartitionedTopKRank {
18191819/// `RecordBatch`. `TieEntry` is reused verbatim from [`RankPartitionState`].
18201820struct 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
18321831impl 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