vortex_fastlanes/delta/array/
mod.rs

1// SPDX-License-Identifier: Apache-2.0
2// SPDX-FileCopyrightText: Copyright the Vortex contributors
3
4use std::fmt::Display;
5use std::fmt::Formatter;
6
7use fastlanes::FastLanes;
8use vortex_array::ArrayRef;
9use vortex_array::TypedArrayRef;
10use vortex_array::array_slots;
11use vortex_array::dtype::PType;
12use vortex_array::match_each_unsigned_integer_ptype;
13use vortex_error::VortexResult;
14use vortex_error::vortex_ensure;
15
16pub mod delta_compress;
17pub mod delta_decompress;
18
19#[array_slots(crate::Delta)]
20pub struct DeltaSlots {
21    /// The base values for each block of deltas.
22    pub bases: ArrayRef,
23    /// The delta-encoded values relative to the base values.
24    pub deltas: ArrayRef,
25}
26
27/// A FastLanes-style delta-encoded array of primitive values.
28///
29/// A DeltaArray comprises a sequence of _chunks_ each representing exactly 1,024
30/// delta-encoded values. If the input array length is not a multiple of 1,024, the last chunk
31/// is padded with zeros to fill a complete 1,024-element chunk.
32///
33/// # Examples
34///
35/// ```
36/// use vortex_array::arrays::PrimitiveArray;
37/// use vortex_array::VortexSessionExecute;
38/// use vortex_array::session::ArraySession;
39/// use vortex_session::VortexSession;
40/// use vortex_fastlanes::Delta;
41///
42/// let session = vortex_array::array_session();
43/// let primitive = PrimitiveArray::from_iter([1_u32, 2, 3, 5, 10, 11]);
44/// let array = Delta::try_from_primitive_array(&primitive, &mut session.create_execution_ctx()).unwrap();
45/// ```
46///
47/// Signed inputs are also supported; deltas across negative values are encoded by
48/// `wrapping_sub` and recovered by `wrapping_add` at decompress time:
49///
50/// ```
51/// use vortex_array::arrays::PrimitiveArray;
52/// use vortex_array::VortexSessionExecute;
53/// use vortex_array::session::ArraySession;
54/// use vortex_session::VortexSession;
55/// use vortex_fastlanes::Delta;
56///
57/// let session = vortex_array::array_session();
58/// let primitive = PrimitiveArray::from_iter([-3_i32, -2, -1, 0, 1, 2]);
59/// let array = Delta::try_from_primitive_array(&primitive, &mut session.create_execution_ctx()).unwrap();
60/// ```
61///
62/// # Details
63///
64/// To facilitate slicing, this array accepts an `offset` and `logical_len`. The offset must be
65/// strictly less than 1,024 and the sum of `offset` and `logical_len` must not exceed the length of
66/// the `deltas` array. These values permit logical slicing without modifying any chunk containing a
67/// kept value. In particular, we may defer decompresison until the array is canonicalized or
68/// indexed. The `offset` is a physical offset into the first chunk, which necessarily contains
69/// 1,024 values. The `logical_len` is the number of logical values following the `offset`, which
70/// may be less than the number of physically stored values.
71///
72/// Each chunk is stored as a vector of bases and a vector of deltas. There are as many bases as
73/// there are _lanes_ of this type in a 1024-bit register. For example, for 64-bit values, there
74/// are 16 bases because there are 16 _lanes_. Each lane is a
75/// [delta-encoding](https://en.wikipedia.org/wiki/Delta_encoding) `1024 / bit_width` long vector
76/// of values. The deltas are stored in the
77/// [FastLanes](https://www.vldb.org/pvldb/vol16/p2132-afroozeh.pdf) order which splits the 1,024
78/// values into one contiguous sub-sequence per-lane, thus permitting delta encoding.
79///
80/// Note the validity is stored in the deltas array.
81#[derive(Clone, Debug)]
82pub struct DeltaData {
83    pub(super) offset: usize,
84}
85
86impl Display for DeltaData {
87    fn fmt(&self, f: &mut Formatter<'_>) -> std::fmt::Result {
88        write!(f, "offset: {}", self.offset)
89    }
90}
91
92pub trait DeltaArrayExt: DeltaArraySlotsExt {
93    fn offset(&self) -> usize {
94        self.offset
95    }
96}
97
98impl<T: TypedArrayRef<crate::Delta>> DeltaArrayExt for T {}
99
100impl DeltaData {
101    pub fn try_new(offset: usize) -> VortexResult<Self> {
102        vortex_ensure!(offset < 1024, "offset must be less than 1024: {offset}");
103        Ok(Self { offset })
104    }
105}
106
107pub(crate) fn lane_count(ptype: PType) -> usize {
108    match_each_unsigned_integer_ptype!(ptype.to_unsigned(), |T| { T::LANES })
109}
vortex_fastlanes/delta/array/mod.rs

vortex_fastlanes/delta/array/
mod.rs
