Skip to content

Commit 341e173

Browse files
goutamadwantthorrester
authored andcommitted
feat: union nested Parquet leaves across projection accesses (apache#24130)
## Which issue does this PR close? - Closes apache#24121. ## Rationale for this change When one projected nested column is consumed through multiple narrowing casts, or through both a narrowing cast and `get_field`, the Parquet read plan currently falls back to reading the entire root column. The leaves required by those consumers can be combined, so reading the full root performs unnecessary I/O. ## What changes are included in this PR? - Accumulate and deduplicate the leaf offsets required by every narrowing cast on a root column. - Add leaves required by `get_field` accesses to the same union. - Derive the Arrow type emitted by the reader from the merged leaf set while retaining a full-read fallback for unsupported partial wrapper shapes. - Add coverage for disjoint, overlapping, and repeated casts, cast plus `get_field`, and casts that diverge below `List<Struct>`. ## Are these changes tested? Yes. The following checks pass: - `cargo fmt --all -- --check` - `cargo test -p datafusion-datasource-parquet --lib` - `cargo test --profile=ci --test sqllogictests -- parquet_nested_schema_pruning.slt` - `cargo clippy -p datafusion-datasource-parquet --all-targets --all-features -- -D warnings` The SQL logic test also verifies that the merged projections return the expected values and scan fewer bytes than a full-root read. ## Are there any user-facing changes? No API or SQL behavior changes. Queries with multiple nested accesses to the same Parquet root can read fewer leaf columns. (cherry picked from commit f660ee5)
1 parent 7d3835c commit 341e173

3 files changed

Lines changed: 287 additions & 79 deletions

File tree

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

Lines changed: 109 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -128,6 +128,35 @@ pub(crate) fn clip_for_cast(
128128
Some((kept, pruned_type))
129129
}
130130

131+
/// Rebuilds `physical` for a sorted, deduplicated subset of its leaf offsets.
132+
///
133+
/// This is the second half of merging several nested accesses to one root:
134+
/// callers union the offsets required by each access, then use this function
135+
/// to derive the Arrow type the Parquet reader emits for that union. Partial
136+
/// projection is supported through the same struct, list, and large-list
137+
/// shapes as [`clip_for_cast`]. Any partial selection below another wrapper
138+
/// returns `None`, preserving the total-fallback property of cast clipping.
139+
pub(crate) fn type_for_leaf_subset(
140+
physical: &DataType,
141+
kept: &[usize],
142+
) -> Option<DataType> {
143+
let total = count_leaves(physical);
144+
if kept.is_empty()
145+
|| kept.len() >= total
146+
|| kept.windows(2).any(|pair| pair[0] >= pair[1])
147+
|| kept.last().is_some_and(|last| *last >= total)
148+
{
149+
return None;
150+
}
151+
152+
let mut next_leaf = 0;
153+
let projected = project_type_for_leaves(physical, kept, &mut next_leaf);
154+
if projected.is_ok() {
155+
debug_assert_eq!(next_leaf, total, "leaf accounting must cover the type");
156+
}
157+
projected.ok().flatten()
158+
}
159+
131160
/// Number of Parquet leaf columns a (Parquet-derived) Arrow type occupies.
132161
pub(crate) fn count_leaves(dt: &DataType) -> usize {
133162
match dt {
@@ -249,6 +278,54 @@ fn clip_type(
249278
}
250279
}
251280

281+
/// Rebuilds one physical type subtree for `kept` leaf offsets.
282+
///
283+
/// `Ok(None)` means no selected leaf lies below this subtree. `Err(())` means
284+
/// only part of an unsupported wrapper was selected, so the caller must fall
285+
/// back to reading the full root.
286+
fn project_type_for_leaves(
287+
physical: &DataType,
288+
kept: &[usize],
289+
next_leaf: &mut usize,
290+
) -> Result<Option<DataType>, ()> {
291+
match physical {
292+
DataType::Struct(fields) => {
293+
let mut projected = Vec::with_capacity(fields.len());
294+
for field in fields {
295+
if let Some(dt) =
296+
project_type_for_leaves(field.data_type(), kept, next_leaf)?
297+
{
298+
projected.push(field_with_type(field, dt));
299+
}
300+
}
301+
Ok((!projected.is_empty()).then(|| DataType::Struct(projected.into())))
302+
}
303+
DataType::List(item) => {
304+
Ok(project_type_for_leaves(item.data_type(), kept, next_leaf)?
305+
.map(|projected| DataType::List(field_with_type(item, projected))))
306+
}
307+
DataType::LargeList(item) => {
308+
Ok(project_type_for_leaves(item.data_type(), kept, next_leaf)?
309+
.map(|projected| DataType::LargeList(field_with_type(item, projected))))
310+
}
311+
_ => {
312+
let start = *next_leaf;
313+
let end = start + count_leaves(physical);
314+
let selected_start = kept.partition_point(|leaf| *leaf < start);
315+
let selected_end = kept.partition_point(|leaf| *leaf < end);
316+
let selected = selected_end - selected_start;
317+
*next_leaf = end;
318+
if selected == 0 {
319+
Ok(None)
320+
} else if selected == end - start {
321+
Ok(Some(physical.clone()))
322+
} else {
323+
Err(())
324+
}
325+
}
326+
}
327+
}
328+
252329
/// Keep every leaf of `dt` (no pruning below this point); returns `dt`
253330
/// unchanged since nothing was clipped.
254331
fn keep_all_leaves(
@@ -455,6 +532,38 @@ mod tests {
455532
assert_eq!(emitted, list_of(struct_of(vec![int64("x"), utf8("y")])));
456533
}
457534

535+
/// A union assembled from two casts below a shared List<Struct> prefix
536+
/// reconstructs one emitted type in physical field order.
537+
#[test]
538+
fn type_for_leaf_subset_unions_nested_cast_leaves() {
539+
let physical = list_of(struct_of(vec![int64("x"), utf8("y"), utf8("pad")]));
540+
let emitted = type_for_leaf_subset(&physical, &[0, 1]).unwrap();
541+
assert_eq!(emitted, list_of(struct_of(vec![int64("x"), utf8("y")])));
542+
}
543+
544+
/// A complete leaf set has nothing to prune, so callers must retain the
545+
/// original root type rather than treating it as a clipped projection.
546+
#[test]
547+
fn type_for_leaf_subset_rejects_complete_selection() {
548+
let physical = struct_of(vec![int64("x"), utf8("y"), utf8("pad")]);
549+
assert!(type_for_leaf_subset(&physical, &[0, 1, 2]).is_none());
550+
}
551+
552+
/// Partial selection below a wrapper cast clipping does not understand
553+
/// must fall back instead of predicting a type the reader may not emit.
554+
#[test]
555+
fn type_for_leaf_subset_rejects_unsupported_partial_wrapper() {
556+
let physical = DataType::FixedSizeList(
557+
Arc::new(Field::new(
558+
"item",
559+
struct_of(vec![int64("x"), utf8("pad")]),
560+
true,
561+
)),
562+
2,
563+
);
564+
assert!(type_for_leaf_subset(&physical, &[0]).is_none());
565+
}
566+
458567
/// Two levels of `list<struct>` nesting, the inner one also narrowed,
459568
/// the `events: array<struct<..., items: array<struct<...>>>>` shape
460569
/// reported in `datafusion-comet#4859`, where a sibling struct field at

0 commit comments

Comments
 (0)