Skip to content

Commit c7a39c7

Browse files
committed
always encode chunked in for v2 and use the v1 estimate
Signed-off-by: Matt Katz <[email protected]>
1 parent 780db75 commit c7a39c7

2 files changed

Lines changed: 34 additions & 104 deletions

File tree

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

Lines changed: 10 additions & 98 deletions
Original file line numberDiff line numberDiff line change
@@ -9,22 +9,17 @@ use vortex_array::Canonical;
99
use vortex_array::ExecutionCtx;
1010
use vortex_array::IntoArray;
1111
use vortex_array::arrays::PrimitiveArray;
12-
use vortex_array::arrays::primitive::PrimitiveArrayExt;
13-
use vortex_array::match_each_unsigned_integer_ptype;
1412
use vortex_compressor::builtins::BinaryDictScheme;
1513
use vortex_compressor::builtins::FloatDictScheme;
1614
use vortex_compressor::builtins::IntDictScheme;
1715
use vortex_compressor::builtins::StringDictScheme;
1816
use vortex_compressor::scheme::AncestorExclusion;
1917
use vortex_compressor::scheme::ChildSelection;
2018
use vortex_compressor::scheme::CompressionEstimate;
21-
use vortex_compressor::scheme::DeferredEstimate;
22-
use vortex_compressor::scheme::EstimateScore;
2319
use vortex_compressor::scheme::EstimateVerdict;
2420
use vortex_error::VortexExpect;
2521
use vortex_error::VortexResult;
2622
use vortex_fastlanes::FoR;
27-
use vortex_fastlanes::FoRArray;
2823
use vortex_fastlanes::FoRArrayExt;
2924
use vortex_fastlanes::FoRArraySlotsExt;
3025
use vortex_fastlanes::for_v1_id;
@@ -52,10 +47,9 @@ pub(crate) static FOR_V2: FoRScheme = FoRScheme::v2();
5247
/// Frame of Reference encoding.
5348
///
5449
/// The v1 mode subtracts one reference, the array's minimum. The v2 mode subtracts one reference
55-
/// per 1024-element chunk when that packs to a narrower bit width than one reference, and
56-
/// otherwise produces the same single-reference arrays as v1. Single-reference arrays serialize
57-
/// as `fastlanes.for` in either mode, while per-chunk references serialize as
58-
/// `fastlanes.for.v2`.
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`.
5953
///
6054
/// The default uses v1. [`refine`](Scheme::refine) picks v2 when the v2 ID is allowed and v1
6155
/// otherwise.
@@ -151,11 +145,12 @@ impl Scheme for FoRScheme {
151145
if compress_ctx.finished_cascading() {
152146
return CompressionEstimate::Verdict(EstimateVerdict::Skip);
153147
}
154-
if self.mode == FoRSchemeMode::V2 {
155-
return CompressionEstimate::Deferred(DeferredEstimate::Callback(Box::new(
156-
estimate_v2,
157-
)));
158-
}
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.
159154
let stats = data.integer_stats(exec_ctx);
160155

161156
// Only apply when the min is not already zero.
@@ -207,17 +202,7 @@ impl Scheme for FoRScheme {
207202
let primitive = data.array().clone().execute::<PrimitiveArray>(exec_ctx)?;
208203
let for_array = match self.mode {
209204
FoRSchemeMode::V1 => FoR::encode(primitive, exec_ctx)?,
210-
FoRSchemeMode::V2 => {
211-
// Per-chunk references only pay off when they pack to a narrower width.
212-
let chunked = FoR::encode_chunked(primitive.clone(), exec_ctx)?;
213-
let global = global_bit_width(data, exec_ctx);
214-
let chunked_width = encoded_bit_width(&chunked, exec_ctx)?;
215-
if global.is_some_and(|global| chunked_width < global) {
216-
chunked
217-
} else {
218-
FoR::encode(primitive, exec_ctx)?
219-
}
220-
}
205+
FoRSchemeMode::V2 => FoR::encode_chunked(primitive, exec_ctx)?,
221206
};
222207
let biased = for_array
223208
.encoded()
@@ -256,79 +241,6 @@ impl Scheme for FoRScheme {
256241
}
257242
}
258243

259-
/// Estimates v2 from the widest chunk after subtracting each chunk's minimum.
260-
///
261-
/// Sampling can't estimate this: samples stitch short runs from across the array, so no sampled
262-
/// chunk resembles a real one.
263-
fn estimate_v2(
264-
_compressor: &CascadingCompressor,
265-
data: &ArrayAndStats,
266-
best_so_far: Option<EstimateScore>,
267-
_compress_ctx: CompressorContext,
268-
exec_ctx: &mut ExecutionCtx,
269-
) -> VortexResult<EstimateVerdict> {
270-
let primitive = data.array().clone().execute::<PrimitiveArray>(exec_ctx)?;
271-
let full_width: u32 = primitive.ptype().bit_width().try_into()?;
272-
273-
// The best case packs to one bit per value.
274-
let threshold = best_so_far.and_then(EstimateScore::finite_ratio);
275-
if threshold.is_some_and(|t| f64::from(full_width) <= t) {
276-
return Ok(EstimateVerdict::Skip);
277-
}
278-
279-
// If max-min == 0, we should be compressing this as a constant array.
280-
let Some(global) = global_bit_width(data, exec_ctx) else {
281-
return Ok(EstimateVerdict::Skip);
282-
};
283-
let chunked = encoded_bit_width(&FoR::encode_chunked(primitive, exec_ctx)?, exec_ctx)?;
284-
let width = chunked.min(global);
285-
286-
// A single reference of zero is a no-op.
287-
let stats = data.integer_stats(exec_ctx);
288-
if width == global && stats.erased().min_is_zero() {
289-
return Ok(EstimateVerdict::Skip);
290-
}
291-
292-
// As in v1, skip when plain BitPacking (only non-negative values) is as narrow.
293-
if let Some(max_log) = stats
294-
.erased()
295-
.max_ilog2()
296-
.filter(|_| !stats.erased().min_is_negative())
297-
&& width > max_log
298-
{
299-
return Ok(EstimateVerdict::Skip);
300-
}
301-
302-
Ok(EstimateVerdict::Ratio(
303-
f64::from(full_width) / f64::from(width.max(1)),
304-
))
305-
}
306-
307-
/// The bit width of `max - min` over the whole array, or `None` if it is constant.
308-
fn global_bit_width(data: &ArrayAndStats, exec_ctx: &mut ExecutionCtx) -> Option<u32> {
309-
data.integer_stats(exec_ctx)
310-
.erased()
311-
.max_minus_min()
312-
.checked_ilog2()
313-
.map(|l| l + 1)
314-
}
315-
316-
/// The bit width of the widest encoded value, which is the widest chunk's range.
317-
///
318-
/// Encoded values are non-negative offsets from their chunk's reference once reinterpreted as
319-
/// unsigned, and nulls encode as zero.
320-
fn encoded_bit_width(for_array: &FoRArray, exec_ctx: &mut ExecutionCtx) -> VortexResult<u32> {
321-
let encoded = for_array
322-
.encoded()
323-
.clone()
324-
.execute::<PrimitiveArray>(exec_ctx)?;
325-
let unsigned = encoded.reinterpret_cast(encoded.ptype().to_unsigned());
326-
Ok(match_each_unsigned_integer_ptype!(unsigned.ptype(), |T| {
327-
let max = unsigned.as_slice::<T>().iter().copied().max().unwrap_or(0);
328-
T::BITS - max.leading_zeros()
329-
}))
330-
}
331-
332244
#[cfg(test)]
333245
mod tests {
334246
use rstest::rstest;

‎vortex-btrblocks/tests/for_config.rs‎

Lines changed: 24 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -64,14 +64,17 @@ static CORE_SESSION: LazyLock<VortexSession> = LazyLock::new(|| {
6464
session
6565
});
6666

67-
/// Values that step up by a million every chunk: per-chunk references pack to 7 bits instead of
68-
/// the 22 bits one reference needs.
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.
6969
fn drifting() -> ArrayRef {
70-
PrimitiveArray::from_iter((0..8192u32).map(|i| 1_000_000 + (i / 1024) * 1_000_000 + i % 100))
71-
.into_array()
70+
PrimitiveArray::from_iter(
71+
(0..8192u32).map(|i| 1_000_000_000 + (i / 1024) * 1_000_000 + i % 100),
72+
)
73+
.into_array()
7274
}
7375

74-
/// Values clustered around one base: per-chunk references pack no narrower than one reference.
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`.
7578
fn clustered() -> ArrayRef {
7679
PrimitiveArray::from_iter((0..8192u32).map(|i| 1_000_000 + i % 100)).into_array()
7780
}
@@ -110,7 +113,7 @@ fn for_only() -> BtrBlocksCompressorBuilder {
110113
#[rstest]
111114
#[case::drifting(drifting(), true)]
112115
#[case::clustered(clustered(), false)]
113-
fn v2_uses_chunk_references_when_narrower(
116+
fn v2_serializes_varying_references_as_v2(
114117
#[case] array: ArrayRef,
115118
#[case] expect_v2: bool,
116119
) -> VortexResult<()> {
@@ -120,6 +123,21 @@ fn v2_uses_chunk_references_when_narrower(
120123
Ok(())
121124
}
122125

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+
123141
#[test]
124142
fn core_edition_keeps_single_reference() -> VortexResult<()> {
125143
let ids = compress_roundtrip(

0 commit comments

Comments
 (0)