Canonicalization re-associates floating-point Add/Multiply, producing wrong results

XMLWordPrintableJSON

      Add.canonicalized and Multiply.canonicalized flatten and reorder adjacent operands
      (Expression.buildCanonicalizedPlan -> orderCommutative -> gatherCommutative) with no
      exception for FLOAT/DOUBLE. Floating-point addition and multiplication are commutative but *not
      associative*, so (a + b) + c and a + (b + c) canonicalize to the same expression while
      evaluating to different values.

      Every consumer of semantic equality is therefore allowed to substitute one for the other. Two of
      them return wrong results today: the cached-plan lookup in CacheManager (sameResult) and
      subexpression elimination (EquivalentExpressions.ExpressionEquals -> semanticEquals).

      Reproduction

      Measured on current master (5.0.0-SNAPSHOT), local[4], AQE disabled. One Parquet row:

      -- a = 1.0E16, b = -1.0E16, c = 1.0, all DOUBLE
      -- (a + b) + c = 1.0      a + (b + c) = 0.0
      

      1. Subexpression elimination, same query

      SELECT (a + b) + c AS x, a + (b + c) AS y FROM t
      
      cse=true  wholeStage=true  -> x=1.0 y=1.0     <-- y is wrong
      cse=true  wholeStage=false -> x=1.0 y=1.0     <-- y is wrong
      cse=false wholeStage=true  -> x=1.0 y=0.0
      cse=false wholeStage=false -> x=1.0 y=0.0
      

      The physical plan still contains both expressions; only the evaluation is shared. Setting
      spark.sql.subexpressionElimination.enabled=false restores the correct answer, which isolates
      the mechanism.

      2. Cached-plan reuse, across queries

      val d1 = spark.sql("select (a+b)+c as v from t")
      d1.cache(); d1.collect()                       // [1.0], correct
      spark.sql("select a+(b+c) as v from t").collect()   // [1.0], expected [0.0]
      d1.unpersist()
      spark.sql("select a+(b+c) as v from t").collect()   // [0.0], correct again
      

      The second query's plan is served from the cache entry built for the first:

      == Physical Plan ==
      InMemoryTableScan [v#49]
         +- InMemoryRelation [v#49], StorageLevel(disk, memory, deserialized, 1 replicas)
               +- *(1) Project [((a#3 + b#4) + c#5) AS v#20]
      

      3. Directly, at the expression level

      val a = AttributeReference("a", DoubleType)()
      val b = AttributeReference("b", DoubleType)()
      val c = AttributeReference("c", DoubleType)()
      Add(Add(a, b), c).semanticEquals(Add(a, Add(b, c)))                // true
      Multiply(Multiply(a, b), c).semanticEquals(Multiply(a, Multiply(b, c)))  // true
      

      Proposed fix

      Floating-point + and * are commutative, so a + b and b + a may still be treated as
      semantically equal; it is only the re-association across levels that is unsound. The narrow fix is
      to stop flattening when the operation's dataType is FloatType or DoubleType, and
      canonicalize just the two direct children, sorting them as today. That keeps commutative reuse and
      rejects (a + b) + c vs a + (b + c).

      A more conservative variant is to return withCanonicalizedChildren for floating-point types,
      mirroring the existing decimal fallback added in SPARK-40903 for a comparable reason (reordering
      changing the result), at the cost of also losing the commutative case.

      The same buildCanonicalizedPlan path produces MultiCommutativeOp above
      spark.sql.analyzer.canonicalization.multiCommutativeOpMemoryOptThreshold operands, so the guard
      belongs in canonicalized before the operands are gathered rather than in the reduce step.

      Suggested coverage: an assertion pair in the canonicalization suite ((a+b)+c not semantically
      equal to a+(b+c) for DOUBLE, while a+b stays equal to b+a), plus the two end-to-end
      cases above.

      Notes

      Integer, boolean and bitwise operands are unaffected: reordering those changes only the order in
      which ANSI errors may be raised, which Spark does not specify. For FLOAT/DOUBLE the returned value
      itself changes.

      Not a regression. Add.canonicalized / Multiply.canonicalized have the same shape on
      branch-3.5 through master, so every maintained branch is affected; the numbers above were measured
      on master.

      Found while reviewing https://github.com/apache/spark/pull/58424, where an optimizer rule relies on
      sameResult to prove two scans are equivalent. The gap is in the shared canonicalization, not in
      that rule.

            Assignee:
            Unassigned
            Reporter:
            Hengrui Hu
            Votes:
            0 Vote for this issue
            Watchers:
            1 Start watching this issue

              Created:
              Updated: