parquet/encodings/encoding/
dict_encoder.rs1use bytes::Bytes;
9
10use crate::basic::{Encoding, Type};
11use crate::data_type::DataType;
12use crate::data_type::private::ParquetValueType;
13use crate::encodings::encoding::{Encoder, PlainEncoder};
14use crate::encodings::rle::RleEncoder;
15use crate::errors::Result;
16use crate::schema::types::ColumnDescPtr;
17use crate::util::bit_util::num_required_bits;
18use crate::util::interner::{Interner, Storage};
19
20#[derive(Debug)]
21struct KeyStorage<T: DataType> {
22 uniques: Vec<T::T>,
23
24 size_in_bytes: usize,
26
27 type_length: usize,
28}
29
30impl<T: DataType> Storage for KeyStorage<T> {
31 type Key = u64;
32 type Value = T::T;
33
34 fn get(&self, idx: Self::Key) -> &Self::Value {
35 &self.uniques[idx as usize]
36 }
37
38 fn push(&mut self, value: &Self::Value) -> Self::Key {
39 let (base_size, num_elements) = value.dict_encoding_size();
40
41 let unique_size = match T::get_physical_type() {
42 Type::BYTE_ARRAY => base_size + num_elements,
43 Type::FIXED_LEN_BYTE_ARRAY => self.type_length,
44 _ => base_size,
45 };
46 self.size_in_bytes += unique_size;
47
48 let key = self.uniques.len() as u64;
49 self.uniques.push(value.clone());
50 key
51 }
52
53 fn estimated_memory_size(&self) -> usize {
54 let uniques_heap_bytes = match T::get_physical_type() {
55 Type::FIXED_LEN_BYTE_ARRAY => self.type_length * self.uniques.len(),
56 _ => <Self::Value as ParquetValueType>::variable_length_bytes(&self.uniques)
57 .unwrap_or(0) as usize,
58 };
59 self.uniques.capacity() * std::mem::size_of::<T::T>() + uniques_heap_bytes
60 }
61}
62
63pub struct DictEncoder<T: DataType> {
74 interner: Interner<KeyStorage<T>>,
75
76 indices: Vec<u64>,
78}
79
80impl<T: DataType> DictEncoder<T> {
81 pub fn new(desc: ColumnDescPtr) -> Self {
83 let storage = KeyStorage {
84 uniques: vec![],
85 size_in_bytes: 0,
86 type_length: desc.type_length() as usize,
87 };
88
89 Self {
90 interner: Interner::new(storage),
91 indices: vec![],
92 }
93 }
94
95 pub fn is_sorted(&self) -> bool {
97 false
99 }
100
101 pub fn num_entries(&self) -> usize {
103 self.interner.storage().uniques.len()
104 }
105
106 pub fn uniques(&self) -> &[T::T] {
108 &self.interner.storage().uniques
109 }
110
111 pub fn dict_encoded_size(&self) -> usize {
113 self.interner.storage().size_in_bytes
114 }
115
116 pub fn write_dict(&self) -> Result<Bytes> {
119 let mut plain_encoder = PlainEncoder::<T>::new();
120 plain_encoder.put(&self.interner.storage().uniques)?;
121 plain_encoder.flush_buffer()
122 }
123
124 pub fn write_indices(&mut self) -> Result<Bytes> {
127 let buffer_len = self.estimated_data_encoded_size();
128 let mut buffer = Vec::with_capacity(buffer_len);
129 buffer.push(self.bit_width());
130
131 let mut encoder = RleEncoder::new_from_buf(self.bit_width(), buffer);
133 encoder.put_batch(&self.indices);
134 self.indices.clear();
135 Ok(encoder.consume().into())
136 }
137
138 fn put_one(&mut self, value: &T::T) {
139 self.indices.push(self.interner.intern(value));
140 }
141
142 #[inline]
143 fn bit_width(&self) -> u8 {
144 num_required_bits(self.num_entries().saturating_sub(1) as u64)
145 }
146}
147
148impl<T: DataType> Encoder<T> for DictEncoder<T> {
149 fn put(&mut self, values: &[T::T]) -> Result<()> {
150 self.indices.reserve(values.len());
151 for i in values {
152 self.put_one(i)
153 }
154 Ok(())
155 }
156
157 fn encoding(&self) -> Encoding {
161 Encoding::PLAIN_DICTIONARY
162 }
163
164 fn estimated_data_encoded_size(&self) -> usize {
169 let bit_width = self.bit_width();
170 RleEncoder::max_buffer_size(bit_width, self.indices.len())
171 }
172
173 fn flush_buffer(&mut self) -> Result<Bytes> {
174 self.write_indices()
175 }
176
177 fn estimated_memory_size(&self) -> usize {
181 self.interner.estimated_memory_size() + self.indices.capacity() * std::mem::size_of::<u64>()
182 }
183}
184
185#[cfg(test)]
186mod tests {
187 use std::sync::Arc;
188
189 use super::*;
190 use crate::data_type::{
191 ByteArray, ByteArrayType, FixedLenByteArray, FixedLenByteArrayType, Int32Type,
192 };
193 use crate::encodings::encoding::Encoder;
194 use crate::schema::types::{ColumnDescriptor, ColumnPath, Type as SchemaType};
195
196 fn make_col_desc<T: DataType>() -> ColumnDescPtr {
197 make_col_desc_with_length::<T>(-1)
198 }
199
200 fn make_col_desc_with_length<T: DataType>(type_length: i32) -> ColumnDescPtr {
201 let ty = SchemaType::primitive_type_builder("col", T::get_physical_type())
202 .with_length(type_length)
203 .build()
204 .unwrap();
205 Arc::new(ColumnDescriptor::new(
206 Arc::new(ty),
207 0,
208 0,
209 ColumnPath::new(vec![]),
210 ))
211 }
212
213 #[test]
214 fn test_estimated_memory_size_primitive_with_duplicates() {
215 let mut encoder = DictEncoder::<Int32Type>::new(make_col_desc::<Int32Type>());
216 let empty_size = encoder.estimated_memory_size();
217
218 encoder.put(&[1, 2, 3, 1, 2, 3, 1, 2, 3]).unwrap();
220
221 let size = encoder.estimated_memory_size();
222
223 let dict_entry_size = 3 * std::mem::size_of::<i32>();
225 assert!(
226 size >= empty_size + dict_entry_size,
227 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
228 );
229
230 let indices_size = 9 * std::mem::size_of::<u64>();
232 assert!(
233 size >= empty_size + dict_entry_size + indices_size,
234 "memory size {size} should include indices ({indices_size} bytes)"
235 );
236 }
237
238 #[test]
239 fn test_estimated_memory_size_primitive_all_distinct() {
240 let mut encoder = DictEncoder::<Int32Type>::new(make_col_desc::<Int32Type>());
241 let empty_size = encoder.estimated_memory_size();
242
243 let values: Vec<i32> = (0..100).collect();
244 encoder.put(&values).unwrap();
245
246 let size = encoder.estimated_memory_size();
247
248 let dict_entry_size = 100 * std::mem::size_of::<i32>();
250 assert!(
251 size >= empty_size + dict_entry_size,
252 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
253 );
254
255 let indices_size = 100 * std::mem::size_of::<u64>();
257 assert!(
258 size >= empty_size + dict_entry_size + indices_size,
259 "memory size {size} should include indices ({indices_size} bytes)"
260 );
261 }
262
263 #[test]
264 fn test_estimated_memory_size_byte_array_with_duplicates() {
265 let mut encoder = DictEncoder::<ByteArrayType>::new(make_col_desc::<ByteArrayType>());
266 let empty_size = encoder.estimated_memory_size();
267
268 let vals: Vec<ByteArray> = [
271 "foo", "bar", "baz", "foo", "bar", "baz", "foo", "bar", "baz",
272 ]
273 .iter()
274 .map(|s| ByteArray::from(*s))
275 .collect();
276 encoder.put(&vals).unwrap();
277
278 let size = encoder.estimated_memory_size();
279
280 let dict_entry_size = 3 * std::mem::size_of::<ByteArray>() + 3 * 3; assert!(
283 size >= empty_size + dict_entry_size,
284 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
285 );
286
287 let indices_size = 9 * std::mem::size_of::<u64>();
289 assert!(
290 size >= empty_size + dict_entry_size + indices_size,
291 "memory size {size} should include indices ({indices_size} bytes)"
292 );
293 }
294
295 #[test]
296 fn test_estimated_memory_size_byte_array_all_distinct() {
297 let mut encoder = DictEncoder::<ByteArrayType>::new(make_col_desc::<ByteArrayType>());
298 let empty_size = encoder.estimated_memory_size();
299
300 let values: Vec<ByteArray> = (0..100_u32)
302 .map(|i| ByteArray::from(i.to_string().into_bytes()))
303 .collect();
304 let bytes_total: usize = values.iter().map(|v| v.len()).sum(); encoder.put(&values).unwrap();
306
307 let size = encoder.estimated_memory_size();
308
309 let dict_entry_size = 100 * std::mem::size_of::<ByteArray>() + bytes_total;
311 assert!(
312 size >= empty_size + dict_entry_size,
313 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
314 );
315
316 let indices_size = 100 * std::mem::size_of::<u64>();
318 assert!(
319 size >= empty_size + dict_entry_size + indices_size,
320 "memory size {size} should include indices ({indices_size} bytes)"
321 );
322 }
323
324 #[test]
325 fn test_estimated_memory_size_fixed_len_byte_array_with_duplicates() {
326 const TYPE_LEN: usize = 3;
327 let mut encoder = DictEncoder::<FixedLenByteArrayType>::new(make_col_desc_with_length::<
328 FixedLenByteArrayType,
329 >(TYPE_LEN as i32));
330 let empty_size = encoder.estimated_memory_size();
331
332 let vals = [
334 b"foo", b"bar", b"baz", b"foo", b"bar", b"baz", b"foo", b"bar", b"baz",
335 ]
336 .iter()
337 .map(|b| FixedLenByteArray::from(b.to_vec()))
338 .collect::<Vec<_>>();
339 encoder.put(&vals).unwrap();
340
341 let size = encoder.estimated_memory_size();
342
343 let dict_entry_size = 3 * std::mem::size_of::<FixedLenByteArray>() + 3 * TYPE_LEN;
346 assert!(
347 size >= empty_size + dict_entry_size,
348 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
349 );
350
351 let indices_size = 9 * std::mem::size_of::<u64>();
353 assert!(
354 size >= empty_size + dict_entry_size + indices_size,
355 "memory size {size} should include indices ({indices_size} bytes)"
356 );
357 }
358
359 #[test]
360 fn test_estimated_memory_size_fixed_len_byte_array_all_distinct() {
361 const TYPE_LEN: usize = 3;
362 let mut encoder = DictEncoder::<FixedLenByteArrayType>::new(make_col_desc_with_length::<
363 FixedLenByteArrayType,
364 >(TYPE_LEN as i32));
365 let empty_size = encoder.estimated_memory_size();
366
367 let values = (0..100_u8)
369 .map(|i| FixedLenByteArray::from(vec![0u8, 0u8, i]))
370 .collect::<Vec<_>>();
371 encoder.put(&values).unwrap();
372
373 let size = encoder.estimated_memory_size();
374
375 let dict_entry_size = 100 * std::mem::size_of::<FixedLenByteArray>() + 100 * TYPE_LEN;
378 assert!(
379 size >= empty_size + dict_entry_size,
380 "memory size {size} should grow by at least the dict storage ({dict_entry_size} bytes)"
381 );
382
383 let indices_size = 100 * std::mem::size_of::<u64>();
385 assert!(
386 size >= empty_size + dict_entry_size + indices_size,
387 "memory size {size} should include indices ({indices_size} bytes)"
388 );
389 }
390
391 #[test]
392 fn test_estimated_memory_size_includes_interner_dedup_table() {
393 let encoder = DictEncoder::<Int32Type>::new(make_col_desc::<Int32Type>());
397
398 let size = encoder.estimated_memory_size();
399
400 assert!(
401 size > 0,
402 "memory size should include the preallocated dedup hash table"
403 );
404 }
405
406 #[test]
407 fn test_estimated_memory_size_accounts_for_indices_capacity() {
408 let mut encoder = DictEncoder::<Int32Type>::new(make_col_desc::<Int32Type>());
412
413 let big: Vec<i32> = vec![0; 64];
414 encoder.put(&big).unwrap();
415 let _ = encoder.flush_buffer().unwrap();
416
417 let flushed_size = encoder.estimated_memory_size();
418
419 encoder.put(&[0]).unwrap();
422
423 let size = encoder.estimated_memory_size();
424
425 assert_eq!(
426 size, flushed_size,
427 "memory size should include retained indices capacity",
428 );
429 }
430
431 #[test]
432 fn test_estimated_memory_size_accounts_for_uniques_capacity() {
433 let mut encoder = DictEncoder::<Int32Type>::new(make_col_desc::<Int32Type>());
434
435 let values: Vec<i32> = (0..64).collect();
436 encoder.put(&values).unwrap();
437 let _ = encoder.flush_buffer().unwrap();
439
440 let size1 = encoder.estimated_memory_size();
441
442 let values: Vec<i32> = (64..128).collect();
445 encoder.put(&values).unwrap();
446 let _ = encoder.flush_buffer().unwrap();
448
449 let size2 = encoder.estimated_memory_size();
450
451 let min_uniques_bytes = 64 * std::mem::size_of::<i32>();
452 assert!(
453 size2 >= size1 + min_uniques_bytes,
454 "memory size {size2} should grow from {size1} by allocated uniques capacity \
455 (at least {min_uniques_bytes} bytes)"
456 );
457 }
458}