This is an automated email from the ASF dual-hosted git repository.

dongjoon-hyun pushed a commit to branch branch-4.0
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/branch-4.0 by this push:
     new 076b9d674fbf [SPARK-60508][SQL] Fix wrong results from 
`semanticEquals` of higher-order functions capturing lambda variables
076b9d674fbf is described below

commit 076b9d674fbf6c4b887f8cc155c4efb476869afd
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         | 33 +++++++++++-
 .../expressions/HigherOrderFunctionsSuite.scala    | 62 ++++++++++++++++++++++
 .../apache/spark/sql/DataFrameFunctionsSuite.scala | 36 ++++++++++++-
 3 files changed, 128 insertions(+), 3 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 7635690a4605..2addf00a9469 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
@@ -223,22 +223,51 @@ trait HigherOrderFunction extends Expression with 
ExpectsInputTypes {
 
   override lazy val canonicalized: Expression = {
     var currExprId = -1
+    // 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 =>
+      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)
   }
 }
 
+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 cc36cd73d6d7..85095ad5df1f 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
@@ -841,6 +841,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 3dcdc73759b0..4fd329e3f962 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
@@ -6010,6 +6010,40 @@ class DataFrameFunctionsSuite extends QueryTest with 
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] {


---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]

Reply via email to