Skip to content

Commit 7c1dcb5

Browse files
Rachel IntRachel Int
authored andcommitted
perf: grow StringView group payloads in progressive blocks
1 parent 89dc47d commit 7c1dcb5

2 files changed

Lines changed: 59 additions & 40 deletions

File tree

‎datafusion/physical-expr-common/src/binary_view_map.rs‎

Lines changed: 43 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -30,8 +30,12 @@ use datafusion_common::hash_utils::create_hashes;
3030
use datafusion_common::utils::proxy::VecAllocExt;
3131
use datafusion_common::{Result, exec_err};
3232
use std::fmt::Debug;
33+
use std::mem;
3334
use std::sync::Arc;
3435

36+
const BYTE_VIEW_STARTING_BLOCK_SIZE: usize = 8 * 1024;
37+
const BYTE_VIEW_MAX_BLOCK_SIZE: usize = 2 * 1024 * 1024;
38+
3539
/// HashSet optimized for storing string or binary values that can produce that
3640
/// the final set as a `GenericBinaryViewArray` with minimal copies.
3741
#[derive(Debug)]
@@ -125,9 +129,6 @@ impl ArrowBytesViewSet {
125129
/// This map is used by the special `COUNT DISTINCT` aggregate function to
126130
/// store the distinct values, and by the `GROUP BY` operator to store
127131
/// group values when they are a single string array.
128-
/// Max size of the in-progress buffer before flushing to completed buffers
129-
const BYTE_VIEW_MAX_BLOCK_SIZE: usize = 2 * 1024 * 1024;
130-
131132
pub struct ArrowBytesViewMap<V>
132133
where
133134
V: Debug + PartialEq + Eq + Clone + Copy + Default,
@@ -147,6 +148,9 @@ where
147148
in_progress: Vec<u8>,
148149
/// Completed buffers containing string data
149150
completed: Vec<Buffer>,
151+
/// Allocation target, doubled for each new payload block up to 2 MiB.
152+
/// Zero keeps lazy payload growth for the small per-group distinct maps.
153+
block_size: usize,
150154

151155
/// random state used to generate hashes
152156
random_state: RandomState,
@@ -191,6 +195,11 @@ where
191195
views: Vec::new(),
192196
in_progress: Vec::new(),
193197
completed: Vec::new(),
198+
block_size: if map_capacity == 0 {
199+
0
200+
} else {
201+
BYTE_VIEW_STARTING_BLOCK_SIZE
202+
},
194203
random_state: RandomState::default(),
195204
hashes_buffer: vec![],
196205
null: None,
@@ -199,6 +208,9 @@ where
199208

200209
/// Reserves group slots without preallocating variable-length string payloads.
201210
pub fn reserve_groups(&mut self, capacity: usize) {
211+
if self.block_size == 0 && capacity != 0 {
212+
self.block_size = BYTE_VIEW_STARTING_BLOCK_SIZE;
213+
}
202214
self.map
203215
.reserve(capacity.saturating_sub(self.map.len()), |entry| entry.hash);
204216
self.views
@@ -208,16 +220,16 @@ where
208220
}
209221

210222
/// Emits keys, retains the hash table and scratch buffer, and reserves fixed
211-
/// view capacity. Payload buffers keep their normal block size and growth.
223+
/// view capacity. Payload blocks restart their exponential allocation growth.
212224
pub fn take_with_capacity(&mut self, capacity: usize) -> ArrayRef {
213225
let mut outgoing = Self::new(self.output_type);
214-
std::mem::swap(self, &mut outgoing);
215-
std::mem::swap(&mut self.map, &mut outgoing.map);
226+
mem::swap(self, &mut outgoing);
227+
mem::swap(&mut self.map, &mut outgoing.map);
216228
self.map.clear();
217-
std::mem::swap(&mut self.hashes_buffer, &mut outgoing.hashes_buffer);
229+
mem::swap(&mut self.hashes_buffer, &mut outgoing.hashes_buffer);
218230
self.hashes_buffer.clear();
219231
self.initial_map_capacity = outgoing.initial_map_capacity;
220-
std::mem::swap(&mut self.random_state, &mut outgoing.random_state);
232+
mem::swap(&mut self.random_state, &mut outgoing.random_state);
221233
self.reserve_groups(capacity);
222234
outgoing.into_state()
223235
}
@@ -227,7 +239,7 @@ where
227239
pub fn take(&mut self) -> Self {
228240
let mut new_self =
229241
Self::with_capacity(self.output_type, self.initial_map_capacity);
230-
std::mem::swap(self, &mut new_self);
242+
mem::swap(self, &mut new_self);
231243
new_self
232244
}
233245

@@ -470,7 +482,7 @@ where
470482
pub fn into_state(mut self) -> ArrayRef {
471483
// Flush any remaining in-progress buffer
472484
if !self.in_progress.is_empty() {
473-
let flushed = std::mem::take(&mut self.in_progress);
485+
let flushed = mem::take(&mut self.in_progress);
474486
self.completed.push(Buffer::from_vec(flushed));
475487
}
476488

@@ -562,13 +574,23 @@ where
562574
let view = if len <= 12 {
563575
make_view(value, 0, 0)
564576
} else {
565-
// Ensure buffer is big enough
566-
if self.in_progress.len() + len > BYTE_VIEW_MAX_BLOCK_SIZE {
567-
let flushed = std::mem::replace(
568-
&mut self.in_progress,
569-
Vec::with_capacity(BYTE_VIEW_MAX_BLOCK_SIZE),
570-
);
571-
self.completed.push(Buffer::from_vec(flushed));
577+
let block_limit = if self.block_size == 0 {
578+
BYTE_VIEW_MAX_BLOCK_SIZE
579+
} else {
580+
self.in_progress.capacity()
581+
};
582+
if self.in_progress.len() + len > block_limit {
583+
if !self.in_progress.is_empty() {
584+
let flushed = mem::take(&mut self.in_progress);
585+
self.completed.push(Buffer::from_vec(flushed));
586+
}
587+
let capacity = if self.block_size == 0 {
588+
BYTE_VIEW_MAX_BLOCK_SIZE
589+
} else {
590+
self.block_size = (self.block_size * 2).min(BYTE_VIEW_MAX_BLOCK_SIZE);
591+
len.max(self.block_size)
592+
};
593+
self.in_progress = Vec::with_capacity(capacity);
572594
}
573595

574596
let buffer_index = self.completed.len() as u32;
@@ -972,6 +994,10 @@ mod tests {
972994
map.views.reserve_exact(1);
973995
map.completed.shrink_to_fit();
974996
map.completed.reserve_exact(1);
997+
let completed = &mut map.completed[0];
998+
let mut padded = Vec::with_capacity(completed.len() + 16);
999+
padded.extend_from_slice(completed);
1000+
*completed = Buffer::from_vec(padded);
9751001

9761002
// The map owns these allocations; `values` and its Arrow buffers remain external.
9771003
assert!(map.views.capacity() > map.views.len());

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

Lines changed: 16 additions & 23 deletions
Original file line numberDiff line numberDiff line change
@@ -29,9 +29,10 @@ use datafusion_common::Result;
2929
use datafusion_common::utils::split_vec_min_alloc;
3030
use datafusion_expr::GroupSelection;
3131
use std::marker::PhantomData;
32-
use std::mem::{replace, size_of};
32+
use std::mem::{self, replace, size_of};
3333
use std::sync::Arc;
3434

35+
const BYTE_VIEW_STARTING_BLOCK_SIZE: usize = 8 * 1024;
3536
const BYTE_VIEW_MAX_BLOCK_SIZE: usize = 2 * 1024 * 1024;
3637

3738
/// An implementation of [`GroupColumn`] for binary view and utf8 view types.
@@ -55,19 +56,16 @@ pub struct ByteViewGroupValueBuilder<B: ByteViewType> {
5556
/// The progressing block
5657
///
5758
/// New values will be inserted into it until its capacity
58-
/// is not enough(detail can see `max_block_size`).
59+
/// cannot hold the next value.
5960
in_progress: Vec<u8>,
6061

6162
/// The completed blocks
6263
completed: Vec<Buffer>,
6364

64-
/// The max size of `in_progress`
65-
///
66-
/// `in_progress` will be flushed into `completed`, and create new `in_progress`
67-
/// when found its remaining capacity(`max_block_size` - `len(in_progress)`),
68-
/// is no enough to store the appended value.
69-
///
70-
/// Currently it is fixed at 2MB.
65+
/// Allocation target, doubled for each new payload block.
66+
block_size: usize,
67+
68+
/// Maximum allocation target. A single larger value gets its own block.
7169
max_block_size: usize,
7270

7371
/// Nulls
@@ -89,6 +87,7 @@ impl<B: ByteViewType> ByteViewGroupValueBuilder<B> {
8987
views: Vec::new(),
9088
in_progress: Vec::new(),
9189
completed: Vec::new(),
90+
block_size: BYTE_VIEW_STARTING_BLOCK_SIZE,
9291
max_block_size: BYTE_VIEW_MAX_BLOCK_SIZE,
9392
nulls: NullBufferBuilder::empty(),
9493
_phantom: PhantomData {},
@@ -98,6 +97,7 @@ impl<B: ByteViewType> ByteViewGroupValueBuilder<B> {
9897
/// Set the max block size
9998
fn with_max_block_size(mut self, max_block_size: usize) -> Self {
10099
self.max_block_size = max_block_size;
100+
self.block_size = self.block_size.min(max_block_size);
101101
self
102102
}
103103

@@ -236,16 +236,12 @@ impl<B: ByteViewType> ByteViewGroupValueBuilder<B> {
236236

237237
fn ensure_in_progress_big_enough(&mut self, value_len: usize) {
238238
debug_assert!(value_len > 12);
239-
let require_cap = self.in_progress.len() + value_len;
240-
241-
// If current block isn't big enough, flush it and create a new in progress block
242-
if require_cap > self.max_block_size {
243-
let flushed_block = replace(
244-
&mut self.in_progress,
245-
Vec::with_capacity(self.max_block_size),
246-
);
247-
let buffer = Buffer::from_vec(flushed_block);
248-
self.completed.push(buffer);
239+
if value_len > self.in_progress.capacity() - self.in_progress.len() {
240+
if !self.in_progress.is_empty() {
241+
self.flush_in_progress();
242+
}
243+
self.block_size = (self.block_size * 2).min(self.max_block_size);
244+
self.in_progress = Vec::with_capacity(value_len.max(self.block_size));
249245
}
250246
}
251247

@@ -564,10 +560,7 @@ impl<B: ByteViewType> ByteViewGroupValueBuilder<B> {
564560
}
565561

566562
fn flush_in_progress(&mut self) {
567-
let flushed_block = replace(
568-
&mut self.in_progress,
569-
Vec::with_capacity(self.max_block_size),
570-
);
563+
let flushed_block = mem::take(&mut self.in_progress);
571564
let buffer = Buffer::from_vec(flushed_block);
572565
self.completed.push(buffer);
573566
}

0 commit comments

Comments
 (0)