Skip to content

Commit e0a4d3e

Browse files
committed
Adds replace max function
1 parent 5f96ec4 commit e0a4d3e

1 file changed

Lines changed: 44 additions & 23 deletions

File tree

  • datafusion/physical-plan/src/topk

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

Lines changed: 44 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -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.
922923
const 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

Comments
 (0)