Skip to content

Commit bf62c82

Browse files
committed
replace multiple buffers with single flat buffer. closes apache#22078
1 parent f6f5950 commit bf62c82

1 file changed

Lines changed: 152 additions & 99 deletions

File tree

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

‎datafusion/physical-plan/src/aggregates/group_values/single_group_by/dictionary.rs‎

Lines changed: 152 additions & 99 deletions
Original file line numberDiff line numberDiff line change
@@ -28,7 +28,6 @@ use datafusion_common::Result;
2828
use datafusion_common::hash_utils::create_hashes;
2929
use datafusion_expr::EmitTo;
3030
use hashbrown::HashTable;
31-
use hashbrown::hash_table::Entry as HashTableEntry;
3231
use std::borrow::Cow;
3332
use std::marker::PhantomData;
3433
use std::sync::Arc;
@@ -88,16 +87,18 @@ macro_rules! decode_scalar_string {
8887
Ok(Arc::new(builder.finish()) as ArrayRef)
8988
}};
9089
}
91-
/// Entry stored inside `unique_dict_value_mapping`. Caching `hash` on the entry
9290
struct DictEntry {
9391
hash: u64,
9492
group_id: usize,
95-
bytes: Vec<u8>,
93+
offset: usize,
94+
len: usize,
9695
}
9796

