@@ -9,22 +9,17 @@ use vortex_array::Canonical;
99use vortex_array:: ExecutionCtx ;
1010use vortex_array:: IntoArray ;
1111use vortex_array:: arrays:: PrimitiveArray ;
12- use vortex_array:: arrays:: primitive:: PrimitiveArrayExt ;
13- use vortex_array:: match_each_unsigned_integer_ptype;
1412use vortex_compressor:: builtins:: BinaryDictScheme ;
1513use vortex_compressor:: builtins:: FloatDictScheme ;
1614use vortex_compressor:: builtins:: IntDictScheme ;
1715use vortex_compressor:: builtins:: StringDictScheme ;
1816use vortex_compressor:: scheme:: AncestorExclusion ;
1917use vortex_compressor:: scheme:: ChildSelection ;
2018use vortex_compressor:: scheme:: CompressionEstimate ;
21- use vortex_compressor:: scheme:: DeferredEstimate ;
22- use vortex_compressor:: scheme:: EstimateScore ;
2319use vortex_compressor:: scheme:: EstimateVerdict ;
2420use vortex_error:: VortexExpect ;
2521use vortex_error:: VortexResult ;
2622use vortex_fastlanes:: FoR ;
27- use vortex_fastlanes:: FoRArray ;
2823use vortex_fastlanes:: FoRArrayExt ;
2924use vortex_fastlanes:: FoRArraySlotsExt ;
3025use 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) ]
333245mod tests {
334246 use rstest:: rstest;
0 commit comments