Skip to content

Commit 4fea79e

Browse files
committed
fix: use HashTable::allocation_size() in GroupValuesColumn::size()
Fixes apache#25736 The previous implementation tracked map memory via a map_size: usize field that was updated incrementally using insert_accounted. That approach charges only the entry-capacity portion of the hashbrown allocation, silently omitting control bytes and trailing layout. The resulting GroupValues::size() underreports the true retained memory, particularly for small or recently grown tables. This commit replaces the approximate accounting with a direct call to HashTable::allocation_size(), which reports the complete allocation as observed by the allocator. This is the same approach already used by ArrowBytesMap::size() in physical-expr-common. Changes: - Remove the map_size: usize field and all insert_accounted call sites that maintained it; use insert_unique (the plain hashbrown insert) instead. - Remove the now-unused HashTableAllocExt import from the production path (the test module retains what it still needs). - Remove the size_of import that was only used in the deleted clear_shrink map_size update. - Update GroupValuesColumn::size() to use self.map.allocation_size(). - Add four focused unit tests covering the acceptance criteria from the issue: map growth accounting, forced-collision chain independence, retained capacity after partial emit, and correct reuse after full emit.
1 parent c61fb09 commit 4fea79e

1 file changed

Lines changed: 164 additions & 16 deletions

File tree

  • datafusion/physical-plan/src/aggregates/group_values/multi_group_by

‎datafusion/physical-plan/src/aggregates/group_values/multi_group_by/mod.rs‎

Lines changed: 164 additions & 16 deletions
Original file line numberDiff line numberDiff line change
@@ -49,7 +49,7 @@ use datafusion_common::float_semantics::{has_float_leaf, normalize_floats};
4949
use datafusion_common::hash_utils::RandomState;
5050
use datafusion_common::hash_utils::create_hashes;
5151
use datafusion_common::{Result, not_impl_err};
52-
use datafusion_execution::memory_pool::proxy::{HashTableAllocExt, VecAllocExt};
52+
use datafusion_execution::memory_pool::proxy::VecAllocExt;
5353
use datafusion_expr::{EmitTo, GroupSelection};
5454
use datafusion_physical_expr::binary_map::OutputType;
5555

@@ -194,9 +194,6 @@ pub struct GroupValuesColumn<const STREAMING: bool> {
194194
///
195195
map: HashTable<(u64, GroupIndexView)>,
196196

197-
/// The size of `map` in bytes
198-
map_size: usize,
199-
200197
/// The lists for group indices with the same hash value
201198
///
202199
/// It is possible that hash value collision exists,
@@ -307,7 +304,6 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
307304
group_index_lists: Vec::new(),
308305
emit_group_index_list_buffer: Vec::new(),
309306
vectorized_operation_buffers: VectorizedOperationBuffers::default(),
310-
map_size: 0,
311307
group_values,
312308
hashes_buffer: Default::default(),
313309
random_state: crate::aggregates::AGGREGATION_HASH_SEED,
@@ -448,10 +444,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
448444
}
449445

