Skip to content

Commit 5d8fa18

Browse files
authored
Don't pass extension arrays through the compressor unchanged (#10424)
The compressor indicates whether the array was returned unchanged. Extension scheme canonicalises input and only keeps extension scheme compressed arrays if they actually compressed anything instead of returning input unchanged fix #10417
1 parent 8c2534e commit 5d8fa18

2 files changed

Lines changed: 139 additions & 34 deletions

File tree

‎vortex-compressor/src/compressor/cascade.rs‎

Lines changed: 58 additions & 34 deletions
Original file line numberDiff line numberDiff line change
@@ -44,6 +44,23 @@ use crate::stats::ArrayAndStats;
4444
use crate::stats::GenerateStatsOptions;
4545
use crate::trace;
4646

47+
/// The outcome of [`CascadingCompressor::choose_and_compress`].
48+
enum Selection {
49+
/// A scheme, or the compressor's own empty, null or constant handling, produced a new array.
50+
Compressed(ArrayRef),
51+
/// Nothing beat the input, which is handed back as it was.
52+
Unchanged(ArrayRef),
53+
}
54+
55+
impl Selection {
56+
/// Returns the array, compressed or not.
57+
fn into_array(self) -> ArrayRef {
58+
match self {
59+
Selection::Compressed(array) | Selection::Unchanged(array) => array,
60+
}
61+
}
62+
}
63+
4764
impl CascadingCompressor {
4865
/// Compresses an array using cascading adaptive compression.
4966
///
@@ -114,15 +131,15 @@ impl CascadingCompressor {
114131
) -> VortexResult<ArrayRef> {
115132
match array {
116133
Canonical::Null(null_array) => Ok(null_array.into_array()),
117-
Canonical::Bool(bool_array) => {
118-
self.choose_and_compress(Canonical::Bool(bool_array), compress_ctx, exec_ctx)
119-
}
120-
Canonical::Primitive(primitive) => {
121-
self.choose_and_compress(Canonical::Primitive(primitive), compress_ctx, exec_ctx)
122-
}
123-
Canonical::Decimal(decimal) => {
124-
self.choose_and_compress(Canonical::Decimal(decimal), compress_ctx, exec_ctx)
125-
}
134+
Canonical::Bool(bool_array) => self
135+
.choose_and_compress(Canonical::Bool(bool_array), compress_ctx, exec_ctx)
136+
.map(Selection::into_array),
137+
Canonical::Primitive(primitive) => self
138+
.choose_and_compress(Canonical::Primitive(primitive), compress_ctx, exec_ctx)
139+
.map(Selection::into_array),
140+
Canonical::Decimal(decimal) => self
141+
.choose_and_compress(Canonical::Decimal(decimal), compress_ctx, exec_ctx)
142+
.map(Selection::into_array),
126143
Canonical::Struct(struct_array) => {
127144
let fields = struct_array
128145
.iter_unmasked_fields()
@@ -169,26 +186,26 @@ impl CascadingCompressor {
169186
)?
170187
.into_array())
171188
}
172-
Canonical::VarBinView(varbinview) => {
173-
self.choose_and_compress(Canonical::VarBinView(varbinview), compress_ctx, exec_ctx)
174-
}
189+
Canonical::VarBinView(varbinview) => self
190+
.choose_and_compress(Canonical::VarBinView(varbinview), compress_ctx, exec_ctx)
191+
.map(Selection::into_array),
175192
Canonical::Extension(ext_array) => {
176193
// Try scheme-based compression first.
177-
let scheme_compressed = self.choose_and_compress(
194+
let selection = self.choose_and_compress(
178195
Canonical::Extension(ext_array.clone()),
179196
compress_ctx,
180197
exec_ctx,
181198
)?;
182199

183200
// A constant extension array (that might be masked) is already in its terminal
184201
// representation, and compressing the storage separately cannot do better.
185-
if scheme_compressed.is::<Constant>() {
186-
return Ok(scheme_compressed);
187-
}
188-
if let Some(masked) = scheme_compressed.as_opt::<Masked>()
189-
&& masked.child().is::<Constant>()
202+
if let Selection::Compressed(compressed) = &selection
203+
&& (compressed.is::<Constant>()
204+
|| compressed
205+
.as_opt::<Masked>()
206+
.is_some_and(|masked| masked.child().is::<Constant>()))
190207
{
191-
return Ok(scheme_compressed);
208+
return Ok(selection.into_array());
192209
}
193210

194211
// Also compress the underlying storage array. Some extension schemes can beat the
@@ -198,10 +215,15 @@ impl CascadingCompressor {
198215
ExtensionArray::new(ext_array.ext_dtype().clone(), compressed_storage)
199216
.into_array();
200217

201-
if scheme_compressed.nbytes() < storage_compressed.nbytes() {
202-
Ok(scheme_compressed)
203-
} else {
204-
Ok(storage_compressed)
218+
match selection {
219+
Selection::Compressed(scheme_compressed)
220+
if scheme_compressed.nbytes() < storage_compressed.nbytes() =>
221+
{
222+
Ok(scheme_compressed)
223+
}
224+
// A canonical extension array's storage is only canonical at its top level,
225+
// so an unchanged input can still hold lazy, unserializable arrays.
226+
Selection::Compressed(_) | Selection::Unchanged(_) => Ok(storage_compressed),
205227
}
206228
}
207229
Canonical::Variant(variant_array) => {
@@ -231,8 +253,10 @@ impl CascadingCompressor {
231253
/// ratio.
232254
///
233255
/// If a winner is found and its compressed output is actually smaller than the exact
234-
/// uncompressed size, that output is returned. Otherwise, the original array is returned
235-
/// unchanged.
256+
/// uncompressed size, that output is returned as [`Selection::Compressed`]. Otherwise, the
257+
/// original array is returned as [`Selection::Unchanged`], and the caller decides whether it
258+
/// is a valid result: it is for leaf arrays, but not for arrays like extensions whose children
259+
/// have yet to be compressed.
236260
///
237261
/// Empty, all-null, and constant arrays are handled by the compressor itself before any
238262
/// scheme evaluation (constant detection is skipped while compressing samples).
@@ -244,7 +268,7 @@ impl CascadingCompressor {
244268
canonical: Canonical,
245269
compress_ctx: CompressorContext,
246270
exec_ctx: &mut ExecutionCtx,
247-
) -> VortexResult<ArrayRef> {
271+
) -> VortexResult<Selection> {
248272
let eligible_schemes: Vec<&'static dyn Scheme> = self
249273
.schemes
250274
.iter()
@@ -255,13 +279,13 @@ impl CascadingCompressor {
255279
let array: ArrayRef = canonical.into();
256280

257281
if array.is_empty() {
258-
return Ok(array);
282+
return Ok(Selection::Unchanged(array));
259283
}
260284

261285
if array.all_invalid(exec_ctx)? {
262-
return Ok(
286+
return Ok(Selection::Compressed(
263287
ConstantArray::new(Scalar::null(array.dtype().clone()), array.len()).into_array(),
264-
);
288+
));
265289
}
266290

267291
// Constant detection is built into the compressor: a constant leaf always short-circuits
@@ -270,7 +294,7 @@ impl CascadingCompressor {
270294
//
271295
// Compare valid values directly so even nullable constants avoid distinct-value counting.
272296
if !compress_ctx.is_sample() && constant::is_constant_for_compression(&array, exec_ctx)? {
273-
return constant::compress_as_constant(array, exec_ctx);
297+
return constant::compress_as_constant(array, exec_ctx).map(Selection::Compressed);
274298
}
275299

276300
// A scheme competes against the bytes the rows reference, not dead bytes in the buffers.
@@ -286,13 +310,13 @@ impl CascadingCompressor {
286310
let data = ArrayAndStats::new(array, merged_opts);
287311

288312
if eligible_schemes.is_empty() {
289-
return Ok(data.into_array());
313+
return Ok(Selection::Unchanged(data.into_array()));
290314
}
291315

292316
let Some((winner, winner_estimate)) =
293317
self.choose_best_scheme(&eligible_schemes, &data, compress_ctx.clone(), exec_ctx)?
294318
else {
295-
return Ok(data.into_array());
319+
return Ok(Selection::Unchanged(data.into_array()));
296320
};
297321

298322
// Run the winning scheme's `compress`. On failure, emit an ERROR event carrying the
@@ -321,9 +345,9 @@ impl CascadingCompressor {
321345
);
322346

323347
if accepted {
324-
Ok(compressed)
348+
Ok(Selection::Compressed(compressed))
325349
} else {
326-
Ok(data.into_array())
350+
Ok(Selection::Unchanged(data.into_array()))
327351
}
328352
}
329353
}

‎vortex-compressor/src/compressor/tests.rs‎

Lines changed: 81 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,10 +14,16 @@ use vortex_array::VortexSessionExecute;
1414
use vortex_array::aggregate_fn::fns::uncompressed_size_in_bytes::UncompressedSizeOpts;
1515
use vortex_array::aggregate_fn::fns::uncompressed_size_in_bytes::uncompressed_size_in_bytes;
1616
use vortex_array::arrays::BoolArray;
17+
use vortex_array::arrays::ChunkedArray;
1718
use vortex_array::arrays::Constant;
19+
use vortex_array::arrays::DictArray;
20+
use vortex_array::arrays::ExtensionArray;
21+
use vortex_array::arrays::FixedSizeListArray;
1822
use vortex_array::arrays::Map;
1923
use vortex_array::arrays::NullArray;
2024
use vortex_array::arrays::PrimitiveArray;
25+
use vortex_array::arrays::Slice;
26+
use vortex_array::arrays::SliceArray;
2127
use vortex_array::arrays::VarBinView;
2228
use vortex_array::arrays::VarBinViewArray;
2329
use vortex_array::arrays::varbinview::BinaryView;
@@ -27,12 +33,17 @@ use vortex_array::dtype::DType;
2733
use vortex_array::dtype::MapDType;
2834
use vortex_array::dtype::Nullability;
2935
use vortex_array::dtype::PType;
36+
use vortex_array::dtype::extension::ExtDType;
37+
use vortex_array::dtype::extension::ExtId;
38+
use vortex_array::dtype::extension::ExtVTable;
3039
use vortex_array::scalar::Scalar;
40+
use vortex_array::scalar::ScalarValue;
3141
use vortex_array::validity::Validity;
3242
use vortex_buffer::Buffer;
3343
use vortex_buffer::ByteBuffer;
3444
use vortex_buffer::buffer;
3545
use vortex_error::VortexResult;
46+
use vortex_error::vortex_ensure;
3647
use vortex_session::VortexSession;
3748

3849
use super::CascadingCompressor;
@@ -881,3 +892,73 @@ fn scheme_must_beat_referenced_bytes_not_held_bytes() -> VortexResult<()> {
881892
assert_arrays_eq!(&compressed, &array, &mut exec_ctx);
882893
Ok(())
883894
}
895+
896+
/// An extension type over fixed-size lists, like UUIDs over 16 bytes.
897+
#[derive(Clone, Debug, Default, PartialEq, Eq, Hash)]
898+
struct BytesExtension;
899+
900+
impl ExtVTable for BytesExtension {
901+
type Metadata = u8;
902+
type NativeValue<'a> = &'a ScalarValue;
903+
904+
#[expect(clippy::disallowed_methods, reason = "test-only id")]
905+
fn id(&self) -> ExtId {
906+
ExtId::new("test.bytes")
907+
}
908+
909+
fn serialize_metadata(&self, metadata: &u8) -> VortexResult<Vec<u8>> {
910+
Ok(vec![*metadata])
911+
}
912+
913+
fn deserialize_metadata(&self, metadata: &[u8]) -> VortexResult<u8> {
914+
vortex_ensure!(metadata.len() == 1, "expected one metadata byte");
915+
Ok(metadata[0])
916+
}
917+
918+
fn validate_dtype(dtype: &ExtDType<Self>) -> VortexResult<()> {
919+
vortex_ensure!(
920+
matches!(dtype.storage_dtype(), DType::FixedSizeList(..)),
921+
"expected fixed-size list storage"
922+
);
923+
Ok(())
924+
}
925+
926+
fn unpack_native<'a>(
927+
_dtype: &'a ExtDType<Self>,
928+
value: &'a ScalarValue,
929+
) -> VortexResult<&'a ScalarValue> {
930+
Ok(value)
931+
}
932+
}
933+
934+
/// Canonicalizing an extension array only canonicalizes its storage's top level, so the elements
935+
/// of fixed-size list storage can stay a lazy slice. When no scheme compresses such an array it
936+
/// must not be returned as-is, because the slice is not serializable.
937+
#[test]
938+
fn extension_with_lazy_storage_is_not_passed_through() -> VortexResult<()> {
939+
// Dictionaries of wide values keep the lazy array smaller than its canonical form, and
940+
// chunked arrays only slice on the execute path, so the slice stays lazy.
941+
let dict = |offset: u64| -> VortexResult<ArrayRef> {
942+
let codes = PrimitiveArray::from_iter((0..1024u32).map(|i| (i % 4) as u8)).into_array();
943+
let values = PrimitiveArray::from_iter([offset, offset + 1, offset + 2, offset + 3]);
944+
Ok(DictArray::try_new(codes, values.into_array())?.into_array())
945+
};
946+
let chunks = vec![dict(0)?, dict(100)?];
947+
let elements_dtype = chunks[0].dtype().clone();
948+
let chunked = ChunkedArray::try_new(chunks, elements_dtype)?.into_array();
949+
let elements = SliceArray::new(chunked, 16..2048).into_array();
950+
let storage = FixedSizeListArray::new(elements, 16, Validity::NonNullable, 127).into_array();
951+
let dtype = ExtDType::<BytesExtension>::try_new(0, storage.dtype().clone())?.erased();
952+
let array = ExtensionArray::new(dtype, storage).into_array();
953+
let mut exec_ctx = SESSION.create_execution_ctx();
954+
955+
let compressed = CascadingCompressor::new(Vec::new()).compress(&array, &mut exec_ctx)?;
956+
957+
assert!(
958+
!compressed.depth_first_traversal().any(|a| a.is::<Slice>()),
959+
"compressed array still contains a lazy slice:\n{}",
960+
compressed.display_tree()
961+
);
962+
assert_arrays_eq!(&compressed, &array, &mut exec_ctx);
963+
Ok(())
964+
}

0 commit comments

Comments
 (0)