Skip to content

Commit afc931c

Browse files
committed
Remove eager heap allocation
1 parent 8e97623 commit afc931c

1 file changed

Lines changed: 32 additions & 7 deletions

File tree

  • datafusion/physical-plan/src/topk

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

Lines changed: 32 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -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)]
18391840
struct 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

Comments
 (0)