vortex_btrblocks/schemes/integer/
delta.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4//! FastLanes Delta integer encoding.
5
6use vortex_array::ArrayId;
7use vortex_array::ArrayRef;
8use vortex_array::Canonical;
9use vortex_array::ExecutionCtx;
10use vortex_array::IntoArray;
11use vortex_array::VTable;
12use vortex_array::arrays::PrimitiveArray;
13use vortex_compressor::builtins::BinaryDictScheme;
14use vortex_compressor::builtins::FloatDictScheme;
15use vortex_compressor::builtins::IntDictScheme;
16use vortex_compressor::builtins::StringDictScheme;
17use vortex_compressor::scheme::AncestorExclusion;
18use vortex_compressor::scheme::ChildSelection;
19use vortex_compressor::scheme::CompressionEstimate;
20use vortex_compressor::scheme::DeferredEstimate;
21use vortex_compressor::scheme::DescendantExclusion;
22use vortex_compressor::scheme::EstimateScore;
23use vortex_compressor::scheme::EstimateVerdict;
24use vortex_error::VortexResult;
25use vortex_fastlanes::Delta;
26use vortex_fastlanes::FL_CHUNK_SIZE;
27
28use crate::ArrayAndStats;
29use crate::CascadingCompressor;
30use crate::CompressorContext;
31use crate::GenerateStatsOptions;
32use crate::Scheme;
33use crate::SchemeExt;
34
35/// FastLanes Delta encoding for smooth / near-monotone integers.
36///
37/// Delta replaces each value with its difference from an earlier value (at the FastLanes lane
38/// stride), so a later cascade layer (FoR / BitPacking) packs the smaller residuals. It only
39/// pays off when those residuals span meaningfully fewer bits than the values themselves.
40///
41/// The minimum penalized compression ratio required for Delta to be selected is configurable via
42/// [`DeltaScheme::new`]; [`DeltaScheme::default`] uses a ratio of `1.25`.
43#[derive(Debug, Copy, Clone, PartialEq)]
44pub struct DeltaScheme {
45    min_ratio: f64,
46}
47
48impl DeltaScheme {
49    /// Creates a Delta scheme requiring `min_ratio` after the delta penalty before it wins.
50    ///
51    /// Pass a higher ratio to make Delta more conservative, or a lower one to select it more
52    /// eagerly. [`DeltaScheme::default`] uses a ratio of `1.25`.
53    pub const fn new(min_ratio: f64) -> Self {
54        Self { min_ratio }
55    }
56}
57
58impl Default for DeltaScheme {
59    fn default() -> Self {
60        Self::new(1.25)
61    }
62}
63
64/// Multiplicative penalty applied to Delta's estimated compression ratio.
65///
66/// Unlike FoR/BitPacking, Delta breaks random access and adds a prefix-sum decode pass, and it
67/// carries a structural sign bit on its residuals. We therefore require Delta to be meaningfully
68/// (~5%) smaller than the best alternative before it wins, rather than picking it for a
69/// single-bit gain. This factor encodes that "delta tax".
70const DELTA_PENALTY: f64 = 0.95;
71
72/// Minimum length before Delta is worth considering (one FastLanes chunk).
73const MIN_DELTA_LEN: usize = 1024;
74
75/// Penalized compression ratio for `len` values of `full_width` bits whose transposed residuals
76/// need `delta_bits` bits each.
77///
78/// Delta writes two children and both are sized by the padded length, since `delta_compress`
79/// rounds the input up to whole [`FL_CHUNK_SIZE`] chunks. The deltas child holds `padded_len`
80/// residuals of `delta_bits`; the bases child holds one base per lane per chunk, and a chunk of
81/// `W`-bit values has `FL_CHUNK_SIZE / W` lanes, so its bases occupy [`FL_CHUNK_SIZE`] bits per
82/// chunk whatever `W` is: one further bit per residual. Charging the bases at full width is an
83/// upper bound, as the cascade compresses that child like any other.
84///
85/// `len` must be non-zero; callers gate on [`MIN_DELTA_LEN`].
86fn penalized_ratio(len: usize, full_width: f64, delta_bits: f64) -> f64 {
87    let padded_len = len.next_multiple_of(FL_CHUNK_SIZE) as f64;
88    (len as f64) * full_width / (padded_len * (delta_bits + 1.0)) * DELTA_PENALTY
89}
90
91impl Scheme for DeltaScheme {
92    fn scheme_name(&self) -> &'static str {
93        "vortex.int.delta"
94    }
95
96    fn matches(&self, canonical: &Canonical) -> bool {
97        canonical.dtype().is_int()
98    }
99
100    fn produced_encodings(&self) -> Vec<ArrayId> {
101        vec![Delta.id()]
102    }
103
104    fn num_children(&self) -> usize {
105        2
106    }
107
108    /// Delta-encode the data at most once per path: exclude Delta from the subtrees of both the
109    /// bases and the deltas children so we never delta-encode data that was already delta-encoded.
110    fn descendant_exclusions(&self) -> Vec<DescendantExclusion> {
111        vec![DescendantExclusion {
112            excluded: self.id(),
113            children: ChildSelection::All,
114        }]
115    }
116
117    /// Delta over dictionary codes just adds indirection: codes are compact integers with no
118    /// monotone structure, so (like FoR/Sequence) skip the codes child.
119    fn ancestor_exclusions(&self) -> Vec<AncestorExclusion> {
120        vec![
121            AncestorExclusion {
122                ancestor: IntDictScheme.id(),
123                children: ChildSelection::One(1),
124            },
125            AncestorExclusion {
126                ancestor: FloatDictScheme.id(),
127                children: ChildSelection::One(1),
128            },
129            AncestorExclusion {
130                ancestor: StringDictScheme.id(),
131                children: ChildSelection::One(1),
132            },
133            AncestorExclusion {
134                ancestor: BinaryDictScheme.id(),
135                children: ChildSelection::One(1),
136            },
137        ]
138    }
139
140    fn expected_compression_ratio(
141        &self,
142        data: &ArrayAndStats,
143        compress_ctx: CompressorContext,
144        _exec_ctx: &mut ExecutionCtx,
145    ) -> CompressionEstimate {
146        // Delta only pays off if a later cascade layer (FoR/BitPacking) packs the residuals.
147        if compress_ctx.finished_cascading() {
148            return CompressionEstimate::Verdict(EstimateVerdict::Skip);
149        }
150        // Too short to transpose into FastLanes chunks meaningfully.
151        if data.array_len() < MIN_DELTA_LEN {
152            return CompressionEstimate::Verdict(EstimateVerdict::Skip);
153        }
154
155        // Estimating Delta needs the real transposed-delta span, so defer to a callback that
156        // delta-encodes the array and measures the residual range.
157        let min_ratio = self.min_ratio;
158        CompressionEstimate::Deferred(DeferredEstimate::Callback(Box::new(
159            move |_compressor, data, best_so_far, _ctx, exec_ctx| {
160                let primitive = data.array().clone().execute::<PrimitiveArray>(exec_ctx)?;
161                let full_width = primitive.ptype().bit_width() as f64;
162                let len = primitive.len();
163
164                // Delta's best case is residuals collapsing to a single bit. If even that, after
165                // the penalty, can't beat the incumbent, skip before doing the encode work.
166                let threshold = best_so_far.and_then(EstimateScore::finite_ratio);
167                if threshold.is_some_and(|t| penalized_ratio(len, full_width, 1.0) <= t) {
168                    return Ok(EstimateVerdict::Skip);
169                }
170
171                // Measure the actual FastLanes transposed-delta span. This is the lane-stride
172                // difference that gets bit-packed, not the lag-1 difference (which the transpose
173                // makes optimistic), so it is what truly drives the compressed size.
174                let (_bases, deltas) = vortex_fastlanes::delta_compress(&primitive, exec_ctx)?;
175                let delta_stats =
176                    ArrayAndStats::new(deltas.into_array(), GenerateStatsOptions::default());
177                let span = delta_stats.integer_stats(exec_ctx).erased().max_minus_min();
178
179                // Bits needed to FoR-pack the residuals. A zero span means constant deltas, which
180                // SequenceScheme already captures more cheaply, so defer to it.
181                let delta_bits = match span.checked_ilog2() {
182                    Some(l) => (l + 1) as f64,
183                    None => return Ok(EstimateVerdict::Skip),
184                };
185
186                let ratio = penalized_ratio(len, full_width, delta_bits);
187                if ratio <= min_ratio {
188                    return Ok(EstimateVerdict::Skip);
189                }
190                Ok(EstimateVerdict::Ratio(ratio))
191            },
192        )))
193    }
194
195    fn compress(
196        &self,
197        compressor: &CascadingCompressor,
198        data: &ArrayAndStats,
199        compress_ctx: CompressorContext,
200        exec_ctx: &mut ExecutionCtx,
201    ) -> VortexResult<ArrayRef> {
202        let primitive = data.array().clone().execute::<PrimitiveArray>(exec_ctx)?;
203        let len = primitive.len();
204        let (bases, deltas) = vortex_fastlanes::delta_compress(&primitive, exec_ctx)?;
205
206        let compressed_bases = compressor.compress_child(
207            &bases.into_array(),
208            &compress_ctx,
209            self.id(),
210            0,
211            exec_ctx,
212        )?;
213        let compressed_deltas = compressor.compress_child(
214            &deltas.into_array(),
215            &compress_ctx,
216            self.id(),
217            1,
218            exec_ctx,
219        )?;
220
221        Delta::try_new(
222            compressed_bases,
223            compressed_deltas,
224            primitive.validity()?,
225            0,
226            len,
227        )
228        .map(IntoArray::into_array)
229    }
230}
vortex_btrblocks/schemes/integer/delta.rs

vortex_btrblocks/schemes/integer/
delta.rs
