Skip to main content

parquet/encodings/encoding/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: See the NOTICE file distributed with this work for additional information regarding copyright ownership
3// SPDX-FileContributor: Licensed to the Apache Software Foundation (ASF) under one or more contributor license agreements
4
5//! Contains all supported encoders for Parquet.
6
7use std::{cmp, marker::PhantomData};
8
9use crate::basic::*;
10use crate::data_type::private::ParquetValueType;
11use crate::data_type::*;
12use crate::encodings::rle::RleEncoder;
13use crate::errors::{ParquetError, Result};
14use crate::file::properties::ResolvedColumnProperties;
15use crate::schema::types::ColumnDescPtr;
16use crate::util::bit_util::{BitWriter, num_required_bits};
17use crate::util::prefix::common_prefix_length;
18
19pub use alp_encoder::AlpEncoder;
20pub use byte_stream_split_encoder::{ByteStreamSplitEncoder, VariableWidthByteStreamSplitEncoder};
21use bytes::Bytes;
22pub use dict_encoder::DictEncoder;
23
24mod alp_encoder;
25mod byte_stream_split_encoder;
26mod dict_encoder;
27
28// ----------------------------------------------------------------------
29// Encoders
30
31/// An Parquet encoder for the data type `T`.
32///
33/// Currently this allocates internal buffers for the encoded values. After done putting
34/// values, caller should call `flush_buffer()` to get an immutable buffer pointer.
35pub trait Encoder<T: DataType>: Send {
36    /// Encodes data from `values`.
37    fn put(&mut self, values: &[T::T]) -> Result<()>;
38
39    /// Encodes data from `values`, which contains spaces for null values, that is
40    /// identified by `valid_bits`.
41    ///
42    /// Returns the number of non-null values encoded.
43    #[cfg(test)]
44    fn put_spaced(&mut self, values: &[T::T], valid_bits: &[u8]) -> Result<usize> {
45        let num_values = values.len();
46        let mut buffer = Vec::with_capacity(num_values);
47        // TODO: this is pretty inefficient. Revisit in future.
48        for (i, item) in values.iter().enumerate().take(num_values) {
49            if crate::util::bit_util::get_bit(valid_bits, i) {
50                buffer.push(item.clone());
51            }
52        }
53        self.put(&buffer[..])?;
54        Ok(buffer.len())
55    }
56
57    /// Returns the encoding type of this encoder.
58    fn encoding(&self) -> Encoding;
59
60    /// Returns an estimate of the encoded data, in bytes.
61    /// Method call must be O(1).
62    fn estimated_data_encoded_size(&self) -> usize;
63
64    /// Returns an estimate of the memory use of this encoder, in bytes
65    fn estimated_memory_size(&self) -> usize;
66
67    /// Flushes the underlying byte buffer that's being processed by this encoder, and
68    /// return the immutable copy of it. This will also reset the internal state.
69    fn flush_buffer(&mut self) -> Result<Bytes>;
70}
71
72/// Gets a encoder for the particular data type `T` and encoding `encoding`. Memory usage
73/// for the encoder instance is tracked by `mem_tracker`.
74#[cfg_attr(all(not(feature = "experimental"), not(test)), expect(dead_code))]
75pub fn get_encoder<T: DataType>(
76    encoding: Encoding,
77    descr: &ColumnDescPtr,
78) -> Result<Box<dyn Encoder<T>>> {
79    <T::T as private::GetEncoder>::get_encoder(descr, encoding, None)
80}
81
82pub(crate) fn get_encoder_with_properties<T: DataType>(
83    encoding: Encoding,
84    descr: &ColumnDescPtr,
85    column_props: &ResolvedColumnProperties,
86) -> Result<Box<dyn Encoder<T>>> {
87    <T::T as private::GetEncoder>::get_encoder(descr, encoding, Some(column_props))
88}
89
90pub(crate) mod private {
91    use super::*;
92
93    /// A trait that allows getting an [`Encoder`] implementation for a [`DataType`]
94    /// with the corresponding [`ParquetValueType`]. This is necessary to support
95    /// [`Encoder`] implementations that may not be applicable for all [`DataType`]
96    /// and by extension all [`ParquetValueType`], such as ALP, which encodes only
97    /// floating-point columns.
98    ///
99    /// [`ParquetValueType`]: crate::data_type::private::ParquetValueType
100    pub trait GetEncoder {
101        #[expect(
102            private_interfaces,
103            reason = "this trait is not nameable outside the crate"
104        )]
105        fn get_encoder<T: DataType<T = Self>>(
106            descr: &ColumnDescPtr,
107            encoding: Encoding,
108            options: Option<&ResolvedColumnProperties>,
109        ) -> Result<Box<dyn Encoder<T>>> {
110            get_encoder_default(descr, encoding, options)
111        }
112    }
113
114    fn get_encoder_default<T: DataType>(
115        descr: &ColumnDescPtr,
116        encoding: Encoding,
117        options: Option<&ResolvedColumnProperties>,
118    ) -> Result<Box<dyn Encoder<T>>> {
119        let encoder: Box<dyn Encoder<T>> = match encoding {
120            Encoding::PLAIN => Box::new(PlainEncoder::new()),
121            Encoding::RLE_DICTIONARY | Encoding::PLAIN_DICTIONARY => {
122                return Err(general_err!(
123                    "Cannot initialize this encoding through this function"
124                ));
125            }
126            Encoding::RLE => match T::get_physical_type() {
127                Type::BOOLEAN => Box::new(RleValueEncoder::new()),
128                physical_type => return Err(unsupported_column_encoding(encoding, physical_type)),
129            },
130            Encoding::DELTA_BINARY_PACKED => match T::get_physical_type() {
131                Type::INT32 | Type::INT64 => Box::new(
132                    match options.and_then(|props| props.delta_binary_packed_encoder_options) {
133                        Some(options) => DeltaBitPackEncoder::new_with_options(options),
134                        None => DeltaBitPackEncoder::new(),
135                    },
136                ),
137                physical_type => return Err(unsupported_column_encoding(encoding, physical_type)),
138            },
139            Encoding::DELTA_LENGTH_BYTE_ARRAY => match T::get_physical_type() {
140                Type::BYTE_ARRAY => Box::new(
141                    match options.and_then(|props| props.delta_binary_packed_encoder_options) {
142                        Some(options) => DeltaLengthByteArrayEncoder::new_with_options(options),
143                        None => DeltaLengthByteArrayEncoder::new(),
144                    },
145                ),
146                physical_type => return Err(unsupported_column_encoding(encoding, physical_type)),
147            },
148            Encoding::DELTA_BYTE_ARRAY => match T::get_physical_type() {
149                Type::BYTE_ARRAY | Type::FIXED_LEN_BYTE_ARRAY => Box::new(
150                    match options.and_then(|props| props.delta_binary_packed_encoder_options) {
151                        Some(options) => DeltaByteArrayEncoder::new_with_options(options),
152                        None => DeltaByteArrayEncoder::new(),
153                    },
154                ),
155                physical_type => return Err(unsupported_column_encoding(encoding, physical_type)),
156            },
157            Encoding::BYTE_STREAM_SPLIT => match T::get_physical_type() {
158                Type::FIXED_LEN_BYTE_ARRAY => Box::new(VariableWidthByteStreamSplitEncoder::new(
159                    descr.type_length(),
160                )),
161                Type::INT32 | Type::INT64 | Type::FLOAT | Type::DOUBLE => {
162                    Box::new(ByteStreamSplitEncoder::new())
163                }
164                physical_type => return Err(unsupported_column_encoding(encoding, physical_type)),
165            },
166            Encoding::ALP => {
167                return Err(general_err!(
168                    "Encoding {} only supports FLOAT and DOUBLE, got {}",
169                    encoding,
170                    T::get_physical_type()
171                ));
172            }
173            #[expect(deprecated, reason = "BIT_PACKED is the encoding we reject here")]
174            e @ Encoding::BIT_PACKED => return Err(nyi_err!("Encoding {} is not supported", e)),
175        };
176        Ok(encoder)
177    }
178
179    impl GetEncoder for bool {}
180    impl GetEncoder for i32 {}
181    impl GetEncoder for i64 {}
182    impl GetEncoder for Int96 {}
183    impl GetEncoder for ByteArray {}
184    impl GetEncoder for FixedLenByteArray {}
185
186    impl GetEncoder for f32 {
187        #[expect(
188            private_interfaces,
189            reason = "this trait is not nameable outside the crate"
190        )]
191        fn get_encoder<T: DataType<T = Self>>(
192            descr: &ColumnDescPtr,
193            encoding: Encoding,
194            options: Option<&ResolvedColumnProperties>,
195        ) -> Result<Box<dyn Encoder<T>>> {
196            match encoding {
197                Encoding::ALP => Ok(Box::new(AlpEncoder::new())),
198                _ => get_encoder_default(descr, encoding, options),
199            }
200        }
201    }
202
203    impl GetEncoder for f64 {
204        #[expect(
205            private_interfaces,
206            reason = "this trait is not nameable outside the crate"
207        )]
208        fn get_encoder<T: DataType<T = Self>>(
209            descr: &ColumnDescPtr,
210            encoding: Encoding,
211            options: Option<&ResolvedColumnProperties>,
212        ) -> Result<Box<dyn Encoder<T>>> {
213            match encoding {
214                Encoding::ALP => Ok(Box::new(AlpEncoder::new())),
215                _ => get_encoder_default(descr, encoding, options),
216            }
217        }
218    }
219}
220
221fn unsupported_column_encoding(encoding: Encoding, physical_type: Type) -> ParquetError {
222    nyi_err!(
223        "Encoding {} is not supported for physical type {:?}",
224        encoding,
225        physical_type
226    )
227}
228
229// ----------------------------------------------------------------------
230// Plain encoding
231
232/// Plain encoding that supports all types.
233/// Values are encoded back to back.
234/// The plain encoding is used whenever a more efficient encoding can not be used.
235/// It stores the data in the following format:
236/// - BOOLEAN - 1 bit per value, 0 is false; 1 is true.
237/// - INT32 - 4 bytes per value, stored as little-endian.
238/// - INT64 - 8 bytes per value, stored as little-endian.
239/// - FLOAT - 4 bytes per value, stored as IEEE little-endian.
240/// - DOUBLE - 8 bytes per value, stored as IEEE little-endian.
241/// - BYTE_ARRAY - 4 byte length stored as little endian, followed by bytes.
242/// - FIXED_LEN_BYTE_ARRAY - just the bytes are stored.
243pub struct PlainEncoder<T: DataType> {
244    buffer: Vec<u8>,
245    bit_writer: BitWriter,
246    _phantom: PhantomData<T>,
247}
248
249impl<T: DataType> Default for PlainEncoder<T> {
250    fn default() -> Self {
251        Self::new()
252    }
253}
254
255impl<T: DataType> PlainEncoder<T> {
256    /// Creates new plain encoder.
257    pub fn new() -> Self {
258        Self {
259            buffer: vec![],
260            bit_writer: BitWriter::new(256),
261            _phantom: PhantomData,
262        }
263    }
264}
265
266impl<T: DataType> Encoder<T> for PlainEncoder<T> {
267    // Performance Note:
268    // As far as can be seen these functions are rarely called and as such we can hint to the
269    // compiler that they dont need to be folded into hot locations in the final output.
270    #[cold]
271    fn encoding(&self) -> Encoding {
272        Encoding::PLAIN
273    }
274
275    fn estimated_data_encoded_size(&self) -> usize {
276        self.buffer.len() + self.bit_writer.bytes_written()
277    }
278
279    #[inline]
280    fn flush_buffer(&mut self) -> Result<Bytes> {
281        self.buffer
282            .extend_from_slice(self.bit_writer.flush_buffer());
283        self.bit_writer.clear();
284        Ok(std::mem::take(&mut self.buffer).into())
285    }
286
287    #[inline]
288    fn put(&mut self, values: &[T::T]) -> Result<()> {
289        T::T::encode(values, &mut self.buffer, &mut self.bit_writer)?;
290        Ok(())
291    }
292
293    /// Return the estimated memory size of this encoder.
294    fn estimated_memory_size(&self) -> usize {
295        self.buffer.capacity() * std::mem::size_of::<u8>() + self.bit_writer.estimated_memory_size()
296    }
297}
298
299// ----------------------------------------------------------------------
300// RLE encoding
301
302const DEFAULT_RLE_BUFFER_LEN: usize = 1024;
303
304/// RLE/Bit-Packing hybrid encoding for values.
305/// Currently is used only for data pages v2 and supports boolean types.
306pub struct RleValueEncoder<T: DataType> {
307    // Buffer with raw values that we collect,
308    // when flushing buffer they are encoded using RLE encoder
309    encoder: Option<RleEncoder>,
310    _phantom: PhantomData<T>,
311}
312
313impl<T: DataType> Default for RleValueEncoder<T> {
314    fn default() -> Self {
315        Self::new()
316    }
317}
318
319impl<T: DataType> RleValueEncoder<T> {
320    /// Creates new rle value encoder.
321    pub fn new() -> Self {
322        Self {
323            encoder: None,
324            _phantom: PhantomData,
325        }
326    }
327}
328
329impl<T: DataType> Encoder<T> for RleValueEncoder<T> {
330    #[inline]
331    fn put(&mut self, values: &[T::T]) -> Result<()> {
332        ensure_phys_ty!(Type::BOOLEAN, "RleValueEncoder only supports BoolType");
333
334        let rle_encoder = self.encoder.get_or_insert_with(|| {
335            let mut buffer = Vec::with_capacity(DEFAULT_RLE_BUFFER_LEN);
336            // Reserve space for length
337            buffer.extend_from_slice(&[0; 4]);
338            RleEncoder::new_from_buf(1, buffer)
339        });
340
341        let mut buf = [0_u64; 64];
342        for chunk in values.chunks(buf.len()) {
343            let buf = &mut buf[..chunk.len()];
344            for (b, value) in buf.iter_mut().zip(chunk) {
345                *b = value.as_u64()?;
346            }
347            rle_encoder.put_batch(buf);
348        }
349        Ok(())
350    }
351
352    // Performance Note:
353    // As far as can be seen these functions are rarely called and as such we can hint to the
354    // compiler that they dont need to be folded into hot locations in the final output.
355    #[cold]
356    fn encoding(&self) -> Encoding {
357        Encoding::RLE
358    }
359
360    #[inline]
361    fn estimated_data_encoded_size(&self) -> usize {
362        match self.encoder {
363            Some(ref enc) => enc.len(),
364            None => 0,
365        }
366    }
367
368    #[inline]
369    fn flush_buffer(&mut self) -> Result<Bytes> {
370        ensure_phys_ty!(Type::BOOLEAN, "RleValueEncoder only supports BoolType");
371        let rle_encoder = self
372            .encoder
373            .take()
374            .expect("RLE value encoder is not initialized");
375
376        // Flush all encoder buffers and raw values
377        let mut buf = rle_encoder.consume();
378        assert!(buf.len() >= 4, "should have had padding inserted");
379
380        // Note that buf does not have any offset, all data is encoded bytes
381        let len = (buf.len() - 4) as i32;
382        buf[..4].copy_from_slice(&len.to_le_bytes());
383
384        Ok(buf.into())
385    }
386
387    /// return the estimated memory size of this encoder.
388    fn estimated_memory_size(&self) -> usize {
389        self.encoder
390            .as_ref()
391            .map_or(0, |enc| enc.estimated_memory_size())
392    }
393}
394
395// ----------------------------------------------------------------------
396// DELTA_BINARY_PACKED encoding
397
398const MAX_PAGE_HEADER_WRITER_SIZE: usize = 32;
399const DEFAULT_NUM_MINI_BLOCKS: usize = 4;
400
401/// Controls the block layout emitted by [`DeltaBitPackEncoder`] and the integer sub-encoders used
402/// by [`DeltaLengthByteArrayEncoder`] and [`DeltaByteArrayEncoder`].
403///
404/// In the [Parquet DELTA_BINARY_PACKED encoding], each block records a minimum delta and each mini
405/// block records its own bit width. The defaults use 128 values per block and 4 mini blocks for
406/// `INT32`, and 256 values per block and 4 mini blocks for `INT64`.
407///
408/// Smaller blocks or mini blocks can reduce encoded size for bursty data, where the required bit
409/// width changes over short ranges, and for short pages that would otherwise need more padding.
410/// They also add more minimum-delta and bit-width metadata. Larger blocks or mini blocks can reduce
411/// that metadata and block-processing overhead for long inputs with stable delta distributions,
412/// improving compression or throughput, but an outlier then affects more values and the encoder
413/// uses a larger scratch buffer. Benchmark representative data before changing the defaults.
414///
415/// The format requires block sizes to be multiples of 128 and mini block sizes to be multiples
416/// of 32.
417///
418/// [Parquet DELTA_BINARY_PACKED encoding]: https://github.com/apache/parquet-format/blob/master/Encodings.md#delta-encoding-delta_binary_packed--5
419#[derive(Debug, Clone, Copy, PartialEq, Eq)]
420pub struct DeltaBinaryPackedEncoderOptions {
421    block_size: usize,
422    mini_blocks_per_block: usize,
423}
424
425impl DeltaBinaryPackedEncoderOptions {
426    /// Creates validated delta binary packed encoder options.
427    pub fn try_new(block_size: usize, mini_blocks_per_block: usize) -> Result<Self> {
428        if block_size == 0 || !block_size.is_multiple_of(128) {
429            return Err(general_err!(
430                "delta binary packed block size must be a positive multiple of 128, got {block_size}"
431            ));
432        }
433        if mini_blocks_per_block == 0 || !block_size.is_multiple_of(mini_blocks_per_block) {
434            return Err(general_err!(
435                "delta binary packed mini block count must be a positive divisor of the block size, got {mini_blocks_per_block} for block size {block_size}"
436            ));
437        }
438
439        let mini_block_size = block_size / mini_blocks_per_block;
440        if !mini_block_size.is_multiple_of(32) {
441            return Err(general_err!(
442                "delta binary packed mini block size must be a multiple of 32, got {mini_block_size}"
443            ));
444        }
445
446        Ok(Self {
447            block_size,
448            mini_blocks_per_block,
449        })
450    }
451
452    /// Returns the number of values in each block.
453    pub fn block_size(&self) -> usize {
454        self.block_size
455    }
456
457    /// Returns the number of mini blocks in each block.
458    pub fn mini_blocks_per_block(&self) -> usize {
459        self.mini_blocks_per_block
460    }
461}
462
463/// Delta bit packed encoder.
464/// Consists of a header followed by blocks of delta encoded values binary packed.
465///
466/// Delta-binary-packing:
467/// ```shell
468///   [page-header] [block 1], [block 2], ... [block N]
469/// ```
470///
471/// Each page header consists of:
472/// ```shell
473///   [block size] [number of miniblocks in a block] [total value count] [first value]
474/// ```
475///
476/// Each block consists of:
477/// ```shell
478///   [min delta] [list of bitwidths of miniblocks] [miniblocks]
479/// ```
480///
481/// Current implementation writes values in `put` method, multiple calls to `put` to
482/// existing block or start new block if block size is exceeded. Calling `flush_buffer`
483/// writes out all data and resets internal state, including page header.
484///
485/// Supports only INT32 and INT64.
486pub struct DeltaBitPackEncoder<T: DataType> {
487    page_header_writer: BitWriter,
488    bit_writer: BitWriter,
489    total_values: usize,
490    first_value: i64,
491    current_value: i64,
492    block_size: usize,
493    mini_block_size: usize,
494    num_mini_blocks: usize,
495    values_in_block: usize,
496    deltas: Vec<i64>,
497    _phantom: PhantomData<T>,
498}
499
500impl<T: DataType> Default for DeltaBitPackEncoder<T> {
501    fn default() -> Self {
502        Self::new()
503    }
504}
505
506impl<T: DataType> DeltaBitPackEncoder<T> {
507    /// Creates new delta bit packed encoder.
508    pub fn new() -> Self {
509        Self::assert_supported_type();
510
511        // Size miniblocks so that they can be efficiently decoded
512        let mini_block_size = match T::T::PHYSICAL_TYPE {
513            Type::INT32 => 32,
514            Type::INT64 => 64,
515            _ => unreachable!(),
516        };
517
518        let num_mini_blocks = DEFAULT_NUM_MINI_BLOCKS;
519        let block_size = mini_block_size * num_mini_blocks;
520        assert_eq!(block_size % 128, 0);
521
522        Self::new_with_layout(block_size, num_mini_blocks)
523    }
524
525    fn new_with_layout(block_size: usize, num_mini_blocks: usize) -> Self {
526        DeltaBitPackEncoder {
527            page_header_writer: BitWriter::new(MAX_PAGE_HEADER_WRITER_SIZE),
528            // Don't pre-allocate: encoders are often created eagerly (e.g. as a
529            // byte array fallback encoder) and may never be used. The buffer
530            // grows on demand and retains its capacity across pages.
531            bit_writer: BitWriter::new(0),
532            total_values: 0,
533            first_value: 0,
534            current_value: 0, // current value to keep adding deltas
535            block_size,       // can write fewer values than block size for last block
536            mini_block_size: block_size / num_mini_blocks,
537            num_mini_blocks,
538            values_in_block: 0, // will be at most block_size
539            deltas: vec![0; block_size],
540            _phantom: PhantomData,
541        }
542    }
543
544    /// Creates a delta bit packed encoder with a custom block layout.
545    pub fn new_with_options(options: DeltaBinaryPackedEncoderOptions) -> Self {
546        Self::assert_supported_type();
547
548        let block_size = options.block_size();
549        let num_mini_blocks = options.mini_blocks_per_block();
550        Self::new_with_layout(block_size, num_mini_blocks)
551    }
552
553    /// Writes page header for blocks, this method is invoked when we are done encoding
554    /// values. It is also okay to encode when no values have been provided
555    fn write_page_header(&mut self) {
556        // We ignore the result of each 'put' operation, because
557        // MAX_PAGE_HEADER_WRITER_SIZE is chosen to fit all header values and
558        // guarantees that writes will not fail.
559
560        // Write the size of each block
561        self.page_header_writer.put_vlq_int(self.block_size as u64);
562        // Write the number of mini blocks
563        self.page_header_writer
564            .put_vlq_int(self.num_mini_blocks as u64);
565        // Write the number of all values (including non-encoded first value)
566        self.page_header_writer
567            .put_vlq_int(self.total_values as u64);
568        // Write first value
569        self.page_header_writer.put_zigzag_vlq_int(self.first_value);
570    }
571
572    // Write current delta buffer (<= 'block size' values) into bit writer
573    #[inline(never)]
574    fn flush_block_values(&mut self) -> Result<()> {
575        if self.values_in_block == 0 {
576            return Ok(());
577        }
578
579        let mut min_delta = i64::MAX;
580        assert!(self.values_in_block <= self.deltas.len());
581        for &delta in self.deltas.iter().take(self.values_in_block) {
582            min_delta = cmp::min(min_delta, delta);
583        }
584
585        // Write min delta
586        self.bit_writer.put_zigzag_vlq_int(min_delta);
587
588        // Slice to store bit width for each mini block
589        let offset = self.bit_writer.skip(self.num_mini_blocks);
590
591        for i in 0..self.num_mini_blocks {
592            // Find how many values we need to encode - either block size or whatever
593            // values left
594            let n = cmp::min(self.mini_block_size, self.values_in_block);
595            if n == 0 {
596                // Decoders should be agnostic to the padding value, we therefore use 0xFF
597                // when running tests. However, not all implementations may handle this correctly
598                // so pad with 0 when not running tests
599                let pad_value = cfg!(test).then(|| 0xFF).unwrap_or(0);
600                for j in i..self.num_mini_blocks {
601                    self.bit_writer.write_at(offset + j, pad_value);
602                }
603                break;
604            }
605
606            // Compute the max delta in current mini block
607            let mut max_delta = i64::MIN;
608            for j in 0..n {
609                max_delta = cmp::max(max_delta, self.deltas[i * self.mini_block_size + j]);
610            }
611
612            // Compute bit width to store (max_delta - min_delta)
613            let bit_width = num_required_bits(self.subtract_u64(max_delta, min_delta)) as usize;
614            self.bit_writer.write_at(offset + i, bit_width as u8);
615
616            // Encode values in current mini block using min_delta and bit_width. This
617            // mini block's deltas are not read again, so they can be rewritten in place
618            // with the values to pack
619            let start = i * self.mini_block_size;
620            for j in start..start + n {
621                self.deltas[j] = self.subtract_u64(self.deltas[j], min_delta) as i64;
622            }
623            self.bit_writer
624                .put_batch(&self.deltas[start..start + n], bit_width);
625
626            // Pad the last block (n < mini_block_size)
627            for _ in n..self.mini_block_size {
628                self.bit_writer.put_value(0, bit_width);
629            }
630
631            self.values_in_block -= n;
632        }
633
634        assert_eq!(
635            self.values_in_block, 0,
636            "Expected 0 values in block, found {}",
637            self.values_in_block
638        );
639        Ok(())
640    }
641}
642
643// Implementation is shared between Int32Type and Int64Type,
644// see `DeltaBitPackEncoderConversion` below for specifics.
645impl<T: DataType> Encoder<T> for DeltaBitPackEncoder<T> {
646    fn put(&mut self, values: &[T::T]) -> Result<()> {
647        if values.is_empty() {
648            return Ok(());
649        }
650
651        // Define values to encode, initialize state
652        let mut idx = if self.total_values == 0 {
653            self.first_value = self.as_i64(values, 0);
654            self.current_value = self.first_value;
655            1
656        } else {
657            0
658        };
659        // Add all values (including first value)
660        self.total_values += values.len();
661
662        // Write block
663        while idx < values.len() {
664            let value = self.as_i64(values, idx);
665            self.deltas[self.values_in_block] = self.subtract(value, self.current_value);
666            self.current_value = value;
667            idx += 1;
668            self.values_in_block += 1;
669            if self.values_in_block == self.block_size {
670                self.flush_block_values()?;
671            }
672        }
673        Ok(())
674    }
675
676    // Performance Note:
677    // As far as can be seen these functions are rarely called and as such we can hint to the
678    // compiler that they dont need to be folded into hot locations in the final output.
679    #[cold]
680    fn encoding(&self) -> Encoding {
681        Encoding::DELTA_BINARY_PACKED
682    }
683
684    fn estimated_data_encoded_size(&self) -> usize {
685        self.bit_writer.bytes_written()
686    }
687
688    fn flush_buffer(&mut self) -> Result<Bytes> {
689        // Write remaining values
690        self.flush_block_values()?;
691        // Write page header with total values
692        self.write_page_header();
693
694        let mut buffer = Vec::new();
695        buffer.extend_from_slice(self.page_header_writer.flush_buffer());
696        buffer.extend_from_slice(self.bit_writer.flush_buffer());
697
698        // Reset state
699        self.page_header_writer.clear();
700        self.bit_writer.clear();
701        self.total_values = 0;
702        self.first_value = 0;
703        self.current_value = 0;
704        self.values_in_block = 0;
705
706        Ok(buffer.into())
707    }
708
709    /// return the estimated memory size of this encoder.
710    fn estimated_memory_size(&self) -> usize {
711        self.page_header_writer.estimated_memory_size()
712            + self.bit_writer.estimated_memory_size()
713            + self.deltas.capacity() * std::mem::size_of::<i64>()
714            + std::mem::size_of::<Self>()
715    }
716}
717
718/// Helper trait to define specific conversions and subtractions when computing deltas
719trait DeltaBitPackEncoderConversion<T: DataType> {
720    // Method should panic if type is not supported, otherwise no-op
721    fn assert_supported_type();
722
723    fn as_i64(&self, values: &[T::T], index: usize) -> i64;
724
725    fn subtract(&self, left: i64, right: i64) -> i64;
726
727    fn subtract_u64(&self, left: i64, right: i64) -> u64;
728}
729
730const DELTA_BIT_PACK_TYPE_ERROR: &str =
731    "DeltaBitPackDecoder only supports Int32Type, UInt32Type, Int64Type, and UInt64Type";
732
733impl<T: DataType> DeltaBitPackEncoderConversion<T> for DeltaBitPackEncoder<T> {
734    #[inline]
735    fn assert_supported_type() {
736        ensure_phys_ty!(Type::INT32 | Type::INT64, "{}", DELTA_BIT_PACK_TYPE_ERROR);
737    }
738
739    #[inline]
740    fn as_i64(&self, values: &[T::T], index: usize) -> i64 {
741        values[index].as_i64().expect(DELTA_BIT_PACK_TYPE_ERROR)
742    }
743
744    #[inline]
745    fn subtract(&self, left: i64, right: i64) -> i64 {
746        // It is okay for values to overflow, wrapping_sub wrapping around at the boundary
747        match T::get_physical_type() {
748            Type::INT32 => (left as i32).wrapping_sub(right as i32) as i64,
749            Type::INT64 => left.wrapping_sub(right),
750            _ => panic!("{}", DELTA_BIT_PACK_TYPE_ERROR),
751        }
752    }
753
754    #[inline]
755    fn subtract_u64(&self, left: i64, right: i64) -> u64 {
756        match T::get_physical_type() {
757            // Conversion of i32 -> u32 -> u64 is to avoid non-zero left most bytes in int repr
758            Type::INT32 => (left as i32).wrapping_sub(right as i32) as u32 as u64,
759            Type::INT64 => left.wrapping_sub(right) as u64,
760            _ => panic!("{}", DELTA_BIT_PACK_TYPE_ERROR),
761        }
762    }
763}
764
765// ----------------------------------------------------------------------
766// DELTA_LENGTH_BYTE_ARRAY encoding
767
768/// Encoding for byte arrays to separate the length values and the data.
769/// The lengths are encoded using DELTA_BINARY_PACKED encoding, data is
770/// stored as raw bytes.
771pub struct DeltaLengthByteArrayEncoder<T: DataType> {
772    // length encoder
773    len_encoder: DeltaBitPackEncoder<Int32Type>,
774    // byte array data
775    data: Vec<ByteArray>,
776    // data size in bytes of encoded values
777    encoded_size: usize,
778    _phantom: PhantomData<T>,
779}
780
781impl<T: DataType> Default for DeltaLengthByteArrayEncoder<T> {
782    fn default() -> Self {
783        Self::new()
784    }
785}
786
787impl<T: DataType> DeltaLengthByteArrayEncoder<T> {
788    /// Creates new delta length byte array encoder.
789    pub fn new() -> Self {
790        Self {
791            len_encoder: DeltaBitPackEncoder::new(),
792            data: vec![],
793            encoded_size: 0,
794            _phantom: PhantomData,
795        }
796    }
797
798    /// Creates a delta length byte array encoder with a custom layout for its length encoder.
799    pub fn new_with_options(options: DeltaBinaryPackedEncoderOptions) -> Self {
800        Self {
801            len_encoder: DeltaBitPackEncoder::new_with_options(options),
802            data: vec![],
803            encoded_size: 0,
804            _phantom: PhantomData,
805        }
806    }
807}
808
809impl<T: DataType> Encoder<T> for DeltaLengthByteArrayEncoder<T> {
810    fn put(&mut self, values: &[T::T]) -> Result<()> {
811        ensure_phys_ty!(
812            Type::BYTE_ARRAY | Type::FIXED_LEN_BYTE_ARRAY,
813            "DeltaLengthByteArrayEncoder only supports ByteArrayType"
814        );
815
816        let val_it = || {
817            values
818                .iter()
819                .map(|x| x.as_any().downcast_ref::<ByteArray>().unwrap())
820        };
821
822        let lengths: Vec<i32> = val_it().map(|byte_array| byte_array.len() as i32).collect();
823        self.len_encoder.put(&lengths)?;
824        for byte_array in val_it() {
825            self.encoded_size += byte_array.len();
826            self.data.push(byte_array.clone());
827        }
828
829        Ok(())
830    }
831
832    // Performance Note:
833    // As far as can be seen these functions are rarely called and as such we can hint to the
834    // compiler that they dont need to be folded into hot locations in the final output.
835    #[cold]
836    fn encoding(&self) -> Encoding {
837        Encoding::DELTA_LENGTH_BYTE_ARRAY
838    }
839
840    fn estimated_data_encoded_size(&self) -> usize {
841        self.len_encoder.estimated_data_encoded_size() + self.encoded_size
842    }
843
844    fn flush_buffer(&mut self) -> Result<Bytes> {
845        ensure_phys_ty!(
846            Type::BYTE_ARRAY | Type::FIXED_LEN_BYTE_ARRAY,
847            "DeltaLengthByteArrayEncoder only supports ByteArrayType"
848        );
849
850        let mut total_bytes = vec![];
851        let lengths = self.len_encoder.flush_buffer()?;
852        total_bytes.extend_from_slice(&lengths);
853        self.data.iter().for_each(|byte_array| {
854            total_bytes.extend_from_slice(byte_array.data());
855        });
856        self.data.clear();
857        self.encoded_size = 0;
858
859        Ok(total_bytes.into())
860    }
861
862    /// return the estimated memory size of this encoder.
863    fn estimated_memory_size(&self) -> usize {
864        self.len_encoder.estimated_memory_size() + self.data.len() + std::mem::size_of::<Self>()
865    }
866}
867
868// ----------------------------------------------------------------------
869// DELTA_BYTE_ARRAY encoding
870
871/// Encoding for byte arrays, prefix lengths are encoded using DELTA_BINARY_PACKED
872/// encoding, followed by suffixes with DELTA_LENGTH_BYTE_ARRAY encoding.
873pub struct DeltaByteArrayEncoder<T: DataType> {
874    prefix_len_encoder: DeltaBitPackEncoder<Int32Type>,
875    suffix_writer: DeltaLengthByteArrayEncoder<ByteArrayType>,
876    previous: Vec<u8>,
877    _phantom: PhantomData<T>,
878}
879
880impl<T: DataType> Default for DeltaByteArrayEncoder<T> {
881    fn default() -> Self {
882        Self::new()
883    }
884}
885
886impl<T: DataType> DeltaByteArrayEncoder<T> {
887    /// Creates new delta byte array encoder.
888    pub fn new() -> Self {
889        Self {
890            prefix_len_encoder: DeltaBitPackEncoder::new(),
891            suffix_writer: DeltaLengthByteArrayEncoder::new(),
892            previous: vec![],
893            _phantom: PhantomData,
894        }
895    }
896
897    /// Creates a delta byte array encoder with a custom layout for its prefix and suffix length
898    /// encoders.
899    pub fn new_with_options(options: DeltaBinaryPackedEncoderOptions) -> Self {
900        Self {
901            prefix_len_encoder: DeltaBitPackEncoder::new_with_options(options),
902            suffix_writer: DeltaLengthByteArrayEncoder::new_with_options(options),
903            previous: vec![],
904            _phantom: PhantomData,
905        }
906    }
907}
908
909impl<T: DataType> Encoder<T> for DeltaByteArrayEncoder<T> {
910    fn put(&mut self, values: &[T::T]) -> Result<()> {
911        let mut prefix_lengths: Vec<i32> = vec![];
912        let mut suffixes: Vec<ByteArray> = vec![];
913
914        let values = values
915            .iter()
916            .map(|x| x.as_any())
917            .map(|x| match T::get_physical_type() {
918                Type::BYTE_ARRAY => x.downcast_ref::<ByteArray>().unwrap(),
919                Type::FIXED_LEN_BYTE_ARRAY => x.downcast_ref::<FixedLenByteArray>().unwrap(),
920                _ => panic!(
921                    "DeltaByteArrayEncoder only supports ByteArrayType and FixedLenByteArrayType"
922                ),
923            });
924
925        for byte_array in values {
926            let current = byte_array.data();
927            // Number of leading bytes shared with the previous value
928            let match_len = common_prefix_length(&self.previous, current);
929            prefix_lengths.push(match_len as i32);
930            suffixes.push(byte_array.slice(match_len, byte_array.len() - match_len));
931            // Update previous for the next prefix
932            self.previous.clear();
933            self.previous.extend_from_slice(current);
934        }
935        self.prefix_len_encoder.put(&prefix_lengths)?;
936        self.suffix_writer.put(&suffixes)?;
937
938        Ok(())
939    }
940
941    // Performance Note:
942    // As far as can be seen these functions are rarely called and as such we can hint to the
943    // compiler that they dont need to be folded into hot locations in the final output.
944    #[cold]
945    fn encoding(&self) -> Encoding {
946        Encoding::DELTA_BYTE_ARRAY
947    }
948
949    fn estimated_data_encoded_size(&self) -> usize {
950        self.prefix_len_encoder.estimated_data_encoded_size()
951            + self.suffix_writer.estimated_data_encoded_size()
952    }
953
954    fn flush_buffer(&mut self) -> Result<Bytes> {
955        match T::get_physical_type() {
956            Type::BYTE_ARRAY | Type::FIXED_LEN_BYTE_ARRAY => {
957                // TODO: investigate if we can merge lengths and suffixes
958                // without copying data into new vector.
959                let mut total_bytes = vec![];
960                // Insert lengths ...
961                let lengths = self.prefix_len_encoder.flush_buffer()?;
962                total_bytes.extend_from_slice(&lengths);
963                // ... followed by suffixes
964                let suffixes = self.suffix_writer.flush_buffer()?;
965                total_bytes.extend_from_slice(&suffixes);
966
967                self.previous.clear();
968                Ok(total_bytes.into())
969            }
970            _ => panic!(
971                "DeltaByteArrayEncoder only supports ByteArrayType and FixedLenByteArrayType"
972            ),
973        }
974    }
975
976    /// return the estimated memory size of this encoder.
977    fn estimated_memory_size(&self) -> usize {
978        self.prefix_len_encoder.estimated_memory_size()
979            + self.suffix_writer.estimated_memory_size()
980            + (self.previous.capacity() * std::mem::size_of::<u8>())
981    }
982}
983
984#[cfg(test)]
985mod tests {
986    use super::*;
987
988    use std::sync::Arc;
989
990    use crate::encodings::decoding::{Decoder, DictDecoder, PlainDecoder, get_decoder};
991    use crate::file::properties::WriterProperties;
992    use crate::schema::types::{ColumnDescPtr, ColumnDescriptor, ColumnPath, Type as SchemaType};
993    use crate::util::bit_util;
994    use crate::util::test_common::rand_gen::{RandGen, random_bytes};
995
996    const TEST_SET_SIZE: usize = 1024;
997
998    #[test]
999    fn test_delta_binary_packed_encoder_options() {
1000        let options = DeltaBinaryPackedEncoderOptions::try_new(256, 4).unwrap();
1001        assert_eq!(options.block_size(), 256);
1002        assert_eq!(options.mini_blocks_per_block(), 4);
1003
1004        let encoder = DeltaBitPackEncoder::<Int32Type>::new_with_options(options);
1005        assert_eq!(encoder.block_size, 256);
1006        assert_eq!(encoder.mini_block_size, 64);
1007        assert_eq!(encoder.num_mini_blocks, 4);
1008
1009        let props = WriterProperties::builder()
1010            .set_delta_binary_packed_encoder_options(options)
1011            .build();
1012        let column_props = props.resolve_column_properties(&ColumnPath::new(vec![]));
1013        let desc = create_test_col_desc_ptr(-1, Type::INT32);
1014        let mut encoder = get_encoder_with_properties::<Int32Type>(
1015            Encoding::DELTA_BINARY_PACKED,
1016            &desc,
1017            &column_props,
1018        )
1019        .unwrap();
1020        let input: Vec<i32> = (0..600).map(|value| value * value).collect();
1021        encoder.put(&input).unwrap();
1022        let encoded = encoder.flush_buffer().unwrap();
1023        let mut header = bit_util::BitReader::new(encoded.clone());
1024        assert_eq!(header.get_vlq_int(), Some(256));
1025        assert_eq!(header.get_vlq_int(), Some(4));
1026
1027        let mut decoder = create_test_decoder::<Int32Type>(-1, Encoding::DELTA_BINARY_PACKED);
1028        decoder.set_data(encoded, input.len()).unwrap();
1029        let mut output = vec![0; input.len()];
1030        assert_eq!(decoder.get(&mut output).unwrap(), input.len());
1031        assert_eq!(output, input);
1032
1033        let encoder = DeltaLengthByteArrayEncoder::<ByteArrayType>::new_with_options(options);
1034        assert_eq!(encoder.len_encoder.block_size, 256);
1035        let encoder = DeltaByteArrayEncoder::<ByteArrayType>::new_with_options(options);
1036        assert_eq!(encoder.prefix_len_encoder.block_size, 256);
1037        assert_eq!(encoder.suffix_writer.len_encoder.block_size, 256);
1038
1039        let input: Vec<ByteArray> = (0..600)
1040            .map(|value| ByteArray::from(format!("prefix-{value:04}-suffix").into_bytes()))
1041            .collect();
1042        let desc = create_test_col_desc_ptr(-1, Type::BYTE_ARRAY);
1043        for encoding in [
1044            Encoding::DELTA_LENGTH_BYTE_ARRAY,
1045            Encoding::DELTA_BYTE_ARRAY,
1046        ] {
1047            let mut encoder =
1048                get_encoder_with_properties::<ByteArrayType>(encoding, &desc, &column_props)
1049                    .unwrap();
1050            encoder.put(&input).unwrap();
1051            let encoded = encoder.flush_buffer().unwrap();
1052            let mut header = bit_util::BitReader::new(encoded.clone());
1053            assert_eq!(header.get_vlq_int(), Some(256));
1054            assert_eq!(header.get_vlq_int(), Some(4));
1055
1056            let mut decoder = create_test_decoder::<ByteArrayType>(-1, encoding);
1057            decoder.set_data(encoded, input.len()).unwrap();
1058            let mut output = vec![ByteArray::default(); input.len()];
1059            assert_eq!(decoder.get(&mut output).unwrap(), input.len());
1060            assert_eq!(output, input);
1061        }
1062    }
1063
1064    #[test]
1065    fn test_delta_binary_packed_encoder_options_validation() {
1066        for (block_size, mini_blocks_per_block, message) in [
1067            (0, 4, "positive multiple of 128"),
1068            (127, 4, "positive multiple of 128"),
1069            (128, 0, "positive divisor"),
1070            (128, 3, "positive divisor"),
1071            (256, 16, "must be a multiple of 32"),
1072        ] {
1073            let error = DeltaBinaryPackedEncoderOptions::try_new(block_size, mini_blocks_per_block)
1074                .unwrap_err();
1075            assert!(error.to_string().contains(message), "{error}");
1076        }
1077    }
1078
1079    #[test]
1080    fn test_get_encoders_with_properties() {
1081        fn check<T: DataType>(
1082            encoding: Encoding,
1083            values: &[T::T],
1084            props: &ResolvedColumnProperties,
1085        ) {
1086            let desc = create_test_col_desc_ptr(-1, T::get_physical_type());
1087            let mut default = get_encoder::<T>(encoding, &desc).unwrap();
1088            let mut resolved = get_encoder_with_properties::<T>(encoding, &desc, props).unwrap();
1089            default.put(values).unwrap();
1090            resolved.put(values).unwrap();
1091            assert_eq!(resolved.encoding(), encoding);
1092            assert_eq!(
1093                resolved.flush_buffer().unwrap(),
1094                default.flush_buffer().unwrap()
1095            );
1096        }
1097
1098        let path = ColumnPath::from("col");
1099        let props = WriterProperties::builder().build();
1100        let defaults = props.resolve_column_properties(&path);
1101        let ints: Vec<i32> = (0..600).map(|value| value * value).collect();
1102        check::<Int32Type>(Encoding::DELTA_BINARY_PACKED, &ints, &defaults);
1103        let longs: Vec<i64> = ints.iter().map(|&value| i64::from(value)).collect();
1104        check::<Int64Type>(Encoding::DELTA_BINARY_PACKED, &longs, &defaults);
1105        let bytes: Vec<ByteArray> = ints
1106            .iter()
1107            .map(|value| ByteArray::from(format!("prefix-{value}").into_bytes()))
1108            .collect();
1109        for encoding in [
1110            Encoding::DELTA_LENGTH_BYTE_ARRAY,
1111            Encoding::DELTA_BYTE_ARRAY,
1112        ] {
1113            check::<ByteArrayType>(encoding, &bytes, &defaults);
1114        }
1115
1116        let props = WriterProperties::builder()
1117            .set_delta_binary_packed_encoder_options(
1118                DeltaBinaryPackedEncoderOptions::try_new(256, 4).unwrap(),
1119            )
1120            .build();
1121        let custom = props.resolve_column_properties(&path);
1122        for props in [&defaults, &custom] {
1123            check::<Int32Type>(Encoding::PLAIN, &ints, props);
1124            for encoding in [Encoding::PLAIN, Encoding::BYTE_STREAM_SPLIT, Encoding::ALP] {
1125                check::<FloatType>(encoding, &[1.25, -2.5, 3.75], props);
1126                check::<DoubleType>(encoding, &[1.25, -2.5, 3.75], props);
1127            }
1128        }
1129    }
1130
1131    #[test]
1132    fn test_get_encoders() {
1133        // supported encodings
1134        create_and_check_encoder::<Int32Type>(0, Encoding::PLAIN, None);
1135        create_and_check_encoder::<Int32Type>(0, Encoding::DELTA_BINARY_PACKED, None);
1136        create_and_check_encoder::<BoolType>(0, Encoding::RLE, None);
1137
1138        // error when initializing
1139        create_and_check_encoder::<Int32Type>(
1140            0,
1141            Encoding::RLE_DICTIONARY,
1142            Some(general_err!(
1143                "Cannot initialize this encoding through this function"
1144            )),
1145        );
1146        create_and_check_encoder::<Int32Type>(
1147            0,
1148            Encoding::PLAIN_DICTIONARY,
1149            Some(general_err!(
1150                "Cannot initialize this encoding through this function"
1151            )),
1152        );
1153        create_and_check_encoder::<Int32Type>(
1154            0,
1155            Encoding::DELTA_LENGTH_BYTE_ARRAY,
1156            Some(unsupported_column_encoding(
1157                Encoding::DELTA_LENGTH_BYTE_ARRAY,
1158                Type::INT32,
1159            )),
1160        );
1161        create_and_check_encoder::<Int32Type>(
1162            0,
1163            Encoding::DELTA_BYTE_ARRAY,
1164            Some(unsupported_column_encoding(
1165                Encoding::DELTA_BYTE_ARRAY,
1166                Type::INT32,
1167            )),
1168        );
1169        create_and_check_encoder::<Int32Type>(
1170            0,
1171            Encoding::ALP,
1172            Some(general_err!(
1173                "Encoding ALP only supports FLOAT and DOUBLE, got INT32"
1174            )),
1175        );
1176
1177        // unsupported
1178        #[expect(deprecated)]
1179        create_and_check_encoder::<Int32Type>(
1180            0,
1181            Encoding::BIT_PACKED,
1182            Some(nyi_err!("Encoding BIT_PACKED is not supported")),
1183        );
1184    }
1185
1186    #[test]
1187    fn column_construction_validates_encoding_fallback_matrix() {
1188        use crate::file::properties::{WriterProperties, WriterVersion};
1189        use crate::file::writer::SerializedFileWriter;
1190        use std::panic::{AssertUnwindSafe, catch_unwind};
1191        use std::sync::Arc;
1192
1193        fn check_encoder<T: DataType>(encoding: Encoding, supported: bool) {
1194            let error = if supported {
1195                None
1196            } else if encoding == Encoding::ALP {
1197                Some(general_err!(
1198                    "Encoding ALP only supports FLOAT and DOUBLE, got {}",
1199                    T::get_physical_type()
1200                ))
1201            } else {
1202                Some(unsupported_column_encoding(
1203                    encoding,
1204                    T::get_physical_type(),
1205                ))
1206            };
1207            create_and_check_encoder::<T>(4, encoding, error);
1208        }
1209
1210        let encodings = [
1211            Encoding::PLAIN,
1212            Encoding::RLE,
1213            Encoding::DELTA_BINARY_PACKED,
1214            Encoding::DELTA_LENGTH_BYTE_ARRAY,
1215            Encoding::DELTA_BYTE_ARRAY,
1216            Encoding::BYTE_STREAM_SPLIT,
1217            Encoding::ALP,
1218        ];
1219        for physical in [
1220            Type::BOOLEAN,
1221            Type::INT32,
1222            Type::INT64,
1223            Type::INT96,
1224            Type::FLOAT,
1225            Type::DOUBLE,
1226            Type::BYTE_ARRAY,
1227            Type::FIXED_LEN_BYTE_ARRAY,
1228        ] {
1229            let valid: &[Encoding] = match physical {
1230                Type::BOOLEAN => &[Encoding::PLAIN, Encoding::RLE],
1231                Type::INT32 | Type::INT64 => &[
1232                    Encoding::PLAIN,
1233                    Encoding::DELTA_BINARY_PACKED,
1234                    Encoding::BYTE_STREAM_SPLIT,
1235                ],
1236                Type::INT96 => &[Encoding::PLAIN],
1237                Type::FLOAT | Type::DOUBLE => {
1238                    &[Encoding::PLAIN, Encoding::BYTE_STREAM_SPLIT, Encoding::ALP]
1239                }
1240                Type::BYTE_ARRAY => &[
1241                    Encoding::PLAIN,
1242                    Encoding::DELTA_LENGTH_BYTE_ARRAY,
1243                    Encoding::DELTA_BYTE_ARRAY,
1244                ],
1245                Type::FIXED_LEN_BYTE_ARRAY => &[
1246                    Encoding::PLAIN,
1247                    Encoding::DELTA_BYTE_ARRAY,
1248                    Encoding::BYTE_STREAM_SPLIT,
1249                ],
1250            };
1251            // Check the factory's returned errors directly, independently of the
1252            // infallible column writer constructor that unwraps those errors.
1253            for encoding in encodings {
1254                let supported = valid.contains(&encoding);
1255                match physical {
1256                    Type::BOOLEAN => check_encoder::<BoolType>(encoding, supported),
1257                    Type::INT32 => check_encoder::<Int32Type>(encoding, supported),
1258                    Type::INT64 => check_encoder::<Int64Type>(encoding, supported),
1259                    Type::INT96 => check_encoder::<Int96Type>(encoding, supported),
1260                    Type::FLOAT => check_encoder::<FloatType>(encoding, supported),
1261                    Type::DOUBLE => check_encoder::<DoubleType>(encoding, supported),
1262                    Type::BYTE_ARRAY => check_encoder::<ByteArrayType>(encoding, supported),
1263                    Type::FIXED_LEN_BYTE_ARRAY => {
1264                        check_encoder::<FixedLenByteArrayType>(encoding, supported)
1265                    }
1266                }
1267            }
1268            for version in [WriterVersion::PARQUET_1_0, WriterVersion::PARQUET_2_0] {
1269                for dictionary in [false, true] {
1270                    for encoding in encodings {
1271                        let field = Arc::new(
1272                            SchemaType::primitive_type_builder("a", physical)
1273                                .with_length(4)
1274                                .build()
1275                                .unwrap(),
1276                        );
1277                        let schema = Arc::new(
1278                            SchemaType::group_type_builder("schema")
1279                                .with_fields(vec![field])
1280                                .build()
1281                                .unwrap(),
1282                        );
1283                        let props = Arc::new(
1284                            WriterProperties::builder()
1285                                .set_writer_version(version)
1286                                .set_dictionary_enabled(dictionary)
1287                                .set_encoding(encoding)
1288                                .build(),
1289                        );
1290                        let created = catch_unwind(AssertUnwindSafe(|| {
1291                            let mut writer =
1292                                SerializedFileWriter::new(Vec::new(), schema, props).unwrap();
1293                            let mut group = writer.next_row_group().unwrap();
1294                            group.next_column().unwrap().unwrap();
1295                        }));
1296                        assert_eq!(
1297                            created.is_ok(),
1298                            valid.contains(&encoding),
1299                            "{physical:?} {version:?} dictionary={dictionary} {encoding:?}"
1300                        );
1301                    }
1302                }
1303            }
1304        }
1305    }
1306
1307    #[test]
1308    fn test_bool() {
1309        BoolType::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1310        BoolType::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1311        BoolType::test(Encoding::RLE, TEST_SET_SIZE, -1);
1312    }
1313
1314    #[test]
1315    #[cfg_attr(miri, ignore)] // Takes too long
1316    fn test_i32() {
1317        Int32Type::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1318        Int32Type::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1319        Int32Type::test(Encoding::DELTA_BINARY_PACKED, TEST_SET_SIZE, -1);
1320        Int32Type::test(Encoding::BYTE_STREAM_SPLIT, TEST_SET_SIZE, -1);
1321    }
1322
1323    #[test]
1324    #[cfg_attr(miri, ignore)] // Takes too long
1325    fn test_i64() {
1326        Int64Type::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1327        Int64Type::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1328        Int64Type::test(Encoding::DELTA_BINARY_PACKED, TEST_SET_SIZE, -1);
1329        Int64Type::test(Encoding::BYTE_STREAM_SPLIT, TEST_SET_SIZE, -1);
1330    }
1331
1332    #[test]
1333    #[cfg_attr(miri, ignore)] // Takes too long
1334    fn test_i96() {
1335        Int96Type::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1336        Int96Type::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1337    }
1338
1339    #[test]
1340    fn test_float() {
1341        FloatType::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1342        FloatType::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1343        FloatType::test(Encoding::BYTE_STREAM_SPLIT, TEST_SET_SIZE, -1);
1344    }
1345
1346    #[test]
1347    #[cfg_attr(miri, ignore)] // Takes too long
1348    fn test_double() {
1349        DoubleType::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1350        DoubleType::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1351        DoubleType::test(Encoding::BYTE_STREAM_SPLIT, TEST_SET_SIZE, -1);
1352    }
1353
1354    #[test]
1355    #[cfg_attr(miri, ignore)] // Takes too long
1356    fn test_byte_array() {
1357        ByteArrayType::test(Encoding::PLAIN, TEST_SET_SIZE, -1);
1358        ByteArrayType::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, -1);
1359        ByteArrayType::test(Encoding::DELTA_LENGTH_BYTE_ARRAY, TEST_SET_SIZE, -1);
1360        ByteArrayType::test(Encoding::DELTA_BYTE_ARRAY, TEST_SET_SIZE, -1);
1361    }
1362
1363    #[test]
1364    #[cfg_attr(miri, ignore)] // Takes too long
1365    fn test_fixed_len_byte_array() {
1366        FixedLenByteArrayType::test(Encoding::PLAIN, TEST_SET_SIZE, 100);
1367        FixedLenByteArrayType::test(Encoding::PLAIN_DICTIONARY, TEST_SET_SIZE, 100);
1368        FixedLenByteArrayType::test(Encoding::DELTA_BYTE_ARRAY, TEST_SET_SIZE, 100);
1369        FixedLenByteArrayType::test(Encoding::BYTE_STREAM_SPLIT, TEST_SET_SIZE, 100);
1370    }
1371
1372    #[test]
1373    fn test_dict_encoded_size() {
1374        fn run_test<T: DataType>(type_length: i32, values: &[T::T], expected_size: usize) {
1375            let mut encoder = create_test_dict_encoder::<T>(type_length);
1376            assert_eq!(encoder.dict_encoded_size(), 0);
1377            encoder.put(values).unwrap();
1378            assert_eq!(encoder.dict_encoded_size(), expected_size);
1379            // We do not reset encoded size of the dictionary keys after flush_buffer
1380            encoder.flush_buffer().unwrap();
1381            assert_eq!(encoder.dict_encoded_size(), expected_size);
1382        }
1383
1384        // Only 2 variations of values 1 byte each
1385        run_test::<BoolType>(-1, &[true, false, true, false, true], 2);
1386        run_test::<Int32Type>(-1, &[1i32, 2i32, 3i32, 4i32, 5i32], 20);
1387        run_test::<Int64Type>(-1, &[1i64, 2i64, 3i64, 4i64, 5i64], 40);
1388        run_test::<FloatType>(-1, &[1f32, 2f32, 3f32, 4f32, 5f32], 20);
1389        run_test::<DoubleType>(-1, &[1f64, 2f64, 3f64, 4f64, 5f64], 40);
1390        // Int96: len + reference
1391        run_test::<Int96Type>(
1392            -1,
1393            &[Int96::from(vec![1, 2, 3]), Int96::from(vec![2, 3, 4])],
1394            24,
1395        );
1396        run_test::<ByteArrayType>(-1, &[ByteArray::from("abcd"), ByteArray::from("efj")], 15);
1397        run_test::<FixedLenByteArrayType>(
1398            2,
1399            &[ByteArray::from("ab").into(), ByteArray::from("bc").into()],
1400            4,
1401        );
1402    }
1403
1404    #[test]
1405    fn test_estimated_data_encoded_size() {
1406        fn run_test<T: DataType>(
1407            encoding: Encoding,
1408            type_length: i32,
1409            values: &[T::T],
1410            initial_size: usize,
1411            max_size: usize,
1412            flush_size: usize,
1413        ) {
1414            let mut encoder = match encoding {
1415                Encoding::PLAIN_DICTIONARY | Encoding::RLE_DICTIONARY => {
1416                    Box::new(create_test_dict_encoder::<T>(type_length))
1417                }
1418                _ => create_test_encoder::<T>(type_length, encoding),
1419            };
1420            assert_eq!(encoder.estimated_data_encoded_size(), initial_size);
1421
1422            encoder.put(values).unwrap();
1423            assert_eq!(encoder.estimated_data_encoded_size(), max_size);
1424
1425            encoder.flush_buffer().unwrap();
1426            assert_eq!(encoder.estimated_data_encoded_size(), flush_size);
1427        }
1428
1429        // PLAIN
1430        run_test::<Int32Type>(Encoding::PLAIN, -1, &[123; 1024], 0, 4096, 0);
1431
1432        // DICTIONARY
1433        // NOTE: The final size is almost the same because the dictionary entries are
1434        // preserved after encoded values have been written.
1435        run_test::<Int32Type>(Encoding::RLE_DICTIONARY, -1, &[123, 1024], 0, 2, 0);
1436
1437        // DELTA_BINARY_PACKED
1438        run_test::<Int32Type>(Encoding::DELTA_BINARY_PACKED, -1, &[123; 1024], 0, 35, 0);
1439
1440        // RLE
1441        let mut values = vec![];
1442        values.extend_from_slice(&[true; 16]);
1443        values.extend_from_slice(&[false; 16]);
1444        run_test::<BoolType>(Encoding::RLE, -1, &values, 0, 6, 0);
1445
1446        // DELTA_LENGTH_BYTE_ARRAY
1447        run_test::<ByteArrayType>(
1448            Encoding::DELTA_LENGTH_BYTE_ARRAY,
1449            -1,
1450            &[ByteArray::from("ab"), ByteArray::from("abc")],
1451            0,
1452            5, // only value bytes, length encoder is not flushed yet
1453            0,
1454        );
1455
1456        // DELTA_BYTE_ARRAY
1457        run_test::<ByteArrayType>(
1458            Encoding::DELTA_BYTE_ARRAY,
1459            -1,
1460            &[ByteArray::from("ab"), ByteArray::from("abc")],
1461            0,
1462            3, // only suffix bytes, length encoder is not flushed yet
1463            0,
1464        );
1465
1466        // BYTE_STREAM_SPLIT
1467        run_test::<FloatType>(Encoding::BYTE_STREAM_SPLIT, -1, &[0.1, 0.2], 0, 8, 0);
1468    }
1469
1470    #[test]
1471    fn test_byte_stream_split_example_f32() {
1472        // Test data from https://github.com/apache/parquet-format/blob/2a481fe1aad64ff770e21734533bb7ef5a057dac/Encodings.md#byte-stream-split-byte_stream_split--9
1473        let mut encoder = create_test_encoder::<FloatType>(0, Encoding::BYTE_STREAM_SPLIT);
1474        let mut decoder = create_test_decoder::<FloatType>(0, Encoding::BYTE_STREAM_SPLIT);
1475
1476        let input = vec![
1477            f32::from_le_bytes([0xAA, 0xBB, 0xCC, 0xDD]),
1478            f32::from_le_bytes([0x00, 0x11, 0x22, 0x33]),
1479            f32::from_le_bytes([0xA3, 0xB4, 0xC5, 0xD6]),
1480        ];
1481
1482        encoder.put(&input).unwrap();
1483        let encoded = encoder.flush_buffer().unwrap();
1484
1485        assert_eq!(
1486            encoded,
1487            Bytes::from(vec![
1488                0xAA_u8, 0x00, 0xA3, 0xBB, 0x11, 0xB4, 0xCC, 0x22, 0xC5, 0xDD, 0x33, 0xD6
1489            ])
1490        );
1491
1492        let mut decoded = vec![0.0; input.len()];
1493        decoder.set_data(encoded, input.len()).unwrap();
1494        decoder.get(&mut decoded).unwrap();
1495
1496        assert_eq!(decoded, input);
1497    }
1498
1499    // See: https://github.com/sunchao/parquet-rs/issues/47
1500    #[test]
1501    fn test_issue_47() {
1502        let mut encoder = create_test_encoder::<ByteArrayType>(0, Encoding::DELTA_BYTE_ARRAY);
1503        let mut decoder = create_test_decoder::<ByteArrayType>(0, Encoding::DELTA_BYTE_ARRAY);
1504
1505        let input = vec![
1506            ByteArray::from("aa"),
1507            ByteArray::from("aaa"),
1508            ByteArray::from("aa"),
1509            ByteArray::from("aaa"),
1510        ];
1511
1512        let mut output = vec![ByteArray::default(); input.len()];
1513
1514        let mut result = put_and_get(&mut encoder, &mut decoder, &input[..2], &mut output[..2]);
1515        assert!(
1516            result.is_ok(),
1517            "first put_and_get() failed with: {}",
1518            result.unwrap_err()
1519        );
1520        result = put_and_get(&mut encoder, &mut decoder, &input[2..], &mut output[2..]);
1521        assert!(
1522            result.is_ok(),
1523            "second put_and_get() failed with: {}",
1524            result.unwrap_err()
1525        );
1526        assert_eq!(output, input);
1527    }
1528
1529    trait EncodingTester<T: DataType> {
1530        fn test(enc: Encoding, total: usize, type_length: i32) {
1531            let result = match enc {
1532                Encoding::PLAIN_DICTIONARY | Encoding::RLE_DICTIONARY => {
1533                    Self::test_dict_internal(total, type_length)
1534                }
1535                enc => Self::test_internal(enc, total, type_length),
1536            };
1537
1538            assert!(
1539                result.is_ok(),
1540                "Expected result to be OK but got err:\n {}",
1541                result.unwrap_err()
1542            );
1543        }
1544
1545        fn test_internal(enc: Encoding, total: usize, type_length: i32) -> Result<()>;
1546
1547        fn test_dict_internal(total: usize, type_length: i32) -> Result<()>;
1548    }
1549
1550    impl<T: DataType + RandGen<T>> EncodingTester<T> for T {
1551        fn test_internal(enc: Encoding, total: usize, type_length: i32) -> Result<()> {
1552            let mut encoder = create_test_encoder::<T>(type_length, enc);
1553            let mut decoder = create_test_decoder::<T>(type_length, enc);
1554            let mut values = <T as RandGen<T>>::gen_vec(type_length, total);
1555            let mut result_data = vec![T::T::default(); total];
1556
1557            // Test put/get spaced.
1558            let num_bytes = bit_util::ceil(total as i64, 8);
1559            let valid_bits = random_bytes(num_bytes as usize);
1560            let values_written = encoder.put_spaced(&values[..], &valid_bits[..])?;
1561            let data = encoder.flush_buffer()?;
1562            decoder.set_data(data, values_written)?;
1563            let _ = decoder.get_spaced(
1564                &mut result_data[..],
1565                values.len() - values_written,
1566                &valid_bits[..],
1567            )?;
1568
1569            // Check equality
1570            for i in 0..total {
1571                if bit_util::get_bit(&valid_bits[..], i) {
1572                    assert_eq!(result_data[i], values[i]);
1573                } else {
1574                    assert_eq!(result_data[i], T::T::default());
1575                }
1576            }
1577
1578            let mut actual_total = put_and_get(
1579                &mut encoder,
1580                &mut decoder,
1581                &values[..],
1582                &mut result_data[..],
1583            )?;
1584            assert_eq!(actual_total, total);
1585            assert_eq!(result_data, values);
1586
1587            // Encode more data after flush and test with decoder
1588
1589            values = <T as RandGen<T>>::gen_vec(type_length, total);
1590            actual_total = put_and_get(
1591                &mut encoder,
1592                &mut decoder,
1593                &values[..],
1594                &mut result_data[..],
1595            )?;
1596            assert_eq!(actual_total, total);
1597            assert_eq!(result_data, values);
1598
1599            Ok(())
1600        }
1601
1602        fn test_dict_internal(total: usize, type_length: i32) -> Result<()> {
1603            let mut encoder = create_test_dict_encoder::<T>(type_length);
1604            let mut values = <T as RandGen<T>>::gen_vec(type_length, total);
1605            encoder.put(&values[..])?;
1606
1607            let mut data = encoder.flush_buffer()?;
1608            let mut decoder = create_test_dict_decoder::<T>();
1609            let mut dict_decoder = PlainDecoder::<T>::new(type_length);
1610            dict_decoder.set_data(encoder.write_dict()?, encoder.num_entries())?;
1611            decoder.set_dict(Box::new(dict_decoder))?;
1612            let mut result_data = vec![T::T::default(); total];
1613            decoder.set_data(data, total)?;
1614            let mut actual_total = decoder.get(&mut result_data)?;
1615
1616            assert_eq!(actual_total, total);
1617            assert_eq!(result_data, values);
1618
1619            // Encode more data after flush and test with decoder
1620
1621            values = <T as RandGen<T>>::gen_vec(type_length, total);
1622            encoder.put(&values[..])?;
1623            data = encoder.flush_buffer()?;
1624
1625            let mut dict_decoder = PlainDecoder::<T>::new(type_length);
1626            dict_decoder.set_data(encoder.write_dict()?, encoder.num_entries())?;
1627            decoder.set_dict(Box::new(dict_decoder))?;
1628            decoder.set_data(data, total)?;
1629            actual_total = decoder.get(&mut result_data)?;
1630
1631            assert_eq!(actual_total, total);
1632            assert_eq!(result_data, values);
1633
1634            Ok(())
1635        }
1636    }
1637
1638    fn put_and_get<T: DataType>(
1639        encoder: &mut Box<dyn Encoder<T>>,
1640        decoder: &mut Box<dyn Decoder<T>>,
1641        input: &[T::T],
1642        output: &mut [T::T],
1643    ) -> Result<usize> {
1644        encoder.put(input)?;
1645        let data = encoder.flush_buffer()?;
1646        decoder.set_data(data, input.len())?;
1647        decoder.get(output)
1648    }
1649
1650    fn create_and_check_encoder<T: DataType>(
1651        type_length: i32,
1652        encoding: Encoding,
1653        err: Option<ParquetError>,
1654    ) {
1655        let desc = create_test_col_desc_ptr(type_length, T::get_physical_type());
1656        let defaults = WriterProperties::builder().build();
1657        let custom = WriterProperties::builder()
1658            .set_delta_binary_packed_encoder_options(
1659                DeltaBinaryPackedEncoderOptions::try_new(256, 4).unwrap(),
1660            )
1661            .build();
1662        let path = ColumnPath::from("t");
1663        for encoder in [
1664            get_encoder::<T>(encoding, &desc),
1665            get_encoder_with_properties::<T>(
1666                encoding,
1667                &desc,
1668                &defaults.resolve_column_properties(&path),
1669            ),
1670            get_encoder_with_properties::<T>(
1671                encoding,
1672                &desc,
1673                &custom.resolve_column_properties(&path),
1674            ),
1675        ] {
1676            match &err {
1677                Some(parquet_error) => {
1678                    assert_eq!(
1679                        encoder.err().unwrap().to_string(),
1680                        parquet_error.to_string()
1681                    )
1682                }
1683                None => assert_eq!(encoder.unwrap().encoding(), encoding),
1684            }
1685        }
1686    }
1687
1688    // Creates test column descriptor.
1689    fn create_test_col_desc_ptr(type_len: i32, t: Type) -> ColumnDescPtr {
1690        let ty = SchemaType::primitive_type_builder("t", t)
1691            .with_length(type_len)
1692            .build()
1693            .unwrap();
1694        Arc::new(ColumnDescriptor::new(
1695            Arc::new(ty),
1696            0,
1697            0,
1698            ColumnPath::new(vec![]),
1699        ))
1700    }
1701
1702    fn create_test_encoder<T: DataType>(type_len: i32, enc: Encoding) -> Box<dyn Encoder<T>> {
1703        let desc = create_test_col_desc_ptr(type_len, T::get_physical_type());
1704        get_encoder(enc, &desc).unwrap()
1705    }
1706
1707    fn create_test_decoder<T: DataType>(type_len: i32, enc: Encoding) -> Box<dyn Decoder<T>> {
1708        let desc = create_test_col_desc_ptr(type_len, T::get_physical_type());
1709        get_decoder(desc, enc).unwrap()
1710    }
1711
1712    fn create_test_dict_encoder<T: DataType>(type_len: i32) -> DictEncoder<T> {
1713        let desc = create_test_col_desc_ptr(type_len, T::get_physical_type());
1714        DictEncoder::<T>::new(desc)
1715    }
1716
1717    fn create_test_dict_decoder<T: DataType>() -> DictDecoder<T> {
1718        DictDecoder::<T>::new()
1719    }
1720}