[jira] [Assigned] (SPARK-59933) Eliminate quadratic nested field aliasing deduplication

["L. C. Hsieh (Jira)" <ji...@apache.org>]

     [ https://issues.apache.org/jira/browse/SPARK-59933?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]

L. C. Hsieh reassigned SPARK-59933:
-----------------------------------

    Assignee: Anish Mahto

> 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
>            Assignee: 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: issues-unsubscribe@spark.apache.org
For additional commands, e-mail: issues-help@spark.apache.org