Skip to main content

parquet/arrow/arrow_writer/
byte_array.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
5use crate::basic::Encoding;
6use crate::bloom_filter::Sbbf;
7use crate::column::writer::encoder::{
8    ColumnValueEncoder, DataPageValues, DictionaryPage, create_bloom_filter,
9};
10use crate::column::writer::{compare_greater_byte_array_decimals, is_decimal_descr};
11use crate::data_type::{AsBytes, ByteArray, Int32Type};
12use crate::encodings::encoding::{DeltaBitPackEncoder, Encoder};
13use crate::encodings::rle::RleEncoder;
14use crate::errors::{ParquetError, Result};
15use crate::file::properties::{
16    EnabledStatistics, ResolvedColumnProperties, WriterProperties, WriterVersion,
17};
18use crate::geospatial::accumulator::{GeoStatsAccumulator, try_new_geo_stats_accumulator};
19use crate::geospatial::statistics::GeospatialStatistics;
20use crate::schema::types::ColumnDescPtr;
21use crate::util::bit_util::num_required_bits;
22use crate::util::prefix::common_prefix_length;
23use arrow_array::cast::AsArray;
24use arrow_array::types::{ArrowDictionaryKeyType, ByteArrayType};
25use arrow_array::{
26    Array, ArrayAccessor, ArrayRef, BinaryArray, BinaryViewArray, DictionaryArray,
27    FixedSizeBinaryArray, GenericByteArray, LargeBinaryArray, LargeStringArray, StringArray,
28    StringViewArray, TypedDictionaryArray,
29};
30use arrow_buffer::{ArrowNativeType, Buffer};
31use arrow_schema::DataType;
32use std::sync::{Arc, Weak};
33
34macro_rules! downcast_dict_impl {
35    ($array:ident, $key:ident, $val:ident, $op:expr $(, $arg:expr)*) => {{
36        $op($array
37            .as_any()
38            .downcast_ref::<DictionaryArray<arrow_array::types::$key>>()
39            .unwrap()
40            .downcast_dict::<$val>()
41            .unwrap()$(, $arg)*)
42    }};
43}
44
45macro_rules! downcast_dict_op {
46    ($key_type:expr, $val:ident, $array:ident, $op:expr $(, $arg:expr)*) => {
47        match $key_type.as_ref() {
48            DataType::UInt8 => downcast_dict_impl!($array, UInt8Type, $val, $op$(, $arg)*),
49            DataType::UInt16 => downcast_dict_impl!($array, UInt16Type, $val, $op$(, $arg)*),
50            DataType::UInt32 => downcast_dict_impl!($array, UInt32Type, $val, $op$(, $arg)*),
51            DataType::UInt64 => downcast_dict_impl!($array, UInt64Type, $val, $op$(, $arg)*),
52            DataType::Int8 => downcast_dict_impl!($array, Int8Type, $val, $op$(, $arg)*),
53            DataType::Int16 => downcast_dict_impl!($array, Int16Type, $val, $op$(, $arg)*),
54            DataType::Int32 => downcast_dict_impl!($array, Int32Type, $val, $op$(, $arg)*),
55            DataType::Int64 => downcast_dict_impl!($array, Int64Type, $val, $op$(, $arg)*),
56            _ => unreachable!(),
57        }
58    };
59}
60
61macro_rules! downcast_dict_values_op {
62    ($key_type:expr, $value_type:expr, $array:ident, $op:expr $(, $arg:expr)*) => {
63        match $value_type.as_ref() {
64            DataType::Utf8 => downcast_dict_op!($key_type, StringArray, $array, $op$(, $arg)*),
65            DataType::LargeUtf8 => {
66                downcast_dict_op!($key_type, LargeStringArray, $array, $op$(, $arg)*)
67            }
68            DataType::Utf8View => {
69                downcast_dict_op!($key_type, StringViewArray, $array, $op$(, $arg)*)
70            }
71            DataType::Binary => downcast_dict_op!($key_type, BinaryArray, $array, $op$(, $arg)*),
72            DataType::LargeBinary => {
73                downcast_dict_op!($key_type, LargeBinaryArray, $array, $op$(, $arg)*)
74            }
75            DataType::BinaryView => {
76                downcast_dict_op!($key_type, BinaryViewArray, $array, $op$(, $arg)*)
77            }
78            DataType::FixedSizeBinary(_) => {
79                downcast_dict_op!($key_type, FixedSizeBinaryArray, $array, $op$(, $arg)*)
80            }
81            d => unreachable!("cannot downcast {} dictionary value to byte array", d),
82        }
83    };
84}
85
86macro_rules! downcast_op {
87    ($data_type:expr, $array:ident, $op:expr $(, $arg:expr)*) => {
88        match $data_type {
89            DataType::Utf8 => $op($array.as_any().downcast_ref::<StringArray>().unwrap()$(, $arg)*),
90            DataType::LargeUtf8 => {
91                $op($array.as_any().downcast_ref::<LargeStringArray>().unwrap()$(, $arg)*)
92            }
93            DataType::Utf8View => $op($array.as_any().downcast_ref::<StringViewArray>().unwrap()$(, $arg)*),
94            DataType::Binary => {
95                $op($array.as_any().downcast_ref::<BinaryArray>().unwrap()$(, $arg)*)
96            }
97            DataType::LargeBinary => {
98                $op($array.as_any().downcast_ref::<LargeBinaryArray>().unwrap()$(, $arg)*)
99            }
100            DataType::BinaryView => {
101                $op($array.as_any().downcast_ref::<BinaryViewArray>().unwrap()$(, $arg)*)
102            }
103            DataType::Dictionary(key, value) => {
104                downcast_dict_values_op!(key, value, $array, $op$(, $arg)*)
105            }
106            d => unreachable!("cannot downcast {} to byte array", d),
107        }
108    };
109}
110
111/// A fallback encoder, i.e. non-dictionary, for [`ByteArray`]
112struct FallbackEncoder {
113    encoder: FallbackEncoderImpl,
114    num_values: usize,
115    variable_length_bytes: i64,
116}
117
118/// The fallback encoder in use
119///
120/// Note: DeltaBitPackEncoder is boxed as it is rather large
121enum FallbackEncoderImpl {
122    Plain {
123        buffer: Vec<u8>,
124    },
125    DeltaLength {
126        buffer: Vec<u8>,
127        lengths: Box<DeltaBitPackEncoder<Int32Type>>,
128    },
129    Delta {
130        buffer: Vec<u8>,
131        last_value: Vec<u8>,
132        prefix_lengths: Box<DeltaBitPackEncoder<Int32Type>>,
133        suffix_lengths: Box<DeltaBitPackEncoder<Int32Type>>,
134    },
135}
136
137impl FallbackEncoder {
138    /// Create the fallback encoder for the given [`WriterProperties`] and the
139    /// column settings already resolved from them
140    fn new(props: &WriterProperties, column_props: &ResolvedColumnProperties) -> Result<Self> {
141        // Set either main encoder or fallback encoder.
142        let encoding = column_props
143            .encoding
144            .unwrap_or_else(|| match props.writer_version() {
145                WriterVersion::PARQUET_1_0 => Encoding::PLAIN,
146                WriterVersion::PARQUET_2_0 => Encoding::DELTA_BYTE_ARRAY,
147            });
148
149        let encoder = match encoding {
150            Encoding::PLAIN => FallbackEncoderImpl::Plain { buffer: vec![] },
151            Encoding::DELTA_LENGTH_BYTE_ARRAY => FallbackEncoderImpl::DeltaLength {
152                buffer: vec![],
153                lengths: Box::new(DeltaBitPackEncoder::new()),
154            },
155            Encoding::DELTA_BYTE_ARRAY => FallbackEncoderImpl::Delta {
156                buffer: vec![],
157                last_value: vec![],
158                prefix_lengths: Box::new(DeltaBitPackEncoder::new()),
159                suffix_lengths: Box::new(DeltaBitPackEncoder::new()),
160            },
161            _ => {
162                return Err(general_err!(
163                    "unsupported encoding {} for byte array",
164                    encoding
165                ));
166            }
167        };
168
169        Ok(Self {
170            encoder,
171            num_values: 0,
172            variable_length_bytes: 0,
173        })
174    }
175
176    /// Encode `values` to the in-progress page
177    fn encode<T>(&mut self, values: T, indices: &[usize])
178    where
179        T: ArrayAccessor + Copy,
180        T::Item: AsRef<[u8]>,
181    {
182        self.num_values += indices.len();
183        match &mut self.encoder {
184            FallbackEncoderImpl::Plain { buffer } => {
185                for &idx in indices {
186                    let value = values.value(idx);
187                    let value = value.as_ref();
188                    buffer.extend_from_slice((value.len() as u32).as_bytes());
189                    buffer.extend_from_slice(value);
190                    self.variable_length_bytes += value.len() as i64;
191                }
192            }
193            FallbackEncoderImpl::DeltaLength { buffer, lengths } => {
194                for &idx in indices {
195                    let value = values.value(idx);
196                    let value = value.as_ref();
197                    lengths.put(&[value.len() as i32]).unwrap();
198                    buffer.extend_from_slice(value);
199                    self.variable_length_bytes += value.len() as i64;
200                }
201            }
202            FallbackEncoderImpl::Delta {
203                buffer,
204                last_value,
205                prefix_lengths,
206                suffix_lengths,
207            } => {
208                for &idx in indices {
209                    let value = values.value(idx);
210                    let value = value.as_ref();
211
212                    let prefix_length = common_prefix_length(last_value, value);
213                    let suffix_length = value.len() - prefix_length;
214
215                    last_value.clear();
216                    last_value.extend_from_slice(value);
217
218                    buffer.extend_from_slice(&value[prefix_length..]);
219                    prefix_lengths.put(&[prefix_length as i32]).unwrap();
220                    suffix_lengths.put(&[suffix_length as i32]).unwrap();
221                    self.variable_length_bytes += value.len() as i64;
222                }
223            }
224        }
225    }
226
227    /// Returns an estimate of the data page size in bytes
228    ///
229    /// This includes:
230    /// <already_written_encoded_byte_size> + <estimated_encoded_size_of_unflushed_bytes>
231    fn estimated_data_page_size(&self) -> usize {
232        match &self.encoder {
233            FallbackEncoderImpl::Plain { buffer, .. } => buffer.len(),
234            FallbackEncoderImpl::DeltaLength { buffer, lengths } => {
235                buffer.len() + lengths.estimated_data_encoded_size()
236            }
237            FallbackEncoderImpl::Delta {
238                buffer,
239                prefix_lengths,
240                suffix_lengths,
241                ..
242            } => {
243                buffer.len()
244                    + prefix_lengths.estimated_data_encoded_size()
245                    + suffix_lengths.estimated_data_encoded_size()
246            }
247        }
248    }
249
250    fn flush_data_page(
251        &mut self,
252        min_value: Option<ByteArray>,
253        max_value: Option<ByteArray>,
254    ) -> Result<DataPageValues<ByteArray>> {
255        let (buf, encoding) = match &mut self.encoder {
256            FallbackEncoderImpl::Plain { buffer } => (std::mem::take(buffer), Encoding::PLAIN),
257            FallbackEncoderImpl::DeltaLength { buffer, lengths } => {
258                let lengths = lengths.flush_buffer()?;
259
260                let mut out = Vec::with_capacity(lengths.len() + buffer.len());
261                out.extend_from_slice(&lengths);
262                out.extend_from_slice(buffer);
263                buffer.clear();
264                (out, Encoding::DELTA_LENGTH_BYTE_ARRAY)
265            }
266            FallbackEncoderImpl::Delta {
267                buffer,
268                prefix_lengths,
269                suffix_lengths,
270                last_value,
271            } => {
272                let prefix_lengths = prefix_lengths.flush_buffer()?;
273                let suffix_lengths = suffix_lengths.flush_buffer()?;
274
275                let mut out =
276                    Vec::with_capacity(prefix_lengths.len() + suffix_lengths.len() + buffer.len());
277                out.extend_from_slice(&prefix_lengths);
278                out.extend_from_slice(&suffix_lengths);
279                out.extend_from_slice(buffer);
280                buffer.clear();
281                last_value.clear();
282                (out, Encoding::DELTA_BYTE_ARRAY)
283            }
284        };
285
286        // Capture value of variable_length_bytes and reset for next page
287        let variable_length_bytes = Some(self.variable_length_bytes);
288        self.variable_length_bytes = 0;
289
290        Ok(DataPageValues {
291            buf: buf.into(),
292            num_values: std::mem::take(&mut self.num_values),
293            encoding,
294            min_value,
295            max_value,
296            nan_count: None,
297            variable_length_bytes,
298        })
299    }
300}
301
302/// Maximum size of a value that can be inlined in the hash table
303const SHORT_VALUE_LEN: usize = std::mem::size_of::<u64>() - 1;
304
305/// Entry in the hash table
306#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
307struct Entry {
308    /// hash of the value (stored to avoid recomputing it in hash table check)
309    hash: u64,
310    /// if len =< [`SHORT_VALUE_LEN`]: the data inlined
311    /// if len > [`SHORT_VALUE_LEN`], the offset of where the data starts
312    offset_or_inline: OffsetOrInlineView,
313    index_in_dict: u64,
314}
315
316/// Either offset to the dictionary page bytes or inline bytes when the bytes are short enough
317/// to avoid doing the indirection
318///
319/// For inlined view:
320///   +------------+---------------+------------------------------+
321///   | 1 bit set  | len {7 bits}  | value {56 bits}              |
322///   +------------+---------------+------------------------------+
323///
324/// For non-inlined view:
325///   +--------------+--------------------------------------------+
326///   | 1 bit unset  | offset in dict {63 bits}                   |
327///   +--------------+--------------------------------------------+
328///
329/// the inline view contain its length to avoid having another field for length in the entry
330/// since if the hashes are the same, most probably the length will be the same, so we can do the indirection check
331#[derive(Debug, Clone, Copy, PartialEq, Eq, Hash)]
332struct OffsetOrInlineView(u64);
333
334impl OffsetOrInlineView {
335    const INLINE_FLAG: u64 = 1 << 63;
336    const LEN_SHIFT: u32 = 56;
337
338    #[inline]
339    fn is_non_inlined(&self) -> bool {
340        (self.0 & Self::INLINE_FLAG) == 0
341    }
342
343    #[inline]
344    fn is_inlined(&self) -> bool {
345        !self.is_non_inlined()
346    }
347
348    #[inline]
349    fn new_inlined(value: &[u8]) -> Self {
350        debug_assert!(value.len() <= 7);
351
352        // Value bytes occupy the low 56 bits, byte 0 in the least significant position
353        let mut buf = [0u8; 8];
354        buf[..value.len()].copy_from_slice(value);
355        let packed = u64::from_le_bytes(buf);
356
357        Self(Self::INLINE_FLAG | ((value.len() as u64) << Self::LEN_SHIFT) | packed)
358    }
359
360    #[inline]
361    fn new_non_inlined(offset: u64) -> Self {
362        // `offset` is a position in the dictionary page `Vec`, whose length is at
363        // most `isize::MAX`, so it always fits in 63 bits and can't collide with
364        // `INLINE_FLAG`
365        // also, having the inline flag set for non-inlined values would mean the dictionary page is at least 9 exabytes.
366        debug_assert_eq!(
367            offset & Self::INLINE_FLAG,
368            0,
369            "dictionary page offset must fit in 63 bits"
370        );
371        let non_inlined_value = offset;
372        Self(non_inlined_value)
373    }
374
375    fn maybe_non_inlined_value(&self) -> Option<u64> {
376        if self.is_non_inlined() {
377            // Not inlined is when the first bit is unset, so the value
378            Some(self.0)
379        } else {
380            None
381        }
382    }
383}
384
385#[derive(Debug, Default)]
386struct ByteArrayInterner {
387    state: ahash::RandomState,
388    /// Underlying hash set for each distinct value
389    map: hashbrown::hash_table::HashTable<Entry>,
390    /// Encoded dictionary page: each value prefixed by its length as a `u32`
391    page: Vec<u8>,
392}
393
394impl ByteArrayInterner {
395    fn intern(&mut self, value: &[u8]) -> Result<u64> {
396        let hash = self.state.hash_one(value);
397
398        // value is "small" - can be inlined
399        let (found_entry, inline) = if let Some(inline) = maybe_inline_value(value) {
400            // is value is already present in the set?
401            let entry = self.map.find(hash, |header| {
402                // value is stored inline so no need to consult buffer
403                // (this is the "small string optimization")
404                //
405                // no need to compare the hashes since the hash is a function of the value which is compared here
406                let is_same = inline == header.offset_or_inline;
407
408                if is_same {
409                    debug_assert_eq!(
410                        header.hash, hash,
411                        "hashes must match if the values are the same"
412                    );
413                }
414
415                is_same
416            });
417
418            (entry, Some(inline))
419        } else {
420            // value is not "small"
421            // Check if the value is already present in the set
422            let entry = self.map.find(hash, |header| {
423                // compare hash
424                if header.hash != hash {
425                    return false;
426                }
427
428                // If the value is not inlined compare it
429                let Some(offset) = header.offset_or_inline.maybe_non_inlined_value() else {
430                    // that value is inline, so it must be different
431                    return false;
432                };
433
434                self.is_at(offset, value)
435            });
436
437            (entry, None)
438        };
439
440        if let Some(entry) = found_entry {
441            return Ok(entry.index_in_dict);
442        }
443
444        // if no existing entry, make a new one
445        self.insert(value, hash, inline)
446    }
447
448    /// Returns whether `value` is in the dictionary page at `offset`
449    #[inline(always)]
450    fn is_at(&self, offset: u64, value: &[u8]) -> bool {
451        let offset = offset as usize;
452        // SAFETY: every value in the page is preceded by its length
453        let stored_len = unsafe { self.page.get_unchecked(offset - 4..offset) };
454        // Rarely false, as the hashes matched, so the branch predicts well and
455        // the comparison's reads issue before the length is known
456        if u32::from_le_bytes(stored_len.try_into().unwrap()) as usize != value.len() {
457            return false;
458        }
459        // SAFETY: the value at `offset` has the length just checked
460        let existing = unsafe { self.page.get_unchecked(offset..offset + value.len()) };
461        existing == value
462    }
463
464    fn num_unique_values(&self) -> usize {
465        self.map.len()
466    }
467
468    /// Appends `value` to the dictionary, in the empty slot at `pos`
469    fn insert(
470        &mut self,
471        value: &[u8],
472        hash: u64,
473        inline: Option<OffsetOrInlineView>,
474    ) -> Result<u64> {
475        // If inline provided it should inlined
476        debug_assert!(inline.is_none_or(|i| i.is_inlined()));
477
478        // The dictionary page is PLAIN encoded, where each value is prefixed by
479        // its length as a 4-byte little endian integer so we need to reject that since we use unsafe access later
480        //
481        // From the parquet-format spec:
482        // > Encoding PLAIN:
483        // > [...] For the byte array type, it encodes the length as a 4-byte little
484        // > endian integer, followed by the bytes.
485        // >
486        // > Dictionary Encoding:
487        // > [...] Dictionary page format: the entries in the dictionary using the plain encoding.
488        // >
489        //
490        // Reference:
491        // - Plain encoding: https://github.com/apache/parquet-format/blob/53b8bd8576827080d4382fa457003f45b41cda6e/Encodings.md?plain=1#L72-L73
492        // - Plain dictionary encoding: https://github.com/apache/parquet-format/blob/53b8bd8576827080d4382fa457003f45b41cda6e/Encodings.md?plain=1#L83
493        if value.len() > u32::MAX as usize {
494            return Err(ParquetError::General(format!(
495                "Byte array value is too large to be written in dictionary: {} bytes",
496                value.len()
497            )));
498        }
499
500        let key = self.num_unique_values() as u64;
501        let len = value.len();
502
503        self.page.reserve(4 + value.len());
504        self.page.extend_from_slice(&(len as u32).to_le_bytes());
505        let offset = self.page.len() as u64;
506        self.page.extend_from_slice(value);
507
508        // Make the new entry
509        let new_header = Entry {
510            hash,
511            offset_or_inline: inline.unwrap_or_else(|| OffsetOrInlineView::new_non_inlined(offset)),
512            index_in_dict: key,
513        };
514        self.map
515            .insert_unique(hash, new_header, |header| header.hash);
516
517        Ok(key)
518    }
519
520    fn estimated_memory_size(&self) -> usize {
521        self.page.capacity() * std::mem::size_of::<u8>() + self.map.allocation_size()
522    }
523
524    fn iter(&self) -> impl Iterator<Item = &[u8]> {
525        ByteArrayInternerIterator {
526            values: &self.page,
527            current_index: 0,
528        }
529    }
530}
531
532/// Iterates the values of a [`ByteArrayInterner`]'s dictionary page
533///
534/// `values` must be a page built by [`ByteArrayInterner::insert`], which is a
535/// sequence of values each preceded by its exact length as a `u32`, and
536/// `current_index` must start at 0, so it is always at the start of a value
537struct ByteArrayInternerIterator<'a> {
538    values: &'a [u8],
539    current_index: usize,
540}
541
542impl<'a> Iterator for ByteArrayInternerIterator<'a> {
543    type Item = &'a [u8];
544
545    fn next(&mut self) -> Option<Self::Item> {
546        if self.current_index >= self.values.len() {
547            return None;
548        }
549
550        // SAFETY: `current_index` is at the start of a value and is not past
551        // the end of the page, so the value's 4-byte length prefix is in bounds
552        let len_bytes = unsafe {
553            self.values
554                .get_unchecked(self.current_index..self.current_index + 4)
555        };
556        let len = u32::from_le_bytes(len_bytes.try_into().unwrap()) as usize;
557
558        let start = self.current_index + 4;
559        let end = start + len;
560
561        // SAFETY: `insert` writes exactly `len` bytes after the prefix, and
562        // rejects values whose length does not fit in a `u32`, so the prefix is
563        // never truncated and `start..end` is within the page
564        let value = unsafe { self.values.get_unchecked(start..end) };
565
566        self.current_index = end;
567
568        Some(value)
569    }
570}
571
572/// A dictionary encoder for byte array data
573#[derive(Debug, Default)]
574struct DictEncoder {
575    interner: ByteArrayInterner,
576    indices: Vec<u64>,
577    variable_length_bytes: i64,
578    /// The interned index of each value of the last arrow dictionary encoded
579    dictionary_cache: Option<DictionaryCache>,
580}
581
582/// The interned index of each value of an arrow dictionary, so each value is hashed once
583/// rather than once per row that references it
584#[derive(Debug)]
585struct DictionaryCache {
586    /// The dictionary's values, to identify the dictionary in later batches. A weak reference,
587    /// so the values aren't kept alive, while their allocation can't be reused by another
588    /// dictionary
589    values: Weak<dyn Array>,
590    /// The interned index of each value, or [`DictionaryCache::NOT_INTERNED`]
591    interned: Vec<u64>,
592}
593
594impl DictionaryCache {
595    const NOT_INTERNED: u64 = u64::MAX;
596
597    fn is_for(&self, dictionary: &ArrayRef) -> bool {
598        std::ptr::addr_eq(self.values.as_ptr(), Arc::as_ptr(dictionary))
599    }
600}
601
602impl DictEncoder {
603    /// Encode `values` to the in-progress page
604    fn encode<T>(&mut self, values: T, indices: &[usize]) -> Result<()>
605    where
606        T: ArrayAccessor + Copy,
607        T::Item: AsRef<[u8]>,
608    {
609        self.indices.reserve(indices.len());
610
611        for &idx in indices {
612            let value = values.value(idx);
613            let interned = self.interner.intern(value.as_ref())?;
614            self.indices.push(interned);
615            self.variable_length_bytes += value.as_ref().len() as i64;
616        }
617
618        Ok(())
619    }
620
621    /// Whether to encode the rows of an arrow dictionary with `dictionary` as its values and
622    /// `num_rows` rows with [`Self::encode_dictionary`]
623    fn use_dictionary_cache(&self, dictionary: &ArrayRef, num_rows: usize) -> bool {
624        // A new cache has a slot per dictionary value, which only pays off if the values are
625        // referenced by enough rows
626        dictionary.len() <= num_rows
627            || self
628                .dictionary_cache
629                .as_ref()
630                .is_some_and(|cache| cache.is_for(dictionary))
631    }
632
633    /// Encode the rows of an arrow dictionary at `indices` to the in-progress page
634    fn encode_dictionary<'a, K, V>(
635        &mut self,
636        values: TypedDictionaryArray<'a, K, V>,
637        indices: &[usize],
638        dictionary: &ArrayRef,
639    ) -> Result<()>
640    where
641        K: ArrowDictionaryKeyType,
642        &'a V: ArrayAccessor,
643        <&'a V as ArrayAccessor>::Item: AsRef<[u8]>,
644    {
645        let cache = match &mut self.dictionary_cache {
646            Some(cache) if cache.is_for(dictionary) => cache,
647            cache => cache.insert(DictionaryCache {
648                values: Arc::downgrade(dictionary),
649                interned: vec![DictionaryCache::NOT_INTERNED; dictionary.len()],
650            }),
651        };
652
653        let keys = values.keys().values();
654        let dictionary_values = values.values();
655        self.indices.reserve(indices.len());
656        for &idx in indices {
657            let key = keys[idx].as_usize();
658
659            // Shadowed for lifetime reasons
660            let value = dictionary_values.value(key);
661            let value = value.as_ref();
662
663            let mut interned = cache.interned[key];
664            if interned == DictionaryCache::NOT_INTERNED {
665                interned = self.interner.intern(value)?;
666                cache.interned[key] = interned;
667            }
668            self.indices.push(interned);
669            self.variable_length_bytes += value.len() as i64;
670        }
671
672        Ok(())
673    }
674
675    fn bit_width(&self) -> u8 {
676        let length = self.interner.num_unique_values();
677        num_required_bits(length.saturating_sub(1) as u64)
678    }
679
680    fn estimated_memory_size(&self) -> usize {
681        let dictionary_cache_size = self
682            .dictionary_cache
683            .as_ref()
684            .map(|cache| cache.interned.capacity() * std::mem::size_of::<u64>())
685            .unwrap_or_default();
686        self.interner.estimated_memory_size()
687            + self.indices.capacity() * std::mem::size_of::<u64>()
688            + dictionary_cache_size
689    }
690
691    fn estimated_data_page_size(&self) -> usize {
692        let bit_width = self.bit_width();
693        1 + RleEncoder::max_buffer_size(bit_width, self.indices.len())
694    }
695
696    fn estimated_dict_page_size(&self) -> usize {
697        self.interner.page.len()
698    }
699
700    fn flush_dict_page(self) -> DictionaryPage {
701        let unique_values = self.interner.num_unique_values();
702        let bytes = self.interner.page;
703
704        DictionaryPage {
705            buf: bytes.into(),
706            num_values: unique_values,
707            is_sorted: false,
708        }
709    }
710
711    fn flush_data_page(
712        &mut self,
713        min_value: Option<ByteArray>,
714        max_value: Option<ByteArray>,
715    ) -> DataPageValues<ByteArray> {
716        let num_values = self.indices.len();
717        let buffer_len = self.estimated_data_page_size();
718        let mut buffer = Vec::with_capacity(buffer_len);
719        buffer.push(self.bit_width());
720
721        let mut encoder = RleEncoder::new_from_buf(self.bit_width(), buffer);
722        encoder.put_batch(&self.indices);
723
724        self.indices.clear();
725
726        // Capture value of variable_length_bytes and reset for next page
727        let variable_length_bytes = Some(self.variable_length_bytes);
728        self.variable_length_bytes = 0;
729
730        DataPageValues {
731            buf: encoder.consume().into(),
732            num_values,
733            encoding: Encoding::RLE_DICTIONARY,
734            min_value,
735            max_value,
736            nan_count: None,
737            variable_length_bytes,
738        }
739    }
740}
741
742fn maybe_inline_value(value: &[u8]) -> Option<OffsetOrInlineView> {
743    if value.len() <= SHORT_VALUE_LEN {
744        Some(OffsetOrInlineView::new_inlined(value))
745    } else {
746        None
747    }
748}
749
750pub struct ByteArrayEncoder {
751    fallback: FallbackEncoder,
752    dict_encoder: Option<DictEncoder>,
753    statistics_enabled: EnabledStatistics,
754    min_value: Option<ByteArray>,
755    max_value: Option<ByteArray>,
756    bloom_filter: Option<Sbbf>,
757    bloom_filter_target_fpp: f64,
758    geo_stats_accumulator: Option<Box<dyn GeoStatsAccumulator>>,
759    is_decimal: bool,
760}
761
762impl ColumnValueEncoder for ByteArrayEncoder {
763    type T = ByteArray;
764    type Values = dyn Array;
765    fn flush_bloom_filter(&mut self) -> Option<Sbbf> {
766        let mut sbbf = self.bloom_filter.take()?;
767        sbbf.fold_to_target_fpp(self.bloom_filter_target_fpp);
768        Some(sbbf)
769    }
770
771    fn try_new(
772        descr: &ColumnDescPtr,
773        props: &WriterProperties,
774        column_props: &ResolvedColumnProperties,
775    ) -> Result<Self>
776    where
777        Self: Sized,
778    {
779        let dictionary = column_props.dictionary_enabled.then(DictEncoder::default);
780
781        let fallback = FallbackEncoder::new(props, column_props)?;
782
783        let (bloom_filter, bloom_filter_target_fpp) = create_bloom_filter(column_props)?;
784
785        let statistics_enabled = column_props.statistics_enabled;
786
787        let geo_stats_accumulator = try_new_geo_stats_accumulator(descr);
788
789        let is_decimal = is_decimal_descr(descr.get_basic_info());
790
791        Ok(Self {
792            fallback,
793            statistics_enabled,
794            bloom_filter,
795            bloom_filter_target_fpp,
796            dict_encoder: dictionary,
797            min_value: None,
798            max_value: None,
799            geo_stats_accumulator,
800            is_decimal,
801        })
802    }
803
804    fn write(&mut self, _values: &Self::Values, _offset: usize, _len: usize) -> Result<()> {
805        unreachable!("should call write_gather instead")
806    }
807
808    fn write_gather(
809        &mut self,
810        values: &Self::Values,
811        indices: &[usize],
812        num_values_in_batch: usize,
813    ) -> Result<()> {
814        if let DataType::Dictionary(key, value) = values.data_type() {
815            let dictionary = values.as_any_dictionary().values();
816            if self.dict_encoder.as_ref().is_some_and(|encoder| {
817                encoder.use_dictionary_cache(dictionary, num_values_in_batch)
818            }) {
819                return downcast_dict_values_op!(
820                    key,
821                    value,
822                    values,
823                    encode_with_dictionary_cache,
824                    indices,
825                    dictionary,
826                    self
827                );
828            }
829        }
830
831        downcast_op!(values.data_type(), values, encode, indices, self)
832    }
833
834    fn count_values_within_byte_budget_gather(
835        values: &Self::Values,
836        indices: &[usize],
837        byte_budget: usize,
838    ) -> Option<usize> {
839        // `ByteArrayEncoder` only ever writes via `write_gather`, so this
840        // is the relevant method.
841        //
842        // Two-stage walk for the simple offset-buffer byte array types:
843        //   1. If indices are contiguous, compute the total payload in
844        //      O(1) via a single subtraction on the offsets buffer.
845        //      When the total fits the budget — the overwhelmingly
846        //      common "small values" case — return immediately.
847        //   2. Otherwise, walk per-value byte sizes from the offsets
848        //      buffer (still cheap, no slice/UTF-8 construction) and
849        //      exit at the first value that pushes the cumulative sum
850        //      past the budget. This bounds skewed distributions: an
851        //      outlier value is caught wherever it lands in the chunk.
852        let count = match values.data_type() {
853            DataType::Utf8 => count_within_budget_offsets(
854                values.as_any().downcast_ref::<StringArray>().unwrap(),
855                indices,
856                byte_budget,
857            ),
858            DataType::LargeUtf8 => count_within_budget_offsets(
859                values.as_any().downcast_ref::<LargeStringArray>().unwrap(),
860                indices,
861                byte_budget,
862            ),
863            DataType::Binary => count_within_budget_offsets(
864                values.as_any().downcast_ref::<BinaryArray>().unwrap(),
865                indices,
866                byte_budget,
867            ),
868            DataType::LargeBinary => count_within_budget_offsets(
869                values.as_any().downcast_ref::<LargeBinaryArray>().unwrap(),
870                indices,
871                byte_budget,
872            ),
873            // View arrays carry each value's length in the low 32 bits of
874            // its u128 view word, so lengths are scannable without touching
875            // any data buffer — and the common small-value case skips even
876            // that scan via an O(1) conservative bound.
877            DataType::Utf8View => {
878                let array = values.as_any().downcast_ref::<StringViewArray>().unwrap();
879                count_within_budget_views(
880                    array.views(),
881                    indices,
882                    byte_budget,
883                    max_view_value_len(array.data_buffers()),
884                )
885            }
886            DataType::BinaryView => {
887                let array = values.as_any().downcast_ref::<BinaryViewArray>().unwrap();
888                count_within_budget_views(
889                    array.views(),
890                    indices,
891                    byte_budget,
892                    max_view_value_len(array.data_buffers()),
893                )
894            }
895            // The values in an arrow dictionary are already small and
896            // deduplicated, so there is nothing to bound — treat every
897            // chunk as fitting and stay on the batched path. (A per-value
898            // walk through dict keys on every chunk also measured ~+30-80%
899            // slower than `main`.)
900            DataType::Dictionary(_, _) => indices.len(),
901            // Every byte-array type `ByteArrayEncoder` is constructed for
902            // has an explicit arm above. A `Dictionary(value = FixedSizeBinary)`
903            // column hits the `Dictionary(_, _)` arm (its `values.data_type()`
904            // is `Dictionary`), and a bare `FixedSizeBinary` column is routed
905            // to the generic column writer, never this encoder — so no other
906            // type can reach here.
907            data_type => unreachable!("ByteArrayEncoder cannot be constructed for {data_type:?}"),
908        };
909        Some(count)
910    }
911
912    fn num_values(&self) -> usize {
913        match &self.dict_encoder {
914            Some(encoder) => encoder.indices.len(),
915            None => self.fallback.num_values,
916        }
917    }
918
919    fn has_dictionary(&self) -> bool {
920        self.dict_encoder.is_some()
921    }
922
923    fn compresses_against_previous_value(&self) -> bool {
924        // While dictionary encoding is active the data page holds RLE
925        // indices, which carry no cross-value state; only the DELTA_BYTE_ARRAY
926        // fallback shares prefixes with the preceding value.
927        self.dict_encoder.is_none()
928            && matches!(self.fallback.encoder, FallbackEncoderImpl::Delta { .. })
929    }
930
931    fn estimated_memory_size(&self) -> usize {
932        let encoder_size = match &self.dict_encoder {
933            Some(encoder) => encoder.estimated_memory_size(),
934            // For the FallbackEncoder, these unflushed bytes are already encoded.
935            // Therefore, the size should be the same as estimated_data_page_size.
936            None => self.fallback.estimated_data_page_size(),
937        };
938
939        let bloom_filter_size = self
940            .bloom_filter
941            .as_ref()
942            .map(|bf| bf.estimated_memory_size())
943            .unwrap_or_default();
944
945        let stats_size = self.min_value.as_ref().map(|v| v.len()).unwrap_or_default()
946            + self.max_value.as_ref().map(|v| v.len()).unwrap_or_default();
947
948        encoder_size + bloom_filter_size + stats_size
949    }
950
951    fn estimated_dict_page_size(&self) -> Option<usize> {
952        Some(self.dict_encoder.as_ref()?.estimated_dict_page_size())
953    }
954
955    /// Returns an estimate of the data page size in bytes
956    ///
957    /// This includes:
958    /// <already_written_encoded_byte_size> + <estimated_encoded_size_of_unflushed_bytes>
959    fn estimated_data_page_size(&self) -> usize {
960        match &self.dict_encoder {
961            Some(encoder) => encoder.estimated_data_page_size(),
962            None => self.fallback.estimated_data_page_size(),
963        }
964    }
965
966    fn flush_dict_page(&mut self) -> Result<Option<DictionaryPage>> {
967        match self.dict_encoder.take() {
968            Some(encoder) => {
969                if !encoder.indices.is_empty() {
970                    return Err(general_err!(
971                        "Must flush data pages before flushing dictionary"
972                    ));
973                }
974
975                if let Some(bloom_filter) = &mut self.bloom_filter {
976                    for value in encoder.interner.iter() {
977                        bloom_filter.insert(value);
978                    }
979                }
980
981                Ok(Some(encoder.flush_dict_page()))
982            }
983            _ => Ok(None),
984        }
985    }
986
987    fn flush_data_page(&mut self) -> Result<DataPageValues<ByteArray>> {
988        let min_value = self.min_value.take();
989        let max_value = self.max_value.take();
990
991        match &mut self.dict_encoder {
992            Some(encoder) => Ok(encoder.flush_data_page(min_value, max_value)),
993            _ => self.fallback.flush_data_page(min_value, max_value),
994        }
995    }
996
997    fn flush_geospatial_statistics(&mut self) -> Option<Box<GeospatialStatistics>> {
998        self.geo_stats_accumulator.as_mut().map(|a| a.finish())?
999    }
1000}
1001
1002/// Encodes the provided `values` and `indices` to `encoder`
1003///
1004/// This is a free function so it can be used with `downcast_op!`
1005fn encode<T>(values: T, indices: &[usize], encoder: &mut ByteArrayEncoder) -> Result<()>
1006where
1007    T: ArrayAccessor + Copy,
1008    T::Item: Copy + Ord + AsRef<[u8]>,
1009{
1010    update_statistics(values, indices, encoder);
1011
1012    // While a dictionary is in use the filter is populated from its distinct values in
1013    // `flush_dict_page`, so each value is hashed once rather than once per row.
1014    match &mut encoder.dict_encoder {
1015        Some(dict_encoder) => dict_encoder.encode(values, indices),
1016        None => {
1017            if let Some(bloom_filter) = &mut encoder.bloom_filter {
1018                for &idx in indices {
1019                    bloom_filter.insert(values.value(idx).as_ref());
1020                }
1021            }
1022            encoder.fallback.encode(values, indices);
1023
1024            Ok(())
1025        }
1026    }
1027}
1028
1029/// Encodes the rows of an arrow dictionary at `indices` to `encoder`, which must have a
1030/// dictionary encoder
1031///
1032/// This is a free function so it can be used with `downcast_dict_values_op!`
1033fn encode_with_dictionary_cache<'a, K, V>(
1034    values: TypedDictionaryArray<'a, K, V>,
1035    indices: &[usize],
1036    dictionary: &ArrayRef,
1037    encoder: &mut ByteArrayEncoder,
1038) -> Result<()>
1039where
1040    K: ArrowDictionaryKeyType,
1041    V: Sync + Send,
1042    &'a V: ArrayAccessor,
1043    <&'a V as ArrayAccessor>::Item: Copy + Ord + Default + AsRef<[u8]>,
1044{
1045    update_statistics(values, indices, encoder);
1046    encoder
1047        .dict_encoder
1048        .as_mut()
1049        .expect("dictionary encoder")
1050        .encode_dictionary(values, indices, dictionary)
1051}
1052
1053/// Updates the statistics of `encoder` with the values at `indices`
1054fn update_statistics<T>(values: T, indices: &[usize], encoder: &mut ByteArrayEncoder)
1055where
1056    T: ArrayAccessor + Copy,
1057    T::Item: Copy + Ord + AsRef<[u8]>,
1058{
1059    if encoder.statistics_enabled != EnabledStatistics::None {
1060        if let Some(accumulator) = encoder.geo_stats_accumulator.as_mut() {
1061            update_geo_stats_accumulator(accumulator.as_mut(), values, indices);
1062        } else if let Some((min, max)) = compute_min_max(values, indices, encoder.is_decimal) {
1063            // Compare before copying: `write_gather` runs once per
1064            // mini-batch, and a byte-budgeted mini-batch of large values can
1065            // hold a single value, so an unconditional copy here would
1066            // duplicate every value once for `min` and once for `max`.
1067            let min = min.as_ref();
1068            if encoder
1069                .min_value
1070                .as_ref()
1071                .is_none_or(|m| is_greater(encoder.is_decimal, m.data(), min))
1072            {
1073                encoder.min_value = Some(min.to_vec().into());
1074            }
1075
1076            let max = max.as_ref();
1077            if encoder
1078                .max_value
1079                .as_ref()
1080                .is_none_or(|m| is_greater(encoder.is_decimal, max, m.data()))
1081            {
1082                encoder.max_value = Some(max.to_vec().into());
1083            }
1084        }
1085    }
1086}
1087
1088/// Upper bound on any single value's byte length in a view array.
1089fn max_view_value_len(buffers: &[Buffer]) -> usize {
1090    /// Bytes that fit inline in a u128 view word (the rest is len + prefix).
1091    const MAX_INLINE_VIEW_LEN: usize = 12;
1092    // An out-of-line view's data is a contiguous slice of exactly one data
1093    // buffer, so it cannot exceed the largest buffer; inline views hold at
1094    // most `MAX_INLINE_VIEW_LEN`. Loose (a value is usually far smaller than
1095    // a whole buffer) but O(number of buffers) and always sound.
1096    buffers
1097        .iter()
1098        .map(|b| b.len())
1099        .max()
1100        .unwrap_or(0)
1101        .max(MAX_INLINE_VIEW_LEN)
1102}
1103
1104/// Number of leading `indices` whose cumulative plain-encoded size fits
1105/// `byte_budget` (boundary value included), for view arrays (`Utf8View`,
1106/// `BinaryView`).
1107fn count_within_budget_views(
1108    views: &[u128],
1109    indices: &[usize],
1110    byte_budget: usize,
1111    max_value_len: usize,
1112) -> usize {
1113    // Each plain-encoded BYTE_ARRAY value carries a 4-byte length prefix, so
1114    // the budget is compared against `value_len + std::mem::size_of::<u32>()` — the
1115    // bytes actually written to the page, not just the payload.
1116    //
1117    // Stage 1: O(1) conservative bound. View arrays have no prefix-sum
1118    // offsets buffer, so the exact span subtraction used by
1119    // `count_within_budget_offsets` is unavailable; instead bound every
1120    // value by `max_value_len`. Skips the walk for the common small-value
1121    // case (what view arrays are built for, and where there is nothing to
1122    // bound).
1123    let per_value = max_value_len + std::mem::size_of::<u32>();
1124    if indices.len().saturating_mul(per_value) <= byte_budget {
1125        return indices.len();
1126    }
1127    // Stage 2: exact per-value scan, reading each length from the low 32
1128    // bits of its u128 view word (no data-buffer dereference).
1129    let mut cum: usize = 0;
1130    for (i, idx) in indices.iter().enumerate() {
1131        let len = (views[*idx] as u32) as usize;
1132        cum = cum.saturating_add(len + std::mem::size_of::<u32>());
1133        if cum > byte_budget {
1134            return i + 1;
1135        }
1136    }
1137    indices.len()
1138}
1139
1140/// Number of leading `indices` whose cumulative plain-encoded size fits
1141/// `byte_budget` (boundary value included), for offset-buffer byte arrays
1142/// (`Utf8`/`LargeUtf8`/`Binary`/`LargeBinary`).
1143///
1144/// `indices` are assumed sorted ascending — they always are here, since
1145/// they come from `non_null_indices`, which is built in array order.
1146fn count_within_budget_offsets<T: ByteArrayType>(
1147    values: &GenericByteArray<T>,
1148    indices: &[usize],
1149    byte_budget: usize,
1150) -> usize {
1151    if indices.is_empty() {
1152        return 0;
1153    }
1154    let n = indices.len();
1155    let first = indices[0];
1156    let last = indices[n - 1];
1157    let offsets = values.value_offsets();
1158    // Each plain-encoded value carries a 4-byte length prefix on the page.
1159    let prefix_overhead = std::mem::size_of::<u32>();
1160
1161    // Stage 1: O(1) span upper bound. The span `offsets[last+1] -
1162    // offsets[first]` covers every array position in `[first, last]`, a
1163    // superset of `indices` — and the skipped positions in a nullable
1164    // column are nulls with zero offset delta, so the span still equals the
1165    // exact payload. If it fits the budget, every value fits. Covers the
1166    // common small-value case for both non-null and (sparse) nullable
1167    // columns.
1168    if last >= first {
1169        let payload = (offsets[last + 1] - offsets[first]).as_usize();
1170        if payload + n * prefix_overhead <= byte_budget {
1171            return n;
1172        }
1173    }
1174
1175    // Stage 2: scan per-index lengths from the offsets buffer.
1176    let mut cum: usize = 0;
1177    for (i, idx) in indices.iter().enumerate() {
1178        let len = (offsets[idx + 1] - offsets[*idx]).as_usize() + prefix_overhead;
1179        cum = cum.saturating_add(len);
1180        if cum > byte_budget {
1181            return i + 1;
1182        }
1183    }
1184    n
1185}
1186
1187/// Returns `true` if `a > b`.
1188#[inline]
1189fn is_greater(is_decimal: bool, a: &[u8], b: &[u8]) -> bool {
1190    if is_decimal {
1191        compare_greater_byte_array_decimals(a, b)
1192    } else {
1193        a > b
1194    }
1195}
1196
1197/// Computes the min and max for the provided array and indices
1198///
1199/// This is a free function so it can be used with `downcast_op!`
1200fn compute_min_max<T>(array: T, valid: &[usize], is_decimal: bool) -> Option<(T::Item, T::Item)>
1201where
1202    T: ArrayAccessor,
1203    T::Item: Copy + Ord + AsRef<[u8]>,
1204{
1205    let (&first_idx, valid) = valid.split_first()?;
1206
1207    let first_val = array.value(first_idx);
1208    let mut min = first_val;
1209    let mut max = first_val;
1210    for &idx in valid {
1211        let val = array.value(idx);
1212        if is_greater(is_decimal, min.as_ref(), val.as_ref()) {
1213            min = val;
1214        }
1215        if is_greater(is_decimal, val.as_ref(), max.as_ref()) {
1216            max = val;
1217        }
1218    }
1219    Some((min, max))
1220}
1221
1222/// Updates geospatial statistics for the provided array and indices
1223fn update_geo_stats_accumulator<T>(bounder: &mut dyn GeoStatsAccumulator, array: T, valid: &[usize])
1224where
1225    T: ArrayAccessor,
1226    T::Item: Copy + Ord + AsRef<[u8]>,
1227{
1228    if !bounder.is_valid() {
1229        return;
1230    }
1231
1232    for &idx in valid {
1233        let val = array.value(idx);
1234        bounder.update_wkb(val.as_ref());
1235    }
1236}
1237
1238#[cfg(test)]
1239mod tests {
1240    use super::*;
1241    use arrow_array::{DictionaryArray, Int32Array, StringArray};
1242
1243    fn string_values(n: usize) -> ArrayRef {
1244        Arc::new(StringArray::from_iter_values(
1245            (0..n).map(|i| format!("v{i}")),
1246        ))
1247    }
1248
1249    #[test]
1250    fn use_dictionary_cache_new_dictionary() {
1251        let encoder = DictEncoder::default();
1252        let dictionary = string_values(3);
1253
1254        // A new cache only pays off with at least one row per dictionary value
1255        assert!(encoder.use_dictionary_cache(&dictionary, 4));
1256        assert!(encoder.use_dictionary_cache(&dictionary, 3));
1257        assert!(!encoder.use_dictionary_cache(&dictionary, 2));
1258        assert!(!encoder.use_dictionary_cache(&dictionary, 0));
1259    }
1260
1261    #[test]
1262    fn use_dictionary_cache_cached_dictionary() {
1263        let mut encoder = DictEncoder::default();
1264        let dictionary = string_values(3);
1265        let array = DictionaryArray::new(Int32Array::from(vec![0, 1, 2]), dictionary.clone());
1266        encoder
1267            .encode_dictionary(
1268                array.downcast_dict::<StringArray>().unwrap(),
1269                &[0, 1, 2],
1270                &dictionary,
1271            )
1272            .unwrap();
1273
1274        // An existing cache is reused however few rows reference it
1275        assert!(encoder.use_dictionary_cache(&dictionary, 1));
1276        assert!(encoder.use_dictionary_cache(&dictionary, 0));
1277
1278        // Equal values in a different allocation do not use the existing cache
1279        let other = string_values(3);
1280        assert!(!encoder.use_dictionary_cache(&other, 2));
1281        assert!(encoder.use_dictionary_cache(&other, 3));
1282    }
1283}