James Xu created SPARK-58501:
--------------------------------
Summary: [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
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]
