Repository navigation
Commit 86f1f26
perf: resolve parquet leaf columns in O(1) during statistics collection (apache#26355)
## Which issue does this PR close?
- Part of apache#21968.
This revives apache#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 apache#22829 or apache#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 apache#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?
- Seven unit tests in `leaf_resolver.rs`. Five of them check, for every
field name plus some absent names, that `LeafResolver::leaf_index`
returns exactly what `parquet_column` returns and that
`LeafResolver::converter` matches `StatisticsConverter::try_new` (same
leaf index, same Arrow field, same error text). 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 two check specific leaf indices, and that a
duplicated name uses the first field's type. The schemas cover:
- primitives, a nested struct, a nested list, and a duplicate field name
with a different type from the first
- a primitive Arrow field over a multi-leaf Parquet group (lowest leaf
wins)
- a Parquet root with no leaves (an empty group)
- more Arrow fields than Parquet roots
- an empty schema
- No `.slt` test: this changes how columns are looked up, not the
statistics produced, so the unit tests compare directly against
`parquet_column` and `try_new`.
- 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` (e732212) 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)
---------
Co-authored-by: Adrian Garcia Badaracco <[email protected]>
Co-authored-by: Claude Opus 5 <[email protected]>1 parent 5e44766 commit 86f1f26
4 files changed
Lines changed: 352 additions & 59 deletions
File tree
- datafusion/datasource-parquet
- benches
- src
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
72 | 72 | | |
73 | 73 | | |
74 | 74 | | |
75 | | - | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
76 | 78 | | |
77 | 79 | | |
78 | 80 | | |
| |||
| Original file line number | Diff line number | Diff line change | |
|---|---|---|---|
| |||
| 1 | + | |
| 2 | + | |
| 3 | + | |
| 4 | + | |
| 5 | + | |
| 6 | + | |
| 7 | + | |
| 8 | + | |
| 9 | + | |
| 10 | + | |
| 11 | + | |
| 12 | + | |
| 13 | + | |
| 14 | + | |
| 15 | + | |
| 16 | + | |
| 17 | + | |
| 18 | + | |
| 19 | + | |
| 20 | + | |
| 21 | + | |
| 22 | + | |
| 23 | + | |
| 24 | + | |
| 25 | + | |
| 26 | + | |
| 27 | + | |
| 28 | + | |
| 29 | + | |
| 30 | + | |
| 31 | + | |
| 32 | + | |
| 33 | + | |
| 34 | + | |
| 35 | + | |
| 36 | + | |
| 37 | + | |
| 38 | + | |
| 39 | + | |
| 40 | + | |
| 41 | + | |
| 42 | + | |
| 43 | + | |
| 44 | + | |
| 45 | + | |
| 46 | + | |
| 47 | + | |
| 48 | + | |
| 49 | + | |
| 50 | + | |
| 51 | + | |
| 52 | + | |
| 53 | + | |
| 54 | + | |
| 55 | + | |
| 56 | + | |
| 57 | + | |
| 58 | + | |
| 59 | + | |
| 60 | + | |
| 61 | + | |
| 62 | + | |
| 63 | + | |
| 64 | + | |
| 65 | + | |
| 66 | + | |
| 67 | + | |
| 68 | + | |
| 69 | + | |
| 70 | + | |
| 71 | + | |
| 72 | + | |
| 73 | + | |
| 74 | + | |
| 75 | + | |
| 76 | + | |
| 77 | + | |
| 78 | + | |
| 79 | + | |
| 80 | + | |
| 81 | + | |
| 82 | + | |
| 83 | + | |
| 84 | + | |
| 85 | + | |
| 86 | + | |
| 87 | + | |
| 88 | + | |
| 89 | + | |
| 90 | + | |
| 91 | + | |
| 92 | + | |
| 93 | + | |
| 94 | + | |
| 95 | + | |
| 96 | + | |
| 97 | + | |
| 98 | + | |
| 99 | + | |
| 100 | + | |
| 101 | + | |
| 102 | + | |
| 103 | + | |
| 104 | + | |
| 105 | + | |
| 106 | + | |
| 107 | + | |
| 108 | + | |
| 109 | + | |
| 110 | + | |
| 111 | + | |
| 112 | + | |
| 113 | + | |
| 114 | + | |
| 115 | + | |
| 116 | + | |
| 117 | + | |
| 118 | + | |
| 119 | + | |
| 120 | + | |
| 121 | + | |
| 122 | + | |
| 123 | + | |
| 124 | + | |
| 125 | + | |
| 126 | + | |
| 127 | + | |
| 128 | + | |
| 129 | + | |
| 130 | + | |
| 131 | + | |
| 132 | + | |
| 133 | + | |
| 134 | + | |
| 135 | + | |
| 136 | + | |
| 137 | + | |
| 138 | + | |
| 139 | + | |
| 140 | + | |
| 141 | + | |
| 142 | + | |
| 143 | + | |
| 144 | + | |
| 145 | + | |
| 146 | + | |
| 147 | + | |
| 148 | + | |
| 149 | + | |
| 150 | + | |
| 151 | + | |
| 152 | + | |
| 153 | + | |
| 154 | + | |
| 155 | + | |
| 156 | + | |
| 157 | + | |
| 158 | + | |
| 159 | + | |
| 160 | + | |
| 161 | + | |
| 162 | + | |
| 163 | + | |
| 164 | + | |
| 165 | + | |
| 166 | + | |
| 167 | + | |
| 168 | + | |
| 169 | + | |
| 170 | + | |
| 171 | + | |
| 172 | + | |
| 173 | + | |
| 174 | + | |
| 175 | + | |
| 176 | + | |
| 177 | + | |
| 178 | + | |
| 179 | + | |
| 180 | + | |
| 181 | + | |
| 182 | + | |
| 183 | + | |
| 184 | + | |
| 185 | + | |
| 186 | + | |
| 187 | + | |
| 188 | + | |
| 189 | + | |
| 190 | + | |
| 191 | + | |
| 192 | + | |
| 193 | + | |
| 194 | + | |
| 195 | + | |
| 196 | + | |
| 197 | + | |
| 198 | + | |
| 199 | + | |
| 200 | + | |
| 201 | + | |
| 202 | + | |
| 203 | + | |
| 204 | + | |
| 205 | + | |
| 206 | + | |
| 207 | + | |
| 208 | + | |
| 209 | + | |
| 210 | + | |
| 211 | + | |
| 212 | + | |
| 213 | + | |
| 214 | + | |
| 215 | + | |
| 216 | + | |
| 217 | + | |
| 218 | + | |
| 219 | + | |
| 220 | + | |
| 221 | + | |
| 222 | + | |
| 223 | + | |
| 224 | + | |
| 225 | + | |
| 226 | + | |
| 227 | + | |
| 228 | + | |
| 229 | + | |
| 230 | + | |
| 231 | + | |
| 232 | + | |
| 233 | + | |
| 234 | + | |
| 235 | + | |
| 236 | + | |
| 237 | + | |
| 238 | + | |
| 239 | + | |
| 240 | + | |
| 241 | + | |
| 242 | + | |
| 243 | + | |
| 244 | + | |
| 245 | + | |
| 246 | + | |
| 247 | + | |
| 248 | + | |
| 249 | + | |
| 250 | + | |
| 251 | + | |
| 252 | + | |
| 253 | + | |
| 254 | + | |
| 255 | + | |
| 256 | + | |
| 257 | + | |
| 258 | + | |
| 259 | + | |
| 260 | + | |
| 261 | + | |
| 262 | + | |
| 263 | + | |
| 264 | + | |
| 265 | + | |
| 266 | + | |
| 267 | + | |
| 268 | + | |
| 269 | + | |
| 270 | + | |
| 271 | + | |
| 272 | + | |
| 273 | + | |
| 274 | + | |
| 275 | + | |
| 276 | + | |
| 277 | + | |
| 278 | + | |
| 279 | + | |
| 280 | + | |
| 281 | + | |
| 282 | + | |
| 283 | + | |
| 284 | + | |
| 285 | + | |
| 286 | + | |
| 287 | + | |
| 288 | + | |
| 289 | + | |
| 290 | + | |
| 291 | + | |
| 292 | + | |
| 293 | + | |
0 commit comments