Skip to content

Commit 8bada73

Browse files
authored
fix: preserve sliced patch offsets during deserialization (#11168)
Preserve and validate sliced patch offsets when deserializing BitPacked and ALP arrays to prevent incorrect values after serialization round trips. --------- Signed-off-by: blaginin <[email protected]>
1 parent fcb28af commit 8bada73

6 files changed

Lines changed: 276 additions & 6 deletions

File tree

‎encodings/alp/src/alp/array.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -158,9 +158,9 @@ impl VTable for ALP {
158158
.map(|dtype| children.get(3, &dtype, usize::try_from(p.chunk_offsets_len())?))
159159
.transpose()?;
160160

161-
Patches::new(
161+
Patches::from_metadata(
162162
len,
163-
p.offset()?,
163+
&p,
164164
indices,
165165
values,
166166
chunk_offsets,

‎encodings/alp/src/alp/mod.rs‎

Lines changed: 48 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -26,12 +26,27 @@ pub(crate) fn initialize(session: &VortexSession) {
2626

2727
#[cfg(test)]
2828
mod tests {
29+
use std::f64::consts::PI;
30+
2931
use prost::Message;
32+
use rstest::rstest;
33+
use vortex_array::Array;
34+
use vortex_array::IntoArray;
35+
use vortex_array::VortexSessionExecute;
36+
use vortex_array::arrays::PrimitiveArray;
37+
use vortex_array::arrays::slice::SliceKernel;
38+
use vortex_array::assert_arrays_eq;
3039
use vortex_array::dtype::PType;
3140
use vortex_array::patches::PatchesMetadata;
3241
use vortex_array::test_harness::check_metadata;
42+
use vortex_array::vtable::VTable;
43+
use vortex_error::VortexResult;
44+
use vortex_session::VortexSession;
3345

46+
use crate::ALP;
47+
use crate::Exponents;
3448
use crate::alp::array::ALPMetadata;
49+
use crate::alp_encode;
3550

3651
#[cfg_attr(miri, ignore)]
3752
#[test]
@@ -53,4 +68,37 @@ mod tests {
5368
.encode_to_vec(),
5469
);
5570
}
71+
72+
#[rstest]
73+
fn serde_roundtrip_sliced_chunked_patches(
74+
#[values(500, 1500)] start: usize,
75+
) -> VortexResult<()> {
76+
let session = VortexSession::empty();
77+
crate::initialize(&session);
78+
let mut ctx = session.create_execution_ctx();
79+
let values =
80+
PrimitiveArray::from_iter((0..4096).map(|i| if i % 7 == 0 { PI } else { 1.0 }));
81+
let encoded = alp_encode(values.as_view(), Some(Exponents { e: 0, f: 0 }), &mut ctx)?;
82+
let sliced = <ALP as SliceKernel>::slice(encoded.as_view(), start..4096, &mut ctx)?
83+
.expect("ALP slices");
84+
let metadata = ALP::serialize(sliced.as_::<ALP>(), &session)?.expect("ALP serializes");
85+
let parts = ALP.deserialize(
86+
sliced.dtype(),
87+
sliced.len(),
88+
&metadata,
89+
&[],
90+
&sliced.children(),
91+
&session,
92+
)?;
93+
let read = Array::<ALP>::try_from_parts(parts)?.into_array();
94+
let expected = values.into_array().slice(start..4096)?;
95+
96+
let patch_index = ((start / 1024 + 1) * 1024).next_multiple_of(7) - start;
97+
assert_eq!(
98+
read.execute_scalar(patch_index, &mut ctx)?,
99+
expected.execute_scalar(patch_index, &mut ctx)?
100+
);
101+
assert_arrays_eq!(read, expected, &mut ctx);
102+
Ok(())
103+
}
56104
}

‎encodings/fastlanes/src/bitpacking/plugin/tests.rs‎

Lines changed: 78 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -14,6 +14,7 @@ use vortex_array::VortexSessionExecute;
1414
use vortex_array::arrays::PatchedArray;
1515
use vortex_array::arrays::PrimitiveArray;
1616
use vortex_array::arrays::patched::PatchedArraySlotsExt;
17+
use vortex_array::arrays::slice::SliceKernel;
1718
use vortex_array::assert_arrays_eq;
1819
use vortex_array::buffer::BufferHandle;
1920
use vortex_array::builtins::ArrayBuiltins;
@@ -423,3 +424,80 @@ fn test_decode_blocked_bitpacked_patches() -> VortexResult<()> {
423424
assert_arrays_eq!(patched, values, &mut ctx);
424425
Ok(())
425426
}
427+
428+
/// Slicing removes individual patches while retaining the first chunk's original offset.
429+
#[rstest]
430+
#[case::v1(false)]
431+
#[case::v2(true)]
432+
fn serde_roundtrip_sliced_chunked_patches(
433+
#[case] blocked: bool,
434+
#[values(500, 1500)] start: usize,
435+
) -> VortexResult<()> {
436+
let mut ctx = PLUGIN_SESSION.create_execution_ctx();
437+
// Every 7th value does not fit 11 bits and becomes a patch, in every chunk.
438+
let values =
439+
PrimitiveArray::from_iter((0u32..4096).map(|i| if i % 7 == 0 { 5000 } else { i % 2048 }));
440+
let encoded = BitPackedData::encode(&values.clone().into_array(), 11, &mut ctx)?;
441+
// Slice mid-chunk while still encoded, as the slice kernel does.
442+
let sliced = <BitPacked as SliceKernel>::slice(encoded.as_view(), start..4096, &mut ctx)?
443+
.ok_or_else(|| vortex_err!("BitPacked slices"))?;
444+
let sliced = if blocked {
445+
// Represent the same sliced blocks as v2 without relying on a blocked slice kernel.
446+
let view = sliced.as_::<BitPacked>();
447+
let num_blocks = (usize::from(view.offset()) + view.len()).div_ceil(1024);
448+
let block_offsets = PrimitiveArray::from_iter(
449+
(0..=u32::try_from(num_blocks)?).map(|block| block * 11 * 128),
450+
);
451+
BitPacked::try_new_with_block_offsets(
452+
view.packed().clone(),
453+
PType::U32,
454+
view.validity()?,
455+
view.patches(),
456+
block_offsets.into_array(),
457+
view.len(),
458+
view.offset(),
459+
)?
460+
.into_array()
461+
} else {
462+
sliced
463+
};
464+
let read = roundtrip(&sliced)?;
465+
assert_eq!(read.as_::<BitPacked>().bit_widths().is_global(), !blocked);
466+
let expected = values.into_array().slice(start..4096)?;
467+
// Probe the first patch of the second retained chunk (row 529 when start is 500).
468+
let patch_index = ((start / 1024 + 1) * 1024).next_multiple_of(7) - start;
469+
assert_eq!(
470+
read.execute_scalar(patch_index, &mut ctx)?,
471+
expected.execute_scalar(patch_index, &mut ctx)?
472+
);
473+
assert_arrays_eq!(read, expected, &mut ctx);
474+
475+
let indices = PrimitiveArray::from_iter([
476+
u32::try_from(patch_index - 1)?,
477+
u32::try_from(patch_index)?,
478+
u32::try_from(patch_index + 1)?,
479+
])
480+
.into_array();
481+
let taken = read
482+
.take(indices.clone())?
483+
.execute::<PrimitiveArray>(&mut ctx)?;
484+
assert_arrays_eq!(taken, expected.take(indices)?, &mut ctx);
485+
486+
let read_patches = read.as_::<BitPacked>().patches().unwrap();
487+
let expected_patches = sliced.as_::<BitPacked>().patches().unwrap();
488+
assert_eq!(
489+
read_patches.offset_within_chunk(),
490+
expected_patches.offset_within_chunk()
491+
);
492+
let resliced = read_patches.slice(800..read.len(), &mut ctx)?.unwrap();
493+
let expected_resliced = expected_patches
494+
.slice(800..sliced.len(), &mut ctx)?
495+
.unwrap();
496+
assert_eq!(
497+
resliced.offset_within_chunk(),
498+
expected_resliced.offset_within_chunk()
499+
);
500+
assert_arrays_eq!(resliced.indices(), expected_resliced.indices(), &mut ctx);
501+
assert_arrays_eq!(resliced.values(), expected_resliced.values(), &mut ctx);
502+
Ok(())
503+
}

‎encodings/fastlanes/src/bitpacking/plugin/v1.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -113,9 +113,9 @@ pub(super) fn deserialize(
113113
.map(|dtype| children.get(2, &dtype, p.chunk_offsets_len() as usize))
114114
.transpose()?;
115115

116-
Patches::new(
116+
Patches::from_metadata(
117117
len,
118-
p.offset()?,
118+
&p,
119119
indices,
120120
values,
121121
chunk_offsets,

‎encodings/fastlanes/src/bitpacking/plugin/v2.rs‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -132,9 +132,9 @@ pub(super) fn deserialize(
132132
.map(|dtype| children.get(2, &dtype, p.chunk_offsets_len() as usize))
133133
.transpose()?;
134134

135-
Patches::new(
135+
Patches::from_metadata(
136136
len,
137-
p.offset()?,
137+
&p,
138138
indices,
139139
values,
140140
chunk_offsets,

‎vortex-array/src/patches.rs‎

Lines changed: 144 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -290,6 +290,59 @@ impl Patches {
290290
})
291291
}
292292

293+
/// Reconstruct patches from serialized metadata and their child arrays.
294+
///
295+
/// Preserves the number of patches sliced off within the first chunk. Metadata without this
296+
/// field defaults to zero for compatibility with older arrays.
297+
pub fn from_metadata(
298+
array_len: usize,
299+
metadata: &PatchesMetadata,
300+
indices: ArrayRef,
301+
values: ArrayRef,
302+
chunk_offsets: Option<ArrayRef>,
303+
ctx: &mut ExecutionCtx,
304+
) -> VortexResult<Self> {
305+
let mut patches = Self::new(
306+
array_len,
307+
metadata.offset()?,
308+
indices,
309+
values,
310+
chunk_offsets,
311+
ctx,
312+
)?;
313+
if let Some(chunk_offsets) = &patches.chunk_offsets {
314+
let offset_within_chunk = usize::try_from(metadata.offset_within_chunk())?;
315+
let sliced_rows = patches.offset % PATCH_CHUNK_SIZE;
316+
vortex_ensure!(
317+
offset_within_chunk <= sliced_rows,
318+
"Patch offset within chunk exceeds the sliced row count"
319+
);
320+
321+
// A wrong offset can assign first-chunk patches to a later chunk during decoding.
322+
// Check the boundary against the indices, not just the original chunk's patch count.
323+
if chunk_offsets.len() > 1 && chunk_offsets.is_host() && patches.indices.is_host() {
324+
let first_chunk_end = patches
325+
.offset
326+
.checked_add(PATCH_CHUNK_SIZE - sliced_rows)
327+
.ok_or_else(|| vortex_err!("Patch chunk boundary overflows usize"))?;
328+
let retained =
329+
search_index_binary_search(&patches.indices, first_chunk_end, ctx)?.to_index();
330+
let expected_offset = patches
331+
.chunk_offset_at(1, ctx)?
332+
.checked_sub(patches.chunk_offset_at(0, ctx)?)
333+
.and_then(|count| count.checked_sub(retained))
334+
.ok_or_else(|| vortex_err!("Invalid patch chunk offsets"))?;
335+
vortex_ensure_eq!(
336+
offset_within_chunk,
337+
expected_offset,
338+
"Patch offset within chunk disagrees with the patch indices"
339+
);
340+
}
341+
patches.offset_within_chunk = Some(offset_within_chunk);
342+
}
343+
Ok(patches)
344+
}
345+
293346
/// Construct new patches without validating any of the arguments
294347
///
295348
/// # Safety
@@ -1354,6 +1407,7 @@ fn take_indices_with_search_fn<
13541407

13551408
#[cfg(test)]
13561409
mod test {
1410+
use std::ops::Range;
13571411
use std::sync::LazyLock;
13581412

13591413
use rstest::rstest;
@@ -1369,13 +1423,103 @@ mod test {
13691423
use crate::IntoArray;
13701424
use crate::VortexSessionExecute;
13711425
use crate::assert_arrays_eq;
1426+
use crate::dtype::PType;
13721427
use crate::patches::Patches;
1428+
use crate::patches::PatchesMetadata;
13731429
use crate::patches::PrimitiveArray;
13741430
use crate::search_sorted::SearchResult;
13751431
use crate::validity::Validity;
13761432

13771433
static SESSION: LazyLock<VortexSession> = LazyLock::new(VortexSession::empty);
13781434

1435+
#[rstest]
1436+
#[case::unchunked(false)]
1437+
#[case::chunked(true)]
1438+
fn test_from_metadata_without_offset_within_chunk(#[case] chunked: bool) -> VortexResult<()> {
1439+
let mut ctx = SESSION.create_execution_ctx();
1440+
let metadata = PatchesMetadata::new(
1441+
3,
1442+
0,
1443+
PType::U32,
1444+
chunked.then_some(3),
1445+
chunked.then_some(PType::U32),
1446+
None,
1447+
);
1448+
let patches = Patches::from_metadata(
1449+
3072,
1450+
&metadata,
1451+
buffer![7u32, 1029, 2051].into_array(),
1452+
buffer![11i32, 22, 33].into_array(),
1453+
chunked.then(|| buffer![0u32, 1, 2].into_array()),
1454+
&mut ctx,
1455+
)?;
1456+
1457+
assert_eq!(patches.offset_within_chunk(), chunked.then_some(0));
1458+
assert_eq!(
1459+
patches.search_index(1029, &mut ctx)?,
1460+
SearchResult::Found(1)
1461+
);
1462+
Ok(())
1463+
}
1464+
1465+
#[rstest]
1466+
fn test_from_metadata_rejects_inconsistent_chunk_offset(
1467+
#[values(0, 2, 3, 501, usize::MAX)] offset_within_chunk: usize,
1468+
) {
1469+
let mut ctx = SESSION.create_execution_ctx();
1470+
// The original first chunk had patches at 100 and 500; slicing at 500 removed one.
1471+
let metadata = PatchesMetadata::new(
1472+
2,
1473+
500,
1474+
PType::U32,
1475+
Some(2),
1476+
Some(PType::U32),
1477+
Some(offset_within_chunk),
1478+
);
1479+
let error = Patches::from_metadata(
1480+
1000,
1481+
&metadata,
1482+
buffer![500u32, 1200].into_array(),
1483+
buffer![11i32, 22].into_array(),
1484+
Some(buffer![0u32, 2].into_array()),
1485+
&mut ctx,
1486+
)
1487+
.expect_err("inconsistent patch offset must be rejected");
1488+
assert!(error.to_string().contains("Patch offset within chunk"));
1489+
}
1490+
1491+
#[rstest]
1492+
#[case::single_chunk(900..901)]
1493+
#[case::later_single_chunk(1500..1501)]
1494+
#[case::multiple_chunks(900..2050)]
1495+
fn test_from_metadata_short_slice(#[case] range: Range<usize>) -> VortexResult<()> {
1496+
let mut ctx = SESSION.create_execution_ctx();
1497+
let indices = PrimitiveArray::from_iter(0u32..3072).into_array();
1498+
let patches = Patches::new(
1499+
3072,
1500+
0,
1501+
indices.clone(),
1502+
indices,
1503+
Some(buffer![0u32, 1024, 2048].into_array()),
1504+
&mut ctx,
1505+
)?;
1506+
let sliced = patches.slice(range, &mut ctx)?.expect("slice has patches");
1507+
let metadata = sliced.to_metadata(sliced.array_len(), sliced.dtype())?;
1508+
let read = Patches::from_metadata(
1509+
sliced.array_len(),
1510+
&metadata,
1511+
sliced.indices().clone(),
1512+
sliced.values().clone(),
1513+
sliced.chunk_offsets().clone(),
1514+
&mut ctx,
1515+
)?;
1516+
1517+
assert_eq!(read.offset_within_chunk(), sliced.offset_within_chunk());
1518+
assert_eq!(read.search_index(0, &mut ctx)?, SearchResult::Found(0));
1519+
assert_arrays_eq!(read.values(), sliced.values(), &mut ctx);
1520+
Ok(())
1521+
}
1522+
13791523
#[test]
13801524
fn test_filter() {
13811525
let mut ctx = SESSION.create_execution_ctx();

0 commit comments

Comments
 (0)