Repository navigation
perf: index DFSchema field names to avoid quadratic lookups on wide schemas - #26630
Conversation
…chemas `DFSchema` resolved a column by comparing its name against every field, so resolving N columns against an N-column schema was O(N^2). This runs for every projection built by the SQL planner, the analyzer and the optimizer, which made logical planning of `SELECT *` over wide tables quadratic in the column count. Schemas wider than `LINEAR_NAME_SCAN_MAX` (8) fields now build a name index on first lookup. It stores field positions rather than copies of the names, is shared by clones and qualifier rewrites, and is reset by `merge`. Narrower schemas keep the linear scan. The index takes no part in `Hash`, `Eq` or `Debug`, so `DFSchema` remains a sound hash key; `clippy.toml` tells `mutable_key_type` to ignore its `OnceLock`. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01FmZ3Fcw2tCfc7VGTQ8UnVB
|
run benchmark sql_planner |
|
🤖 Benchmark running (GKE) | trigger CPU Details (lscpu)Comparing dfschema-name-index (e7f471d) to 5026ac4 (merge-base) diff Run configurationrun benchmark sql_planner
env:
BENCH_FILTER: "select_all_from_1000|with_param_values_many_columns|logical_union_8_branches|logical_correlated_subquery_in|physical_join_distinct|physical_unnest_to_join|physical_plan_tpch_all"Results will be posted here when complete File an issue against this benchmark runner |
|
🤖 Benchmark completed (GKE) | trigger Instance: Comparing dfschema-name-index (e7f471d) to 5026ac4 (merge-base) diff Run configurationrun benchmark sql_planner
env:
BENCH_FILTER: "select_all_from_1000|with_param_values_many_columns|logical_union_8_branches|logical_correlated_subquery_in|physical_join_distinct|physical_unnest_to_join|physical_plan_tpch_all"CPU Details (lscpu)Details
Resource Usagesql_planner — base (merge-base)
sql_planner — branch
File an issue against this benchmark runner |
|
interesting, thanks @cetra3 checking |
comphead
left a comment
comphead
left a comment
There was a problem hiding this comment.
qualified_field_with_unqualified_nameis the hot path for unqualified columns and was left unchanged. It collects all matches into aVecand then builds a secondVecfor the unqualified ones. Withindices_of_namethe match count and the single unqualified match can be found in one walk without allocating. Optional and unmeasured.
| /// Derived from the field names alone, so it is shared by clones and by | ||
| /// schemas that only change qualifiers, and must be reset whenever `inner` | ||
| /// changes. It takes no part in equality, hashing or `Debug` output. | ||
| name_index: OnceLock<Arc<NameIndex>>, |
There was a problem hiding this comment.
The OnceLock makes DFSchema interior mutable for clippy::mutable_key_type. A std-only crate confirms the lint propagates through Arc<LogicalPlan>, so a downstream HashSet<Expr> or HashMap<LogicalPlan, _> that lints with -D warnings can start failing. The clippy.toml entry only covers this workspace. That is a visible change for a PR that lists no API changes.
check_names already runs a BTreeSet pass over every field on each construction. Building the index eagerly (for example an Option<Arc<NameIndex>> set in the constructors above the threshold) may therefore cost less than that pass. That is an expectation, not a measurement. Could you bench an eager variant with sql_planner? If it is close, it drops the lint change and the lazy-init state. It interacts with the threshold comment below, since eager builds also hit schemas that are never probed.
There was a problem hiding this comment.
I benchmarked an eager variant, which builds the index in the constructors once a schema has more than 8 fields. sql_planner against main, both variants from the same run:
| Benchmark | Eager | Lazy (this PR) |
|---|---|---|
logical_select_one_from_700 |
+7.8% | +0.5% |
logical_union_8_branches |
+6.9% | +1.3% |
physical_join_distinct |
+5.5% | +0.2% |
*_select_all_from_1000 |
−67% | −67% |
Most wide schemas built during planning are never looked up by name, so eager pays for indexes that are never used. I've kept lazy.
You're right that the lint change is user-facing, so I've added it to the user-facing section of the PR body: downstream crates that use Expr or LogicalPlan as hash keys and lint with -D warnings need datafusion_common::DFSchema in ignore-interior-mutability.
| /// field; wider ones use a lazily built [`NameIndex`]. Below it, the scan is | ||
| /// cheaper than building the index (the same trade-off as | ||
| /// `LINEAR_FIELD_SCAN_MAX` in `datafusion-datasource-parquet`). | ||
| const LINEAR_NAME_SCAN_MAX: usize = 8; |
There was a problem hiding this comment.
8 looks low. The benchmark run on this PR shows logical_union_8_branches at 625.7 ±2.0 µs on the base and 642.7 ±1.7 µs here (+2.7%), and logical_correlated_subquery_in at 208.9 vs 212.2 µs (+1.6%). Both queries use t1/t2 with 200 columns and project two of them, so each scan schema pays an O(W) index build for two lookups that a scan likely answers more cheaply (not measured). The PR body lists these as within noise, but the intervals do not overlap. SELECT a, b FROM wide_table is the common shape, so this is the case to protect.
The linked issue suggested a break-even near 64 fields. Could you add a width sweep (for example 9, 16, 32, 64, 128, 200) with 2 lookups and with W lookups, and choose the threshold from that? The SELECT id case on the 10,240-column file (23 ms on main) is also missing from the benchmark table.
There was a problem hiding this comment.
You're right that both regressions are real; the "within noise" line came from a bad local run. I've done a sweep with sql_planner. Each threshold was run twice, interleaved with three runs of main that agreed within ±0.3%:
| Benchmark | main |
8 (this PR) | 64 | 256 |
|---|---|---|---|---|
logical_union_8_branches |
339.1 µs | +2.1% / +1.8% | +2.2% / +2.1% | −0.2% / −0.3% |
logical_correlated_subquery_in |
109.9 µs | +1.7% / +1.4% | +1.4% / +1.2% | +0.2% / −0.3% |
with_param_values_many_columns |
228.0 µs | −36.8% / −36.8% | −35.4% / −35.7% | −16.4% / −14.8% |
logical_trivial_join_high_numbered_columns |
113.2 µs | −6.7% / −6.3% | −6.9% / −6.5% | −6.7% / −6.6% |
physical_many_self_joins |
4.36 ms | −5.6% / −5.9% | −6.1% / −5.8% | −5.8% / −5.0% |
*_select_all_from_1000 (3 benchmarks) |
4.2–10.6 ms | −67% | −67% | −67% |
optimizer_tpcds_all |
155.5 ms | −2.8% / −2.7% | −2.7% / −2.3% | −1.8% / −2.4% |
| Other 6 benchmarks | within ±2% | within ±2% | within ±2% |
64 behaves the same as 8, since no schema in these benchmarks has between 9 and 64 columns. 256 removes the cost on union_8 and correlated_in, but with_param_values_many_columns plans SELECT MAX(a0), …, MAX(a199) over the same 200-column t1, and it loses about 20 points.
So on the same 200-column table, the index costs about 7 µs when 2 columns are projected and saves about 46 µs when 200 are. Width alone can't tell those apart. A local microbenchmark agrees: building the index costs about 4 ns per field, and it pays for itself after 4–8 lookups at every width from 32 to 1000. I've kept 8, so the remaining cost is bounded by one index build per wide schema that gets looked up.
SELECT id over the 10,240-column file takes 23 ms on both main and this PR.
| field_qualifiers: vec![None; self.inner.fields.len()], | ||
| inner: self.inner, | ||
| functional_dependencies: self.functional_dependencies, | ||
| name_index: self.name_index, |
There was a problem hiding this comment.
Sharing the index here, in replace_qualifier and in with_field_specific_qualified_schema only helps when the source schema was probed before the rewrite. Outside tests these have a few callers (substrait read, the unparser rewrite, a physical planner join-schema helper) and none in the analyzer or optimizer rules the PR targets. Unless a profile shows one of them hot, I would drop these moves and keep the index tied to Clone and merge only. That shrinks the "index follows inner" invariant to two places and removes the Arc::ptr_eq assertions on the rewrite paths from the test.
There was a problem hiding this comment.
Agreed. None of those callers are on the analyzer or optimizer paths, and in most of them the source schema hasn't been probed, so sharing buys nothing. In 5d6c906 the rewrites start with an empty index, so it only follows Clone, and merge resets it. I've dropped the rewrite assertion from the test.
Compare `fields_with_unqualified_name` and `columns_with_unqualified_name` with a scan, and check that a probed schema equals an unprobed one under `PartialEq` and `Debug`. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01FmZ3Fcw2tCfc7VGTQ8UnVB
Qualifier rewrites now start with an empty index. Their callers are outside the planning paths the index targets and rarely see a probed schema, so sharing saved nothing and widened the invariant. Co-Authored-By: Claude Opus 5.5 <[email protected]> Claude-Session: https://claude.ai/code/session_01FmZ3Fcw2tCfc7VGTQ8UnVB
jayzhan211
left a comment
jayzhan211
left a comment
There was a problem hiding this comment.
@cetra3 thanks for this. The index matches the scan, it's reset everywhere inner changes, and the bot numbers line up with what you reported. Approving.
Optional: the clippy mutable_key_type note for downstream crates is currently only in the PR body. Could you add a short entry to docs/source/library-user-guide/upgrading/56.0.0.md as well? People who use Expr or LogicalPlan as hash keys and lint with -D warnings will look there when their CI breaks. Something like:
# clippy.toml
ignore-interior-mutability = ["datafusion_common::DFSchema"]
|
Merging this one in to keep things moving. Let's do the updates as a follow on PR |
Which issue does this PR close?
DFSchemacolumn lookup is a linear scan, making logical planning and type coercion quadratic in schema width #26314.Rationale for this change
Planning a query over a wide table is quadratic in the number of columns.
DFSchema::index_of_column_by_nameand 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, planningSELECT *over a single Parquet file takes about 0.74 s, whileSELECT idon the same file takes 23 ms.What changes are included in this PR?
DFSchemabuilds a name → field positions index on first lookup, once the schema has more thanLINEAR_NAME_SCAN_MAX(8) fields. Narrower schemas keep the existing linear scan, so the common case pays nothing extra. This follows the same pattern asLINEAR_FIELD_SCAN_MAXin Parquet nested schema pruning.The index is a
hashbrown::HashTable<usize>of field positions plus anextlist linking fields that share a name. No names are copied, and lookups compare against the schema's own fields, asArrayStaticFilterdoes forINlists.These lookups go through the index:
index_of_column_by_namequalified_fields_with_unqualified_namefields_with_unqualified_namecolumns_with_unqualified_namehas_column_with_unqualified_namehas_column_with_qualified_nameEach 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:
mergeresets it, and qualifier rewrites start with an empty one.PartialEqandDebugare now written by hand to leave it out, so plan snapshots don't change.clippy.toml: adddatafusion_common::DFSchematoignore-interior-mutability. TheOnceLockholding the index otherwise tripsmutable_key_typewherever anExprorLogicalPlanis used as a hash key. The lint doesn't apply here becauseHashandEqignore the index. Downstream crates that lint with-D warningsand useExpras 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_scancompares 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_changescovers sharing across clones, lookups after a qualifier rewrite, and the reset inmerge. It also checks that a schema whose index was built and one that was never probed compare equal and print the sameDebugoutput.Benchmarks (local,
release-nonlto,mainvs this PR)sql_plannernumbers are the mean of threemainruns and two runs of this PR, interleaved. Themainruns agreed within about ±1%, exceptlogical_select_one_from_700(up to 3%).mainSELECT *over one 10,240-column Parquet fileSELECT idover the same filelogical_select_all_from_1000physical_select_all_from_1000optimizer_select_all_from_1000with_param_values_many_columnslogical_trivial_join_high_numbered_columnsphysical_many_self_joinsoptimizer_tpcds_alllogical_trivial_join_low_numbered_columnsphysical_plan_tpch_alllogical_select_one_from_700,physical_select_one_from_700,physical_join_distinct,physical_unnest_to_joinlogical_correlated_subquery_inlogical_union_8_branchesThe two regressions come from building the index for 200-column scan schemas that are looked up only a few times. Raising the threshold to 256 removes them, but
with_param_values_many_columns, which looks up 200 columns of the same table, then gains only about 16% instead of 37%. Whether the index pays off depends on the number of lookups rather than the width, so the threshold stays at 8. The threshold sweep is in the review thread.Are there any user-facing changes?
Faster planning on wide schemas. There are no API changes: lookup results,
Debugoutput andHash/Eqbehaviour are unchanged.DFSchemanow holds aOnceLock, so clippy'smutable_key_typelint treats it as interior-mutable. Downstream crates that useExprorLogicalPlanas hash keys and lint with-D warningsneeddatafusion_common::DFSchemainignore-interior-mutabilityin theirclippy.toml, as this workspace does.HashandEqignore the index, so such keys stay sound.🤖 Generated with Claude Code
https://claude.ai/code/session_01FmZ3Fcw2tCfc7VGTQ8UnVB