@@ -1836,6 +1836,7 @@ struct GroupEntry {
18361836/// BY bytes, capped at `k` distinct keys. Each key's `Vec<GroupEntry>`
18371837/// holds every row seen at that ob value, one entry per contributing
18381838/// source `RecordBatch`.
1839+ #[ derive( Default ) ]
18391840struct DenseRankPartitionState {
18401841 groups : HashMap < Vec < u8 > , Vec < GroupEntry > > ,
18411842 /// The same keys as `groups`, in a max-heap: the admission boundary
@@ -2061,13 +2062,10 @@ impl PartitionedTopKDenseRank {
20612062 // (within-call accumulation), then merge each bucket into the
20622063 // partition state as a single `GroupEntry`.
20632064 for ( pk, indices) in groups. drain ( ) {
2064- let state =
2065- self . states
2066- . entry ( pk)
2067- . or_insert_with ( || DenseRankPartitionState {
2068- groups : HashMap :: new ( ) ,
2069- keys : BinaryHeap :: with_capacity ( k) ,
2070- } ) ;
2065+ let state = self
2066+ . states
2067+ . entry ( pk)
2068+ . or_insert_with ( DenseRankPartitionState :: default) ;
20712069
20722070 // Bucket by ob key. `ob_runs` is a reused scratch map (taken
20732071 // out and drained below) so its backing table is allocated
@@ -4168,6 +4166,33 @@ mod tests {
41684166 Ok ( ( ) )
41694167 }
41704168
4169+ /// `keys` must grow on demand rather than reserve K slots when a
4170+ /// partition is first seen. `size()` charges `keys.capacity()`, so
4171+ /// eager sizing reserves O(partitions * K) for slots that never hold
4172+ /// a key — enough to fail a memory limit on a high-cardinality input
4173+ /// whose partitions each keep a handful of distinct values.
4174+ #[ tokio:: test]
4175+ async fn test_partitioned_topk_dense_rank_heap_grows_on_demand ( ) -> Result < ( ) > {
4176+ const K : usize = 512 ;
4177+ const PARTITIONS : usize = 64 ;
4178+ let ( schema, mut state) = build_partitioned_topk_dense_rank ( K ) ?;
4179+
4180+ // One row per partition: every partition holds exactly one
4181+ // distinct ob value, K - 1 slots short of capacity.
4182+ let pks: Vec < i32 > = ( 0 ..PARTITIONS as i32 ) . collect ( ) ;
4183+ let vals = pks. clone ( ) ;
4184+ state. insert_batch ( & pk_val_batch ( & schema, pks, vals) ?) ?;
4185+
4186+ assert_eq ! ( state. states. len( ) , PARTITIONS ) ;
4187+ let heap_slots: usize = state. states . values ( ) . map ( |s| s. keys . capacity ( ) ) . sum ( ) ;
4188+ // Eager `with_capacity(K)` would reserve PARTITIONS * K = 32768.
4189+ assert ! (
4190+ heap_slots <= PARTITIONS * 8 ,
4191+ "reserved {heap_slots} heap slots to hold {PARTITIONS} keys"
4192+ ) ;
4193+ Ok ( ( ) )
4194+ }
4195+
41714196 /// A group admitted and then evicted within the *same*
41724197 /// `insert_batch` call: the batch is still pending (not yet handed to
41734198 /// the store), so releasing it must decrement the in-flight use count
0 commit comments