Skip to content

Commit b9e6252

Browse files
committed
fix: grow the value buffer on a power of two ladder
`ArrowBytesMap::new` starts its value buffer empty and `ArrowBytesMap::with_capacity` starts it at `INITIAL_BUFFER_CAPACITY`. `Vec` then doubles from wherever its first allocation landed, so the two sit on different ladders and can hold the same values at capacities differing by up to 2x, in either direction depending on the value lengths. Measured on 500,000 distinct 28 byte values, the lazily grown map reported 52,494,344 bytes against 45,154,312 for a pre-allocated one, 16% more for identical contents. That matters because the ungrouped `COUNT(DISTINCT <string>)` accumulator is the caller that had a use for the warm up: it builds one map and grows it to hold every distinct value in the input. Rounding every buffer growth up to a power of two puts both constructors on one ladder, so a lazily allocated map is never larger than a pre-allocated one holding the same values. Growth stays geometric, so appending is still amortized constant time. `ArrowBytesViewMap` has no such buffer and is unaffected. Two new tests cover the ungrouped path, which had none: `ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set` and its `Utf8View` counterpart drive an accumulator to 0 through 500,000 distinct values and assert it is strictly cheaper than a pre-allocated set at per group cardinalities and exactly equal at ungrouped ones. The `Utf8` one fails without this change, at 1,000 distinct values, with the lazy set reporting 110,408 bytes against 96,072. Two map level tests pin the ladder itself.
1 parent 37d3ac2 commit b9e6252

2 files changed

Lines changed: 223 additions & 2 deletions

File tree

  • datafusion

‎datafusion/functions-aggregate-common/src/aggregate/count_distinct/bytes.rs‎

