[
https://issues.apache.org/jira/browse/SPARK-59933?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
ASF GitHub Bot updated SPARK-59933:
-----------------------------------
Labels: pull-request-available (was: )
> Eliminate quadratic nested field aliasing deduplication
> -------------------------------------------------------
>
> Key: SPARK-59933
> URL: https://issues.apache.org/jira/browse/SPARK-59933
> Project: Spark
> Issue Type: Improvement
> Components: Optimizer
> Affects Versions: 4.4.0
> Reporter: Anish Mahto
> Priority: Minor
> Labels: pull-request-available
>
> Within any expression, there can be multiple nested struct read
> subexpressions (ex. read `a.b.c`, `a.b`, and `a.d`). All of these are
> independent candidates for column aliasing, and
> `NestedColumnAliasing.getAttributeToExtractValues` is responsible for
> dropping read expressions that are nested anywhere beneath another read. Ex.
> instead of aliasing `a.b.c` and `a.b` independently, we should only alias
> `a.b` and then reuse that alias as `some_alias.c`
> But `NestedColumnAliasing` achieves this by iterating over every nested read
> subexpression, and comparing it against every other read subexpression for
> semantic equality on its ancestor.
> This is quadratic with respect to the number of nested field read
> subexpressions, which can be noticeable for plans constructed against large
> (wide/deep) tables, especially generated ones. Two behavior-preserving
> optimizations are proposed:
> # Build an `ExpressionSet` of the reads once and look up each parent node in
> it. This is equivalent to `semanticEquals`. `ExpressionSet` stores only
> deterministic expressions in canonical form and canonicalizes the queried
> expression, so a match requires both expressions to be deterministic with
> equal canonical forms.
> # Plans often repeat the same read many times, so deduplicate with
> `.distinct` before filtering rather than after, to avoid repeated work. The
> result is the same, because removing exact duplicates doesn't change which
> reads are semantically present.
> For typical small plans, the overhead is negligible - the previous
> `semanticEquals` comparisons already canonicalized every read, so the only
> added work is building a small hash set.
--
This message was sent by Atlassian Jira
(v8.20.10#820010)
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
