Anish Mahto created SPARK-59933:
-----------------------------------
Summary: 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
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]
