[
https://issues.apache.org/jira/browse/SPARK-58501?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Wenchen Fan reassigned SPARK-58501:
-----------------------------------
Assignee: James Xu
> [SQL] Eliminate redundant subexpression evaluation across Expand branches in
> whole-stage codegen
> ------------------------------------------------------------------------------------------------
>
> Key: SPARK-58501
> URL: https://issues.apache.org/jira/browse/SPARK-58501
> Project: Spark
> Issue Type: Improvement
> Components: SQL
> Affects Versions: 4.3.0
> Reporter: James Xu
> Assignee: James Xu
> Priority: Major
> Labels: pull-request-available
>
> h3. Problem:
> Traffic/BI rollup queries stack many conditional aggregates whose
> conditions
> share one expensive subexpression. A typical "N-day active users" dashboard
> query computes retention over many windows in a single pass:
> {code:java}
> SELECT
> COUNT(DISTINCT IF(datediff(date '2026-01-01',
> from_unixtime(unix_timestamp(ts, 'yyyy-MM-dd HH:mm:ss'))) <= 1,
> uid, NULL)) AS uv_1d,
> COUNT(DISTINCT IF(datediff(date '2026-01-01',
> from_unixtime(unix_timestamp(ts, 'yyyy-MM-dd HH:mm:ss'))) <= 7,
> uid, NULL)) AS uv_7d,
> SUM(IF(datediff(date '2026-01-01',
> from_unixtime(unix_timestamp(ts, 'yyyy-MM-dd HH:mm:ss'))) <= 1,
> 1, 0)) AS pv_1d,
> -- ... 15 more conditional aggregates over longer windows
> FROM traffic{code}
> RewriteDistinctAggregates gives each distinct group its own Expand branch
> with the condition expression verbatim, so the shared datetime
> subexpression
> (unix_timestamp parse + from_unixtime format + datediff) appears in every
> branch. In whole-stage codegen it is compiled into each branch body and
> re-evaluated once per branch per input row, even though every branch of an
> Expand consumes the same input row.
> h3. Root Cause:
> Two facts combine to produce the redundant work:
> - RewriteDistinctAggregates groups distinct aggregates by their unfoldable
> child sets. Each unique IF(cond_i, col, NULL) child forms its own group,
> so N conditions produce N Expand branches, and the branch projections
> carry the full condition expressions (not attributes).
> - Expand whole-stage codegen never participated in subexpression
> elimination. Each branch body is generated independently, so a subtree
> shared by B branches is emitted B times and evaluated B times per input
> row. In the example above the shared subexpression is evaluated 18 times
> per input row (9 distinct-aggregate conditions + 9 regular-aggregate
> conditions across 10 branches).
> Grouping keys do not suffer from this: complex grouping expressions are
> pulled into a Project below the Expand and referenced as attributes. Only
> branch-varying expressions such as aggregate conditions are affected.
> h3. Solution:
> During whole-stage codegen, analyze all branch expressions of an Expand
> together: any subtree shared across branches (or repeated within a branch)
> is evaluated once per input row, before the branch loop, and each branch
> references the cached value. Hoisting is semantics-preserving because every
> branch consumes the same input row.
> - Applies automatically wherever Expand branches carry repeated
> non-trivial expressions, most notably multi-conditional DISTINCT
> aggregate queries produced by RewriteDistinctAggregates.
> - Interoperates with the large-Expand safeguard that splits branch bodies
> into separate generated methods for JVM method-size limits: the cached
> values are passed into the split methods as parameters.
> - No new configuration. The optimization honors the existing subexpression
> elimination setting and is active whenever whole-stage codegen is.
> - Evaluation results are unchanged; only the number of evaluations per
> input row changes.
> h3. Expected Impact:
> Measured with a new ExpandBenchmark case modeling the rollup above (5M
> rows, 3 iterations, Apple M4 Pro, JDK 17):
> - Shared subexpression evaluations per input row: 18 -> 1
> - Average runtime: 82485 ms -> 51457 ms (15701 -> 9756 ns/row), 1.6X faster
> The benefit grows with the number of branches and with the cost of the
> shared subexpression (datetime parsing, regex, JSON extraction). Queries
> whose Expand branches share no non-trivial subexpressions are unaffected.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
