[
https://issues.apache.org/jira/browse/SPARK-59933?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel
]
Anish Mahto updated SPARK-59933:
--------------------------------
Description:
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:
#1 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.
#2 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.
was:
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:
1. 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.
2. 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.
> 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
>
> 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:
> #1 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.
> #2 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]
