1use 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
111struct FallbackEncoder {
113 encoder: FallbackEncoderImpl,
114 num_values: usize,
115 variable_length_bytes: i64,
116}
117
118enum 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 fn new(props: &WriterProperties, column_props: &ResolvedColumnProperties) -> Result<Self> {
141 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 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 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 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
302const SHORT_VALUE_LEN: usize = std::mem::size_of::<u64>() - 1;
304
305#[derive(Debug, PartialEq, Eq, Hash, Clone, Copy)]
307struct Entry {
308 hash: u64,
310 offset_or_inline: OffsetOrInlineView,
313 index_in_dict: u64,
314}
315
316#[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 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 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 Some(self.0)
379 } else {
380 None
381 }
382 }
383}
384
385#[derive(Debug, Default)]
386struct ByteArrayInterner {
387 state: ahash::RandomState,
388 map: hashbrown::hash_table::HashTable<Entry>,
390 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 let (found_entry, inline) = if let Some(inline) = maybe_inline_value(value) {
400 let entry = self.map.find(hash, |header| {
402 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 let entry = self.map.find(hash, |header| {
423 if header.hash != hash {
425 return false;
426 }
427
428 let Some(offset) = header.offset_or_inline.maybe_non_inlined_value() else {
430 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 self.insert(value, hash, inline)
446 }
447
448 #[inline(always)]
450 fn is_at(&self, offset: u64, value: &[u8]) -> bool {
451 let offset = offset as usize;
452 let stored_len = unsafe { self.page.get_unchecked(offset - 4..offset) };
454 if u32::from_le_bytes(stored_len.try_into().unwrap()) as usize != value.len() {
457 return false;
458 }
459 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 fn insert(
470 &mut self,
471 value: &[u8],
472 hash: u64,
473 inline: Option<OffsetOrInlineView>,
474 ) -> Result<u64> {
475 debug_assert!(inline.is_none_or(|i| i.is_inlined()));
477
478 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 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
532struct 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 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 let value = unsafe { self.values.get_unchecked(start..end) };
565
566 self.current_index = end;
567
568 Some(value)
569 }
570}
571
572#[derive(Debug, Default)]
574struct DictEncoder {
575 interner: ByteArrayInterner,
576 indices: Vec<u64>,
577 variable_length_bytes: i64,
578 dictionary_cache: Option<DictionaryCache>,
580}
581
582#[derive(Debug)]
585struct DictionaryCache {
586 values: Weak<dyn Array>,
590 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 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 fn use_dictionary_cache(&self, dictionary: &ArrayRef, num_rows: usize) -> bool {
624 dictionary.len() <= num_rows
627 || self
628 .dictionary_cache
629 .as_ref()
630 .is_some_and(|cache| cache.is_for(dictionary))
631 }
632
633 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 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 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 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 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 DataType::Dictionary(_, _) => indices.len(),
901 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 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 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 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
1002fn 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 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
1029fn 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
1053fn 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 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
1088fn max_view_value_len(buffers: &[Buffer]) -> usize {
1090 const MAX_INLINE_VIEW_LEN: usize = 12;
1092 buffers
1097 .iter()
1098 .map(|b| b.len())
1099 .max()
1100 .unwrap_or(0)
1101 .max(MAX_INLINE_VIEW_LEN)
1102}
1103
1104fn count_within_budget_views(
1108 views: &[u128],
1109 indices: &[usize],
1110 byte_budget: usize,
1111 max_value_len: usize,
1112) -> usize {
1113 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 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
1140fn 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 let prefix_overhead = std::mem::size_of::<u32>();
1160
1161 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 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#[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
1197fn 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
1222fn 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 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 assert!(encoder.use_dictionary_cache(&dictionary, 1));
1276 assert!(encoder.use_dictionary_cache(&dictionary, 0));
1277
1278 let other = string_values(3);
1280 assert!(!encoder.use_dictionary_cache(&other, 2));
1281 assert!(encoder.use_dictionary_cache(&other, 3));
1282 }
1283}