Skip to content

Commit 86f1f26

Browse files
cetra3adriangbclaude
committed
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/parquet_metadata_statistics.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -72,7 +72,9 @@ fn parquet_metadata_statistics(c: &mut Criterion) {
7272
MetadataState::Mixed,
7373
MetadataState::None,
7474
];
75-
let column_counts = [8, 64, 256];
75+
// 1024 covers wide schemas, where the cost of resolving each field to a
76+
// parquet leaf column dominates.
77+
let column_counts = [8, 64, 256, 1024];
7678
let row_group_counts = [1, 32, 128];
7779

7880
let mut group = c.benchmark_group("parquet_metadata_statistics");
Lines changed: 293 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,293 @@
1+
// Licensed to the Apache Software Foundation (ASF) under one
2+
// or more contributor license agreements. See the NOTICE file
3+
// distributed with this work for additional information
4+
// regarding copyright ownership. The ASF licenses this file
5+
// to you under the Apache License, Version 2.0 (the
6+
// "License"); you may not use this file except in compliance
7+
// with the License. You may obtain a copy of the License at
8+
//
9+
// http://www.apache.org/licenses/LICENSE-2.0
10+
//
11+
// Unless required by applicable law or agreed to in writing,
12+
// software distributed under the License is distributed on an
13+
// "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
14+
// KIND, either express or implied. See the License for the
15+
// specific language governing permissions and limitations
16+
// under the License.
17+
18+
//! O(1) resolution of an Arrow field name to its Parquet leaf column index.
19+
20+
use arrow::datatypes::Schema;
21+
use datafusion_common::HashMap;
22+
use parquet::arrow::arrow_reader::statistics::StatisticsConverter;
23+
use parquet::schema::types::SchemaDescriptor;
24+
25+
/// Resolves Arrow field names to Parquet leaf column indices in O(1), after
26+
/// an O(N) build.
27+
///
28+
/// [`parquet::arrow::parquet_column`], and [`StatisticsConverter::try_new`]
29+
/// which calls it, is O(N) per lookup, so resolving every field of a file
30+
/// with it is O(N²). This resolver builds the lookup maps once per file
31+
/// instead.
32+
///
33+
/// Results match `parquet_column` exactly, including its tie-breaks (see
34+
/// [`Self::leaf_index`]). A mismatch would attribute one column's statistics
35+
/// to another, so the tests compare the two directly.
36+
pub(crate) struct LeafResolver<'a> {
37+
parquet_schema: &'a SchemaDescriptor,
38+
schema: &'a Schema,
39+
/// Arrow field name to root field index. The first field with a name
40+
/// wins, as in `Fields::find`.
41+
name_to_root: HashMap<&'a str, usize>,
42+
/// Parquet root index to its lowest leaf index, or `None` for a root
43+
/// with no leaves (an empty group).
44+
root_to_first_leaf: Vec<Option<usize>>,
45+
}
46+
47+
impl<'a> LeafResolver<'a> {
48+
pub(crate) fn new(parquet_schema: &'a SchemaDescriptor, schema: &'a Schema) -> Self {
49+
let fields = schema.fields();
50+
let mut name_to_root = HashMap::with_capacity(fields.len());
51+
for (idx, field) in fields.iter().enumerate() {
52+
name_to_root.entry(field.name().as_str()).or_insert(idx);
53+
}
54+
55+
let num_roots = parquet_schema.root_schema().get_fields().len();
56+
let mut root_to_first_leaf = vec![None; num_roots];
57+
// Iterate in reverse so the lowest leaf index for each root is kept.
58+
for leaf in (0..parquet_schema.columns().len()).rev() {
59+
let root = parquet_schema.get_column_root_idx(leaf);
60+
if root < num_roots {
61+
root_to_first_leaf[root] = Some(leaf);
62+
}
63+
}
64+
65+
Self {
66+
parquet_schema,
67+
schema,
68+
name_to_root,
69+
root_to_first_leaf,
70+
}
71+
}
72+
73+
/// The Parquet leaf column index for `name`.
74+
///
75+
/// Returns `None` in the same cases as [`parquet::arrow::parquet_column`]:
76+
/// * `name` is not in the Arrow schema,
77+
/// * the matched field is nested,
78+
/// * the matched root has no Parquet leaf columns.
79+
pub(crate) fn leaf_index(&self, name: &str) -> Option<usize> {
80+
self.resolve(name).map(|(_, leaf)| leaf)
81+
}
82+
83+
/// Build a [`StatisticsConverter`] for `name`.
84+
///
85+
/// When `name` has no leaf this falls back to
86+
/// [`StatisticsConverter::try_new`], which is O(N). The fallback gives the
87+
/// same error as `try_new` for an unknown column, and is needed because
88+
/// [`StatisticsConverter::from_column_index`] cannot express a column with
89+
/// no Parquet leaf. Flat schemas never take it.
90+
pub(crate) fn converter(
91+
&self,
92+
name: &str,
93+
) -> parquet::errors::Result<StatisticsConverter<'a>> {
94+
match self.resolve(name) {
95+
Some((root, leaf)) => StatisticsConverter::from_column_index(
96+
leaf,
97+
self.schema.field(root),
98+
self.parquet_schema,
99+
),
100+
None => StatisticsConverter::try_new(name, self.schema, self.parquet_schema),
101+
}
102+
}
103+
104+
/// The Arrow root index and Parquet leaf index for `name`.
105+
fn resolve(&self, name: &str) -> Option<(usize, usize)> {
106+
let root = *self.name_to_root.get(name)?;
107+
if self.schema.field(root).data_type().is_nested() {
108+
return None;
109+
}
110+
let leaf = self.root_to_first_leaf.get(root).copied().flatten()?;
111+
Some((root, leaf))
112+
}
113+
}
114+
115+
#[cfg(test)]
116+
mod tests {
117+
use super::*;
118+
use arrow::datatypes::{DataType, Field, Fields};
119+
use parquet::arrow::{ArrowSchemaConverter, parquet_column};
120+
use parquet::schema::parser::parse_message_type;
121+
use std::sync::Arc;
122+
123+
/// Primitives, a nested struct, a nested list, and a duplicate field name
124+
/// with a different type from the first.
125+
fn test_schema() -> Schema {
126+
Schema::new(vec![
127+
Field::new("a", DataType::Int64, true),
128+
Field::new("b", DataType::Utf8, true),
129+
Field::new(
130+
"s",
131+
DataType::Struct(Fields::from(vec![
132+
Field::new("x", DataType::Int32, true),
133+
Field::new("y", DataType::Int32, true),
134+
])),
135+
true,
136+
),
137+
Field::new(
138+
"l",
139+
DataType::List(Arc::new(Field::new("item", DataType::Int32, true))),
140+
true,
141+
),
142+
Field::new("c", DataType::Float64, true),
143+
// Unreachable by name: "a" resolves to index 0.
144+
Field::new("a", DataType::Utf8, true),
145+
])
146+
}
147+
148+
fn descriptor(message: &str) -> SchemaDescriptor {
149+
SchemaDescriptor::new(Arc::new(parse_message_type(message).unwrap()))
150+
}
151+
152+
/// Asserts `leaf_index` and `converter` agree with `parquet_column` and
153+
/// `try_new` for every field name in `schema`, plus some absent names.
154+
fn assert_matches_upstream(descr: &SchemaDescriptor, schema: &Schema) {
155+
let resolver = LeafResolver::new(descr, schema);
156+
157+
let mut names: Vec<&str> =
158+
schema.fields().iter().map(|f| f.name().as_str()).collect();
159+
names.extend(["missing", "", "A"]);
160+
161+
for name in names {
162+
let expected = parquet_column(descr, schema, name).map(|(idx, _)| idx);
163+
assert_eq!(
164+
resolver.leaf_index(name),
165+
expected,
166+
"leaf_index disagreed with parquet_column for {name:?}"
167+
);
168+
169+
match (
170+
resolver.converter(name),
171+
StatisticsConverter::try_new(name, schema, descr),
172+
) {
173+
(Ok(actual), Ok(expected)) => {
174+
assert_eq!(
175+
actual.parquet_column_index(),
176+
expected.parquet_column_index(),
177+
"converter targeted a different column for {name:?}"
178+
);
179+
assert_eq!(
180+
actual.arrow_field(),
181+
expected.arrow_field(),
182+
"converter used a different Arrow field for {name:?}"
183+
);
184+
}
185+
(Err(actual), Err(expected)) => {
186+
assert_eq!(actual.to_string(), expected.to_string());
187+
}
188+
(actual, expected) => panic!(
189+
"converter for {name:?} returned {:?}, try_new returned {:?}",
190+
actual.map(|c| c.parquet_column_index()),
191+
expected.map(|c| c.parquet_column_index()),
192+
),
193+
}
194+
}
195+
}
196+
197+
#[test]
198+
fn matches_upstream() {
199+
let schema = test_schema();
200+
let descr = ArrowSchemaConverter::new().convert(&schema).unwrap();
201+
assert_matches_upstream(&descr, &schema);
202+
}
203+
204+
#[test]
205+
fn resolves_expected_leaves() {
206+
let schema = test_schema();
207+
let descr = ArrowSchemaConverter::new().convert(&schema).unwrap();
208+
let resolver = LeafResolver::new(&descr, &schema);
209+
210+
assert_eq!(resolver.leaf_index("a"), Some(0));
211+
assert_eq!(resolver.leaf_index("b"), Some(1));
212+
// "s" has two leaves and "l" one, so "c" is leaf 5.
213+
assert_eq!(resolver.leaf_index("c"), Some(5));
214+
assert_eq!(resolver.leaf_index("s"), None);
215+
assert_eq!(resolver.leaf_index("l"), None);
216+
assert_eq!(resolver.leaf_index("missing"), None);
217+
}
218+
219+
/// The converter for a duplicated name must use the first field's type.
220+
#[test]
221+
fn duplicate_name_uses_first_field() {
222+
let schema = test_schema();
223+
let descr = ArrowSchemaConverter::new().convert(&schema).unwrap();
224+
let resolver = LeafResolver::new(&descr, &schema);
225+
226+
let converter = resolver.converter("a").unwrap();
227+
assert_eq!(converter.arrow_field().data_type(), &DataType::Int64);
228+
}
229+
230+
/// A root with no leaves must resolve to no leaf, even when the Arrow
231+
/// field at that index is a primitive.
232+
#[test]
233+
fn empty_group_root() {
234+
let descr = descriptor(
235+
"message schema {
236+
required int64 a;
237+
optional group g {}
238+
required int64 c;
239+
}",
240+
);
241+
let schema = Schema::new(vec![
242+
Field::new("a", DataType::Int64, false),
243+
Field::new("g", DataType::Int64, true),
244+
Field::new("c", DataType::Int64, false),
245+
]);
246+
assert_eq!(LeafResolver::new(&descr, &schema).leaf_index("g"), None);
247+
assert_matches_upstream(&descr, &schema);
248+
}
249+
250+
/// A primitive Arrow field over a multi-leaf Parquet root must resolve to
251+
/// the root's lowest leaf.
252+
#[test]
253+
fn multi_leaf_root_uses_lowest_leaf() {
254+
let descr = descriptor(
255+
"message schema {
256+
required int64 a;
257+
optional group g {
258+
required int64 x;
259+
required int64 y;
260+
}
261+
}",
262+
);
263+
let schema = Schema::new(vec![
264+
Field::new("a", DataType::Int64, false),
265+
Field::new("g", DataType::Int64, true),
266+
]);
267+
assert_eq!(LeafResolver::new(&descr, &schema).leaf_index("g"), Some(1));
268+
assert_matches_upstream(&descr, &schema);
269+
}
270+
271+
/// Arrow fields beyond the last Parquet root must resolve to no leaf.
272+
#[test]
273+
fn more_arrow_fields_than_parquet_roots() {
274+
let descr = descriptor("message schema { required int64 a; }");
275+
let schema = Schema::new(vec![
276+
Field::new("a", DataType::Int64, false),
277+
Field::new("b", DataType::Int64, true),
278+
]);
279+
assert_eq!(LeafResolver::new(&descr, &schema).leaf_index("b"), None);
280+
assert_matches_upstream(&descr, &schema);
281+
}
282+
283+
#[test]
284+
fn empty_schema() {
285+
let schema = Schema::empty();
286+
let descr = ArrowSchemaConverter::new().convert(&schema).unwrap();
287+
assert_eq!(
288+
LeafResolver::new(&descr, &schema).leaf_index("anything"),
289+
None
290+
);
291+
assert_matches_upstream(&descr, &schema);
292+
}
293+
}

0 commit comments

Comments
 (0)