Skip to content

Commit 0eecdfc

Browse files
authored
refactor(parquet): strip empty row groups so PreparedAccessPlan stays well-formed (apache#24509)
## Which issue does this PR close? - Closes apache#24287. ## Rationale for this change Split out from apache#23696 (per @adriangb's [decomposition proposal](apache#23696 (comment))). This keeps `PreparedAccessPlan` well-formed: a row group whose `RowSelection` selects zero rows is dropped so `with_row_groups(...)` never names a row group the push decoder would immediately skip. arrow-rs advances past an all-skipped row group inside `try_next_reader` without handing back a reader, so keeping such a row group in the plan would leave the plan's row-group list one entry longer than the readers produced. This is mostly **hardening** — the two in-tree flat-selection producers already avoid landing an empty `Selection` (`page_filter.rs` maps an all-skip selection to `Skip`; `try_new_from_overall_row_selection` normalizes via `RowGroupAccessBuilder::into_access`), and `RowGroupPruner` is gated off whenever a selection is live. There is, however, **one reachable producer**: `ParquetAccessPlan::scan_selection` intersects an existing `Selection` with a new one and can leave a row group selecting nothing (its `rows_selected > 0` guard checks the incoming selection, not the intersection). A well-formed plan here is also a precondition for re-enabling runtime pruning under a live selection (apache#24358) and for apache#23696. ## What changes are included in this PR? - `access_plan.rs`: `PreparedAccessPlan::prepare` calls a new generic `strip_empty_row_groups(row_group_indexes, row_selection, row_group_meta_data)`. It walks the flat `RowSelection` once with `OverallRowSelectionCursor` (the same single-pass approach `try_new_from_overall_row_selection` uses, rather than a per-row-group `split_off`) and keeps only row groups that still select a row. - `sort.rs`: `test_prepared_access_plan_reverse_empty_selection` — an all-skipped plan now strips to an empty plan. No `fully_matched` coupling, no public API change, no new metric, no slt churn. ## Are these changes tested? Yes — unit tests in `access_plan.rs`: - `test_strip_empty_row_groups_drops_only_empties` — mixed empty/non-empty row groups. - `test_strip_empty_row_groups_non_contiguous_indexes` — `vec![1, 3]` (RGs 0/2 skipped), pinning that `row_group_meta_data` is indexed absolutely. - `test_strip_empty_row_groups_none_selection_unchanged` — `None` passes through. - `test_prepare_strips_row_group_emptied_by_intersecting_selections` — the reachable `scan_selection` empty-intersection path, exercised through `prepare()`. ## Are there any user-facing changes? No. ## Follow-up @adriangb also suggested a complementary one-line normalization in `scan_selection` itself (empty intersection → `Skip`), which would keep `ParquetAccessPlan` well-formed for its other consumers (`row_group_indexes()`, metrics, `is_fully_matched`) too. Left out here to keep this PR scoped to apache#24287; happy to do it as a small follow-up.
1 parent dbdc627 commit 0eecdfc

2 files changed

Lines changed: 171 additions & 13 deletions

File tree

‎datafusion/datasource-parquet/src/access_plan.rs‎

Lines changed: 160 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -573,10 +573,83 @@ impl ParquetAccessPlan {
573573
let row_group_indexes = self.row_group_indexes();
574574
let row_selection = self.into_overall_row_selection(row_group_meta_data)?;
575575

576+
let (row_group_indexes, row_selection) =
577+
strip_empty_row_groups(row_group_indexes, row_selection, row_group_meta_data);
578+
576579
PreparedAccessPlan::new(row_group_indexes, row_selection)
577580
}
578581
}
579582

