This is an automated email from the ASF dual-hosted git repository.
viirya pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/master by this push:
new 30cda07393cc [SPARK-59933][SQL] Eliminate quadratic nested field
aliasing deduplication
30cda07393cc is described below
commit 30cda07393cc6289fdc17a962fcb890a9be3eb42
Author: AnishMahto <[email protected]>
AuthorDate: Mon Oct 5 10:57:42 2026 -0700
[SPARK-59933][SQL] Eliminate quadratic nested field aliasing deduplication
### What changes were proposed in this pull request?
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.
### Why are the changes needed?
Improve nested field read aliasing performance.
### Does this PR introduce _any_ user-facing change?
No. This is a pure optimization that should not introduce any behavioral
change.
### How was this patch tested?
No new logic is added, but added tests to bring coverage for existing
untested contracts (non-deterministic but identically canonicalized plans are
still aliased separately, and deterministic plans that are canonically the same
are indeed considered for shared-aliasing).
### Was this patch authored or co-authored using generative AI tooling?
Co-authored with Claude Opus 5.5.
Closes #59192 from AnishMahto/SPARK-59933-nested-column-aliasing-dedup.
Authored-by: AnishMahto <[email protected]>
Signed-off-by: Liang-Chi Hsieh <[email protected]>
---
.../catalyst/optimizer/NestedColumnAliasing.scala | 8 ++--
.../optimizer/NestedColumnAliasingSuite.scala | 44 ++++++++++++++++++++++
2 files changed, 48 insertions(+), 4 deletions(-)
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasing.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasing.scala
index 8de2663a9809..0f885956f705 100644
---
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasing.scala
+++
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasing.scala
@@ -275,15 +275,15 @@ object NestedColumnAliasing {
// Remove redundant [[ExtractValue]]s if they share the same parent
nest field.
// For example, when `a.b` and `a.b.c` are in project list, we only
need to alias `a.b`.
// Because `a.b` requires all of the inner fields of `b`, we cannot
prune `a.b.c`.
- val dedupNestedFields = nestedFields.filter {
+ val distinctNestedFields = nestedFields.distinct
+ val nestedFieldSet = ExpressionSet(distinctNestedFields)
+ val dedupNestedFields = distinctNestedFields.filter {
// See [[collectExtractValue]]: we only need to deal with
[[GetArrayStructFields]] and
// [[GetStructField]]
case e @ (_: GetStructField | _: GetArrayStructFields) =>
- val child = e.children.head
- nestedFields.forall(f => !child.exists(_.semanticEquals(f)))
+ !e.children.head.exists(p => p.deterministic &&
nestedFieldSet.contains(p))
case _ => true
}
- .distinct
// Discard [[ExtractValue]]s that contain aggregate functions.
.filterNot(containsAggregateFunction)
diff --git
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasingSuite.scala
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasingSuite.scala
index 93b85470d35d..f2701477cd87 100644
---
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasingSuite.scala
+++
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/NestedColumnAliasingSuite.scala
@@ -333,6 +333,50 @@ class NestedColumnAliasingSuite extends SchemaPruningTest {
comparePlans(optimized, expected)
}
+ test("Redundant nested fields are detected through cosmetic variations of
their parents") {
+ val a = $"a".struct(StructType.fromDDL("b struct<c: int, d: int>, e int"))
+ // `a.b`, referenced many times below.
+ val ab = GetStructField(a, 0, Some("b"))
+ // `a.b` without the field name.
+ val unnamedAb = GetStructField(a, 0, None)
+ // `a.b.c` over the unnamed `a.b`.
+ val abc = GetStructField(unnamedAb, 0, Some("c"))
+ // `a.b.d` over a qualified `a`.
+ val abd = GetStructField(
+ GetStructField(a.withQualifier(Seq("t")), 0, Some("b")), 1, Some("d"))
+
+ val attrToExtractValues = NestedColumnAliasing.getAttributeToExtractValues(
+ Seq.fill(100)(ab) ++ Seq(unnamedAb, abc, abd), Seq.empty)
+
+ assert(attrToExtractValues.keys.map(_.exprId).toSeq == Seq(a.exprId))
+ assert(attrToExtractValues.values.toSeq == Seq(Seq(ab, unnamedAb)))
+ }
+
+ test("Nested fields are not redundant with non-deterministic parents") {
+ // `getAttributeToExtractValues` only returns a column if its kept reads'
leaf counts sum to
+ // fewer than its own leaf count. The kept reads below sum to 5, so `e`
through `h` pad `a` to
+ // 6 leaves.
+ val a = $"a".array(StructType.fromDDL("b struct<c: int, d: int>, e int, f
int, g int, h int"))
+ // `a[ordinal].b` and `a[ordinal].b.c`.
+ def parentAndChild(ordinal: Expression): Seq[ExtractValue] = {
+ val parent = GetStructField(GetArrayItem(a, ordinal), 0, Some("b"))
+ Seq(parent, GetStructField(parent, 0, Some("c")))
+ }
+
+ val deterministicReadPair = parentAndChild(Literal(0))
+ val nondeterministicReadPair = parentAndChild(Cast(Rand(Literal(0L)),
IntegerType))
+ // `a[rand].b` is non-deterministic, so `a[rand].b.c` is not redundant
with it, while the
+ // redundant deterministic `a[0].b.c` is still dropped.
+ assert(
+ NestedColumnAliasing.getAttributeToExtractValues(
+ deterministicReadPair ++ nondeterministicReadPair,
+ Seq.empty
+ )
+ .values
+ .toSeq == Seq(deterministicReadPair.take(1) ++ nondeterministicReadPair)
+ )
+ }
+
test("Nested field pruning for Project and Generate") {
val query = contact
.generate(Explode($"friends".getField("first")), outputNames =
Seq("explode"))
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]
