This is an automated email from the ASF dual-hosted git repository.
dongjoon-hyun pushed a commit to branch branch-4.x
in repository https://gitbox.apache.org/repos/asf/spark.git
The following commit(s) were added to refs/heads/branch-4.x by this push:
new abb8527350a7 [SPARK-60508][SQL] Fix wrong results from
`semanticEquals` of higher-order functions capturing lambda variables
abb8527350a7 is described below
commit abb8527350a748b871559681fb70e35549d54c7a
Author: Dongjoon Hyun <[email protected]>
AuthorDate: Sat Oct 24 07:51:51 2026 -0700
[SPARK-60508][SQL] Fix wrong results from `semanticEquals` of higher-order
functions capturing lambda variables
### What changes were proposed in this pull request?
This PR aims to make `HigherOrderFunction.canonicalized` renumber only the
lambda variables that are bound in the higher-order function, i.e. the
arguments of its lambda functions, including those of nested higher-order
functions. A captured lambda variable, which is bound by an enclosing lambda
function, now keeps its own `exprId`. Only its runtime value is replaced with
one shared non-null value, because the optimizer works on a fresh copy of the
plan where every occurrence of a lam [...]
As before, when the enclosing higher-order function is canonicalized, a
nested higher-order function skips the variables that the enclosing one has
already renamed.
### Why are the changes needed?
Since SPARK-35580, `HigherOrderFunction.canonicalized` renames every
`NamedLambdaVariable` in its lambda functions by position, including the
captured ones. As a result, `filter(ys, y -> y > x1)` and `filter(ys, y -> y >
x2)` have the same canonical form when `x1` and `x2` have the same data type
and nullability, and `semanticEquals` returns `true` for them. The optimizer
rules that use `semanticEquals`, such as `SimplifyConditionals`,
`BooleanSimplification`, and `SimplifyBinaryCompa [...]
```sql
CREATE TABLE t USING parquet AS
SELECT array(1, 5) AS xs1, array(3, 2) AS xs2, array(1, 2, 3, 4, 5) AS ys;
SELECT zip_with(xs1, xs2, (x1, x2) ->
IF(x1 > x2, filter(ys, y -> y > x1), filter(ys, y -> y > x2))) FROM t;
```
| Lambda function body of `zip_with(xs1, xs2, (x1, x2) -> ...)` | Expected
| Apache Spark 4.0.4, 4.1.3, 4.2.0, 4.3.0 |
| --- | --- | --- |
| `IF(x1 > x2, filter(ys, y -> y > x1), filter(ys, y -> y > x2))` |
`[[4,5],[]]` | `[[2,3,4,5],[]]` |
| `CASE WHEN x1 > x2 THEN filter(ys, y -> y > x1) ELSE filter(ys, y -> y >
x2) END` | `[[4,5],[]]` | `[[4,5],[3,4,5]]` |
| `exists(ys, y -> y > x1) OR exists(ys, y -> y > x2)` | `[true,true]` |
`[true,false]` |
| `filter(ys, y -> y > x1) <=> filter(ys, y -> y > x2)` | `[false,false]` |
`[true,true]` |
For example, `SimplifyConditionals` replaces the whole `IF` with its first
branch.
```
Project [zip_with(xs1#3, xs2#4, lambdafunction(filter(ys#5,
lambdafunction((lambda y#8 > lambda x1#6), lambda y#8, false)), lambda x1#6,
lambda x2#7, false)) AS ...]
+- Relation spark_catalog.default.t[xs1#3,xs2#4,ys#5] parquet
```
A `LocalRelation` source such as `VALUES` hides this bug because
`ConvertToLocalRelation` evaluates the query before these rules run.
In addition, `ExtractPythonUDFFromLambda`, which exists only in the
unreleased `master` and `branch-4.x`, identifies a Python UDF call in a lambda
function by its canonical form. So, it merges two calls that capture different
lambda variables into one.
```python
from pyspark.sql import functions as sf
sf.udf("int")
def f(xs):
return len(xs)
df = spark.range(1).selectExpr(
"array(1, 2) AS l", "array(10, 20) AS r", "array(0, 5, 15) AS c")
df.select(sf.zip_with("l", "r", lambda a, b:
f(sf.filter("c", lambda y: y < a)) + f(sf.filter("c", lambda y: y <
b)))).collect()
# [3, 4] is expected, but [2, 2] is returned.
```
### Does this PR introduce _any_ user-facing change?
Yes. This fixes the wrong query results that have existed since Apache
Spark 3.2.0 ([v3.2.0](https://github.com/apache/spark/releases/tag/v3.2.0),
2021-10-06). Two higher-order functions that capture different lambda variables
are no longer semantically equal, so the optimizer does not treat them as the
same expression anymore. Two identical higher-order functions that capture the
same lambda variable are still semantically equal. This also fixes the Python
UDF example above in the un [...]
### How was this patch tested?
Pass the CIs with the newly added test cases.
- `HigherOrderFunctionsSuite`: `semanticEquals` returns `false` for
higher-order functions that capture different lambda variables, and `true` for
identical ones that differ only in the IDs of their own lambda variables,
including nested higher-order functions and fresh copies of the captured lambda
variables. A captured lambda variable does not equal a renamed bound one, even
with the same name and ID, and it is not renamed even when its ID is the
canonical ID of a variable bound by [...]
- `DataFrameFunctionsSuite`: the four queries above on a Parquet table, and
a query whose two `exists` capture the same lambda variable and are simplified
into one.
- `ExtractPythonUDFFromLambdaSuite`: the two Python UDF calls of the
example above are lifted as two UDFs instead of being merged into one.
Without the fix, all three new test cases fail. I also ran the Python
example above manually. It returns `[2, 2]` without the fix and `[3, 4]` with
the fix.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Opus 5.5
Closes #59749 from dongjoon-hyun/SPARK-60508.
Authored-by: Dongjoon Hyun <[email protected]>
Signed-off-by: Dongjoon Hyun <[email protected]>
(cherry picked from commit 8bc03dcc6250ecd42225d2423e2500f80615e848)
Signed-off-by: Dongjoon Hyun <[email protected]>
---
.../expressions/higherOrderFunctions.scala | 41 ++++++++++----
.../expressions/HigherOrderFunctionsSuite.scala | 62 ++++++++++++++++++++++
.../apache/spark/sql/DataFrameFunctionsSuite.scala | 36 ++++++++++++-
.../python/ExtractPythonUDFFromLambdaSuite.scala | 15 +++++-
4 files changed, 141 insertions(+), 13 deletions(-)
diff --git
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/higherOrderFunctions.scala
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/higherOrderFunctions.scala
index 2f90d718294b..53b0ae38b08c 100644
---
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/higherOrderFunctions.scala
+++
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/higherOrderFunctions.scala
@@ -244,24 +244,40 @@ trait HigherOrderFunction extends Expression with
ExpectsInputTypes {
override lazy val canonicalized: Expression = {
var currExprId = -1
- // Number the lambda variables of this higher-order function, but only
those not already
- // canonicalized. A canonical `NamedLambdaVariable` carries `value = null`
(see the rename
- // below); an original one carries an `AtomicReference`. When this HOF is
nested inside another,
- // the enclosing HOF's `canonicalized` renames every variable in the whole
subtree first, then
- // canonicalizes the children - which re-enters this method on the nested
HOF. Re-numbering the
- // already-renamed variables here would give a reference to an *enclosing*
lambda's variable a
- // different id than its binding, leaking it into `references`; skipping
them keeps a variable
- // and its references in agreement across nesting levels.
+ // Number the lambda variables bound in this higher-order function: the
arguments of its lambda
+ // functions, including those of nested higher-order functions. A free
variable, bound by an
+ // enclosing lambda function, keeps its exprId. Otherwise `filter(ys, y ->
y > x1)` and
+ // `filter(ys, y -> y > x2)` would be semantically equal whenever `x1` and
`x2` have the same
+ // data type and nullability.
+ //
+ // Only variables not already renamed are numbered or renamed. A renamed
`NamedLambdaVariable`
+ // carries `value = null` (see the rename below); any other one carries an
`AtomicReference`.
+ // When this HOF is nested inside another, the enclosing HOF's
`canonicalized` renames the
+ // variables bound in its whole subtree first, then canonicalizes the
children - which re-enters
+ // this method on the nested HOF. Its variables are then already numbered
uniquely across the
+ // nesting levels, and numbering them again here could make them collide
with the variables of
+ // the enclosing lambda functions.
+ val boundExprIds = functions.flatMap(_.collect {
+ case f: LambdaFunction => f.arguments.collect {
+ case l: NamedLambdaVariable if l.value != null => l.exprId
+ }
+ }.flatten).toSet
val argumentMap = functions.flatMap(_.collect {
- case l: NamedLambdaVariable if l.value != null =>
+ case l: NamedLambdaVariable if l.value != null &&
boundExprIds.contains(l.exprId) =>
currExprId += 1
l.exprId -> currExprId
}).toMap
val cleaned = this.transformUp {
- case l: NamedLambdaVariable if argumentMap.contains(l.exprId) =>
+ case l: NamedLambdaVariable if l.value != null &&
argumentMap.contains(l.exprId) =>
val newExprId = argumentMap(l.exprId)
NamedLambdaVariable("none", l.dataType, l.nullable, exprId =
ExprId(newExprId), null)
+ // A free variable gets one shared value in place of its own. The
optimizer works on a fresh
+ // copy of the plan, where every occurrence of a lambda variable has its
own value, and the
+ // value takes part in the equality. The shared value is not null, so a
free variable never
+ // equals a renamed bound variable.
+ case l: NamedLambdaVariable if l.value != null =>
+ l.copy(value = HigherOrderFunction.FreeVariableValue)
}
val canonicalizedChildren = cleaned.children.map(_.canonicalized)
withNewChildren(canonicalizedChildren)
@@ -325,6 +341,11 @@ trait HigherOrderFunction extends Expression with
ExpectsInputTypes {
}
}
+object HigherOrderFunction {
+ // The value of every free lambda variable in a canonicalized higher-order
function.
+ private val FreeVariableValue = new AtomicReference[Any]()
+}
+
/**
* Trait for functions having as input one argument and one function.
*/
diff --git
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/HigherOrderFunctionsSuite.scala
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/HigherOrderFunctionsSuite.scala
index b9c870f31090..3c1f67109571 100644
---
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/HigherOrderFunctionsSuite.scala
+++
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/HigherOrderFunctionsSuite.scala
@@ -896,6 +896,68 @@ class HigherOrderFunctionsSuite extends SparkFunSuite with
ExpressionEvalHelper
assert(!mapFilter2_1.semanticEquals(mapFilter2_3))
}
+ test("SPARK-60508: semanticEquals between higher-order functions capturing
lambda variables") {
+ val ys = Literal.create(Seq(1, 2, 3, 4, 5), ArrayType(IntegerType,
containsNull = true))
+ // Variables of an enclosing lambda function with the same data type and
nullability, like
+ // `x1` and `x2` of `zip_with(xs1, xs2, (x1, x2) -> ...)`.
+ val x1 = NamedLambdaVariable("x1", IntegerType, nullable = true)
+ val x2 = NamedLambdaVariable("x2", IntegerType, nullable = true)
+
+ // Every call binds fresh lambda variables, so the functions below differ
in the exprIds of
+ // their own variables, which `semanticEquals` ignores, unlike the
variables they capture.
+ val filter1 = filter(ys, y => y > x1)
+ assert(filter1.semanticEquals(filter(ys, y => y > x1)))
+ assert(!filter1.semanticEquals(filter(ys, y => y > x2)))
+
+ val nested1 = transform(ys, y => filter(ys, z => z > y + x1))
+ assert(nested1.semanticEquals(transform(ys, y => filter(ys, z => z > y +
x1))))
+ assert(!nested1.semanticEquals(transform(ys, y => filter(ys, z => z > y +
x2))))
+ assert(!nested1.semanticEquals(transform(ys, y => filter(ys, z => z > z +
x1))))
+
+ // The optimizer works on a fresh copy of the plan, where every occurrence
of a lambda variable
+ // has its own value.
+ Seq(filter1, nested1).foreach { e =>
+ val copied = e.freshCopyIfContainsStatefulExpression()
+ assert(copied.semanticEquals(e))
+ assert(copied.semanticHash() == e.semanticHash())
+ }
+
+ // Canonicalizing the enclosing function numbers its own variables too,
without colliding with
+ // the variables of the nested functions.
+ def zipWith(f: (Expression, Expression) => Expression): Expression =
+ ZipWith(ys, ys, createLambda(IntegerType, true, IntegerType, true,
f)).bind(validateBinding)
+ val zip1 = zipWith((a, b) => If(a > b, filter(ys, y => y > a), filter(ys,
y => y > b)))
+ assert(zip1.semanticEquals(
+ zipWith((a, b) => If(a > b, filter(ys, y => y > a), filter(ys, y => y >
b)))))
+ assert(!zip1.semanticEquals(
+ zipWith((a, b) => If(a > b, filter(ys, y => y > b), filter(ys, y => y >
a)))))
+ assert(!zipWith((a, _) => transform(ys, y => y + a)).semanticEquals(
+ zipWith((_, _) => transform(ys, y => y + y))))
+ assert(zip1.canonicalized.references.isEmpty)
+
+ // The canonical exprIds of the variables bound by each lambda function,
outermost first.
+ def canonicalIds(e: Expression): Seq[Seq[ExprId]] =
e.canonicalized.collect {
+ case f: LambdaFunction => f.arguments.map(_.exprId)
+ }
+
+ // A free variable never equals a renamed bound variable, even with the
same name and exprId.
+ val Seq(abIds) = canonicalIds(zipWith((a, _) => a + x1))
+ assert(canonicalIds(zipWith((_, b) => x1 + b)) == Seq(abIds))
+ val Seq(noneA, noneB) =
+ abIds.map(id => NamedLambdaVariable("none", IntegerType, nullable =
true, exprId = id))
+ assert(!zipWith((a, _) => a + noneB).semanticEquals(zipWith((_, b) =>
noneA + b)))
+
+ // A free variable keeps its exprId, even when it is the canonical exprId
of a variable bound
+ // by a nested function, like `y` below.
+ val Seq(_, Seq(yId)) = canonicalIds(zipWith((_, _) => filter(ys, y => y >
x1)))
+ val x = NamedLambdaVariable("x", IntegerType, nullable = true, exprId =
yId)
+ val zip2 = zipWith((_, _) => filter(ys, y => y > x))
+ assert(canonicalIds(zip2).last == Seq(yId))
+ assert(zip2.canonicalized.collect {
+ case l: NamedLambdaVariable if l.name == "x" => l.exprId
+ } == Seq(yId))
+ }
+
test("SPARK-36740: ArraySort should handle NaN greater than non-NaN value") {
checkEvaluation(arraySort(
Literal.create(Seq(Double.NaN, 1d, 2d, null), ArrayType(DoubleType))),
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameFunctionsSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameFunctionsSuite.scala
index 504a84668068..67ee0b98d27a 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/DataFrameFunctionsSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/DataFrameFunctionsSuite.scala
@@ -26,7 +26,7 @@ import scala.util.Random
import org.apache.spark.{QueryContextType, SPARK_DOC_ROOT, SparkException,
SparkRuntimeException}
import org.apache.spark.sql.catalyst.{ExtendedAnalysisException, InternalRow}
import org.apache.spark.sql.catalyst.analysis.FunctionRegistry
-import org.apache.spark.sql.catalyst.expressions.{Expression, Literal,
UnaryExpression}
+import org.apache.spark.sql.catalyst.expressions.{ArrayExists, Expression,
Literal, UnaryExpression}
import org.apache.spark.sql.catalyst.expressions.Cast._
import org.apache.spark.sql.catalyst.expressions.codegen.CodegenFallback
import org.apache.spark.sql.catalyst.plans.logical.OneRowRelation
@@ -6211,6 +6211,40 @@ class DataFrameFunctionsSuite extends SharedSparkSession
{
)
}
+ test("SPARK-60508: nested higher-order functions capturing lambda
variables") {
+ // A file source, because a `LocalRelation` is evaluated before the
optimizer simplifies the
+ // expressions below.
+ withTable("t") {
+ sql("CREATE TABLE t USING parquet AS " +
+ "SELECT array(1, 5) AS xs1, array(3, 2) AS xs2, array(1, 2, 3, 4, 5)
AS ys")
+ checkAnswer(
+ sql("SELECT zip_with(xs1, xs2, (x1, x2) -> " +
+ "IF(x1 > x2, filter(ys, y -> y > x1), filter(ys, y -> y > x2))) FROM
t"),
+ Row(Seq(Seq(4, 5), Seq.empty)))
+ checkAnswer(
+ sql("SELECT zip_with(xs1, xs2, (x1, x2) -> " +
+ "CASE WHEN x1 > x2 THEN filter(ys, y -> y > x1) ELSE filter(ys, y ->
y > x2) END) " +
+ "FROM t"),
+ Row(Seq(Seq(4, 5), Seq.empty)))
+ checkAnswer(
+ sql("SELECT zip_with(xs1, xs2, (x1, x2) -> " +
+ "exists(ys, y -> y > x1) OR exists(ys, y -> y > x2)) FROM t"),
+ Row(Seq(true, true)))
+ checkAnswer(
+ sql("SELECT zip_with(xs1, xs2, (x1, x2) -> " +
+ "filter(ys, y -> y > x1) <=> filter(ys, y -> y > x2)) FROM t"),
+ Row(Seq(false, false)))
+
+ // The functions capturing the same variable are still simplified into
one.
+ val df = sql("SELECT transform(xs1, x -> " +
+ "exists(ys, y -> y > x) AND exists(ys, y -> y > x)) FROM t")
+ checkAnswer(df, Row(Seq(true, false)))
+ assert(df.queryExecution.optimizedPlan.expressions.flatMap(_.collect {
+ case e: ArrayExists => e
+ }).size == 1)
+ }
+ }
+
test("from_json - invalid schema string") {
checkError(
exception = intercept[AnalysisException] {
diff --git
a/sql/core/src/test/scala/org/apache/spark/sql/execution/python/ExtractPythonUDFFromLambdaSuite.scala
b/sql/core/src/test/scala/org/apache/spark/sql/execution/python/ExtractPythonUDFFromLambdaSuite.scala
index 46596bef42b8..b59d26a1f9ea 100644
---
a/sql/core/src/test/scala/org/apache/spark/sql/execution/python/ExtractPythonUDFFromLambdaSuite.scala
+++
b/sql/core/src/test/scala/org/apache/spark/sql/execution/python/ExtractPythonUDFFromLambdaSuite.scala
@@ -22,8 +22,8 @@ import org.apache.spark.sql.{AnalysisException, QueryTest}
import org.apache.spark.sql.catalyst.expressions.{ArraysZip, LambdaFunction,
Literal,
NamedArgumentExpression, PythonUDF}
import org.apache.spark.sql.catalyst.plans.logical.{Aggregate,
ArrowEvalPython, Join}
-import org.apache.spark.sql.functions.{array_sort, col, collect_list, forall,
lit, map_filter,
- map_zip_with, transform, transform_keys, transform_values, when, zip_with}
+import org.apache.spark.sql.functions.{array_sort, col, collect_list, filter,
forall, lit,
+ map_filter, map_zip_with, transform, transform_keys, transform_values, when,
zip_with}
import org.apache.spark.sql.internal.SQLConf
import org.apache.spark.sql.test.{ExamplePointUDT, SharedSparkSession}
import org.apache.spark.sql.types.{ArrayType, IntegerType, MapType, StringType}
@@ -201,6 +201,17 @@ class ExtractPythonUDFFromLambdaSuite extends QueryTest
with SharedSparkSession
assert(liftedUDFs(df).size == 4)
}
+ test("SPARK-60508: calls capturing different lambda variables are lifted
distinctly") {
+ // `f(filter(c, y -> y < a))` and `f(filter(c, y -> y < b))` differ only
in the lambda variable
+ // they capture, so keying them by canonical form must not merge them into
one lifted call.
+ val df = Seq((Seq(1, 2), Seq(10, 20), Seq(0, 5, 15))).toDF("l", "r",
"c").select(
+ zip_with(col("l"), col("r"), (a, b) =>
+ pythonUDF(filter(col("c"), y => y < a)) || pythonUDF(filter(col("c"),
y => y < b)))
+ .as("res"))
+ assert(udfsInsideLambda(df).isEmpty)
+ assert(liftedUDFs(df).size == 2)
+ }
+
test("transform_values whose result type equals the key type replaces
values, not keys") {
// SPARK-27052: dispatch is by concrete function, not result type. For
map<string, string>,
// transform_values' lambda also returns string, which must not be treated
as new keys.
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]