Skip to content

Commit cea0caa

Browse files
authored
[core] Read sparse bitmap matches from data evolution ROW sidecars (#1173)
1 parent 8809166 commit cea0caa

7 files changed

Lines changed: 1758 additions & 46 deletions

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

Lines changed: 141 additions & 11 deletions
Original file line numberDiff line numberDiff line change
@@ -477,7 +477,10 @@ impl DataEvolutionReader {
477477
let push_down_raw_predicates = !self.predicates.is_empty()
478478
&& self.row_id_index.is_none()
479479
&& filter_before_blob_resolution;
480-
let read_raw_file_index = push_down_raw_predicates
480+
// A bitmap selection preserves physical positions, including when
481+
// `_ROW_ID` needs attaching before the residual predicate runs.
482+
let read_file_index = !self.predicates.is_empty()
483+
&& filter_before_blob_resolution
481484
&& CoreOptions::new(&self.table_options).file_index_read_enabled();
482485
// A managed BLOB file fetches payloads as its batch is decoded.
483486
// Keep batches small and restrict predicate-free file selections
@@ -508,7 +511,9 @@ impl DataEvolutionReader {
508511
if remaining == Some(0) {
509512
break;
510513
}
511-
let row_ranges = split.row_ranges().map(|r| r.to_vec());
514+
let row_ranges = split
515+
.row_ranges()
516+
.map(|ranges| crate::table::merge_row_ranges(ranges.to_vec()));
512517
// A chunk may span several disjoint row-id groups while one
513518
// group still needs column-wise merging. Process each aligned
514519
// group independently; treating the whole chunk as one merge
@@ -541,10 +546,8 @@ impl DataEvolutionReader {
541546
let has_row_id = file_meta.first_row_id.is_some();
542547
let requested_row_ranges = if has_row_id { row_ranges.clone() } else { None };
543548
let mut effective_row_ranges = requested_row_ranges.clone();
544-
if read_raw_file_index {
545-
// Independent files can apply a physical row selection
546-
// before decoding. Column-merge groups cannot: an older
547-
// file may hold values still needed by a newer file.
549+
let mut has_bitmap_selection = false;
550+
if read_file_index {
548551
match evaluate_file_index(
549552
&self.file_io,
550553
split.bucket_path(),
@@ -560,6 +563,7 @@ impl DataEvolutionReader {
560563
&selection,
561564
file_meta.row_count,
562565
)? {
566+
has_bitmap_selection = selection.len() < file_meta.row_count as u64;
563567
let base = file_meta.first_row_id.unwrap_or(0);
564568
let index_ranges = local_ranges
565569
.into_iter()
@@ -578,6 +582,18 @@ impl DataEvolutionReader {
578582
FileIndexResult::Remain => {}
579583
}
580584
}
585+
// Java applies DV to a selective bitmap before
586+
// choosing ROW. DV alone and LIMIT cannot trigger it.
587+
let sidecar_row_ranges = if has_bitmap_selection {
588+
selected_absolute_row_ranges_for_file(
589+
file_meta.first_row_id.unwrap_or(0),
590+
file_meta.row_count,
591+
effective_row_ranges.as_deref(),
592+
deletion_vector.as_deref(),
593+
)?
594+
} else {
595+
effective_row_ranges.clone()
596+
};
581597
if self.predicates.is_empty() {
582598
if let Some(left) = remaining {
583599
let selected = selected_absolute_row_ranges_for_file(
@@ -628,7 +644,7 @@ impl DataEvolutionReader {
628644
data_fields,
629645
deletion_vector,
630646
effective_row_ranges,
631-
requested_row_ranges,
647+
sidecar_row_ranges,
632648
)?;
633649
while remaining != Some(0) {
634650
let Some(batch) = stream.next().await else { break };
@@ -659,6 +675,35 @@ impl DataEvolutionReader {
659675
}
660676
} else {
661677
let prepared_group = PreparedMergeGroup::new(&files)?;
678+
let mut indexed_row_ranges = row_ranges.clone();
679+
let mut has_bitmap_selection = false;
680+
if read_file_index {
681+
match self.evaluate_group_file_indexes(&split, &prepared_group).await? {
682+
FileIndexResult::Skip => continue,
683+
FileIndexResult::Selection(selection) => {
684+
if let Some(local_ranges) = file_index_selection_to_local_ranges(
685+
&selection,
686+
prepared_group.logical_row_count,
687+
)? {
688+
has_bitmap_selection = selection.len() < prepared_group.logical_row_count as u64;
689+
let index_ranges = local_ranges.into_iter().map(|range| {
690+
RowRange::new(
691+
prepared_group.first_row_id + range.from(),
692+
prepared_group.first_row_id + range.to(),
693+
)
694+
}).collect::<Vec<_>>();
695+
indexed_row_ranges = Some(match indexed_row_ranges {
696+
Some(ref ranges) => intersect_local_ranges(ranges, &index_ranges),
697+
None => index_ranges,
698+
});
699+
}
700+
}
701+
FileIndexResult::Remain => {}
702+
}
703+
}
704+
if indexed_row_ranges.as_ref().is_some_and(Vec::is_empty) {
705+
continue;
706+
}
662707
let anchor_deletion_vector = read_anchor_deletion_vector(
663708
&self.file_io,
664709
&split,
@@ -668,11 +713,19 @@ impl DataEvolutionReader {
668713
let mut selected_ranges = selected_absolute_row_ranges_for_file(
669714
prepared_group.first_row_id,
670715
prepared_group.logical_row_count,
671-
row_ranges.as_deref(),
716+
indexed_row_ranges.as_deref(),
672717
anchor_deletion_vector
673718
.as_ref()
674719
.map(|ctx| ctx.deletion_vector.as_ref()),
675720
)?;
721+
// Every provider shares the DV-aware bitmap. Without
722+
// a selective bitmap, only caller ranges choose ROW.
723+
// LIMIT never changes sidecar eligibility.
724+
let sidecar_row_ranges = if has_bitmap_selection {
725+
selected_ranges.clone()
726+
} else {
727+
indexed_row_ranges.clone()
728+
};
676729
let effective_row_ranges = if self.predicates.is_empty() {
677730
if let Some(left) = remaining {
678731
selected_ranges = Some(prefix_row_ranges(
@@ -683,10 +736,10 @@ impl DataEvolutionReader {
683736
));
684737
selected_ranges.clone()
685738
} else {
686-
row_ranges.clone()
739+
indexed_row_ranges.clone()
687740
}
688741
} else {
689-
row_ranges.clone()
742+
indexed_row_ranges
690743
};
691744
let expected_output_rows = match selected_ranges.as_ref() {
692745
Some(ranges) => ranges.iter().map(|r| r.count() as usize).sum(),
@@ -711,7 +764,7 @@ impl DataEvolutionReader {
711764
&split,
712765
&prepared_group,
713766
effective_row_ranges,
714-
row_ranges.clone(),
767+
sidecar_row_ranges,
715768
expected_output_rows,
716769
anchor_deletion_vector,
717770
)?;
@@ -944,6 +997,83 @@ impl DataEvolutionReader {
944997
.await
945998
}
946999

1000+
/// Evaluate only the fields each normal file wins in the merged row.
1001+
///
1002+
/// The group is newest first. A newer writer claims its fields even when
1003+
/// it has no index, so an obsolete value can never reject a live row.
1004+
async fn evaluate_group_file_indexes(
1005+
&self,
1006+
split: &DataSplit,
1007+
group: &PreparedMergeGroup,
1008+
) -> crate::Result<FileIndexResult> {
1009+
// Dedicated sources may cover only part of the normal files' range.
1010+
// Like Java, they prevent a shared positional bitmap selection.
1011+
let can_select = group.files.iter().all(|file| {
1012+
!is_blob_or_video_file_name(&file.file_name)
1013+
&& !is_vector_store_file_name(&file.file_name)
1014+
});
1015+
let mut claimed = HashSet::new();
1016+
let mut result = FileIndexResult::Remain;
1017+
for file in &group.files {
1018+
if is_blob_or_video_file_name(&file.file_name)
1019+
|| is_vector_store_file_name(&file.file_name)
1020+
{
1021+
continue;
1022+
}
1023+
let (data_fields, _) = raw_file_physical_fields(
1024+
&self.schema_manager,
1025+
self.table_schema_id,
1026+
&self.table_fields,
1027+
file,
1028+
)
1029+
.await?;
1030+
let data_fields = data_fields.as_deref().unwrap_or(&self.table_fields);
1031+
let winning_ids = data_fields
1032+
.iter()
1033+
.filter_map(|field| claimed.insert(field.id()).then_some(field.id()))
1034+
.collect::<HashSet<_>>();
1035+
let mapping = self
1036+
.table_fields
1037+
.iter()
1038+
.enumerate()
1039+
.map(|(index, field)| {
1040+
// Partition values come from the split. A partially written
1041+
// ROW can have several providers for its parent nullness.
1042+
(winning_ids.contains(&field.id())
1043+
&& !matches!(field.data_type(), DataType::Row(_))
1044+
&& !self.partition_fields.iter().any(|p| p.id() == field.id()))
1045+
.then_some(index)
1046+
})
1047+
.collect::<Vec<_>>();
1048+
let predicates = self
1049+
.predicates
1050+
.iter()
1051+
.filter_map(|predicate| predicate.project_field_index_inclusive(&mapping))
1052+
.collect::<Vec<_>>();
1053+
let file_result = evaluate_file_index(
1054+
&self.file_io,
1055+
split.bucket_path(),
1056+
file,
1057+
&self.table_fields,
1058+
data_fields,
1059+
&predicates,
1060+
)
1061+
.await?;
1062+
if !file_result.remain() {
1063+
return Ok(FileIndexResult::Skip);
1064+
}
1065+
if can_select {
1066+
// Each file contributes a necessary condition, so intersect
1067+
// candidates rather than independently filtering its stream.
1068+
result = result.and(file_result);
1069+
if !result.remain() {
1070+
return Ok(FileIndexResult::Skip);
1071+
}
1072+
}
1073+
}
1074+
Ok(result)
1075+
}
1076+
9471077
/// Merge multiple logical sources column-wise for data evolution.
9481078
///
9491079
/// Normal partial-column files remain one source per file. Rolling `.blob`

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

Lines changed: 19 additions & 9 deletions
Original file line numberDiff line numberDiff line change
@@ -361,7 +361,7 @@ impl DataFileReader {
361361
)
362362
});
363363
split_file_offset += file_meta.row_count;
364-
let sidecar_ranges = split_ranges.clone();
364+
let mut has_bitmap_selection = false;
365365
let selected_ranges = match file_index_result {
366366
FileIndexResult::Remain => split_ranges,
367367
FileIndexResult::Skip => Some(Vec::new()),
@@ -370,12 +370,15 @@ impl DataFileReader {
370370
&selection,
371371
file_meta.row_count,
372372
)? {
373-
Some(index_ranges) => Some(match split_ranges {
374-
Some(split_ranges) => {
375-
intersect_sorted_ranges(&index_ranges, &split_ranges)
376-
}
377-
None => index_ranges,
378-
}),
373+
Some(index_ranges) => {
374+
has_bitmap_selection = selection.len() < file_meta.row_count as u64;
375+
Some(match split_ranges {
376+
Some(split_ranges) => {
377+
intersect_sorted_ranges(&index_ranges, &split_ranges)
378+
}
379+
None => index_ranges,
380+
})
381+
}
379382
None => split_ranges,
380383
}
381384
}
@@ -385,6 +388,13 @@ impl DataFileReader {
385388
dv.as_deref(),
386389
selected_ranges.as_deref(),
387390
);
391+
// Like Java, only a selective bitmap allows DV to narrow
392+
// sidecar eligibility. DV alone cannot trigger a ROW read.
393+
let sidecar_ranges = if has_bitmap_selection {
394+
row_selection.clone()
395+
} else {
396+
selected_ranges
397+
};
388398

389399
let mut stream = reader.read_single_file_stream_with_selection(
390400
&split,
@@ -480,8 +490,8 @@ impl DataFileReader {
480490
)
481491
}
482492

483-
/// Physical selection may be narrowed by file indexes or a LIMIT, while
484-
/// Java selects the ROW sidecar from the caller's original row ranges.
493+
/// The caller supplies sidecar candidates separately from physical ranges:
494+
/// a selective bitmap includes DV filtering, while LIMIT never affects it.
485495
pub(super) fn read_single_file_stream_with_requested_ranges(
486496
&self,
487497
split: &DataSplit,

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -213,8 +213,9 @@ fn selected_sidecar<'a>(
213213
{
214214
return Ok(None);
215215
}
216-
// The caller clips, sorts and merges the requested ranges into local
217-
// positions before intersecting them with indexes and deletion vectors.
216+
// The caller intersects requested ranges with bitmap indexes in local
217+
// positions, including DV only when a selective bitmap exists. LIMIT
218+
// never affects this decision.
218219
let selected: i64 = ranges.iter().map(RowRange::count).sum();
219220
Ok((selected > 0
220221
&& selected < file.row_count

0 commit comments

Comments
 (0)