Skip to content

Commit 2511f21

Browse files
committed
[core] Build deletion-vector row ranges from roaring runs
Walk the deletion vector run by run instead of row by row when turning it into non-deleted row ranges. Short runs still use next, since next_range is slower on scattered deletes. Closes apache#1146
1 parent 85f68e5 commit 2511f21

3 files changed

Lines changed: 140 additions & 12 deletions

File tree

‎crates/paimon/src/deletion_vector/core.rs‎

Lines changed: 104 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -36,6 +36,9 @@ const MAGIC_NUMBER: u32 = 1581511376;
3636
/// unlike the v1 magic, so the two are told apart by byte order as well as value.
3737
const MAGIC_NUMBER_64: u32 = 1681511377;
3838
const MAGIC_NUMBER_SIZE_BYTES: u64 = 4;
39+
/// Adjacent deleted positions walked one by one before switching to
40+
/// `next_range` in [`DeletionVector::deleted_ranges`].
41+
const RUN_PROBE_LEN: u32 = 4;
3942
/// Size of the `bitmapLength` prefix and of the trailing CRC. Mirrors Java
4043
/// `Bitmap64DeletionVector.LENGTH_SIZE_BYTES` / `CRC_SIZE_BYTES`; a v2 entry
4144
/// counts both in `DeletionFile.length()` while a v1 entry counts neither.
@@ -93,6 +96,50 @@ impl DeletionVector {
9396
self.bitmap.is_empty()
9497
}
9598

99+
/// Deleted positions as ascending inclusive `(start, end)` runs.
100+
///
101+
/// Short runs are walked with `next`; once a run is longer than
102+
/// [`RUN_PROBE_LEN`], the rest of it is taken with `next_range`, one roaring
103+
/// container at a time. `next_range` alone is slower than `next` on
104+
/// scattered deletes.
105+
pub(crate) fn deleted_ranges(&self) -> impl Iterator<Item = (u32, u32)> + '_ {
106+
let mut iter = self.bitmap.iter();
107+
let mut pending: Option<(u32, u32)> = None;
108+
std::iter::from_fn(move || {
109+
let (start, mut end) = match pending.take() {
110+
Some(run) => run,
111+
None => {
112+
let pos = iter.next()?;
113+
(pos, pos)
114+
}
115+
};
116+
let mut walked = end - start;
117+
while walked < RUN_PROBE_LEN {
118+
match iter.next() {
119+
Some(pos) if end.checked_add(1) == Some(pos) => {
120+
end = pos;
121+
walked += 1;
122+
}
123+
Some(pos) => {
124+
pending = Some((pos, pos));
125+
return Some((start, end));
126+
}
127+
None => return Some((start, end)),
128+
}
129+
}
130+
// A run split at a container boundary comes back in pieces; join them.
131+
while let Some(run) = iter.next_range() {
132+
if end.checked_add(1) == Some(*run.start()) {
133+
end = *run.end();
134+
} else {
135+
pending = Some((*run.start(), *run.end()));
136+
break;
137+
}
138+
}
139+
Some((start, end))
140+
})
141+
}
142+
96143
/// Serialize using Java `BitmapDeletionVector` format:
97144
/// `i32 bitmapLength | i32 magic | roaring bitmap bytes | i32 crc`.
98145
pub(crate) fn serialize_to_bytes(&self) -> crate::Result<Vec<u8>> {
@@ -588,4 +635,61 @@ mod tests {
588635
// Positions above u32::MAX cannot exist in a roaring32 bitmap -> not deleted.
589636
assert!(!dv.is_deleted(u64::from(u32::MAX) + 1));
590637
}
638+
639+
/// Runs of `bitmap.iter()`, the obvious way.
640+
fn model_ranges(bitmap: &RoaringBitmap) -> Vec<(u32, u32)> {
641+
let mut ranges: Vec<(u32, u32)> = Vec::new();
642+
for pos in bitmap {
643+
match ranges.last_mut() {
644+
Some((_, end)) if end.checked_add(1) == Some(pos) => *end = pos,
645+
_ => ranges.push((pos, pos)),
646+
}
647+
}
648+
ranges
649+
}
650+
651+
fn assert_ranges(bitmap: RoaringBitmap) {
652+
let expected = model_ranges(&bitmap);
653+
let dv = DeletionVector::from_bitmap(bitmap);
654+
assert_eq!(dv.deleted_ranges().collect::<Vec<_>>(), expected);
655+
}
656+
657+
#[test]
658+
fn test_deleted_ranges_edges() {
659+
assert_ranges(RoaringBitmap::new());
660+
assert_ranges(RoaringBitmap::from([7]));
661+
// Runs right at the probe length, and one past it.
662+
assert_ranges((10..14).chain(20..25).chain(30..31).collect());
663+
// One run across several roaring containers, then a short one.
664+
assert_ranges((65_530..200_000).chain([200_002]).collect());
665+
// A long run followed by an adjacent-container run that does not touch it.
666+
assert_ranges((0..65_535).chain(65_537..70_000).collect());
667+
// Runs ending at u32::MAX.
668+
assert_ranges([u32::MAX].into_iter().collect());
669+
assert_ranges((u32::MAX - 70_000..=u32::MAX).collect());
670+
}
671+
672+
#[test]
673+
fn test_deleted_ranges_match_model_on_random_bitmaps() {
674+
let mut state = 0x2545_f491_4f6c_dd1du64;
675+
let mut next = move || {
676+
state ^= state << 13;
677+
state ^= state >> 7;
678+
state ^= state << 17;
679+
state
680+
};
681+
for round in 0..128 {
682+
let max_gap = [2u64, 30, 3_000, 100_000][round % 4];
683+
let max_len = [3u64, 50, 3_000, 70_000][(round / 4) % 4];
684+
let mut bitmap = RoaringBitmap::new();
685+
let mut pos = (next() % 200_000) as u32;
686+
for _ in 0..40 {
687+
let len = 1 + (next() % max_len) as u32;
688+
let end = pos.saturating_add(len);
689+
bitmap.insert_range(pos..end);
690+
pos = end.saturating_add(1 + (next() % max_gap) as u32);
691+
}
692+
assert_ranges(bitmap);
693+
}
694+
}
591695
}

