zhuqi-lucas opened a new pull request, #24316: URL: https://github.com/apache/datafusion/pull/24316
## Which issue does this close? Related to #24264. This is an alternative to #24281 that stays entirely inside the "make it cheaper" lane: it does not change any schema that is produced, so it does not depend on the semantics question raised in #24284. ## Rationale for this change Deriving a projection's output schema is quadratic in the number of columns, and the constant is doubled for aliases. Two independent causes: 1. **Name lookup is a linear scan.** `DFSchema` has no name to index map, so `index_of_column_by_name` and `qualified_fields_with_unqualified_name` walk every field. `Expr::Column`'s `to_field` goes through `field_from_column` to the latter, which additionally allocates a `Vec` per lookup. With N expressions over an M-column schema that is O(N*M). 2. **The alias arm resolves twice.** In `Expr::to_field`, `Expr::Alias` calls `expr.metadata(schema)` and then `expr.to_field(schema)`. `Expr::metadata` is defined as `to_field(..).1.metadata()`, so the inner expression, and therefore the schema, is walked a second time for no extra information. This shows up on plans with many wide `col AS col` alias projections, where an alias is not a bare `Column` so `is_projection_unnecessary` keeps the projection and its schema is derived again on every pass. ## What changes are included in this PR? - `DFSchema` gains a lazily built `name_index` mapping a field name to the ascending indices carrying it. `index_of_column_by_name` and `qualified_fields_with_unqualified_name` consult it instead of scanning, and the latter stops allocating a `Vec` on every lookup. - `Expr::to_field`'s `Expr::Alias` arm resolves the aliased expression once and takes the metadata from the resulting field. The index is derived state: it takes no part in `PartialEq`, `Clone` starts a fresh cache rather than copying one, and `Debug` is now hand written so it prints exactly the three real fields as before. That last point matters because plan snapshots compare the `Debug` string and a `HashMap`'s iteration order is not deterministic; deriving `Debug` with the new field made `datafusion-sql`'s `test_avoid_add_alias` fail nondeterministically. ## Correctness Every arm of the lookup rules already required the field name to match, so restricting the walk to same-named candidates and applying the qualifier rules in index order returns exactly what the full scan returned, including which duplicate wins and which lookups miss. `name_index_matches_linear_scan` pins this by keeping the previous scan as a reference implementation and comparing both lookups across qualifier and name combinations, over a schema with the same name under two relations, qualified and unqualified fields, a non-ASCII name and absent names. `name_index_is_derived_state` covers `clone`, `strip_qualifiers` and `replace_qualifier`, where the qualifiers change and stale answers would be visible. Both tests were checked against deliberate mutations: reversing the candidate order and making the qualifier comparison always true each make them fail. ## Performance `to_field` over W `col AS col` aliases against a W-column schema, per iteration over 3000 iterations: | W | before | after | speedup | |-----|----------|----------|---------| | 18 | 26.74 us | 12.03 us | 2.2x | | 40 | 75.40 us | 18.64 us | 4.0x | | 100 | 394.8 us | 47.21 us | 8.4x | | 300 | 3124 us | 141.4 us | 22.1x | Per-expression cost goes from 0.98 us at W=18 to 5.32 us at W=300 before, and holds at about 0.47 us after, so the quadratic term is gone. At narrow widths the alias change is what pays; the index takes over as the schema widens. This is a microbenchmark of `to_field` in isolation. An end to end optimizer pass will see a smaller number, since it includes work neither change touches. The two changes are independent and can be split if you would prefer to review them separately. ## Are there any user-facing changes? No. Lookup results, schemas and `Debug` output are unchanged; this is purely a cost reduction. -- 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]
