cetra3 opened a new pull request, #26355:
URL: https://github.com/apache/datafusion/pull/26355
## Which issue does this PR close?
- Part of #21968.
This revives #21987 by @adriangb, which was closed while stale and never
reviewed. The two commits are his, rebased onto current `main`. The fix was
never carried into #22829 or #22830, and the quadratic lookup is still on
`main`.
## Rationale for this change
Planning a query against a wide-schema Parquet table takes time quadratic in
the number of columns, even when the query reads only one or two of them.
`DFParquetMetadata::statistics_from_parquet_metadata` resolves every field
in the logical file schema to a Parquet leaf column. Both branches resolve each
field with an O(N) lookup:
- When the file has statistics, it calls `StatisticsConverter::try_new`.
That does a linear `Schema::column_with_name`, then calls `parquet_column`,
which does a linear `Fields::find` and a linear scan for the first leaf under
the matched root.
- When the file has no statistics, it calls `parquet_column` directly.
This happens once per field, so the cost is O(N²) per file, on every query
plan, for every file in the table.
## What changes are included in this PR?
- A new crate-private `LeafResolver`
(`datafusion/datasource-parquet/src/leaf_resolver.rs`). It builds two maps once
per file: Arrow field name to root index, and Parquet root index to first leaf
index. Both call sites use it in place of the per-field linear lookups, which
makes the statistics pass O(N) per file.
- `LeafResolver` gives the same results as `parquet_column`, including its
tie-breaks: the first Arrow field with a given name wins, and the lowest leaf
index for a root wins. When a leaf exists, it builds the converter with
`StatisticsConverter::from_column_index`, which yields the same converter
`try_new` would (same leaf index, same Arrow field, same physical type).
- A field with no Parquet leaf (a nested type, or a name missing from the
file schema) falls back to `StatisticsConverter::try_new`. This reproduces its
exact error for an unknown column, and it is needed because `from_column_index`
cannot express "this column has no Parquet leaf".
- The `parquet_metadata_statistics` benchmark now also covers 1024 columns,
because the quadratic term only shows up past a few hundred columns.
Rebasing onto `main` conflicted in `statistics_from_parquet_metadata`. The
resolution keeps every change made on `main` since #21987, including the
omitted-null-count handling and the untrusted min/max order checks, and changes
only how each field's converter is built.
**Known limitation:** schemas with many nested fields still take the O(N)
fallback for those fields. apache/arrow-rs#9882 proposes a constructor that
takes an `Option<usize>` leaf, which would remove the fallback. Flat wide
schemas never take it.
## What is the testing strategy for this PR?
- Six unit tests in `leaf_resolver.rs`. The main one is a differential test:
for every field name in a schema that mixes primitives, a nested struct, a
nested list, duplicate field names and absent names, `LeafResolver::leaf_index`
must return exactly what `parquet_column` returns. The tie-break rules are the
risky part: getting either backwards would silently attribute one column's
statistics to another, and nothing in the existing suite covers duplicate
names. The other tests cover:
- nested and missing names resolving to no leaf
- converters built through the resolver matching `try_new`
- byte-identical error text for an unknown column
- an empty schema
- Existing suites: `-p datafusion-datasource-parquet --lib`, `-p datafusion
--test parquet_integration`, and the `parquet_statistics`,
`listing_table_statistics`, `parquet_sorted_statistics` and
`parquet_nested_schema_pruning` sqllogictest files.
### Benchmarks
`wide_schema` (1024 vs 8 columns × 256 files), run locally on an AMD Ryzen 9
9950X3D. These are Criterion medians, `main` (e732212ca) against this branch:
| Query | main | this PR | change |
|---|---:|---:|---:|
| Q01 wide | 694.5 ms | 522.9 ms | −24.7% |
| Q02 wide | 528.0 ms | 350.3 ms | −33.7% |
| Q03 wide | 529.2 ms | 353.4 ms | −33.2% |
| Q04 wide | 617.2 ms | 445.5 ms | −27.8% |
| Q01–Q04 narrow | — | — | within ±0.5% |
For every wide query the confidence intervals do not overlap. The two sides
ran one after the other on the same machine, not interleaved.
## Are there any user-facing changes?
No. `LeafResolver` is crate-private and the statistics produced are
unchanged. Planning against wide-schema Parquet tables is faster.
---
This PR was prepared with AI assistance (Claude Code).
🤖 Generated with [Claude Code](https://claude.com/claude-code)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: [email protected]
For queries about this service, please contact Infrastructure at:
[email protected]
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
