Skip to main content

parquet/column/writer/
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
5use bytes::Bytes;
6
7use crate::basic::{ConvertedType, Encoding, LogicalType, Type};
8use crate::bloom_filter::Sbbf;
9use crate::column::writer::{fallback_encoding, has_dictionary_support, update_max, update_min};
10use crate::data_type::DataType;
11use crate::data_type::private::ParquetValueType;
12use crate::encodings::encoding::{DictEncoder, Encoder, get_encoder_with_properties};
13use crate::errors::{ParquetError, Result};
14use crate::file::properties::{EnabledStatistics, ResolvedColumnProperties, WriterProperties};
15use crate::geospatial::accumulator::{GeoStatsAccumulator, try_new_geo_stats_accumulator};
16use crate::geospatial::statistics::GeospatialStatistics;
17use crate::schema::types::ColumnDescPtr;
18
19/// A collection of [`ParquetValueType`] encoded by a [`ColumnValueEncoder`]
20pub trait ColumnValues {
21    /// The number of values in this collection
22    fn len(&self) -> usize;
23}
24
25#[cfg(feature = "arrow")]
26impl ColumnValues for dyn arrow_array::Array {
27    fn len(&self) -> usize {
28        arrow_array::Array::len(self)
29    }
30}
31
32impl<T: ParquetValueType> ColumnValues for [T] {
33    fn len(&self) -> usize {
34        self.len()
35    }
36}
37
38/// The encoded data for a dictionary page
39pub struct DictionaryPage {
40    pub buf: Bytes,
41    pub num_values: usize,
42    pub is_sorted: bool,
43}
44
45/// The encoded values for a data page, with optional statistics
46pub struct DataPageValues<T> {
47    pub buf: Bytes,
48    pub num_values: usize,
49    pub encoding: Encoding,
50    pub min_value: Option<T>,
51    pub max_value: Option<T>,
52    pub nan_count: Option<u64>,
53    pub variable_length_bytes: Option<i64>,
54}
55
56/// A generic encoder of [`ColumnValues`] to data and dictionary pages used by
57/// [`super::GenericColumnWriter`]
58pub trait ColumnValueEncoder {
59    /// The underlying value type of [`Self::Values`]
60    ///
61    /// Note: this avoids needing to fully qualify `<Self::Values as ColumnValues>::T`
62    type T: ParquetValueType;
63
64    /// The values encoded by this encoder
65    type Values: ColumnValues + ?Sized;
66
67    /// Create a new [`ColumnValueEncoder`]
68    ///
69    /// `column_props` holds the settings in `props` that apply specifically to
70    /// `descr`, already resolved by the caller.
71    #[expect(
72        private_interfaces,
73        reason = "this trait is not nameable outside the crate"
74    )]
75    fn try_new(
76        descr: &ColumnDescPtr,
77        props: &WriterProperties,
78        column_props: &ResolvedColumnProperties,
79    ) -> Result<Self>
80    where
81        Self: Sized;
82
83    /// Write the corresponding values to this [`ColumnValueEncoder`]
84    fn write(&mut self, values: &Self::Values, offset: usize, len: usize) -> Result<()>;
85
86    /// Write the values at the indexes in `indices` to this [`ColumnValueEncoder`]
87    ///
88    /// `num_values_in_batch` is the number of non-null values in the whole write. The
89    /// column writer may split one write into several calls of this method (for
90    /// example by `write_batch_size` or the page size limit), so it can be larger than
91    /// `indices.len()`. It is the length of the write's full index list, which has one
92    /// entry per non-null value. The byte array encoder uses it to decide whether a
93    /// dictionary cache pays off.
94    fn write_gather(
95        &mut self,
96        values: &Self::Values,
97        indices: &[usize],
98        num_values_in_batch: usize,
99    ) -> Result<()>;
100
101    /// Returns the largest `k` such that the first `k` values in
102    /// `values[offset..offset + len]` encode to at most `byte_budget`
103    /// bytes — i.e. how many values fit in a single page byte budget.
104    ///
105    /// Returns `len` if every value fits. Returns at least 1 if a single
106    /// value alone exceeds the budget, matching parquet's "at least one
107    /// value per data page" rule.
108    ///
109    /// `None` means "no cheap estimate available"; the caller stays on
110    /// the batched fast path and lets the post-write
111    /// `should_add_data_page` check handle bounding.
112    ///
113    /// Implementations should short-circuit aggressively: the typical
114    /// case is "everything fits, return `len`", and the next-most-common
115    /// case is "one wide value, return 1." The variable-width walk only
116    /// needs to be precise when the chunk is genuinely near the budget.
117    fn count_values_within_byte_budget(
118        _values: &Self::Values,
119        _offset: usize,
120        _len: usize,
121        _byte_budget: usize,
122    ) -> Option<usize> {
123        None
124    }
125
126    /// As [`Self::count_values_within_byte_budget`] but using gather
127    /// `indices` rather than a contiguous range. Returns the number of
128    /// `indices` that fit, not the maximum index value.
129    fn count_values_within_byte_budget_gather(
130        _values: &Self::Values,
131        _indices: &[usize],
132        _byte_budget: usize,
133    ) -> Option<usize> {
134        None
135    }
136
137    /// Returns the number of buffered values
138    fn num_values(&self) -> usize;
139
140    /// Returns true if this encoder has a dictionary page
141    fn has_dictionary(&self) -> bool;
142
143    /// Returns true if the encoder compresses each value against the value
144    /// immediately before it, within the current page.
145    ///
146    /// For such encodings a page boundary is not free: flushing discards the
147    /// previous value, so the first value of the next page is stored in full.
148    /// [`GenericColumnWriter::should_add_data_page`] uses this to exempt a
149    /// page's mandatory first value from the data page byte limit.
150    ///
151    /// Per encoding:
152    /// * `DELTA_BYTE_ARRAY`: true. Each value is stored as the length of the
153    ///   prefix it shares with its predecessor plus the remaining suffix.
154    /// * Everything else: false, the default. `PLAIN` and
155    ///   `DELTA_LENGTH_BYTE_ARRAY` store a value at the same cost wherever it
156    ///   lands, and a dictionary outlives the pages that index into it, so no
157    ///   page boundary makes a value more expensive.
158    ///
159    /// [`GenericColumnWriter::should_add_data_page`]: crate::column::writer::GenericColumnWriter::should_add_data_page
160    fn compresses_against_previous_value(&self) -> bool {
161        false
162    }
163
164    /// Returns the estimated total memory usage of the encoder
165    ///
166    fn estimated_memory_size(&self) -> usize;
167
168    /// Returns an estimate of the encoded size of dictionary page size in bytes, or `None` if no dictionary
169    fn estimated_dict_page_size(&self) -> Option<usize>;
170
171    /// Returns an estimate of the encoded data page size in bytes
172    ///
173    /// This should include:
174    /// <already_written_encoded_byte_size> + <estimated_encoded_size_of_unflushed_bytes>
175    fn estimated_data_page_size(&self) -> usize;
176
177    /// Flush the dictionary page for this column chunk if any. Any subsequent calls to
178    /// [`Self::write`] will not be dictionary encoded
179    ///
180    /// Note: [`Self::flush_data_page`] must be called first, as this will error if there
181    /// are any pending page values
182    fn flush_dict_page(&mut self) -> Result<Option<DictionaryPage>>;
183
184    /// Flush the next data page for this column chunk
185    fn flush_data_page(&mut self) -> Result<DataPageValues<Self::T>>;
186
187    /// Flushes bloom filter if enabled and returns it, otherwise returns `None`. Subsequent writes
188    /// will *not* be tracked by the bloom filter as it is empty since. This should be called once
189    /// near the end of encoding.
190    fn flush_bloom_filter(&mut self) -> Option<Sbbf>;
191
192    /// Computes [`GeospatialStatistics`], if any, and resets internal state such that any internal
193    /// accumulator is prepared to accumulate statistics for the next column chunk.
194    fn flush_geospatial_statistics(&mut self) -> Option<Box<GeospatialStatistics>>;
195}
196
197pub struct ColumnValueEncoderImpl<T: DataType> {
198    encoder: Box<dyn Encoder<T>>,
199    dict_encoder: Option<DictEncoder<T>>,
200    descr: ColumnDescPtr,
201    num_values: usize,
202    statistics_enabled: EnabledStatistics,
203    min_value: Option<T::T>,
204    max_value: Option<T::T>,
205    nan_count: Option<u64>,
206    bloom_filter: Option<Sbbf>,
207    bloom_filter_target_fpp: f64,
208    variable_length_bytes: Option<i64>,
209    geo_stats_accumulator: Option<Box<dyn GeoStatsAccumulator>>,
210}
211
212impl<T: DataType> ColumnValueEncoderImpl<T> {
213    fn is_floating_point_column(&self) -> bool {
214        matches!(self.descr.physical_type(), Type::FLOAT | Type::DOUBLE)
215            || self.descr.logical_type_ref() == Some(&LogicalType::Float16)
216    }
217
218    fn write_slice(&mut self, slice: &[T::T]) -> Result<()> {
219        if self.statistics_enabled != EnabledStatistics::None
220            // INTERVAL, Geometry, and Geography have undefined sort order, so don't write min/max stats for them
221            && self.descr.converted_type() != ConvertedType::INTERVAL
222        {
223            if let Some(accumulator) = self.geo_stats_accumulator.as_deref_mut() {
224                update_geo_stats_accumulator(accumulator, slice.iter());
225            } else if let Some((min, max, nan_count)) =
226                T::T::min_max(self.descr.get_basic_info(), slice)
227            {
228                update_min(&self.descr, &min, &mut self.min_value);
229                update_max(&self.descr, &max, &mut self.max_value);
230                if self.is_floating_point_column() {
231                    *self.nan_count.get_or_insert(0) += nan_count;
232                }
233            }
234
235            if let Some(var_bytes) = T::T::variable_length_bytes(slice) {
236                *self.variable_length_bytes.get_or_insert(0) += var_bytes;
237            }
238        }
239
240        // While a dictionary is in use the filter is populated from its distinct values
241        // in `flush_dict_page`, so each value is hashed once rather than once per row.
242        match &mut self.dict_encoder {
243            Some(encoder) => encoder.put(slice),
244            _ => {
245                if let Some(bloom_filter) = &mut self.bloom_filter {
246                    for value in slice {
247                        bloom_filter.insert(value);
248                    }
249                }
250                self.encoder.put(slice)
251            }
252        }
253    }
254}
255
256impl<T: DataType> ColumnValueEncoder for ColumnValueEncoderImpl<T> {
257    type T = T::T;
258
259    type Values = [T::T];
260
261    fn flush_bloom_filter(&mut self) -> Option<Sbbf> {
262        let mut sbbf = self.bloom_filter.take()?;
263        sbbf.fold_to_target_fpp(self.bloom_filter_target_fpp);
264        Some(sbbf)
265    }
266
267    #[expect(
268        private_interfaces,
269        reason = "this trait is not nameable outside the crate"
270    )]
271    fn try_new(
272        descr: &ColumnDescPtr,
273        props: &WriterProperties,
274        column_props: &ResolvedColumnProperties,
275    ) -> Result<Self> {
276        let dict_supported =
277            column_props.dictionary_enabled && has_dictionary_support(T::get_physical_type());
278        let dict_encoder = dict_supported.then(|| DictEncoder::new(descr.clone()));
279
280        // Set either main encoder or fallback encoder.
281        let encoder = get_encoder_with_properties(
282            column_props
283                .encoding
284                .unwrap_or_else(|| fallback_encoding(T::get_physical_type(), props)),
285            descr,
286            column_props,
287        )?;
288
289        let statistics_enabled = column_props.statistics_enabled;
290
291        let (bloom_filter, bloom_filter_target_fpp) = create_bloom_filter(column_props)?;
292
293        let geo_stats_accumulator = try_new_geo_stats_accumulator(descr);
294
295        Ok(Self {
296            encoder,
297            dict_encoder,
298            descr: descr.clone(),
299            num_values: 0,
300            statistics_enabled,
301            bloom_filter,
302            bloom_filter_target_fpp,
303            min_value: None,
304            max_value: None,
305            nan_count: None,
306            variable_length_bytes: None,
307            geo_stats_accumulator,
308        })
309    }
310
311    fn write(&mut self, values: &[T::T], offset: usize, len: usize) -> Result<()> {
312        self.num_values += len;
313
314        let slice = values.get(offset..offset + len).ok_or_else(|| {
315            general_err!(
316                "Expected to write {} values, but have only {}",
317                len,
318                values.len() - offset
319            )
320        })?;
321
322        self.write_slice(slice)
323    }
324
325    fn write_gather(
326        &mut self,
327        values: &Self::Values,
328        indices: &[usize],
329        _num_values_in_batch: usize,
330    ) -> Result<()> {
331        self.num_values += indices.len();
332        let slice: Vec<_> = indices.iter().map(|idx| values[*idx].clone()).collect();
333        self.write_slice(&slice)
334    }
335
336    fn count_values_within_byte_budget(
337        values: &[T::T],
338        offset: usize,
339        len: usize,
340        byte_budget: usize,
341    ) -> Option<usize> {
342        // Clamp so that a caller-supplied `len` that overruns the input
343        // (e.g. a level/value mismatch the encoder will reject later)
344        // returns an estimate instead of panicking here.
345        let end = (offset + len).min(values.len());
346        let start = offset.min(end);
347        count_within_budget::<T>(
348            end - start,
349            byte_budget,
350            values[start..end].iter().map(Some),
351        )
352    }
353
354    fn count_values_within_byte_budget_gather(
355        values: &[T::T],
356        indices: &[usize],
357        byte_budget: usize,
358    ) -> Option<usize> {
359        // `values.get` yields `None` for an out-of-range index (defensive
360        // against a level/value mismatch the encoder rejects later); such a
361        // position is counted but contributes no bytes.
362        count_within_budget::<T>(
363            indices.len(),
364            byte_budget,
365            indices.iter().map(|&i| values.get(i)),
366        )
367    }
368
369    fn num_values(&self) -> usize {
370        self.num_values
371    }
372
373    fn has_dictionary(&self) -> bool {
374        self.dict_encoder.is_some()
375    }
376
377    fn compresses_against_previous_value(&self) -> bool {
378        // While dictionary encoding is active `self.encoder` is unused: the
379        // data page holds RLE indices, which carry no cross-value state.
380        self.dict_encoder.is_none() && self.encoder.encoding() == Encoding::DELTA_BYTE_ARRAY
381    }
382
383    fn estimated_memory_size(&self) -> usize {
384        let encoder_size = self.encoder.estimated_memory_size();
385
386        let dict_encoder_size = self
387            .dict_encoder
388            .as_ref()
389            .map(|encoder| encoder.estimated_memory_size())
390            .unwrap_or_default();
391
392        let bloom_filter_size = self
393            .bloom_filter
394            .as_ref()
395            .map(|bf| bf.estimated_memory_size())
396            .unwrap_or_default();
397
398        encoder_size + dict_encoder_size + bloom_filter_size
399    }
400
401    fn estimated_dict_page_size(&self) -> Option<usize> {
402        Some(self.dict_encoder.as_ref()?.dict_encoded_size())
403    }
404
405    fn estimated_data_page_size(&self) -> usize {
406        match &self.dict_encoder {
407            Some(encoder) => encoder.estimated_data_encoded_size(),
408            _ => self.encoder.estimated_data_encoded_size(),
409        }
410    }
411
412    fn flush_dict_page(&mut self) -> Result<Option<DictionaryPage>> {
413        match self.dict_encoder.take() {
414            Some(encoder) => {
415                if self.num_values != 0 {
416                    return Err(general_err!(
417                        "Must flush data pages before flushing dictionary"
418                    ));
419                }
420
421                if let Some(bloom_filter) = &mut self.bloom_filter {
422                    for value in encoder.uniques() {
423                        bloom_filter.insert(value);
424                    }
425                }
426
427                let buf = encoder.write_dict()?;
428
429                Ok(Some(DictionaryPage {
430                    buf,
431                    num_values: encoder.num_entries(),
432                    is_sorted: encoder.is_sorted(),
433                }))
434            }
435            _ => Ok(None),
436        }
437    }
438
439    fn flush_data_page(&mut self) -> Result<DataPageValues<T::T>> {
440        let (buf, encoding) = match &mut self.dict_encoder {
441            Some(encoder) => (encoder.write_indices()?, Encoding::RLE_DICTIONARY),
442            _ => (self.encoder.flush_buffer()?, self.encoder.encoding()),
443        };
444
445        Ok(DataPageValues {
446            buf,
447            encoding,
448            num_values: std::mem::take(&mut self.num_values),
449            min_value: self.min_value.take(),
450            max_value: self.max_value.take(),
451            nan_count: self.nan_count.take(),
452            variable_length_bytes: self.variable_length_bytes.take(),
453        })
454    }
455
456    fn flush_geospatial_statistics(&mut self) -> Option<Box<GeospatialStatistics>> {
457        self.geo_stats_accumulator.as_mut().map(|a| a.finish())?
458    }
459}
460
461/// Creates a bloom filter sized for the column's configured NDV, returning the filter
462/// and the target FPP for folding.
463pub(crate) fn create_bloom_filter(
464    column_props: &ResolvedColumnProperties,
465) -> Result<(Option<Sbbf>, f64)> {
466    match column_props.bloom_filter_properties.as_ref() {
467        Some(bf_props) => Ok((
468            Some(Sbbf::new_with_ndv_fpp(bf_props.ndv(), bf_props.fpp())?),
469            bf_props.fpp(),
470        )),
471        None => Ok((None, 0.0)),
472    }
473}
474
475fn update_geo_stats_accumulator<'a, T, I>(bounder: &mut dyn GeoStatsAccumulator, iter: I)
476where
477    T: ParquetValueType + 'a,
478    I: Iterator<Item = &'a T>,
479{
480    if bounder.is_valid() {
481        for val in iter {
482            bounder.update_wkb(val.as_bytes());
483        }
484    }
485}
486
487/// Plain-encoded byte cost of a single value of type `T::T`.
488///
489/// Derived from [`ParquetValueType::dict_encoding_size`] (which returns
490/// `(per-value overhead, value-bytes)`) so we don't add a parallel
491/// per-value-size hook to the trait. Mirrors the dispatch in
492/// `KeyStorage::push` (`encodings/encoding/dict_encoder.rs`).
493///
494/// Placed at the end of the module deliberately. Inserting it above the
495/// `ColumnValueEncoder` trait shifts the trait and `ColumnValueEncoderImpl`
496/// within the compiled module enough to perturb downstream code placement,
497/// which measurably regresses unrelated arrow-writer string benchmarks
498/// (~5-9% on `string` / `string_and_binary_view`). Defining it last keeps
499/// the hot encoder code at the offsets it has on `main`.
500#[inline]
501fn plain_encoded_byte_size<T: DataType>(value: &T::T) -> usize {
502    let (overhead, bytes) = value.dict_encoding_size();
503    match <T::T as ParquetValueType>::PHYSICAL_TYPE {
504        // Plain BYTE_ARRAY = 4-byte length prefix + payload.
505        Type::BYTE_ARRAY => overhead + bytes,
506        // Plain FLBA = raw bytes only; `dict_encoding_size`'s length prefix
507        // is irrelevant here, so the encoder passes `type_length` directly.
508        Type::FIXED_LEN_BYTE_ARRAY => bytes,
509        // Numeric/bool are short-circuited by the caller via
510        // `mem::size_of`, so this is unreachable in practice; fall back to
511        // `overhead` defensively.
512        _ => overhead,
513    }
514}
515
516/// How many leading values fit in `byte_budget` bytes, shared by the two
517/// `ColumnValueEncoder::count_values_within_byte_budget*` methods (one walks a
518/// contiguous slice, the other gathers by index).
519///
520/// `n` is the answer when everything fits; `vals` yields each candidate value,
521/// or `None` for a position that should still be counted but contributes no
522/// bytes (an out-of-range gather index). The boundary value that crosses the
523/// budget is included in the count so the caller's page-flush check trips on
524/// this mini-batch rather than leaving a sliver for the next page; this also
525/// catches a lone outlier wherever it lands among small values.
526///
527/// Defined at the end of the module alongside `plain_encoded_byte_size` for
528/// the same reason — see that function's note on code placement and the
529/// `string` / `string_and_binary_view` benchmarks.
530#[inline]
531fn count_within_budget<'a, T: DataType>(
532    n: usize,
533    byte_budget: usize,
534    vals: impl Iterator<Item = Option<&'a T::T>>,
535) -> Option<usize>
536where
537    T::T: 'a,
538{
539    // Fixed-size physical types have a constant per-value byte cost, so the
540    // answer is one division — no walk needed.
541    let phys = <T::T as ParquetValueType>::PHYSICAL_TYPE;
542    if phys != Type::BYTE_ARRAY && phys != Type::FIXED_LEN_BYTE_ARRAY {
543        let per = std::mem::size_of::<T::T>().max(1);
544        return Some((byte_budget / per).max(1).min(n));
545    }
546    // Variable-width: accumulate, exit at the first value past the budget.
547    let mut cum: usize = 0;
548    for (i, v) in vals.enumerate() {
549        if let Some(v) = v {
550            cum = cum.saturating_add(plain_encoded_byte_size::<T>(v));
551        }
552        if cum > byte_budget {
553            return Some(i + 1);
554        }
555    }
556    Some(n)
557}