Skip to content

Commit c7e67c9

Browse files
committed
Update size allocation
1 parent afc931c commit c7e67c9

1 file changed

Lines changed: 99 additions & 2 deletions

File tree

  • datafusion/physical-plan/src/topk

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

Lines changed: 99 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -2226,22 +2226,39 @@ impl PartitionedTopKDenseRank {
22262226

22272227
/// Total memory currently held, including all per-partition states.
22282228
fn size(&self) -> usize {
2229+
// Per partition: the state itself plus the encoded partition key
2230+
// owned by the map. The key bytes are a heap allocation the table
2231+
// slot doesn't cover, and with wide or numerous partition keys
2232+
// they dominate the fixed-size slots.
2233+
let states_contents: usize = self
2234+
.states
2235+
.iter()
2236+
.map(|(pk, state)| pk.capacity() + state.size())
2237+
.sum();
2238+
// `partition_groups` and `ob_runs` are drained, not dropped, so
2239+
// their backing tables outlive every `insert_batch` call. Both are
2240+
// empty by the time `size()` runs (drained above), so only the
2241+
// retained capacity is charged.
2242+
let scratch_tables = self.partition_groups.capacity()
2243+
* (size_of::<Vec<u8>>() + size_of::<Vec<u32>>())
2244+
+ self.ob_runs.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<u32>>());
22292245
size_of::<Self>()
22302246
+ self.row_converter.size()
22312247
+ self.partition_converter.size()
22322248
+ self.scratch_rows.size()
22332249
+ self.partition_scratch_rows.size()
2234-
+ self.states.values().map(|s| s.size()).sum::<usize>()
2250+
+ states_contents
22352251
+ self.states.capacity()
22362252
* (size_of::<Vec<u8>>() + size_of::<DenseRankPartitionState>())
2253+
+ scratch_tables
22372254
+ self.store.size()
22382255
}
22392256
}
22402257

22412258
#[cfg(test)]
22422259
mod tests {
22432260
use super::*;
2244-
use arrow::array::{BooleanArray, Float64Array, Int32Array};
2261+
use arrow::array::{BooleanArray, Float64Array, Int32Array, StringArray};
22452262
use arrow::datatypes::{DataType, Field, Schema};
22462263
use arrow_schema::SortOptions;
22472264
use datafusion_common::assert_batches_eq;
@@ -4193,6 +4210,86 @@ mod tests {
41934210
Ok(())
41944211
}
41954212

4213+
/// The encoded partition keys owned by `states`, and the backing
4214+
/// tables the drained scratch maps keep, are long-lived heap
4215+
/// allocations `size()` must charge: they persist for the operator's
4216+
/// life yet belong to no `GroupEntry`, so per-entry accounting can't
4217+
/// see them. With numerous or wide partition keys the key bytes are
4218+
/// the larger term.
4219+
#[tokio::test]
4220+
async fn test_partitioned_topk_dense_rank_size_covers_keys_and_scratch() -> Result<()>
4221+
{
4222+
const PARTITIONS: usize = 64;
4223+
const KEY_WIDTH: usize = 1024;
4224+
4225+
let schema = Arc::new(Schema::new(vec![
4226+
Field::new("pk", DataType::Utf8, false),
4227+
Field::new("val", DataType::Int32, false),
4228+
]));
4229+
let pk_expr: Arc<dyn PhysicalExpr> = col("pk", schema.as_ref())?;
4230+
let partition_sort_fields = build_sort_fields(
4231+
&[PhysicalSortExpr {
4232+
expr: Arc::clone(&pk_expr),
4233+
options: SortOptions::default(),
4234+
}],
4235+
&schema,
4236+
)?;
4237+
let order_expr = LexOrdering::from([PhysicalSortExpr {
4238+
expr: col("val", schema.as_ref())?,
4239+
options: SortOptions::default(),
4240+
}]);
4241+
let mut state = PartitionedTopKDenseRank::try_new(
4242+
0,
4243+
Arc::clone(&schema),
4244+
vec![pk_expr],
4245+
partition_sort_fields,
4246+
order_expr,
4247+
4,
4248+
8, // batch_size
4249+
&Arc::new(RuntimeEnv::default()),
4250+
&ExecutionPlanMetricsSet::new(),
4251+
)?;
4252+
4253+
// One row per partition, each with a wide key.
4254+
let pks: Vec<String> = (0..PARTITIONS)
4255+
.map(|i| format!("{}{i:04}", "p".repeat(KEY_WIDTH - 4)))
4256+
.collect();
4257+
let vals: Vec<i32> = (0..PARTITIONS as i32).collect();
4258+
state.insert_batch(&RecordBatch::try_new(
4259+
Arc::clone(&schema),
4260+
vec![
4261+
Arc::new(StringArray::from(pks)),
4262+
Arc::new(Int32Array::from(vals)),
4263+
],
4264+
)?)?;
4265+
assert_eq!(state.states.len(), PARTITIONS);
4266+
4267+
let key_bytes: usize = state.states.keys().map(|pk| pk.capacity()).sum();
4268+
let scratch_bytes = state.partition_groups.capacity()
4269+
* (size_of::<Vec<u8>>() + size_of::<Vec<u32>>())
4270+
+ state.ob_runs.capacity() * (size_of::<Vec<u8>>() + size_of::<Vec<u32>>());
4271+
assert!(key_bytes >= PARTITIONS * KEY_WIDTH, "key bytes {key_bytes}");
4272+
assert!(scratch_bytes > 0, "scratch tables never allocated");
4273+
4274+
// Reconstruct the total from its parts. Both terms above have to
4275+
// appear for this to balance, so dropping either from `size()`
4276+
// fails here rather than being absorbed by the slack in some
4277+
// other term.
4278+
let expected = size_of::<PartitionedTopKDenseRank>()
4279+
+ state.row_converter.size()
4280+
+ state.partition_converter.size()
4281+
+ state.scratch_rows.size()
4282+
+ state.partition_scratch_rows.size()
4283+
+ key_bytes
4284+
+ state.states.values().map(|s| s.size()).sum::<usize>()
4285+
+ state.states.capacity()
4286+
* (size_of::<Vec<u8>>() + size_of::<DenseRankPartitionState>())
4287+
+ scratch_bytes
4288+
+ state.store.size();
4289+
assert_eq!(state.size(), expected);
4290+
Ok(())
4291+
}
4292+
41964293
/// A group admitted and then evicted within the *same*
41974294
/// `insert_batch` call: the batch is still pending (not yet handed to
41984295
/// the store), so releasing it must decrement the in-flight use count

0 commit comments

Comments
 (0)