@@ -917,8 +917,9 @@ impl TopKMetrics {
917917/// paths bound that the same way — compact once the store holds this multiple
918918/// of what is still referenced — and only the denominator differs: one heap's
919919/// length in [`TopKHeap::maybe_compact`], every partition's retained rows
920- /// (heap slots, plus ties for `RANK`) in [`RecordBatchStore::compact`]. The
921- /// multiplier avoids compacting when the savings would be marginal.
920+ /// (heap slots, plus ties for `RANK` and groups for `DENSE_RANK`) in
921+ /// [`RecordBatchStore::compact`]. The multiplier avoids compacting when the
922+ /// savings would be marginal.
922923const STORE_COMPACTION_RATIO : usize = 2 ;
923924
924925/// This structure keeps at most the *smallest* k items, using the
@@ -2711,18 +2712,47 @@ impl DenseRankPartitionState {
27112712 + ( self . keys . capacity ( ) - heap_before) * size_of :: < Vec < u8 > > ( )
27122713 }
27132714
2714- /// Stop tracking the largest ob value, returning its rows, which the
2715- /// caller owes the store a release each for, and the bytes this freed.
2716- fn evict_max ( & mut self ) -> ( Vec < StoreRef > , usize ) {
2717- let heap_key = self . keys . pop ( ) . expect ( "a full partition holds k >= 1 keys" ) ;
2718- let ( map_key, rows) = self
2715+ /// Replace the largest tracked ob value with the smaller, previously
2716+ /// unseen `key`, holding the row at `at` as its only row, reusing the old
2717+ /// key buffers and letting `PeekMut` sift down, so a steady-state eviction
2718+ /// allocates nothing. Every old row goes back through `admission`.
2719+ fn replace_max ( & mut self , key : & [ u8 ] , at : StoreRef , admission : & mut Admission < ' _ > ) {
2720+ let table_before = self . groups . allocation_size ( ) ;
2721+ let mut heap_key = self
2722+ . keys
2723+ . peek_mut ( )
2724+ . expect ( "a full partition holds k >= 1 keys" ) ;
2725+ let ( mut map_key, mut rows) = self
27192726 . groups
2720- . remove_entry ( & heap_key)
2727+ . remove_entry ( heap_key. as_slice ( ) )
27212728 . expect ( "keys mirrors groups" ) ;
2722- let freed = heap_key. capacity ( )
2729+ // A group's rows from one batch sit next to each other, in arrival
2730+ // order, so each run of them drops its uses with one store lookup
2731+ // rather than one per row.
2732+ for run in rows. chunk_by ( |a, b| a. batch_id == b. batch_id ) {
2733+ admission. release_n ( run[ 0 ] . batch_id , run. len ( ) ) ;
2734+ }
2735+ admission. replacements += rows. len ( ) ;
2736+ admission. freed += heap_key. capacity ( )
2737+ + map_key. capacity ( )
2738+ + rows. capacity ( ) * size_of :: < StoreRef > ( ) ;
2739+
2740+ heap_key. clear ( ) ;
2741+ heap_key. extend_from_slice ( key) ;
2742+ map_key. clear ( ) ;
2743+ map_key. extend_from_slice ( key) ;
2744+ if rows. len ( ) == 1 {
2745+ rows[ 0 ] = at;
2746+ } else {
2747+ // Do not let a group that was large pin its capacity.
2748+ rows = vec ! [ at] ;
2749+ }
2750+ admission. grown += heap_key. capacity ( )
27232751 + map_key. capacity ( )
27242752 + rows. capacity ( ) * size_of :: < StoreRef > ( ) ;
2725- ( rows, freed)
2753+ drop ( heap_key) ;
2754+ self . groups . insert ( map_key, rows) ;
2755+ admission. grown += self . groups . allocation_size ( ) - table_before;
27262756 }
27272757}
27282758
@@ -2821,20 +2851,11 @@ impl PartitionedTopKDenseRank {
28212851 }
28222852 if let Some ( rows) = state. groups . get_mut ( key) {
28232853 admission. grown += push_slot ( rows, at) ;
2854+ } else if full {
2855+ // Every row of the boundary group, from this batch or
2856+ // earlier ones, now ranks below K.
2857+ state. replace_max ( key, at, admission) ;
28242858 } else {
2825- if full {
2826- // Every row of the boundary group, from this batch or
2827- // earlier ones, now ranks below K.
2828- let ( evicted, freed) = state. evict_max ( ) ;
2829- // A group's rows from one batch sit next to each other, in
2830- // arrival order, so each run of them drops its uses with
2831- // one store lookup rather than one per row.
2832- for run in evicted. chunk_by ( |a, b| a. batch_id == b. batch_id ) {
2833- admission. release_n ( run[ 0 ] . batch_id , run. len ( ) ) ;
2834- }
2835- admission. replacements += evicted. len ( ) ;
2836- admission. freed += freed;
2837- }
28382859 admission. grown += state. insert_group ( key, at) ;
28392860 }
28402861 true
0 commit comments