9897
pub struct GroupValuesDictionary<K: ArrowDictionaryKeyType + Send> {
99-
// stores the order new unique elements are seen for self.emit()
100-
seen_elements: Vec<Option<Vec<u8>>>,
98+
/// Packed byte storage for all group values.
99+
row_buffer: Vec<u8>,
100+
/// `row_offsets[g]` = start of group `g` in `row_buffer`;
101+
row_offsets: Vec<usize>,
101102
value_dt: DataType,
102103
_phantom: PhantomData<K>,
103104
// keeps track of which values weve already seen, keyed by raw value hash.
@@ -117,7 +118,8 @@ pub struct GroupValuesDictionary<K: ArrowDictionaryKeyType + Send> {
117118
impl<K: ArrowDictionaryKeyType + Send> GroupValuesDictionary<K> {
118119
pub fn new(data_type: &DataType) -> Self {
119120
Self {
120-
seen_elements: Vec::new(),
121+
row_buffer: Vec::new(),
122+
row_offsets: Vec::new(),
121123
unique_dict_value_mapping: HashTable::new(),
122124
value_dt: data_type.clone(),
123125
_phantom: PhantomData,
@@ -128,25 +130,28 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValuesDictionary<K> {
128130
}
129131
}
130132

131-
/// Returns the existing `group_id` for the value with this hash and bytes,
132-
/// or inserts a new entry and returns the freshly assigned group_id.
133133
fn lookup_or_insert_in_table(&mut self, hash: u64, raw: &[u8]) -> usize {
134-
match self
135-
.unique_dict_value_mapping
136-
.entry(hash, |e| e.bytes == raw, |e| e.hash)
137-
{
138-
HashTableEntry::Occupied(o) => o.get().group_id,
139-
HashTableEntry::Vacant(v) => {
140-
let new_group_id = self.seen_elements.len();
141-
self.seen_elements.push(Some(raw.to_vec())); // replace this with raw buffer to avoid this double copy #TODO see https://github.com/apache/datafusion/issues/22078
142-
v.insert(DictEntry {
143-
hash,
144-
group_id: new_group_id,
145-
bytes: raw.to_vec(),
146-
});
147-
new_group_id
148-
}
134+
let row_buffer = &self.row_buffer;
135+
if let Some(e) = self.unique_dict_value_mapping.find(hash, |e| {
136+
e.hash == hash && &row_buffer[e.offset..e.offset + e.len] == raw
137+
}) {
138+
return e.group_id;
149139
}
140+
let new_group_id = self.row_offsets.len();
141+
let offset = self.row_buffer.len();
142+
self.row_offsets.push(offset);
143+
self.row_buffer.extend_from_slice(raw);
144+
self.unique_dict_value_mapping.insert_unique(
145+
hash,
146+
DictEntry {
147+
hash,
148+
group_id: new_group_id,
149+
offset,
150+
len: raw.len(),
151+
},
152+
|e| e.hash,
153+
);
154+
new_group_id
150155
}
151156
fn compute_value_hashes(&mut self, values: &ArrayRef) -> Result<()> {
152157
self.values_cache.1.clear();
@@ -220,52 +225,64 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValuesDictionary<K> {
220225
if let Some(group_id) = self.null_group_id {
221226
group_id
222227
} else {
223-
let new_group_id = self.seen_elements.len();
224-
self.seen_elements.push(None);
228+
let new_group_id = self.row_offsets.len();
229+
self.row_offsets.push(self.row_buffer.len()); // null: empty span
225230
self.null_group_id = Some(new_group_id);
226231
new_group_id
227232
}
228233
}
229-
fn transform_into_array(&self, raw: &[Option<Vec<u8>>]) -> Result<ArrayRef> {
230-
let item_capacity = raw.len();
231-
let data_capacity = item_capacity * AVG_BYTES_PER_DICT_VALUE;
234+
235+
fn transform_into_array(
236+
&self,
237+
n: usize,
238+
null_group_id: Option<usize>,
239+
) -> Result<ArrayRef> {
240+
let data_capacity = n * AVG_BYTES_PER_DICT_VALUE;
241+
let raw = (0..n).map(|i| {
242+
if Some(i) == null_group_id {
243+
return None;
244+
}
245+
let start = self.row_offsets[i];
246+
// last group has no i+1 entry; its end is the buffer tail.
247+
let end = self
248+
.row_offsets
249+
.get(i + 1)
250+
.copied()
251+
.unwrap_or(self.row_buffer.len());
252+
Some(&self.row_buffer[start..end])
253+
});
232254
match &self.value_dt {
233-
DataType::Utf8 => decode_scalar_string!(
234-
raw,
235-
StringBuilder::with_capacity(item_capacity, data_capacity)
236-
),
255+
DataType::Utf8 => {
256+
decode_scalar_string!(raw, StringBuilder::with_capacity(n, data_capacity))
257+
}
237258
DataType::LargeUtf8 => decode_scalar_string!(
238259
raw,
239-
LargeStringBuilder::with_capacity(item_capacity, data_capacity)
240-
),
241-
DataType::Utf8View => decode_scalar_string!(
242-
raw,
243-
StringViewBuilder::with_capacity(item_capacity)
260+
LargeStringBuilder::with_capacity(n, data_capacity)
244261
),
262+
DataType::Utf8View => {
263+
decode_scalar_string!(raw, StringViewBuilder::with_capacity(n))
264+
}
245265
DataType::List(field) => match field.data_type() {
246266
DataType::Utf8 => decode_list!(
247267
raw,
248268
ListBuilder::with_capacity(
249-
StringBuilder::with_capacity(item_capacity, data_capacity),
250-
item_capacity,
269+
StringBuilder::with_capacity(n, data_capacity),
270+
n,
251271
)
252272
.with_field(Arc::clone(field))
253273
),
254274
DataType::LargeUtf8 => decode_list!(
255275
raw,
256276
ListBuilder::with_capacity(
257-
LargeStringBuilder::with_capacity(item_capacity, data_capacity),
258-
item_capacity,
277+
LargeStringBuilder::with_capacity(n, data_capacity),
278+
n,
259279
)
260280
.with_field(Arc::clone(field))
261281
),
262282
DataType::Utf8View => decode_list!(
263283
raw,
264-
ListBuilder::with_capacity(
265-
StringViewBuilder::with_capacity(item_capacity),
266-
item_capacity,
267-
)
268-
.with_field(Arc::clone(field))
284+
ListBuilder::with_capacity(StringViewBuilder::with_capacity(n), n,)
285+
.with_field(Arc::clone(field))
269286
),
270287
other => Err(NotImplemented(format!(
271288
"transform_into_array not implemented for List<{other:?}>"
@@ -295,22 +312,11 @@ fn valid_bounds<K: ArrowDictionaryKeyType>(n: usize) -> bool {
295312

296313
impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K> {
297314
fn size(&self) -> usize {
298-
let seen_elements_size = self.seen_elements.capacity()
299-
* size_of::<Option<Vec<u8>>>()
300-
+ self
301-
.seen_elements
302-
.iter()
303-
.filter_map(|opt| opt.as_ref())
304-
.map(|inner| inner.capacity())
305-
.sum::<usize>();
306-
307-
let unique_mapping_size = self.unique_dict_value_mapping.capacity()
308-
* size_of::<DictEntry>()
309-
+ self
310-
.unique_dict_value_mapping
311-
.iter()
312-
.map(|e| e.bytes.capacity())
313-
.sum::<usize>();
315+
let row_data_size =
316+
self.row_buffer.capacity() + self.row_offsets.capacity() * size_of::<usize>();
317+
318+
let unique_mapping_size =
319+
self.unique_dict_value_mapping.capacity() * size_of::<DictEntry>();
314320

315321
let values_cache_size = self.values_cache.1.capacity() * size_of::<u64>()
316322
+ self
@@ -320,13 +326,15 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
320326
.map(|a| a.to_data().get_slice_memory_size().unwrap_or(0))
321327
.unwrap_or(0);
322328

323-
size_of::<Self>() + seen_elements_size + unique_mapping_size + values_cache_size
329+
let key_to_group_size = self.key_to_group.capacity() * size_of::<Option<usize>>();
330+
331+
size_of::<Self>() + row_data_size + unique_mapping_size + values_cache_size + key_to_group_size
324332
}
325333
fn len(&self) -> usize {
326-
self.seen_elements.len()
334+
self.row_offsets.len()
327335
}
328336
fn is_empty(&self) -> bool {
329-
self.seen_elements.is_empty()
337+
self.row_offsets.is_empty()
330338
}
331339
fn intern(&mut self, cols: &[ArrayRef], groups: &mut Vec<usize>) -> Result<()> {
332340
assert_eq!(
@@ -390,46 +398,19 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
390398
Ok(())
391399
}
392400
fn emit(&mut self, emit_to: EmitTo) -> Result<Vec<ArrayRef>> {
393-
let (elements_to_emit, null_id) = match emit_to {
394-
EmitTo::All => {
395-
let original_null_id = self.null_group_id;
396-
self.null_group_id = None;
397-
self.unique_dict_value_mapping.clear();
398-
(std::mem::take(&mut self.seen_elements), original_null_id)
399-
}
400-
EmitTo::First(n) => {
401-
let n = n.min(self.seen_elements.len());
402-
let first_n = self.seen_elements.drain(..n).collect::<Vec<_>>(); // again read from raw buffer directly
403-
let original_null_id = self.null_group_id.filter(|&id| id < n);
404-
// update null_group_id if the null group was in the first n
405-
if let Some(null_id) = self.null_group_id {
406-
if null_id < n {
407-
self.null_group_id = None;
408-
} else {
409-
self.null_group_id = Some(null_id - n);
410-
}
411-
}
412-
// shift all remaining group indices down by n in the table
413-
self.unique_dict_value_mapping.retain(|e| {
414-
if e.group_id < n {
415-
false
416-
} else {
417-
e.group_id -= n;
418-
true
419-
}
420-
});
421-
(first_n, original_null_id)
422-
}
401+
let n = match emit_to {
402+
EmitTo::All => self.row_offsets.len(),
403+
EmitTo::First(k) => k.min(self.row_offsets.len()),
423404
};
405+
let null_id = self.null_group_id.filter(|&id| id < n);
424406

425-
let n = elements_to_emit.len();
426407
if !valid_bounds::<K>(n) {
427408
return Err(Internal(format!(
428409
"group count {n} overflows key type {:?}",
429410
K::DATA_TYPE
430411
)));
431412
}
432-
let values_array = self.transform_into_array(&elements_to_emit)?; // ingest a buffer + n then produce an array. should also update the len+offset of other entries #TODO see https://github.com/apache/datafusion/issues/22078
413+
let values_array = self.transform_into_array(n, null_id)?;
433414

434415
let mut keys_builder = PrimitiveBuilder::<K>::with_capacity(n);
435416
if let Some(null_id) = null_id {
@@ -447,17 +428,58 @@ impl<K: ArrowDictionaryKeyType + Send> GroupValues for GroupValuesDictionary<K>
447428
}
448429
let dict_array =
449430
DictionaryArray::<K>::try_new(keys_builder.finish(), values_array)?;
431+
432+
match emit_to {
433+
EmitTo::All => {
434+
self.null_group_id = None;
435+
self.unique_dict_value_mapping.clear();
436+
self.row_buffer.clear();
437+
self.row_offsets.clear();
438+
}
439+
EmitTo::First(_) => {
440+
if let Some(nid) = self.null_group_id {
441+
if nid < n {
442+
self.null_group_id = None;
443+
} else {
444+
self.null_group_id = Some(nid - n);
445+
}
446+
}
447+
let retain_start = self
448+
.row_offsets
449+
.get(n)
450+
.copied()
451+
.unwrap_or(self.row_buffer.len());
452+
self.row_offsets.drain(0..n);
453+
for off in &mut self.row_offsets {
454+
*off -= retain_start;
455+
}
456+
self.row_buffer.drain(0..retain_start);
457+
self.unique_dict_value_mapping.retain(|e| {
458+
if e.group_id < n {
459+
return false;
460+
}
461+
e.group_id -= n;
462+
e.offset -= retain_start;
463+
true
464+
});
465+
}
466+
}
467+
450468
Ok(vec![Arc::new(dict_array)])
451469
}
452470
fn clear_shrink(&mut self, num_rows: usize) {
453-
self.seen_elements.clear();
454-
self.seen_elements.shrink_to(num_rows);
471+
self.row_buffer.clear();
472+
self.row_buffer
473+
.shrink_to(num_rows * AVG_BYTES_PER_DICT_VALUE);
474+
self.row_offsets.clear();
475+
self.row_offsets.shrink_to(num_rows);
455476
self.null_group_id = None;
456477
self.unique_dict_value_mapping.clear();
457478
self.unique_dict_value_mapping
458479
.shrink_to(num_rows, |e| e.hash);
459480
self.values_cache.0 = None;
460481
self.key_to_group.clear();
482+
self.key_to_group.shrink_to(num_rows);
461483
self.values_cache.1.clear();
462484
self.values_cache.1.shrink_to(num_rows);
463485
}
@@ -834,6 +856,37 @@ mod test {
834856
mod streaming_emit {
835857
use super::*;
836858

859+
#[test]
860+
fn test_null_only_group_emit_first() {
861+
let mut gv = GroupValuesDictionary::<Int32Type>::new(&DataType::Utf8);
862+
let mut groups = Vec::new();
863+
864+
// intern a single null value (key is null; the value slot is irrelevant)
865+
let values = make_utf8_values(vec![Some("x")]);
866+
let dict = make_dict_array(values, vec![None]);
867+
gv.intern(&[dict], &mut groups).expect("intern should succeed");
868+
869+
assert_eq!(gv.len(), 1);
870+
assert_eq!(groups, vec![0]);
871+
872+
// emit First(1) -- the null group is the ONLY group
873+
let result = gv.emit(EmitTo::First(1)).expect("emit should succeed");
874+
assert_eq!(result.len(), 1);
875+
876+
let emitted = result[0]
877+
.as_any()
878+
.downcast_ref::<DictionaryArray<Int32Type>>()
879+
.expect("Expected DictionaryArray");
880+
881+
// The emitted DictionaryArray should have 1 element, and it should be null
882+
assert_eq!(emitted.len(), 1);
883+
assert!(emitted.is_null(0), "the emitted row should be null");
884+
885+
// post-emit state: everything should be cleared
886+
assert_eq!(gv.len(), 0);
887+
assert!(gv.is_empty());
888+
}
889+
837890
#[test]
838891
fn test_emit_first_shifts_and_retains() {
839892
let mut gv = GroupValuesDictionary::<Int32Type>::new(&DataType::Utf8);

0 commit comments

Comments
 (0)