cetra3 opened a new pull request, #26630:
URL: https://github.com/apache/datafusion/pull/26630
## Which issue does this PR close?
- Closes #26314.
## Rationale for this change
Planning a query over a wide table is quadratic in the number of columns.
`DFSchema::index_of_column_by_name` and the other name lookups compare the name
against every field, and they run for every column of every projection the SQL
planner, analyzer and optimizer build. With 10,240 columns, planning `SELECT *`
over a single Parquet file takes about 0.74 s, while `SELECT id` on the same
file takes 23 ms.
## What changes are included in this PR?
- `DFSchema` builds a name → field positions index on first lookup, once the
schema has more than `LINEAR_NAME_SCAN_MAX` (8) fields. Narrower schemas keep
the existing linear scan, so the common case pays nothing extra. This follows
the same pattern as `LINEAR_FIELD_SCAN_MAX` in Parquet nested schema pruning.
- The index is a `hashbrown::HashTable<usize>` of field positions plus a
`next` list linking fields that share a name. No names are copied, and lookups
compare against the schema's own fields, as `ArrayStaticFilter` does for `IN`
lists.
- These lookups go through the index:
- `index_of_column_by_name`
- `qualified_fields_with_unqualified_name`
- `fields_with_unqualified_name`
- `columns_with_unqualified_name`
- `has_column_with_unqualified_name`
- `has_column_with_qualified_name`
Each applies the same qualifier rules in field order as before, so results
are unchanged, including which duplicate wins.
- The index is derived from the field names alone:
- Clones, `strip_qualifiers`, `replace_qualifier` and
`with_field_specific_qualified_schema` share it.
- `merge` resets it.
- `PartialEq` and `Debug` are now written by hand to leave it out, so plan
snapshots don't change.
- `clippy.toml`: add `datafusion_common::DFSchema` to
`ignore-interior-mutability`. The `OnceLock` holding the index otherwise trips
`mutable_key_type` wherever an `Expr` or `LogicalPlan` is used as a hash key.
The lint doesn't apply here because `Hash` and `Eq` ignore the index.
Downstream crates that lint with `-D warnings` and use `Expr` as a key may need
the same entry. Building the index eagerly would avoid that, at the cost of
building it for wide schemas that are never queried.
## What is the testing strategy for this PR?
- `name_index_matches_scan` compares every converted lookup against the
previous linear scan at widths 8, 9 and 100. The schema has the same name under
several qualifiers, unqualified duplicates, a partial qualifier, a non-ASCII
name and missing names. Reversing the duplicate order makes it fail.
- `name_index_follows_schema_changes` covers sharing across clones and
qualifier rewrites, and the reset in `merge`.
- Existing tests and sqllogictests pass unchanged.
### Benchmarks (local, `release-nonlto`, `main` vs this PR)
| Benchmark | `main` | This PR | Change |
|---|---|---|---|
| Plan `SELECT *` over one 10,240-column Parquet file | 0.74 s | 0.095 s |
7.8× faster |
| `logical_select_all_from_1000` | 4.28 ms | 1.38 ms | −68% |
| `physical_select_all_from_1000` | 10.76 ms | 3.55 ms | −67% |
| `optimizer_select_all_from_1000` | 4.36 ms | 1.46 ms | −67% |
| `with_param_values_many_columns` | 231 µs | 146 µs | −37% |
| `logical_union_8_branches`, `logical_correlated_subquery_in`,
`physical_join_distinct`, `physical_unnest_to_join`, `physical_plan_tpch_all`,
`optimizer_tpcds_all` | | | within noise |
In the noise row, `main` rerun against its own saved baseline drifted by
+0.5% to +3% on the same benchmarks, and this PR stayed inside that range.
## Are there any user-facing changes?
Faster planning on wide schemas. There are no API changes: lookup results,
`Debug` output and `Hash`/`Eq` behaviour are unchanged.
🤖 Generated with [Claude Code](https://claude.com/claude-code)
https://claude.ai/code/session_01FmZ3Fcw2tCfc7VGTQ8UnVB
--
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]