583+
/// Drop row groups whose post-pruning `RowSelection` selects zero rows, so the
584+
/// prepared plan stays well-formed: `with_row_groups(...)` never names a row
585+
/// group the decoder would immediately skip.
586+
///
587+
/// arrow-rs's push decoder silently advances past an all-skipped row group
588+
/// inside `try_next_reader` without handing back a reader, so keeping such a
589+
/// row group in the plan would leave its row-group list one entry longer than
590+
/// the readers the decoder produces. An empty selection is reachable today via
591+
/// [`ParquetAccessPlan::scan_selection`], which intersects an existing
592+
/// `Selection` with a new one and can leave a row group selecting nothing.
593+
/// A well-formed plan here is also a precondition for re-enabling runtime
594+
/// pruning under a live selection (#24358) and for #23696.
595+
///
596+
/// Walks the flat `RowSelection` once with [`OverallRowSelectionCursor`],
597+
/// rather than a per-row-group [`RowSelection::split_off`] (which reallocates
598+
/// the selector tail on every call, i.e. O(row groups × selectors)), keeping
599+
/// only the row groups that still select at least one row. `row_group_meta_data`
600+
/// is the **full file** metadata, indexed absolutely by row-group index, while
601+
/// `row_selection` covers only the scanned row groups — matching
602+
/// `into_overall_row_selection`, which emits nothing for a skipped row group.
603+
/// When `row_selection` is `None` no row group can be empty and the inputs are
604+
/// returned unchanged.
605+
fn strip_empty_row_groups(
606+
row_group_indexes: Vec<usize>,
607+
row_selection: Option<RowSelection>,
608+
row_group_meta_data: &[RowGroupMetaData],
609+
) -> (Vec<usize>, Option<RowSelection>) {
610+
let Some(selection) = row_selection else {
611+
return (row_group_indexes, None);
612+
};
613+
614+
let mut cursor = OverallRowSelectionCursor::new(selection);
615+
let mut kept_indexes = Vec::with_capacity(row_group_indexes.len());
616+
let mut kept_selectors: Vec<RowSelector> = Vec::new();
617+
618+
for &rg_idx in row_group_indexes.iter() {
619+
let rg_row_count = row_group_meta_data[rg_idx].num_rows() as usize;
620+
// Pull this row group's fragments off the shared cursor in a single
621+
// pass (no `split_off` tail reallocation).
622+
let start = kept_selectors.len();
623+
let mut selected = 0usize;
624+
let mut taken = 0usize;
625+
while taken < rg_row_count {
626+
let Some(fragment) = cursor.take(rg_row_count - taken) else {
627+
break;
628+
};
629+
taken += fragment.row_count;
630+
if !fragment.skip {
631+
selected += fragment.row_count;
632+
}
633+
kept_selectors.push(fragment);
634+
}
635+
if selected > 0 {
636+
kept_indexes.push(rg_idx);
637+
} else {
638+
// Empty row group: arrow-rs would silently skip it. Drop it and its
639+
// fragments so the plan stays 1:1 with the readers.
640+
kept_selectors.truncate(start);
641+
}
642+
}
643+
644+
let result_selection = if kept_selectors.is_empty() {
645+
None
646+
} else {
647+
Some(RowSelection::from(kept_selectors))
648+
};
649+
650+
(kept_indexes, result_selection)
651+
}
652+
580653
/// Represents a prepared, fully resolved [`ParquetAccessPlan`]
581654
///
582655
/// The [`RowSelection`] represents the result of applying all pruning such as
@@ -1430,4 +1503,91 @@ mod test {
14301503
// Ordered by min(a) ASC only: 3, 4, 5.
14311504
assert_eq!(result.row_group_indexes, vec![1, 2, 0]);
14321505
}
1506+
1507+
#[test]
1508+
fn test_strip_empty_row_groups_drops_only_empties() {
1509+
// 4 row groups of [10, 20, 30, 40] rows. RG 1 and RG 3 select nothing
1510+
// after pruning, so they must be dropped; RG 0 and RG 2 survive with
1511+
// their re-concatenated selections intact.
1512+
let selection = RowSelection::from(vec![
1513+
RowSelector::select(10), // RG 0: keep all 10
1514+
RowSelector::skip(30), // RG 1 (20) fully skipped + RG 2's leading 10
1515+
RowSelector::select(20), // RG 2: keep 20
1516+
RowSelector::skip(40), // RG 3: skip all 40
1517+
]);
1518+
1519+
let (indexes, result) = strip_empty_row_groups(
1520+
vec![0, 1, 2, 3],
1521+
Some(selection),
1522+
&ROW_GROUP_METADATA,
1523+
);
1524+
1525+
// RG 1 and RG 3 are dropped; the surviving indexes stay in order.
1526+
assert_eq!(indexes, vec![0, 2]);
1527+
let result = result.expect("survivors keep a selection");
1528+
assert_eq!(result.row_count(), 30); // 10 from RG 0 + 20 from RG 2
1529+
assert_eq!(result.skipped_row_count(), 10); // RG 2's leading skip
1530+
}
1531+
1532+
#[test]
1533+
fn test_strip_empty_row_groups_non_contiguous_indexes() {
1534+
// Only RG 1 (20 rows) and RG 3 (40 rows) are scanned — RG 0 and RG 2
1535+
// are whole-group skips, so the selection covers 20 + 40 = 60 rows.
1536+
// This pins down that `strip` indexes `row_group_meta_data`
1537+
// *absolutely* (meta[1]=20, meta[3]=40): a relative reading would take
1538+
// 10 then 20 rows and misalign the split.
1539+
let selection = RowSelection::from(vec![
1540+
RowSelector::skip(20), // RG 1: skip all 20 -> dropped
1541+
RowSelector::select(40), // RG 3: keep all 40
1542+
]);
1543+
1544+
let (indexes, result) =
1545+
strip_empty_row_groups(vec![1, 3], Some(selection), &ROW_GROUP_METADATA);
1546+
1547+
assert_eq!(indexes, vec![3]);
1548+
let result = result.expect("RG 3 survives");
1549+
assert_eq!(result.row_count(), 40);
1550+
assert_eq!(result.skipped_row_count(), 0);
1551+
}
1552+
1553+
#[test]
1554+
fn test_strip_empty_row_groups_none_selection_unchanged() {
1555+
// With no row selection no row group can be empty, so the inputs pass
1556+
// through unchanged.
1557+
let (indexes, result) =
1558+
strip_empty_row_groups(vec![0, 1, 2, 3], None, &ROW_GROUP_METADATA);
1559+
assert_eq!(indexes, vec![0, 1, 2, 3]);
1560+
assert!(result.is_none());
1561+
}
1562+
1563+
#[test]
1564+
fn test_prepare_strips_row_group_emptied_by_intersecting_selections() {
1565+
// The reachable producer: `scan_selection` intersects two disjoint
1566+
// selections within RG 1 to nothing, leaving an empty `Selection` in
1567+
// the plan (its own `rows_selected > 0` guard checks the incoming
1568+
// selection, not the intersection). `prepare` must strip that row
1569+
// group so the prepared plan never names a row group the decoder would
1570+
// silently skip.
1571+
let mut plan = ParquetAccessPlan::new_all(4); // RGs [10, 20, 30, 40]
1572+
1573+
// RG 1 (20 rows): select rows 0..10, then intersect with rows 10..20.
1574+
plan.scan_selection(
1575+
1,
1576+
RowSelection::from(vec![RowSelector::select(10), RowSelector::skip(10)]),
1577+
);
1578+
plan.scan_selection(
1579+
1,
1580+
RowSelection::from(vec![RowSelector::skip(10), RowSelector::select(10)]),
1581+
);
1582+
// RG 2 keeps a genuine partial selection so a flat selection is emitted.
1583+
plan.scan_selection(
1584+
2,
1585+
RowSelection::from(vec![RowSelector::skip(10), RowSelector::select(20)]),
1586+
);
1587+
1588+
let prepared = plan.prepare(&ROW_GROUP_METADATA).expect("prepare");
1589+
1590+
// RG 1 (emptied by the intersection) is stripped; RG 0/2/3 remain.
1591+
assert_eq!(prepared.row_group_indexes, vec![0, 2, 3]);
1592+
}
14331593
}

