Skip to content

SimplifyExpressions and RewriteSetComparison merge every input schema even for nodes with nothing to rewrite, which is quadratic on wide unions #27526

Description

@marikomedlock

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:

  • Time in SessionState::optimize for the plan above, with perf: build N-ary unions in the Substrait consumer #27525 (N-ary unions) applied: 0.287s → 0.147s (−49%) with this change. Median of 15 warm runs.
  • 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.

Details in #27527. Related: #27523, #17261.

Willingness to contribute

I plan to contribute to this feature independently

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment

Metadata

Metadata

Assignees

No one assigned

    Labels

    enhancementNew feature or request

    Projects

    No projects

      Milestone

      No milestone

      Relationships

      None yet

      Development

      No branches or pull requests

      Issue actions

      Sponsor
      SponsoredKunjungi sekarang
      Promo