xudong963 opened a new pull request, #26786: URL: https://github.com/apache/datafusion/pull/26786
## Which issue does this PR close? - No existing issue. Found while looking at optimizer time for queries joining many tables; happy to file one if preferred. ## Rationale for this change `EliminateCrossJoin` is quadratic (or worse) in the number of joined inputs, both for comma joins (`FROM t0, t1, ..., tn WHERE t0.a = t1.a AND ...`) and for explicit inner join chains (`t0 JOIN t1 ON ... JOIN t2 ON ...`). With 128 tables the rule alone takes ~700 ms. After flattening the join tree and reassembling it, the rule calls `rewrite_children` on the reassembled tree. The left child is the reassembled chain minus one input, so the rule flattens and rebuilds it again, and so on at every nesting level. Each rebuild also checks candidate join keys against the accumulated left schema, which grows with the number of inputs. ## What changes are included in this PR? - `EliminateCrossJoin::rewrite`: rewrite each flattened input once, *before* reassembling the joins, instead of calling `rewrite_children` on the reassembled tree. `rewrite` preserves the schema of its input, which is all that `find_inner_join` looks at, so the result is unchanged. Uncorrelated subqueries in the join keys of each reassembled join (previously visited by `rewrite_children` via `map_uncorrelated_subqueries`) are now rewritten explicitly. - `find_valid_equijoin_key_pair`: check the columns against `right_schema` first. When building a left-deep join tree, `left_schema` is the accumulated schema of all previous inputs and is much more expensive to search, while most candidate keys don't reference the right input at all. `check_all_columns_from_schema` is side-effect free and never returns an error, so reordering the checks does not change the result. - New `eliminate_cross_join` criterion benchmark (comma joins and inner join chains over 8-128 tables). Benchmark results (`cargo bench -p datafusion-optimizer --bench eliminate_cross_join`, Apple M-series, `main` @ c18e5d974 vs this PR): | benchmark | main | this PR | change | |---|---:|---:|---:| | comma_join/8 | 112.90 µs | 29.44 µs | -71% | | comma_join/32 | 4.63 ms | 330.67 µs | -93% | | comma_join/64 | 49.83 ms | 1.26 ms | -97% | | comma_join/128 | 700.59 ms | 4.99 ms | -99% | | inner_join/8 | 81.43 µs | 27.51 µs | -67% | | inner_join/32 | 4.39 ms | 323.37 µs | -93% | | inner_join/64 | 48.80 ms | 1.22 ms | -97% | | inner_join/128 | 623.20 ms | 4.94 ms | -99% | ## What is the testing strategy for this PR? - Existing `eliminate_cross_join` unit tests, plus a new `eliminate_cross_join_in_join_key_subquery` test covering an uncorrelated subquery (containing an eliminable cross join) that ends up in a join key. - The full sqllogictest suite passes (including the join plans in `joins.slt` and `join.slt.part`). - Locally, I ran a randomized differential test comparing the previous and the new implementation on 3,000 generated plans (nested inner/cross/left joins, `ON` filters, `AND`/`OR` predicates and uncorrelated scalar subqueries in filters and join keys): the output plans, `transformed` flags and errors were identical. It is not included here because it needs a copy of the old implementation. ## Are there any user-facing changes? No, other than faster planning for queries with many joins. No public API changes. 🤖 Generated with [Claude Code](https://claude.com/claude-code) -- 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]