Lines changed: 149 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -43,6 +43,14 @@ impl<O: OffsetSizeTrait> BytesDistinctCountAccumulator<O> {
4343
/// creates one accumulator per group, so a grouped `COUNT(DISTINCT)` over a
4444
/// high cardinality key holds hundreds of thousands of these at once and
4545
/// most of them see only a handful of values.
46+
///
47+
/// The ungrouped path builds one of these and grows it to hold every
48+
/// distinct value in the input, so it is the caller that had a use for the
49+
/// warm up. It loses nothing here: the set grows into exactly the
50+
/// capacities a pre-allocated one reaches, which
51+
/// `ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set`
52+
/// pins. That is why this constructor needs no signal distinguishing the
53+
/// two callers.
4654
pub fn new(output_type: OutputType) -> Self {
4755
Self(ArrowBytesSet::new(output_type))
4856
}
@@ -157,3 +165,144 @@ impl Accumulator for BytesViewDistinctCountAccumulator {
157165
size_of_val(self) + self.0.size()
158166
}
159167
}
168+
169+
#[cfg(test)]
170+
mod tests {
171+
use super::*;
172+
use arrow::array::{StringArray, StringViewArray};
173+
use datafusion_physical_expr_common::binary_map::INITIAL_MAP_CAPACITY;
174+
use datafusion_physical_expr_common::binary_view_map::INITIAL_MAP_CAPACITY as INITIAL_VIEW_MAP_CAPACITY;
175+
use std::sync::Arc;
176+
177+
/// The batch size the aggregate stream drives an ungrouped accumulator with.
178+
const BATCH_SIZE: usize = 8192;
179+
180+
/// Distinct value counts spanning both sides of the warm up capacity, up to
181+
/// ones where the two constructors have converged.
182+
const CARDINALITIES: [usize; 7] = [0, 1, 100, 1_000, 10_000, 100_000, 500_000];
183+
184+
/// Cardinalities small enough that the warm up dominates what the set
185+
/// holds. This is the per group population, where `GroupsAccumulatorAdapter`
186+
/// holds one accumulator per group and most see a handful of values.
187+
const PER_GROUP_SCALE: usize = 100;
188+
189+
/// Cardinalities at which a lazily built set has grown into exactly the
190+
/// capacities a pre-allocated one reaches. This is the ungrouped
191+
/// population, one set holding every distinct value in the input.
192+
const UNGROUPED_SCALE: usize = 10_000;
193+
194+
/// Longer than the map's inline value length, so the value lands in the
195+
/// value buffer rather than inside the hash table entry.
196+
fn distinct_value(i: usize) -> String {
197+
format!("distinct value number {i}")
198+
}
199+
200+
fn batches(distinct_values: usize, view: bool) -> Vec<ArrayRef> {
201+
(0..distinct_values)
202+
.step_by(BATCH_SIZE)
203+
.map(|start| {
204+
let values = (start..(start + BATCH_SIZE).min(distinct_values))
205+
.map(distinct_value);
206+
if view {
207+
Arc::new(StringViewArray::from_iter_values(values)) as ArrayRef
208+
} else {
209+
Arc::new(StringArray::from_iter_values(values)) as ArrayRef
210+
}
211+
})
212+
.collect()
213+
}
214+
215+
/// The property that decides whether the ungrouped path can afford to share
216+
/// the lazy constructor with the per group path.
217+
fn assert_lazy_is_not_worse(
218+
distinct_values: usize,
219+
lazy_size: usize,
220+
pre_allocated_size: usize,
221+
) {
222+
// The guarantee that lets both paths share one lazy constructor.
223+
assert!(
224+
lazy_size <= pre_allocated_size,
225+
"at {distinct_values} distinct values the lazy set reported \
226+
{lazy_size} bytes against the {pre_allocated_size} bytes the \
227+
pre-allocated one reported"
228+
);
229+
230+
if distinct_values <= PER_GROUP_SCALE {
231+
// The warm up is pure overhead here, and removing it is the whole
232+
// point of the change.
233+
assert!(
234+
lazy_size < pre_allocated_size,
235+
"at {distinct_values} distinct values the lazy set should be \
236+
strictly cheaper, but reported {lazy_size} bytes against \
237+
{pre_allocated_size}"
238+
);
239+
}
240+
241+
if distinct_values >= UNGROUPED_SCALE {
242+
// The hash table's bucket count is a power of two fixed by the
243+
// number of entries, and the value buffer grows on a power of two
244+
// ladder, so a set that starts empty lands on exactly the
245+
// capacities a pre-allocated one reaches. The ungrouped path gives
246+
// up nothing by starting empty, which is why these accumulators
247+
// need no signal telling them apart from the per group ones.
248+
assert_eq!(
249+
lazy_size, pre_allocated_size,
250+
"at {distinct_values} distinct values the lazy and pre-allocated \
251+
sets should have converged"
252+
);
253+
}
254+
}
255+
256+
/// An ungrouped `COUNT(DISTINCT <string>)` builds a single accumulator that
257+
/// grows to hold every distinct value in its input, which is the population
258+
/// the warm up existed for. It must be no more expensive without one.
259+
#[test]
260+
fn ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set() {
261+
for distinct_values in CARDINALITIES {
262+
let mut accumulator =
263+
BytesDistinctCountAccumulator::<i32>::new(OutputType::Utf8);
264+
let mut pre_allocated = ArrowBytesSet::<i32>::with_capacity(
265+
OutputType::Utf8,
266+
INITIAL_MAP_CAPACITY,
267+
);
268+
269+
for batch in batches(distinct_values, false) {
270+
accumulator.update_batch(&[Arc::clone(&batch)]).unwrap();
271+
pre_allocated.insert(&batch);
272+
}
273+
274+
assert_eq!(accumulator.0.non_null_len(), distinct_values);
275+
assert_lazy_is_not_worse(
276+
distinct_values,
277+
accumulator.0.size(),
278+
pre_allocated.size(),
279+
);
280+
}
281+
}
282+
283+
/// The `Utf8View` counterpart of
284+
/// [`ungrouped_utf8_accumulator_is_never_worse_than_a_pre_allocated_set`].
285+
#[test]
286+
fn ungrouped_utf8_view_accumulator_is_never_worse_than_a_pre_allocated_set() {
287+
for distinct_values in CARDINALITIES {
288+
let mut accumulator =
289+
BytesViewDistinctCountAccumulator::new(OutputType::Utf8View);
290+
let mut pre_allocated = ArrowBytesViewSet::with_capacity(
291+
OutputType::Utf8View,
292+
INITIAL_VIEW_MAP_CAPACITY,
293+
);
294+
295+
for batch in batches(distinct_values, true) {
296+
accumulator.update_batch(&[Arc::clone(&batch)]).unwrap();
297+
pre_allocated.insert(&batch);
298+
}
299+
300+
assert_eq!(accumulator.0.non_null_len(), distinct_values);
301+
assert_lazy_is_not_worse(
302+
distinct_values,
303+
accumulator.0.size(),
304+
pre_allocated.size(),
305+
);
306+
}
307+
}
308+
}

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

