Skip to main content

parquet/encodings/encoding/
dict_encoder.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5// ----------------------------------------------------------------------
6// Dictionary encoding
7
8use 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 of unique values (keys) in the dictionary, in bytes.
25    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
63/// Dictionary encoder.
64/// The dictionary encoding builds a dictionary of values encountered in a given column.
65/// The dictionary page is written first, before the data pages of the column chunk.
66///
67/// Dictionary page format: the entries in the dictionary - in dictionary order -
68/// using the plain encoding.
69///
70/// Data page format: the bit width used to encode the entry ids stored as 1 byte
71/// (max bit width = 32), followed by the values encoded using RLE/Bit packed described
72/// above (with the given bit width).
73pub struct DictEncoder<T: DataType> {
74    interner: Interner<KeyStorage<T>>,
75
76    /// The buffered indices
77    indices: Vec<u64>,
78}
79
80impl<T: DataType> DictEncoder<T> {
81    /// Creates new dictionary encoder.
82    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    /// Returns true if dictionary entries are sorted, false otherwise.
96    pub fn is_sorted(&self) -> bool {
97        // Sorting is not supported currently.
98        false
99    }
100
101    /// Returns number of unique values (keys) in the dictionary.
102    pub fn num_entries(&self) -> usize {
103        self.interner.storage().uniques.len()
104    }
105
106    /// Returns the distinct values interned so far, in dictionary order.
107    pub fn uniques(&self) -> &[T::T] {
108        &self.interner.storage().uniques
109    }
110
111    /// Returns size of unique values (keys) in the dictionary, in bytes.
112    pub fn dict_encoded_size(&self) -> usize {
113        self.interner.storage().size_in_bytes
114    }
115
116    /// Writes out the dictionary values with PLAIN encoding in a byte buffer, and return
117    /// the result.
118    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    /// Writes out the dictionary values with RLE encoding in a byte buffer, and return
125    /// the result.
126    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        // Write bit width in the first byte
132        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    // Performance Note:
158    // As far as can be seen these functions are rarely called and as such we can hint to the
159    // compiler that they dont need to be folded into hot locations in the final output.
160    fn encoding(&self) -> Encoding {
161        Encoding::PLAIN_DICTIONARY
162    }
163
164    /// Returns an estimate of the data page size in bytes
165    ///
166    /// This includes:
167    /// <already_written_encoded_byte_size> + <estimated_encoded_size_of_unflushed_bytes>
168    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    /// Returns the estimated total memory usage
178    ///
179    /// For this encoder, the indices are unencoded bytes (refer to [`Self::write_indices`]).
180    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        // 3 distinct values, repeated to produce 9 indices total.
219        encoder.put(&[1, 2, 3, 1, 2, 3, 1, 2, 3]).unwrap();
220
221        let size = encoder.estimated_memory_size();
222
223        // Must account for the 3 unique dictionary entries.
224        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        // Must also account for the 9 buffered indices.
231        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        // Must account for the 100 unique dictionary entries.
249        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        // Must also account for the 100 buffered indices.
256        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        // 3 distinct byte strings ("foo", "bar", "baz" — 3 bytes each), repeated to produce
269        // 9 indices total.
270        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        // Must account for the 3 unique dictionary entries, including their heap-allocated bytes.
281        let dict_entry_size = 3 * std::mem::size_of::<ByteArray>() + 3 * 3; // 3 values × 3 bytes each
282        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        // Must also account for the 9 buffered indices.
288        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        // 100 distinct values: "0".."9" (1 byte each) and "10".."99" (2 bytes each).
301        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(); // 10×1 + 90×2 = 190
305        encoder.put(&values).unwrap();
306
307        let size = encoder.estimated_memory_size();
308
309        // Must account for the 100 unique dictionary entries, including their heap-allocated bytes.
310        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        // Must also account for the 100 buffered indices.
317        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        // 3 distinct 3-byte values, repeated to produce 9 indices total.
333        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        // Must account for the 3 unique dictionary entries: struct overhead plus the
344        // fixed-length bytes allocated per entry.
345        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        // Must also account for the 9 buffered indices.
352        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        // 100 distinct 3-byte values: zero-padded big-endian u8 indices.
368        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        // Must account for the 100 unique dictionary entries: struct overhead plus the
376        // fixed-length bytes allocated per entry.
377        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        // Must also account for the 100 buffered indices.
384        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        // The dedup `HashTable` in `Interner` is preallocated with
394        // `DEFAULT_DEDUP_CAPACITY` slots at construction, independent of any
395        // values pushed.
396        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        // Exercises the `indices.capacity()` (not `.len()`) accounting.
409        // After a flush, `indices` is cleared but its capacity is retained; pushing a
410        // smaller batch afterwards leaves capacity strictly greater than length.
411        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        // Push a single value — indices.len() == 1 but indices.capacity() >= 64.
420        // No change on the key storage since the value is already interned.
421        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        // Flush indices so they don't mask the uniques accounting in the lower bound.
438        let _ = encoder.flush_buffer().unwrap();
439
440        let size1 = encoder.estimated_memory_size();
441
442        // Push more values to trigger uniques capacity growth.
443        // The pre-allocated dedup hash table is unlikely to be resized.
444        let values: Vec<i32> = (64..128).collect();
445        encoder.put(&values).unwrap();
446        // Flush indices so they don't mask the uniques accounting in the lower bound.
447        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}