‎datafusion/datasource-parquet/src/sort.rs‎

Lines changed: 11 additions & 13 deletions
Original file line numberDiff line numberDiff line change
@@ -407,7 +407,8 @@ mod tests {
407407

408408
#[test]
409409
fn test_prepared_access_plan_reverse_empty_selection() {
410-
// Test: all rows are skipped
410+
// Test: all rows are skipped. After `strip_empty_row_groups`, every row
411+
// group's selection is empty, so the whole plan strips to nothing.
411412
let metadata = create_test_metadata(vec![100, 100, 100]);
412413

413414
let mut access_plan = ParquetAccessPlan::new_all(3);
@@ -423,21 +424,18 @@ mod tests {
423424
.prepare(rg_metadata)
424425
.expect("Failed to create PreparedAccessPlan");
425426

427+
// All row groups are empty after pruning, so they are stripped and the
428+
// prepared plan is empty (rather than carrying a selection that skips
429+
// every row).
430+
assert!(prepared_plan.row_group_indexes.is_empty());
431+
assert!(prepared_plan.row_selection.is_none());
432+
433+
// Reversing an empty plan stays empty.
426434
let reversed_plan = prepared_plan
427435
.reverse(&metadata)
428436
.expect("Failed to reverse PreparedAccessPlan");
429-
430-
// Should still skip all rows
431-
let total_selected: usize = reversed_plan
432-
.row_selection
433-
.as_ref()
434-
.unwrap()
435-
.iter()
436-
.filter(|s| !s.skip)
437-
.map(|s| s.row_count)
438-
.sum();
439-
440-
assert_eq!(total_selected, 0);
437+
assert!(reversed_plan.row_group_indexes.is_empty());
438+
assert!(reversed_plan.row_selection.is_none());
441439
}
442440

443441
#[test]

0 commit comments

Comments
 (0)