Lines changed: 74 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -259,6 +259,28 @@ pub const INITIAL_MAP_CAPACITY: usize = 128;
259259
/// The size, in bytes, of the string data buffer pre-allocated by
260260
/// [`ArrowBytesMap::with_capacity`]
261261
pub const INITIAL_BUFFER_CAPACITY: usize = 8 * 1024;
262+
263+
/// Appends `value` to a map's value buffer, growing the buffer on a power of
264+
/// two ladder.
265+
///
266+
/// `Vec` doubles from wherever its first allocation landed, so a buffer started
267+
/// empty by [`ArrowBytesMap::new`] and one started at
268+
/// [`INITIAL_BUFFER_CAPACITY`] by [`ArrowBytesMap::with_capacity`] sit on
269+
/// different ladders, and can hold the same values at capacities differing by
270+
/// up to 2x in either direction depending on the value lengths. Rounding every
271+
/// growth up to a power of two puts both on one ladder, which is what makes a
272+
/// lazily allocated map never larger than a pre-allocated one holding the same
273+
/// values. Growth stays geometric, so appending is still amortized constant
274+
/// time.
275+
fn push_value_bytes(buffer: &mut Vec<u8>, value: &[u8]) {
276+
let required = buffer.len() + value.len();
277+
if required > buffer.capacity() {
278+
let target = required.checked_next_power_of_two().unwrap_or(required);
279+
buffer.reserve_exact(target - buffer.len());
280+
}
281+
buffer.extend_from_slice(value);
282+
}
283+
262284
impl<O: OffsetSizeTrait, V> ArrowBytesMap<O, V>
263285
where
264286
V: Debug + PartialEq + Eq + Clone + Copy + Default,
@@ -471,7 +493,7 @@ where
471493
// Put the small values into buffer and offsets so it appears
472494
// the output array, but store the actual bytes inline for
473495
// comparison
474-
self.buffer.extend_from_slice(value);
496+
push_value_bytes(&mut self.buffer, value);
475497
self.offsets.push(O::usize_as(self.buffer.len()));
476498
let payload = make_payload_fn(Some(value));
477499
let new_header = Entry {
@@ -509,7 +531,7 @@ where
509531
// appears the output array, and store that offset
510532
// so the bytes can be compared if needed
511533
let offset = self.buffer.len(); // offset of start for data
512-
self.buffer.extend_from_slice(value);
534+
push_value_bytes(&mut self.buffer, value);
513535
self.offsets.push(O::usize_as(self.buffer.len()));
514536

515537
let payload = make_payload_fn(Some(value));
@@ -826,6 +848,56 @@ mod tests {
826848
assert_eq!(map.buffer.capacity(), INITIAL_BUFFER_CAPACITY);
827849
}
828850

851+
#[test]
852+
fn lazy_and_pre_allocated_buffers_grow_on_the_same_ladder() {
853+
// Value lengths chosen so the buffer requirement lands between powers
854+
// of two, which is where the two ladders used to diverge.
855+
for value_len in [9usize, 13, 24, 37] {
856+
let mut lazy = ArrowBytesMap::<i32, ()>::new(OutputType::Utf8);
857+
let mut pre_allocated = ArrowBytesMap::<i32, ()>::with_capacity(
858+
OutputType::Utf8,
859+
INITIAL_MAP_CAPACITY,
860+
);
861+
862+
for batch in 0..8 {
863+
let values: ArrayRef =
864+
Arc::new(StringArray::from_iter_values((0..1_000).map(|i| {
865+
let value = format!("{}:{i}", batch * 1_000 + i);
866+
format!("{value:value_len$}")
867+
})));
868+
lazy.insert_if_new(&values, |_| (), |_| ());
869+
pre_allocated.insert_if_new(&values, |_| (), |_| ());
870+
871+
assert_eq!(lazy.buffer.len(), pre_allocated.buffer.len());
872+
assert_eq!(
873+
lazy.buffer.capacity(),
874+
pre_allocated.buffer.capacity(),
875+
"value length {value_len}, batch {batch}: a buffer that \
876+
started empty reached {} bytes of capacity against {} for \
877+
one that started at INITIAL_BUFFER_CAPACITY",
878+
lazy.buffer.capacity(),
879+
pre_allocated.buffer.capacity(),
880+
);
881+
}
882+
}
883+
}
884+
885+
#[test]
886+
fn a_lazy_buffer_stays_below_the_pre_allocated_floor_while_it_is_small() {
887+
let mut lazy = ArrowBytesMap::<i32, ()>::new(OutputType::Utf8);
888+
let values: ArrayRef = Arc::new(StringArray::from_iter_values(
889+
(0..10).map(|i| format!("distinct value number {i}")),
890+
));
891+
lazy.insert_if_new(&values, |_| (), |_| ());
892+
893+
assert!(
894+
lazy.buffer.capacity() < INITIAL_BUFFER_CAPACITY,
895+
"expected a small lazy buffer to stay under the {INITIAL_BUFFER_CAPACITY} \
896+
byte pre-allocation, got {}",
897+
lazy.buffer.capacity()
898+
);
899+
}
900+
829901
#[test]
830902
fn string_set_empty() {
831903
let mut set = ArrowBytesSet::<i32>::new(OutputType::Utf8);

0 commit comments

Comments
 (0)