Skip to content

Commit df98590

Browse files
authored
Blocked BitPacked: Add Compressor support via BitPackingScheme mode (#10245)
Tracking Issue: #10167 ## Summary Support blocked `BitPacked` encoding in the compressor by adding a new `V2` mode to `BitPackingScheme`. Like `FoRScheme V2` and `DecimalScheme V2`, the new versions use the current `V1` by default and are only "refined" to `V2` when the corresponding edition is enabled. The new scheme mode is quite naive for now. Compression estimate for V2 is the same as for V1. In general, blocked BP will compress an array **at least as much** as regular BP, so this estimate is a decent approximate lower bound on compression ratio. ## CUDA The CUDA preset excludes `fastlanes.bitpacked.v2`, as it does `fastlanes.for.v2`. CUDA decoding returns an error for per-block bit widths. --------- Signed-off-by: Matt Katz <[email protected]>
1 parent df8c104 commit df98590

11 files changed

Lines changed: 412 additions & 61 deletions

File tree

‎encodings/fastlanes/src/bitpacking/array/bitpack_compress/blocked.rs‎

Lines changed: 20 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -50,12 +50,28 @@ pub fn bitpack_blocked_to_best_bit_widths(
5050
array: &PrimitiveArray,
5151
ctx: &mut ExecutionCtx,
5252
) -> VortexResult<BitPackedArray> {
53+
let (bit_widths, num_exceptions) = find_best_bit_widths(array, ctx)?;
54+
bitpack_encode_blocked(array, &bit_widths, Some(num_exceptions), ctx)
55+
}
56+
57+
/// Choose the width minimizing each 1024-value block's packed size plus the cost of its
58+
/// exceptions, and return the widths and total number of exceptions.
59+
///
60+
/// Widths may equal the array's native bit width when packing would not help. An empty array
61+
/// produces no widths and no exceptions.
62+
///
63+
/// # Errors
64+
///
65+
/// Returns an error if `array` is not an integer array or contains negative values.
66+
pub fn find_best_bit_widths(
67+
array: &PrimitiveArray,
68+
ctx: &mut ExecutionCtx,
69+
) -> VortexResult<(Vec<u8>, usize)> {
5370
ensure_non_negative_integers(array, ctx)?;
5471
let validity_mask = array.validity()?.execute_mask(array.len(), ctx)?;
55-
let (bit_widths, num_exceptions) = match_each_integer_ptype!(array.ptype(), |T| {
56-
block_bit_widths(array.as_slice::<T>(), &validity_mask)?
57-
});
58-
bitpack_encode_blocked(array, &bit_widths, Some(num_exceptions), ctx)
72+
match_each_integer_ptype!(array.ptype(), |T| {
73+
block_bit_widths(array.as_slice::<T>(), &validity_mask)
74+
})
5975
}
6076

6177
/// Bit-pack each 1024-value block of `array` at its width in `bit_widths`.

‎encodings/fastlanes/src/bitpacking/array/bitpack_compress/mod.rs‎

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

77
pub use blocked::bitpack_blocked_to_best_bit_widths;
88
pub use blocked::bitpack_encode_blocked;
9+
pub use blocked::find_best_bit_widths;
910
pub use global::bit_width_histogram;
1011
pub use global::bitpack_encode;
1112
pub use global::bitpack_encode_unchecked;

‎vortex-btrblocks/src/builder.rs‎

Lines changed: 22 additions & 3 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::bitpacked_v2_id;
89
use vortex_fastlanes::for_v2_id;
910
use vortex_session::VortexSession;
1011
use vortex_utils::aliases::hash_set::HashSet;
@@ -94,9 +95,9 @@ impl CompressionMode {
9495
fn excluded_encodings(self) -> Vec<ArrayId> {
9596
match self {
9697
Self::All | Self::Default | Self::Compact => Vec::new(),
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()],
98+
// Multi-part DecimalByteParts arrays, FoR arrays with per-chunk references and
99+
// BitPacked arrays with per-block bit widths have no CUDA decode kernel.
100+
Self::Cuda => vec![decimal_byte_parts_v2_id(), for_v2_id(), bitpacked_v2_id()],
100101
}
101102
}
102103
}
@@ -249,9 +250,12 @@ mod tests {
249250
use rstest::rstest;
250251
use vortex_array::ArrayId;
251252
use vortex_array::VTable;
253+
use vortex_array::arrays::Patched;
252254
use vortex_array::arrays::VarBin;
253255
use vortex_decimal_byte_parts::DecimalByteParts;
254256
use vortex_decimal_byte_parts::decimal_byte_parts_v1_id;
257+
use vortex_fastlanes::bitpacked_v1_id;
258+
use vortex_fastlanes::bitpacked_v2_id;
255259
use vortex_fsst::FSST;
256260

257261
use super::*;
@@ -264,6 +268,21 @@ mod tests {
264268
#[case::fsst_with_codes(&string::FSSTScheme, vec![FSST.id(), VarBin.id()], true)]
265269
#[case::decimal_v1_id(&DECIMAL_V1, vec![decimal_byte_parts_v1_id()], true)]
266270
#[case::decimal_both_ids(&DECIMAL_V2, vec![decimal_byte_parts_v1_id(), DecimalByteParts.id()], true)]
271+
#[case::bitpacking_v1_id(
272+
&integer::BITPACKING_V1,
273+
vec![bitpacked_v1_id(), Patched.id()],
274+
true
275+
)]
276+
#[case::bitpacking_both_ids(
277+
&integer::BITPACKING_V1,
278+
vec![bitpacked_v1_id(), bitpacked_v2_id(), Patched.id()],
279+
true
280+
)]
281+
#[case::bitpacking_v2_only(
282+
&integer::BITPACKING_V1,
283+
vec![bitpacked_v2_id(), Patched.id()],
284+
false
285+
)]
267286
fn test_allowed_schemes(
268287
#[case] scheme: &'static dyn Scheme,
269288
#[case] allowed: Vec<ArrayId>,

0 commit comments

Comments
 (0)