‎crates/paimon/src/table/data_evolution_reader.rs‎

Lines changed: 6 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -2167,15 +2167,15 @@ fn prefix_row_ranges(
21672167
fn non_deleted_local_ranges(row_count: i64, deletion_vector: &DeletionVector) -> Vec<RowRange> {
21682168
let mut ranges = Vec::new();
21692169
let mut cursor = 0i64;
2170-
for deleted in deletion_vector.iter() {
2171-
let deleted = deleted as i64;
2172-
if deleted >= row_count {
2170+
for (start, end) in deletion_vector.deleted_ranges() {
2171+
let (start, end) = (i64::from(start), i64::from(end));
2172+
if start >= row_count {
21732173
break;
21742174
}
2175-
if deleted > cursor {
2176-
ranges.push(RowRange::new(cursor, deleted - 1));
2175+
if start > cursor {
2176+
ranges.push(RowRange::new(cursor, start - 1));
21772177
}
2178-
cursor = deleted + 1;
2178+
cursor = end + 1;
21792179
}
21802180
if cursor < row_count {
21812181
ranges.push(RowRange::new(cursor, row_count - 1));

‎crates/paimon/src/table/data_file_reader.rs‎

Lines changed: 30 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -1420,15 +1420,15 @@ fn ranges_cover_all_rows(ranges: &[RowRange], row_count: i64) -> bool {
14201420
fn dv_to_non_deleted_ranges(dv: &DeletionVector, row_count: i64) -> Vec<RowRange> {
14211421
let mut result = Vec::new();
14221422
let mut cursor: i64 = 0;
1423-
for deleted in dv.iter() {
1424-
let del = deleted as i64;
1425-
if del >= row_count {
1423+
for (start, end) in dv.deleted_ranges() {
1424+
let (start, end) = (i64::from(start), i64::from(end));
1425+
if start >= row_count {
14261426
break;
14271427
}
1428-
if del > cursor {
1429-
result.push(RowRange::new(cursor, del - 1));
1428+
if start > cursor {
1429+
result.push(RowRange::new(cursor, start - 1));
14301430
}
1431-
cursor = del + 1;
1431+
cursor = end + 1;
14321432
}
14331433
if cursor < row_count {
14341434
result.push(RowRange::new(cursor, row_count - 1));
@@ -2356,6 +2356,30 @@ mod tests {
23562356
);
23572357
}
23582358

2359+
#[test]
2360+
fn dv_to_non_deleted_ranges_handles_long_runs() {
2361+
let dv = DeletionVector::from_bitmap;
2362+
// A run crossing roaring containers.
2363+
assert_eq!(
2364+
dv_to_non_deleted_ranges(&dv((70_000..140_000).collect()), 200_000),
2365+
vec![RowRange::new(0, 69_999), RowRange::new(140_000, 199_999)]
2366+
);
2367+
// A run that goes past the end of the file.
2368+
assert_eq!(
2369+
dv_to_non_deleted_ranges(&dv((3..100_000).collect()), 50_000),
2370+
vec![RowRange::new(0, 2)]
2371+
);
2372+
// Positions at or past row_count are ignored.
2373+
assert_eq!(
2374+
dv_to_non_deleted_ranges(&dv((0..10).chain(60_000..60_010).collect()), 50_000),
2375+
vec![RowRange::new(10, 49_999)]
2376+
);
2377+
assert_eq!(
2378+
dv_to_non_deleted_ranges(&dv((0..50_000).collect()), 50_000),
2379+
vec![]
2380+
);
2381+
}
2382+
23592383
#[test]
23602384
fn file_index_selection_coalesces_positions_and_rejects_out_of_range_values() {
23612385
let selection = [0_u32, 1, 3].into_iter().collect();

0 commit comments

Comments
 (0)