You signed in with another tab or window. Reload to refresh your session.You signed out in another tab or window. Reload to refresh your session.You switched accounts on another tab or window. Reload to refresh your session.Dismiss alert
{{ message }}
Repository navigation
SimplifyExpressions and RewriteSetComparison merge every input schema even for nodes with nothing to rewrite, which is quadratic on wide unions #27526
Is your feature request related to a problem or challenge?
Both rules build a merged schema of all of a node's inputs before rewriting that node's expressions:
SimplifyExpressions::optimize_internal (datafusion/optimizer/src/simplify_expressions/simplify_exprs.rs): merge_schema(&plan.inputs()) for any node with inputs.
RewriteSetComparison::rewrite_plan (datafusion/optimizer/src/rewrite_set_comparison.rs): merge_schema(&plan.inputs()) for every node.
merge_schema folds the inputs with DFSchema::merge, and each merge rebuilds hash sets of every field merged so far. For a Union with N inputs that's quadratic in the number of fields, and both rules run on every optimizer pass. A Union has no expressions of its own, so the merged schema is never used.
This shows up on any plan with a wide union: OptimizeUnions flattens nested unions early in the first pass, so later passes of both rules merge every input's schema. It also shows up from the very first rule once the Substrait consumer builds unions N-ary (#27523). On a plan with 7 unions of 186, 186, 186, 91, 91, 91 and 3 inputs, these merges were a large share of what was left of SessionState::optimize.
Describe the solution you'd like
Return Transformed::no(plan) before building the schema when there is nothing to rewrite:
SimplifyExpressions: When the node has no expressions of its own.
RewriteSetComparison: When none of the node's own expressions contains an Expr::SetComparison.
For such nodes both rules already return the plan unchanged, so plans are identical.
Describe alternatives you've considered
Making merge_schema itself cheaper for many inputs (build the field sets once). That would help every caller, but these two rules don't need the schema at all for these nodes, so skipping is simpler and cheaper. The two could be done independently.
Additional context
Measured on current main (3e55e62), on an Apple M-series laptop:
New sql_planner benchmark optimizer_wide_union_all (SQL UNION ALL over N distinct 20-column tables), with this change alone: −44% to −46% at 50 inputs and −48% to −50% at 200.
Across all 40 logical_* and optimizer_* benchmarks, none was slower by more than 2% in both of two alternating runs.
Activity