Skip to content

Commit 38037c4

Browse files
authored
perf: preserve native DV bitmap compression (apache#6945)
* perf: preserve native DV bitmap compression Transfer decoded sub-bitmaps instead of reinserting each deleted row to retain compressed runs and implicit high-partition keys. Closes apache#5656 * test: assert native DV plan selection and empty-partition keys Review on apache#6945 asked for the empty intermediate partition to carry its intent where the value guards it, and for the dense native DV to be driven through build_access_plan, which nothing in this file did before.
1 parent 330b29c commit 38037c4

1 file changed

Lines changed: 46 additions & 6 deletions

File tree

‎native/core/src/execution/delta_dv.rs‎

Lines changed: 46 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -129,8 +129,8 @@ pub fn deserialize_dv_bitmap(data: &[u8]) -> Result<RoaringTreemap, ExecutionErr
129129
)));
130130
}
131131
let mut pos = 4usize;
132-
let mut treemap = RoaringTreemap::new();
133-
for key in 0..count as u64 {
132+
let mut bitmaps = Vec::new();
133+
for key in 0..count as u32 {
134134
if rest.len() < pos + 4 {
135135
return Err(GeneralError(
136136
"Native deletion vector bitmap truncated".to_string(),
@@ -148,11 +148,11 @@ pub fn deserialize_dv_bitmap(data: &[u8]) -> Result<RoaringTreemap, ExecutionErr
148148
GeneralError(format!("Invalid deletion vector sub-bitmap: {e}"))
149149
})?;
150150
pos += size as usize;
151-
for value in bitmap {
152-
treemap.insert((key << 32) | value as u64);
151+
if !bitmap.is_empty() {
152+
bitmaps.push((key, bitmap));
153153
}
154154
}
155-
Ok(treemap)
155+
Ok(RoaringTreemap::from_bitmaps(bitmaps))
156156
}
157157
other => Err(GeneralError(format!(
158158
"Unexpected RoaringBitmapArray magic number {other}"
@@ -1122,10 +1122,50 @@ mod tests {
11221122

11231123
#[test]
11241124
fn native_format_decodes() {
1125-
let values = [0u64, 2, 3, 100, (1u64 << 32) + 7];
1125+
let values = [0u64, 2, 3, 100, (2u64 << 32) + 7];
11261126
let decoded = deserialize_dv_bitmap(&native_bytes(&values)).unwrap();
11271127
let expected: RoaringTreemap = values.into_iter().collect();
11281128
assert_eq!(decoded, expected);
1129+
// `native_bytes` emits an entry for every key up to the maximum, so key 1 is an empty
1130+
// partition. The decoder must omit it without shifting key 2's partition index.
1131+
let keys: Vec<u32> = decoded.bitmaps().map(|(key, _)| key).collect();
1132+
assert_eq!(keys, vec![0, 2]);
1133+
}
1134+
1135+
#[test]
1136+
fn native_decode_preserves_dense_bitmap_compression() {
1137+
let mut bitmap = RoaringBitmap::new();
1138+
bitmap.insert_range(0..1_000_000);
1139+
let compressed_size = bitmap.serialized_size();
1140+
let mut bitmap_bytes = Vec::new();
1141+
bitmap.serialize_into(&mut bitmap_bytes).unwrap();
1142+
1143+
let mut data = NATIVE_MAGIC.to_le_bytes().to_vec();
1144+
data.extend(1i32.to_le_bytes());
1145+
data.extend((bitmap_bytes.len() as i32).to_le_bytes());
1146+
data.extend(bitmap_bytes);
1147+
1148+
let decoded = deserialize_dv_bitmap(&data).unwrap();
1149+
let (_, decoded_bitmap) = decoded.bitmaps().next().unwrap();
1150+
assert_eq!(decoded_bitmap.serialized_size(), compressed_size);
1151+
1152+
// Dense native DVs now reach `build_access_plan`, so the same container must survive
1153+
// plan construction. Group 0 (rows 0..600_000) is fully deleted and must be skipped;
1154+
// group 1 (rows 600_000..1_200_000) has its first 400_000 rows deleted, leaving a
1155+
// trailing run of 200_000 live rows to select.
1156+
assert_eq!(decoded.len(), 1_000_000);
1157+
let plan = full_file_access_plan(&[600_000, 600_000], &decoded).unwrap();
1158+
assert_eq!(&plan.inner()[0], &RowGroupAccess::Skip);
1159+
match &plan.inner()[1] {
1160+
RowGroupAccess::Selection(sel) => {
1161+
let selectors: Vec<RowSelector> = sel.clone().into();
1162+
assert_eq!(
1163+
selectors,
1164+
vec![RowSelector::skip(400_000), RowSelector::select(200_000)]
1165+
);
1166+
}
1167+
other => panic!("expected selection, got {other:?}"),
1168+
}
11291169
}
11301170

11311171
#[test]

0 commit comments

Comments
 (0)