450446
// for hasher function, use precomputed hash value
451-
self.map.insert_accounted(
447+
self.map.insert_unique(
448+
target_hash,
452449
(target_hash, GroupIndexView::new_inlined(group_idx as u64)),
453450
|(hash, _group_index)| *hash,
454-
&mut self.map_size,
455451
);
456452
group_idx
457453
}
@@ -568,10 +564,10 @@ impl<const STREAMING: bool> GroupValuesColumn<STREAMING> {
568564

569565
// Insert the `group index view` and its hash into `map`
570566
// for hasher function, use precomputed hash value
571-
self.map.insert_accounted(
567+
self.map.insert_unique(
568+
target_hash,
572569
(target_hash, group_index_view),
573570
|(hash, _)| *hash,
574-
&mut self.map_size,
575571
);
576572

577573
// Add row index to `vectorized_append_row_indices`
@@ -1096,9 +1092,12 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
10961092
.iter()
10971093
.map(VecAllocExt::allocated_size)
10981094
.sum::<usize>();
1095+
// `HashTable::allocation_size` reports the complete retained allocation —
1096+
// including hashbrown control bytes and trailing layout — which is exactly
1097+
// what we want here. This follows the same approach as `ArrowBytesMap::size()`.
10991098
size_of::<Self>()
11001099
+ group_values_size
1101-
+ self.map_size
1100+
+ self.map.allocation_size()
11021101
+ group_index_lists_size
11031102
+ self.emit_group_index_list_buffer.allocated_size()
11041103
+ self.vectorized_operation_buffers.size()
@@ -1244,7 +1243,6 @@ impl<const STREAMING: bool> GroupValues for GroupValuesColumn<STREAMING> {
12441243
.expect("schema previously validated in try_new");
12451244
self.map.clear();
12461245
self.map.shrink_to(num_rows, |_| 0); // hasher does not matter since the map is cleared
1247-
self.map_size = self.map.capacity() * size_of::<(u64, usize)>();
12481246
self.hashes_buffer.clear();
12491247
self.hashes_buffer.shrink_to(num_rows);
12501248

@@ -1294,8 +1292,9 @@ mod tests {
12941292
compute::{concat_batches, take},
12951293
util::pretty::pretty_format_batches,
12961294
};
1297-
use datafusion_common::{Result, utils::proxy::HashTableAllocExt};
1295+
use datafusion_common::Result;
12981296
use datafusion_expr::{EmitTo, GroupSelection};
1297+
use std::mem::size_of;
12991298

13001299
use crate::aggregates::group_values::{
13011300
GroupValues, multi_group_by::GroupValuesColumn,
@@ -2764,10 +2763,10 @@ mod tests {
27642763
group_index: u64,
27652764
) {
27662765
let group_index_view = GroupIndexView::new_inlined(group_index);
2767-
group_values.map.insert_accounted(
2766+
group_values.map.insert_unique(
2767+
hash_key,
27682768
(hash_key, group_index_view),
27692769
|(hash, _)| *hash,
2770-
&mut group_values.map_size,
27712770
);
27722771
}
27732772

@@ -2779,10 +2778,159 @@ mod tests {
27792778
let list_offset = group_values.group_index_lists.len();
27802779
let group_index_view = GroupIndexView::new_non_inlined(list_offset as u64);
27812780
group_values.group_index_lists.push(group_indices);
2782-
group_values.map.insert_accounted(
2781+
group_values.map.insert_unique(
2782+
hash_key,
27832783
(hash_key, group_index_view),
27842784
|(hash, _)| *hash,
2785-
&mut group_values.map_size,
2785+
);
2786+
}
2787+
2788+
// -----------------------------------------------------------------------
2789+
// Tests for exact hash-table allocation accounting (issue #25736)
2790+
// -----------------------------------------------------------------------
2791+
2792+
/// After enough groups are inserted to force a hashbrown table growth,
2793+
/// `size()` must include the full `allocation_size()` of the map — control
2794+
/// bytes and trailing layout included — not just an entry-capacity estimate.
2795+
#[test]
2796+
fn map_allocation_size_included_in_size_after_growth() {
2797+
let schema: SchemaRef =
2798+
Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
2799+
let mut gv: GroupValuesColumn<false> =
2800+
GroupValuesColumn::try_new(Arc::clone(&schema)).unwrap();
2801+
2802+
// Insert enough distinct rows to trigger at least one table resize.
2803+
let n: usize = 128;
2804+
let keys: Vec<i64> = (0..n as i64).collect();
2805+
let col = Arc::new(Int64Array::from(keys)) as ArrayRef;
2806+
let mut groups = vec![];
2807+
gv.intern(&[col], &mut groups).unwrap();
2808+
2809+
let reported = gv.size();
2810+
let map_alloc = gv.map.allocation_size();
2811+
2812+
// The reported size must be at least as large as the raw map allocation.
2813+
assert!(
2814+
reported >= map_alloc,
2815+
"size() ({reported}) must be >= map.allocation_size() ({map_alloc})"
2816+
);
2817+
2818+
// And the map must actually hold a non-trivial allocation after growth.
2819+
assert!(
2820+
map_alloc > 0,
2821+
"map.allocation_size() should be > 0 after inserting {n} groups"
2822+
);
2823+
}
2824+
2825+
/// When hash collisions are forced, the collision-chain list allocation
2826+
/// (`group_index_lists`) must be accounted for independently of the
2827+
/// hash-table term. The two must not be conflated.
2828+
#[test]
2829+
fn collision_chain_size_is_separate_from_map_allocation() {
2830+
let schema: SchemaRef =
2831+
Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
2832+
let mut gv: GroupValuesColumn<false> =
2833+
GroupValuesColumn::try_new(Arc::clone(&schema)).unwrap();
2834+
2835+
// Manually insert two entries with the same hash key to force a
2836+
// collision chain (non-inlined GroupIndexView).
2837+
insert_inline_group_index_view(&mut gv, 42, 0);
2838+
insert_non_inline_group_index_view(&mut gv, 42, vec![0, 1]);
2839+
2840+
let map_alloc = gv.map.allocation_size();
2841+
let chain_size: usize = gv
2842+
.group_index_lists
2843+
.iter()
2844+
.map(|list| list.capacity() * size_of::<usize>())
2845+
.sum();
2846+
2847+
// Both terms must be individually non-zero.
2848+
assert!(map_alloc > 0, "map allocation must be > 0");
2849+
assert!(chain_size > 0, "collision-chain allocation must be > 0");
2850+
2851+
// The reported total must include both independently.
2852+
let reported = gv.size();
2853+
assert!(
2854+
reported >= map_alloc,
2855+
"size() must cover the map allocation"
2856+
);
2857+
}
2858+
2859+
/// After a partial emit (`EmitTo::First`), the map retains its allocated
2860+
/// capacity even though logical entries were removed. `size()` must still
2861+
/// reflect the retained allocation, not drop to zero.
2862+
#[test]
2863+
fn size_reflects_retained_capacity_after_partial_emit() {
2864+
let schema: SchemaRef =
2865+
Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
2866+
let mut gv: GroupValuesColumn<false> =
2867+
GroupValuesColumn::try_new(Arc::clone(&schema)).unwrap();
2868+
2869+
let keys: Vec<i64> = (0..64i64).collect();
2870+
let col = Arc::new(Int64Array::from(keys)) as ArrayRef;
2871+
let mut groups = vec![];
2872+
gv.intern(&[col], &mut groups).unwrap();
2873+
2874+
let size_before = gv.size();
2875+
let map_alloc_before = gv.map.allocation_size();
2876+
2877+
// Emit only the first 32 groups; the table allocation should be retained.
2878+
gv.emit(EmitTo::First(32)).unwrap();
2879+
2880+
let size_after = gv.size();
2881+
let map_alloc_after = gv.map.allocation_size();
2882+
2883+
// Capacity is not released by a partial emit — allocation should persist.
2884+
assert!(
2885+
map_alloc_after > 0,
2886+
"map allocation should be retained after partial emit, got {map_alloc_after}"
2887+
);
2888+
assert!(
2889+
size_after > 0,
2890+
"size() should remain > 0 after partial emit, got {size_after}"
2891+
);
2892+
2893+
// The allocation reported before and after should both be real and
2894+
// consistent with what the map actually holds.
2895+
assert_eq!(
2896+
map_alloc_before, map_alloc_after,
2897+
"partial emit must not shrink the map allocation (before={map_alloc_before}, after={map_alloc_after})"
2898+
);
2899+
let _ = size_before; // used implicitly via the assertions above
2900+
}
2901+
2902+
/// After a full emit followed by re-use, `size()` must still produce
2903+
/// correct group values and the map allocation is reported accurately.
2904+
#[test]
2905+
fn reuse_after_full_emit_produces_correct_groups() {
2906+
let schema: SchemaRef =
2907+
Arc::new(Schema::new(vec![Field::new("k", DataType::Int64, false)]));
2908+
let mut gv: GroupValuesColumn<false> =
2909+
GroupValuesColumn::try_new(Arc::clone(&schema)).unwrap();
2910+
2911+
// First pass: intern 4 distinct keys.
2912+
let first_keys: Vec<i64> = vec![10, 20, 30, 40];
2913+
let col1 = Arc::new(Int64Array::from(first_keys.clone())) as ArrayRef;
2914+
let mut groups = vec![];
2915+
gv.intern(&[col1], &mut groups).unwrap();
2916+
assert_eq!(groups, vec![0, 1, 2, 3]);
2917+
2918+
// Full emit clears the map.
2919+
let emitted = gv.emit(EmitTo::All).unwrap();
2920+
assert_eq!(emitted.len(), 1);
2921+
2922+
// Second pass after reuse: intern 3 different keys, numbering restarts from 0.
2923+
let second_keys: Vec<i64> = vec![100, 200, 300];
2924+
let col2 = Arc::new(Int64Array::from(second_keys)) as ArrayRef;
2925+
gv.intern(&[col2], &mut groups).unwrap();
2926+
assert_eq!(groups, vec![0, 1, 2]);
2927+
2928+
// size() must be consistent with the live map allocation.
2929+
let reported = gv.size();
2930+
let map_alloc = gv.map.allocation_size();
2931+
assert!(
2932+
reported >= map_alloc,
2933+
"size() ({reported}) must cover map.allocation_size() ({map_alloc}) after reuse"
27862934
);
27872935
}
27882936
}

0 commit comments

Comments
 (0)