Skip to content

Commit 0751940

Browse files
authored
Refine FoRScheme to per-chunk references when fastlanes.for.v2 is allowed (#10136)
Stacked on #10135. ## Summary `FoRScheme` compresses with one reference per 1024-element chunk when the compressor's allowed serialized IDs include `fastlanes.for.v2`, following `DecimalScheme`. Default writes are unchanged: the core edition allows only `fastlanes.for`, so `refine` keeps v1. ## `FoRScheme` - `FoRScheme` gains v1 and v2 modes with `v1()` and `v2()` constructors; `Default` is v1. The session registers `FOR_V1`. - `refine` returns v2 when `fastlanes.for.v2` is allowed, and v1 otherwise. - `produced_encodings`: v1 declares `fastlanes.for`; v2 declares `fastlanes.for` and `fastlanes.for.v2`. - **Compress**: v2 always encodes with `FoR::encode_chunked`. Per-chunk references never pack wider than one reference, and the chunked encoder is faster than the single-reference one. The encoded child is bit-packed as before, and the references are compressed as child 0 with `compress_child`. When every chunk has the same minimum, the references compress to a constant and the array serializes as `fastlanes.for`. - **Estimate**: both modes use v1's estimate, unchanged. That is conservative for v2: it can understate v2's ratio, and it skips arrays where only per-chunk references would help, such as those whose minimum is zero or whose single-reference width is no narrower than plain BitPacking. ## CUDA The CUDA preset excludes `fastlanes.for.v2`, as it does multi-part decimals. The GPU FoR decoder returns an error for per-chunk references. ## Follow-ups - **Estimate per-chunk references.** The existing samples can't estimate them: the sampler stitches 64-value runs from across the array, so no sampled chunk resembles a real one. Options are chunk-aligned sampling, or a read-only pass computing each chunk's min and max, which is much cheaper than `encode_chunked` because it writes nothing. The ratio should then count the references child. Done when `estimate_skips_arrays_only_chunk_references_narrow` expects v2, the golden snapshots don't regress, and the change in compression time is measured. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent 4224390 commit 0751940

6 files changed

Lines changed: 297 additions & 12 deletions

File tree

‎vortex-btrblocks/src/builder.rs‎

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -5,6 +5,7 @@
55
66
use vortex_array::ArrayId;
77
use vortex_decimal_byte_parts::decimal_byte_parts_v2_id;
8+
use vortex_fastlanes::for_v2_id;
89
use vortex_session::VortexSession;
910
use vortex_utils::aliases::hash_set::HashSet;
1011

@@ -93,8 +94,9 @@ impl CompressionMode {
9394
fn excluded_encodings(self) -> Vec<ArrayId> {
9495
match self {
9596
Self::All | Self::Default | Self::Compact => Vec::new(),
96-
// Multi-part DecimalByteParts arrays have no CUDA decode kernel.
97-
Self::Cuda => vec![decimal_byte_parts_v2_id()],
97+
// Multi-part DecimalByteParts arrays and FoR arrays with per-chunk references have no
98+
// CUDA decode kernel.
99+
Self::Cuda => vec![decimal_byte_parts_v2_id(), for_v2_id()],
98100
}
99101
}
100102
}

‎vortex-btrblocks/src/schemes/integer/for_.rs‎

Lines changed: 122 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -23,6 +23,7 @@ use vortex_fastlanes::FoR;
2323
use vortex_fastlanes::FoRArrayExt;
2424
use vortex_fastlanes::FoRArraySlotsExt;
2525
use vortex_fastlanes::for_v1_id;
26+
use vortex_fastlanes::for_v2_id;
2627

2728
use super::BitPackingScheme;
2829
use crate::ArrayAndStats;
@@ -31,9 +32,53 @@ use crate::CompressorContext;
3132
use crate::Scheme;
3233
use crate::SchemeExt;
3334

35+
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
36+
enum FoRSchemeMode {
37+
V1,
38+
V2,
39+
}
40+
41+
/// The FoR scheme that only produces single-reference arrays.
42+
pub(crate) static FOR_V1: FoRScheme = FoRScheme::v1();
43+
44+
/// The FoR scheme that may produce one reference per 1024-element chunk.
45+
pub(crate) static FOR_V2: FoRScheme = FoRScheme::v2();
46+
3447
/// Frame of Reference encoding.
48+
///
49+
/// The v1 mode subtracts one reference, the array's minimum. The v2 mode subtracts one reference
50+
/// per 1024-element chunk, the chunk's minimum. Arrays with a single reference, including v2
51+
/// arrays whose references compress to a constant, serialize as `fastlanes.for`, while per-chunk
52+
/// references serialize as `fastlanes.for.v2`.
53+
///
54+
/// The default uses v1. [`refine`](Scheme::refine) picks v2 when the v2 ID is allowed and v1
55+
/// otherwise.
3556
#[derive(Debug, Copy, Clone, PartialEq, Eq)]
36-
pub struct FoRScheme;
57+
pub struct FoRScheme {
58+
mode: FoRSchemeMode,
59+
}
60+
61+
impl FoRScheme {
62+
/// Creates a FoR scheme configured for v1, which uses a single reference.
63+
pub const fn v1() -> Self {
64+
Self {
65+
mode: FoRSchemeMode::V1,
66+
}
67+
}
68+
69+
/// Creates a FoR scheme configured for v2, which may use one reference per chunk.
70+
pub const fn v2() -> Self {
71+
Self {
72+
mode: FoRSchemeMode::V2,
73+
}
74+
}
75+
}
76+
77+
impl Default for FoRScheme {
78+
fn default() -> Self {
79+
Self::v1()
80+
}
81+
}
3782

3883
impl Scheme for FoRScheme {
3984
fn scheme_name(&self) -> &'static str {
@@ -45,8 +90,26 @@ impl Scheme for FoRScheme {
4590
}
4691

4792
fn produced_encodings(&self) -> Vec<ArrayId> {
48-
// Single-reference arrays serialize under the frozen v1 ID.
49-
vec![for_v1_id()]
93+
match self.mode {
94+
FoRSchemeMode::V1 => vec![for_v1_id()],
95+
FoRSchemeMode::V2 => vec![for_v1_id(), for_v2_id()],
96+
}
97+
}
98+
99+
fn refine(&self, allowed: &dyn Fn(&ArrayId) -> bool) -> &dyn Scheme {
100+
if allowed(&for_v2_id()) {
101+
&FOR_V2
102+
} else {
103+
&FOR_V1
104+
}
105+
}
106+
107+
/// Children: references=0 in v2 mode. The encoded child is always bit-packed.
108+
fn num_children(&self) -> usize {
109+
match self.mode {
110+
FoRSchemeMode::V1 => 0,
111+
FoRSchemeMode::V2 => 1,
112+
}
50113
}
51114

52115
/// Dict codes always start at 0, so FoR (which subtracts the min) is a no-op.
@@ -82,6 +145,12 @@ impl Scheme for FoRScheme {
82145
if compress_ctx.finished_cascading() {
83146
return CompressionEstimate::Verdict(EstimateVerdict::Skip);
84147
}
148+
149+
// Both modes estimate single-reference FoR. This is conservative for v2: per-chunk
150+
// references never pack wider than one reference, since each chunk's range lies within the
151+
// array's, so the ratio can understate v2. It also skips arrays where only per-chunk
152+
// references would help, such as those whose minimum is zero, or whose single-reference
153+
// width is no narrower than plain BitPacking.
85154
let stats = data.integer_stats(exec_ctx);
86155

87156
// Only apply when the min is not already zero.
@@ -131,7 +200,10 @@ impl Scheme for FoRScheme {
131200
exec_ctx: &mut ExecutionCtx,
132201
) -> VortexResult<ArrayRef> {
133202
let primitive = data.array().clone().execute::<PrimitiveArray>(exec_ctx)?;
134-
let for_array = FoR::encode(primitive, exec_ctx)?;
203+
let for_array = match self.mode {
204+
FoRSchemeMode::V1 => FoR::encode(primitive, exec_ctx)?,
205+
FoRSchemeMode::V2 => FoR::encode_chunked(primitive, exec_ctx)?,
206+
};
135207
let biased = for_array
136208
.encoded()
137209
.clone()
@@ -147,10 +219,19 @@ impl Scheme for FoRScheme {
147219
let compressed = BitPackingScheme.compress(compressor, &biased_data, leaf_ctx, exec_ctx)?;
148220

149221
// TODO(connor): This should really be `new_unchecked`.
150-
let reference = for_array
151-
.constant_reference()
152-
.vortex_expect("FoR::encode uses a single reference");
153-
let for_compressed = FoR::try_new(compressed, reference)?;
222+
let for_compressed = match for_array.constant_reference() {
223+
Some(reference) => FoR::try_new(compressed, reference)?,
224+
None => {
225+
let references = compressor.compress_child(
226+
for_array.references(),
227+
&compress_ctx,
228+
self.id(),
229+
0,
230+
exec_ctx,
231+
)?;
232+
FoR::try_new_chunked(compressed, references, for_array.offset())?
233+
}
234+
};
154235
for_compressed
155236
.as_ref()
156237
.statistics()
@@ -159,3 +240,36 @@ impl Scheme for FoRScheme {
159240
Ok(for_compressed.into_array())
160241
}
161242
}
243+
244+
#[cfg(test)]
245+
mod tests {
246+
use rstest::rstest;
247+
use vortex_array::ArrayId;
248+
use vortex_fastlanes::for_v1_id;
249+
use vortex_fastlanes::for_v2_id;
250+
251+
use super::FOR_V1;
252+
use super::FOR_V2;
253+
use crate::Scheme;
254+
use crate::SchemeExt;
255+
256+
/// Both variants refine to v2 exactly when the v2 ID is allowed.
257+
#[rstest]
258+
#[case::neither(false, false, false)]
259+
#[case::v1(true, false, false)]
260+
#[case::v2_only(false, true, true)]
261+
#[case::both(true, true, true)]
262+
fn refine_picks_v2_when_v2_id_is_allowed(
263+
#[case] allow_v1: bool,
264+
#[case] allow_v2: bool,
265+
#[case] expect_v2: bool,
266+
#[values(&FOR_V1, &FOR_V2)] scheme: &'static dyn Scheme,
267+
) {
268+
let allowed =
269+
|id: &ArrayId| (allow_v1 && *id == for_v1_id()) || (allow_v2 && *id == for_v2_id());
270+
let refined = scheme.refine(&allowed);
271+
assert_eq!(refined.id(), scheme.id());
272+
let expected: &dyn Scheme = if expect_v2 { &FOR_V2 } else { &FOR_V1 };
273+
assert_eq!(refined.produced_encodings(), expected.produced_encodings());
274+
}
275+
}

‎vortex-btrblocks/src/schemes/integer/mod.rs‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -17,6 +17,7 @@ mod pco;
1717

1818
pub use bitpacking::BitPackingScheme;
1919
pub use delta::DeltaScheme;
20+
pub(crate) use for_::FOR_V1;
2021
pub use for_::FoRScheme;
2122
#[cfg(feature = "pco")]
2223
pub use pco::PcoScheme;

‎vortex-btrblocks/src/session.rs‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -45,7 +45,7 @@ impl Default for CompressionSession {
4545
// Integer schemes.
4646
////////////////////////////////////////////////////////////////////////////////////
4747
// NOTE: FoR must precede BitPacking to avoid unnecessary patches.
48-
&integer::FoRScheme,
48+
&integer::FOR_V1,
4949
// NOTE: ZigZag should precede BitPacking because we don't want negative numbers.
5050
&integer::ZigZagScheme,
5151
&integer::BitPackingScheme,

‎vortex-btrblocks/tests/decimal_config.rs‎

Lines changed: 2 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,7 @@ use vortex_session::VortexSession;
4444
use vortex_session::registry::ReadContext;
4545

4646
static DECIMAL_V2: DecimalScheme = DecimalScheme::v2();
47+
static FOR_V1: FoRScheme = FoRScheme::v1();
4748

4849
/// Registers the decimal and fastlanes encodings, and enables no editions.
4950
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
@@ -197,7 +198,7 @@ fn wide_decimal_parts_roundtrip(
197198
let mut builder = BtrBlocksCompressorBuilder::empty().with_new_scheme(&DECIMAL_V2);
198199
if compress_children {
199200
builder = builder
200-
.with_new_scheme(&FoRScheme)
201+
.with_new_scheme(&FOR_V1)
201202
.with_new_scheme(&BitPackingScheme);
202203
}
203204
let mut ctx = SESSION.create_execution_ctx();
Lines changed: 167 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,167 @@
1+
// SPDX-License-Identifier: Apache-2.0
2+
// SPDX-FileCopyrightText: Copyright the Vortex contributors
3+
4+
//! FoR scheme refinement by allowed serialized IDs, and per-chunk references.
5+
6+
#![cfg(test)]
7+
8+
use std::sync::LazyLock;
9+
10+
use rstest::rstest;
11+
use vortex_array::ArrayContext;
12+
use vortex_array::ArrayId;
13+
use vortex_array::ArrayRef;
14+
use vortex_array::IntoArray;
15+
use vortex_array::VortexSessionExecute;
16+
use vortex_array::arrays::PrimitiveArray;
17+
use vortex_array::assert_arrays_eq;
18+
use vortex_array::serde::SerializeOptions;
19+
use vortex_array::serde::SerializedArray;
20+
use vortex_btrblocks::BtrBlocksCompressorBuilder;
21+
use vortex_btrblocks::schemes::integer::BitPackingScheme;
22+
use vortex_btrblocks::schemes::integer::FoRScheme;
23+
use vortex_buffer::ByteBufferMut;
24+
use vortex_edition::EDITION_DECLARATIONS;
25+
use vortex_edition::EDITION_FAMILIES;
26+
use vortex_edition::EditionSession;
27+
use vortex_edition::EditionSessionExt;
28+
use vortex_edition::declarations::core::CORE_2026_08_3;
29+
use vortex_error::VortexResult;
30+
use vortex_fastlanes::for_v1_id;
31+
use vortex_fastlanes::for_v2_id;
32+
use vortex_session::VortexSession;
33+
use vortex_session::registry::ReadContext;
34+
35+
static FOR_V1: FoRScheme = FoRScheme::v1();
36+
static BITPACKING: BitPackingScheme = BitPackingScheme;
37+
38+
/// Registers the fastlanes encodings, and enables no editions.
39+
static SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
40+
let session = vortex_array::array_session();
41+
vortex_fastlanes::initialize(&session);
42+
session
43+
});
44+
45+
/// Like [`SESSION`], with the latest core edition enabled: it allows `fastlanes.for` but not
46+
/// `fastlanes.for.v2`.
47+
static CORE_SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
48+
let session = vortex_array::array_session().with::<EditionSession>();
49+
for family in EDITION_FAMILIES {
50+
session
51+
.editions()
52+
.declare_family(family)
53+
.expect("first-party edition family");
54+
}
55+
for declaration in EDITION_DECLARATIONS {
56+
session
57+
.register_edition(declaration)
58+
.expect("first-party edition");
59+
}
60+
session
61+
.enable_edition(CORE_2026_08_3)
62+
.expect("core edition is registered");
63+
vortex_fastlanes::initialize(&session);
64+
session
65+
});
66+
67+
/// Values from a billion that step up by a million every chunk. One reference needs 23 bits and
68+
/// plain BitPacking 30, so FoR is estimated to pay off, and per-chunk references then pack to 7.
69+
fn drifting() -> ArrayRef {
70+
PrimitiveArray::from_iter(
71+
(0..8192u32).map(|i| 1_000_000_000 + (i / 1024) * 1_000_000 + i % 100),
72+
)
73+
.into_array()
74+
}
75+
76+
/// Values clustered around one base: every chunk has the same minimum, so the references compress
77+
/// to a constant and the array serializes as `fastlanes.for`.
78+
fn clustered() -> ArrayRef {
79+
PrimitiveArray::from_iter((0..8192u32).map(|i| 1_000_000 + i % 100)).into_array()
80+
}
81+
82+
/// Compresses `array`, round trips it through serialization, and returns the serialized IDs.
83+
fn compress_roundtrip(
84+
builder: BtrBlocksCompressorBuilder,
85+
array: &ArrayRef,
86+
) -> VortexResult<Vec<ArrayId>> {
87+
let mut ctx = SESSION.create_execution_ctx();
88+
let compressed = builder.build().compress(array, &mut ctx)?;
89+
assert_arrays_eq!(array, compressed, &mut ctx);
90+
91+
let array_ctx = ArrayContext::empty();
92+
let mut bytes = ByteBufferMut::empty();
93+
for buffer in compressed.serialize(&array_ctx, &SESSION, &SerializeOptions::default())? {
94+
bytes.extend_from_slice(&buffer);
95+
}
96+
let read = SerializedArray::try_from(bytes.freeze())?.decode(
97+
array.dtype(),
98+
array.len(),
99+
&ReadContext::new(array_ctx.to_ids()),
100+
&SESSION,
101+
)?;
102+
assert_arrays_eq!(array, read, &mut ctx);
103+
Ok(array_ctx.to_ids())
104+
}
105+
106+
/// Only FoR and BitPacking, with every serialized ID allowed, so FoR refines to v2.
107+
fn for_only() -> BtrBlocksCompressorBuilder {
108+
BtrBlocksCompressorBuilder::empty()
109+
.with_new_scheme(&FOR_V1)
110+
.with_new_scheme(&BITPACKING)
111+
}
112+
113+
#[rstest]
114+
#[case::drifting(drifting(), true)]
115+
#[case::clustered(clustered(), false)]
116+
fn v2_serializes_varying_references_as_v2(
117+
#[case] array: ArrayRef,
118+
#[case] expect_v2: bool,
119+
) -> VortexResult<()> {
120+
let ids = compress_roundtrip(for_only(), &array)?;
121+
assert!(ids.contains(&for_v1_id()) != expect_v2);
122+
assert_eq!(ids.contains(&for_v2_id()), expect_v2);
123+
Ok(())
124+
}
125+
126+
/// FoR is estimated as single-reference FoR, which is conservative for v2. Here one reference needs
127+
/// 23 bits, as many as plain BitPacking, so FoR is skipped even though per-chunk references would
128+
/// pack to 7.
129+
#[test]
130+
fn estimate_skips_arrays_only_chunk_references_narrow() -> VortexResult<()> {
131+
let array = PrimitiveArray::from_iter(
132+
(0..8192u32).map(|i| 1_000_000 + (i / 1024) * 1_000_000 + i % 100),
133+
)
134+
.into_array();
135+
let ids = compress_roundtrip(for_only(), &array)?;
136+
assert!(!ids.contains(&for_v1_id()));
137+
assert!(!ids.contains(&for_v2_id()));
138+
Ok(())
139+
}
140+
141+
#[test]
142+
fn core_edition_keeps_single_reference() -> VortexResult<()> {
143+
let ids = compress_roundtrip(
144+
BtrBlocksCompressorBuilder::from_session(&CORE_SESSION),
145+
&drifting(),
146+
)?;
147+
assert!(!ids.contains(&for_v2_id()));
148+
Ok(())
149+
}
150+
151+
#[test]
152+
fn nullable_drifting_roundtrip() -> VortexResult<()> {
153+
let array = PrimitiveArray::from_option_iter(
154+
(0..8192i64).map(|i| (i % 7 != 0).then_some(-5_000_000 + (i / 1024) * 1_000_000 + i % 50)),
155+
)
156+
.into_array();
157+
let ids = compress_roundtrip(for_only(), &array)?;
158+
assert!(ids.contains(&for_v2_id()));
159+
Ok(())
160+
}
161+
162+
#[test]
163+
fn cuda_preset_keeps_single_reference() -> VortexResult<()> {
164+
let ids = compress_roundtrip(for_only().only_cuda_compatible(), &drifting())?;
165+
assert!(!ids.contains(&for_v2_id()));
166+
Ok(())
167+
}

0 commit comments

Comments
 (0)