You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by ya...@apache.org on 2026/09/09 12:44:52 UTC

(spark) branch branch-4.x updated: [SPARK-58818][SQL] Fix wrong results from evaluating a common expression once per reference in a conditional branch

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

LuciferYang 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 93e2850ba31f [SPARK-58818][SQL] Fix wrong results from evaluating a common expression once per reference in a conditional branch
93e2850ba31f is described below

commit 93e2850ba31f500f174368cd190839d9e747c2bc
Author: YangJie <ya...@baidu.com>
AuthorDate: Wed Sep 9 20:44:24 2026 +0800

    [SPARK-58818][SQL] Fix wrong results from evaluating a common expression once per reference in a conditional branch
    
    ### What changes were proposed in this pull request?
    
    `With` becomes evaluable and memoizes each common expression for one evaluation of its child: the first `CommonExpressionRef` reached computes the definition, later ones read the value back. For a projection that is once per row, for a sort key once per comparison side. `RewriteWithExpression` then leaves a `With` in a conditional branch alone instead of substituting its definition into every reference.
    
    This replaces the pre-evaluation approach of the earlier commits on this branch. The branch was not force-pushed, so those commits are still listed; the net diff is the memoization change.
    
    - `With.eval` and `With.doGenCode` (it was `Unevaluable`), with the memoized value on a `CommonExpressionCell`. A reference under a `CodegenFallback`, or under a nested `With` that falls back, makes the whole `With` interpreted: the generated code clears codegen flags, not cells, and mixing the two would hold two values for one evaluation. It raises an internal error for three shapes only a direct case-class caller can build -- two definitions with one id, a definition object shared w [...]
    - `CodegenContext.withCommonExprs` / `getCommonExpr`, modelled on `withLambdaVars` / `getLambdaVar`. A definition gets a value slot and a `computed` flag, and the reference emits the definition's code behind that flag, so it runs where the first reference is reached rather than ahead of the branch.
    - The branch path of `RewriteWithExpression` inlines only definitions that gain nothing from memoizing: referenced at most once, or cheap and deterministic. The count is taken after the nested rewrite, since substituting an inner definition duplicates the outer references it holds and a count taken before reads one where there are two. `CollapseProject.isCheap` answers what one evaluation costs, not whether a second one agrees with the first — it admits a `PythonUDF` — so determinism  [...]
    - `EquivalentExpressions.childrenToRecurse` does not descend into a `With`, for the reason it does not descend into a `CodegenFallback`: a reference cannot be evaluated ahead of the `With` that binds it. The `With` itself is still a candidate.
    - The `PhysicalAggregation` arm returns the original operator when neither rewrite changed anything. A surviving `With` keeps its guard true, so restructuring unconditionally added a `Project` per fixed-point iteration.
    
    ### Why are the changes needed?
    
    `BETWEEN` references its input twice, so:
    
    ```sql
    SELECT CASE WHEN id < 0 THEN false
                ELSE monotonically_increasing_id() BETWEEN 3 AND 5 END AS r
    FROM range(0, 10, 1, 1)
    ```
    
    returns 6 `true` rows where 3 is correct: inlining gives each reference its own counter, and the second only advances on rows whose first comparison passed. `nullif` builds the same shape. Outside a conditional branch this is already correct, because the rule hoists the definition into a `Project` and both references read one column.
    
    Inside a branch it cannot hoist: a `Project` runs for every row, so a definition that can raise would trade a wrong result for a spurious error. The earlier commits hoisted only where the definition provably cannot raise, which left `rand() / col` and `randstr(3, 0)` wrong and shifted a generator's values onto rows whose branch was never taken. The review asked whether `stateful`, `throwable` and `deterministic` suffice to make that judgement safely. Memoization needs no such judgemen [...]
    
    SPARK-58902 tracks what is still substituted: a common expression in a join condition that references both sides, and one whose definition cannot be put in a `Project`.
    
    ### Does this PR introduce _any_ user-facing change?
    
    Yes. The wrong results above become correct for every definition the rule keeps, which is any that is not both cheap and deterministic -- the earlier approach on this branch handled an allowlisted subset instead -- and no evaluation moves to a row that did not reach the branch. A cheap definition that reports itself deterministic is still substituted at every reference, which is unchanged and is why an impure foldable such as an `aes_encrypt` with no IV can still yield two values. Suc [...]
    
    A `With` can now appear in an optimized and physical plan, so `explain` changes for a conditional branch holding a non-cheap common expression referenced more than once. No new configuration and no syntax change. The migration guide gains an entry.
    
    ### How was this patch tested?
    
    New `WithExpressionEvalSuite` drives `eval` and `genCode` directly, with a counter expression standing in for a generator: memoization across references, laziness behind a branch and behind a short circuit, nested scopes, a `With` rebuilt by a rule, copies owning their own cells, two definitions keeping separate state, the definition's code generated once, code size under nesting, the two fallback shapes, and the shapes that are refused.
    
    New cases in `ColumnExpressionSuite` run the repro and eight more shapes end to end on all three evaluation paths, including three hosts other than a `Project` — a `Filter` predicate, a generated sort key, and a branch the analyzer moves into the projection it builds for a window function — and a definition that has to fall back to `eval`. `RewriteWithExpressionSuite` pins the rule's decisions on both paths; `SubexpressionEliminationSuite` pins that nothing below a `With` becomes a co [...]
    
    ### Was this patch authored or co-authored using generative AI tooling?
    
    Generated-by: Claude Opus 5
    
    Closes #58045 from LuciferYang/SPARK-with-nondet-inline.
    
    Authored-by: YangJie <ya...@baidu.com>
    Signed-off-by: yangjie01 <ya...@baidu.com>
    (cherry picked from commit 53b19220d3a2c2f2ff0ac54c017b234a948326a7)
    Signed-off-by: yangjie01 <ya...@baidu.com>
---
 docs/sql-migration-guide.md                        |   1 +
 .../expressions/EquivalentExpressions.scala        |  14 +-
 .../spark/sql/catalyst/expressions/With.scala      | 280 +++++++++++++++-
 .../expressions/codegen/CodeGenerator.scala        | 158 +++++++++
 .../expressions/codegen/CodegenFallback.scala      |  44 ++-
 .../catalyst/optimizer/RewriteWithExpression.scala | 174 +++++++---
 .../SubexpressionEliminationSuite.scala            |  51 +++
 .../expressions/WithExpressionEvalSuite.scala      | 373 +++++++++++++++++++++
 .../optimizer/RewriteWithExpressionSuite.scala     | 195 ++++++++++-
 .../apache/spark/sql/ColumnExpressionSuite.scala   | 217 +++++++++++-
 10 files changed, 1434 insertions(+), 73 deletions(-)

diff --git a/docs/sql-migration-guide.md b/docs/sql-migration-guide.md
index 1fe513d5941b..7577eb18078c 100644
--- a/docs/sql-migration-guide.md
+++ b/docs/sql-migration-guide.md
@@ -26,6 +26,7 @@ license: |
 
 - Since Spark 4.4, the optimizer rule `SimplifyCaseConversionExpressions` no longer simplifies mixed case conversions `LOWER(UPPER(str))` to `LOWER(str)` or `UPPER(LOWER(str))` to `UPPER(str)`. This preserves standard Unicode case mapping semantics for non-ASCII characters such as Latin small letter dotless i (`ı` U+0131) and micro sign (`µ` U+00B5).
 - Since Spark 4.4, the Oracle JDBC datasource maps Oracle DATE and TIMESTAMP to TimestampNTZType unconditionally, ignoring the JDBC read option `preferTimestampNTZ` (DATE only when the driver default `oracle.jdbc.mapDateToTimestamp=true` surfaces it as TIMESTAMP; otherwise DATE stays DateType). In 4.3 and earlier these were read as TimestampType, or as TimestampNTZType only when `preferTimestampNTZ=true`. This faithfully represents these zoneless Oracle types. Unaffected: Oracle DATE rea [...]
+- Since Spark 4.4, a nondeterministic common expression that a conditional branch reads more than once is evaluated once, and every read sees that one value. `BETWEEN` and `NULLIF` read their input twice, so an expression such as `CASE WHEN c THEN monotonically_increasing_id() BETWEEN 3 AND 5 END` previously gave each read its own value and could return a different result. Queries whose results depended on the earlier behaviour change, and an optimized or physical plan may now show a `wi [...]
 - Since Spark 4.4, for storage-partitioned joins, `spark.sql.requireAllClusterKeysForCoPartition` requires every join key to be covered by some partition key instead of matching the partition keys positionally. As a result, a join-key column partitioned by more than one transform no longer prevents shuffle elimination, and `spark.sql.sources.v2.bucketing.allowKeysSubsetOfPartitionKeys.enabled` no longer additionally requires `spark.sql.requireAllClusterKeysForCoPartition` to be `false` w [...]
 
 ## Upgrading from Spark SQL 4.2 to 4.3
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
index 7722d5611670..ed31c69eb82b 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/EquivalentExpressions.scala
@@ -157,9 +157,21 @@ class EquivalentExpressions(
   //        ahead of time.
   private def childrenToRecurse(expr: Expression): Seq[Expression] = expr match {
     case _: CodegenFallback => Nil
+    // A `CommonExpressionRef` cannot be evaluated ahead of the `With` that binds it, for the same
+    // reason a `LambdaVariable` cannot be evaluated ahead of its loop. Do not descend, so that no
+    // subtree holding a reference -- nor a `CommonExpressionDef`, which is unevaluable -- becomes
+    // a candidate. The `With` itself may still be deduplicated as a whole, which is safe: it
+    // carries its own definitions and brings their slots into scope wherever it is generated.
+    case _: With => Nil
     case c: ConditionalExpression => c.alwaysEvaluatedInputs.map(skipForShortcut)
     case h: HigherOrderFunction => h.alwaysEvaluatedArguments
-    case other => skipForShortcut(other).children
+    case other => skipForShortcut(other) match {
+      // The peel walks past `And`/`Or`, which are not `ConditionalExpression`s, so it can land on a
+      // `With` and hand back its children -- the descent the case above exists to prevent. Ask
+      // again after peeling.
+      case _: With => Nil
+      case peeled => peeled.children
+    }
   }
 
   // For some special expressions we cannot just recurse into all of its children, but we can
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/With.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/With.scala
index 5f6f9afa5797..6f7467005369 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/With.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/With.scala
@@ -17,17 +17,49 @@
 
 package org.apache.spark.sql.catalyst.expressions
 
+import scala.collection.mutable
+
+import org.apache.spark.SparkException
+import org.apache.spark.sql.catalyst.InternalRow
 import org.apache.spark.sql.catalyst.expressions.aggregate.AggregateExpression
+import org.apache.spark.sql.catalyst.expressions.codegen.{CodegenContext, CodegenFallback, ExprCode}
+import org.apache.spark.sql.catalyst.expressions.codegen.Block._
 import org.apache.spark.sql.catalyst.trees.TreePattern.{COMMON_EXPR_REF, TreePattern, WITH_EXPRESSION}
 import org.apache.spark.sql.types.DataType
 
+/**
+ * The value of one common expression, computed the first time a [[CommonExpressionRef]] reads it
+ * and reused by every later reference. The reference passes the definition in, so this is a pair of
+ * mutable slots and nothing else.
+ *
+ * [[With]] clears it on entry, which is per entry rather than per row: one `With` object can sit at
+ * two positions of a tree, and `GenerateOrdering` enters one twice, once per comparison side.
+ */
+class CommonExpressionCell extends Serializable {
+  @transient private var computed: Boolean = false
+  @transient private var cached: Any = _
+
+  private[expressions] def clear(): Unit = {
+    computed = false
+    cached = null
+  }
+
+  private[expressions] def get(definition: Expression, input: InternalRow): Any = {
+    if (!computed) {
+      cached = definition.eval(input)
+      computed = true
+    }
+    cached
+  }
+}
+
 /**
  * An expression holder that keeps a list of common expressions and allow the actual expression to
  * reference these common expressions. The common expressions are guaranteed to be evaluated only
  * once even if it's referenced more than once. This is similar to CTE but is expression-level.
  */
 case class With(child: Expression, defs: Seq[CommonExpressionDef])
-  extends Expression with Unevaluable {
+  extends Expression {
   // We do not allow creating a With expression with an AggregateExpression that contains a
   // reference to a common expression defined in that scope (note that it can contain another With
   // expression with a common expression ref of the inner With). This is to prevent the creation of
@@ -38,11 +70,157 @@ case class With(child: Expression, defs: Seq[CommonExpressionDef])
   override def dataType: DataType = child.dataType
   override def nullable: Boolean = child.nullable
   override def children: Seq[Expression] = child +: defs
+
+  /**
+   * The references in `child` that name one of these definitions, paired with the definition each
+   * names, found once since the tree does not change between evaluations. Only `child` is scanned,
+   * which is why the checks below refuse a definition holding a reference of this scope.
+   */
+  @transient private lazy val refsToBind: IndexedSeq[(CommonExpressionRef, CommonExpressionDef)] = {
+    // Three shapes whose bindings cannot be kept straight: before these checks this path answered
+    // the first two with a wrong value, and the third either overflowed the stack or failed as an
+    // unbound reference. Generating them is refused for the first two, by an id-keyed rule in
+    // `withCommonExprs`, and for a definition that reaches its own id, by `filling` -- but not for
+    // one that only reads a sibling, which generates correctly, since every sibling slot is
+    // registered before the child. Only a caller building the case class directly reaches any of
+    // this: `With.apply` mints both the definitions and their ids. The last check keys on the whole
+    // `CommonExpressionId`, so it also fires on a canonicalized or `NormalizePlan`-normalized tree,
+    // where ids are renumbered per scope; those forms are compared, never evaluated.
+    if (defs.map(_.id).distinct.length != defs.length) {
+      throw SparkException.internalError(
+        "Duplicate common expression ids in one With: " + defs.map(_.id.id).mkString(", "))
+    }
+    (child +: defs.map(_.child)).foreach(_.foreach {
+      case w: With if w.defs.exists(innerDef => defs.exists(_ eq innerDef)) =>
+        throw SparkException.internalError(
+          "A nested With shares a common expression definition object with the With around it")
+      case _ =>
+    })
+    val ownIds = defs.map(_.id).toSet
+    defs.foreach(_.child.foreach {
+      case r: CommonExpressionRef if ownIds.contains(r.id) =>
+        throw SparkException.internalError(
+          "A common expression definition references an id its own With defines: " + r.id.id)
+      case _ =>
+    })
+    val idToDef = defs.map(d => d.id -> d).toMap
+    val found = mutable.ArrayBuffer.empty[(CommonExpressionRef, CommonExpressionDef)]
+    child.foreach {
+      // One entry per reference *object*, not per occurrence: `BETWEEN` reads one object twice, and
+      // a second entry would save the binding the first just installed. Identity, not equality --
+      // two objects of one id compare equal while needing separate saves.
+      case r: CommonExpressionRef if idToDef.contains(r.id) && !found.exists(_._1 eq r) =>
+        found += ((r, idToDef(r.id)))
+      case _ =>
+    }
+    found.toIndexedSeq
+  }
+
+  /**
+   * Where each reference pointed before this `With` bound it, restored when the child returns, so a
+   * reference shared with an enclosing `With` goes back to answering for that one. Instance state
+   * rather than per-row allocation: a `With` cannot be re-entered during its own entry, which would
+   * need the tree to contain itself.
+   */
+  @transient private lazy val savedDefinitions = new Array[Expression](refsToBind.length)
+  @transient private lazy val savedCells = new Array[CommonExpressionCell](refsToBind.length)
+
+  /**
+   * Binds this `With`'s references to its own cells, clears them, and evaluates the child, so a
+   * definition is evaluated where the child would have evaluated it, once. See
+   * [[CommonExpressionCell]].
+   *
+   * Binding happens per evaluation, not once: two `With`s can share a reference object, because a
+   * rebuilt reference compares equal to the one it replaces and `transform` therefore keeps the
+   * original. Binding once would leave whichever bound last deciding for both. Bind-and-restore
+   * instead makes the `With` currently evaluating the owner, and only until its child is done.
+   */
+  override def eval(input: InternalRow): Any = {
+    var i = 0
+    while (i < refsToBind.length) {
+      val (ref, exprDef) = refsToBind(i)
+      savedDefinitions(i) = ref.boundDefinition
+      savedCells(i) = ref.boundCell
+      ref.bindTo(exprDef)
+      i += 1
+    }
+    defs.foreach(_.cell.clear())
+    try {
+      child.eval(input)
+    } finally {
+      var j = 0
+      while (j < refsToBind.length) {
+        refsToBind(j)._1.bindTo(savedDefinitions(j), savedCells(j))
+        j += 1
+      }
+    }
+  }
+
+  // The cells are cleared on entry, so this holds state for the duration of one evaluation.
+  override def stateful: Boolean = true
+
+  /**
+   * Whether one of this `With`'s references will be evaluated interpretively even though this
+   * `With` is generated: it sits under a [[CodegenFallback]], or under a nested `With` that itself
+   * falls back (`With` is not a `CodegenFallback`, so it has to be named rather than matched). Such
+   * a reference needs its cell bound and cleared; the generated code clears codegen flags instead.
+   */
+  @transient private lazy val refUnderCodegenFallback: Boolean = {
+    val ids = defs.map(_.id).toSet
+    def holdsMyRef(e: Expression): Boolean = e.exists {
+      case r: CommonExpressionRef => ids.contains(r.id)
+      case _ => false
+    }
+    child.exists {
+      case f: CodegenFallback => holdsMyRef(f)
+      case w: With if w.refUnderCodegenFallback => holdsMyRef(w)
+      case _ => false
+    }
+  }
+
+  /**
+   * Clears each definition's flag, then generates the child into the same block, so on a row that
+   * does not reach the branch holding this `With` neither the clearing nor any reference runs.
+   *
+   * A reference that will be evaluated interpretively (see [[refUnderCodegenFallback]]) sends the
+   * whole `With` down [[eval]] instead. Generating part of it would compute a definition once
+   * through the flags and once through the cell, holding two values for one row. `ctx.INPUT_ROW` is
+   * set on that path because `CollapseCodegenStages.supportCodegen` turns whole-stage codegen off
+   * for a plan whose expressions hold the offending `CodegenFallback`. No builder in the tree
+   * reaches it today -- `Between` and `NullIf` put their references under nodes that generate code
+   * -- so this is for the next builder and for the nested case.
+   *
+   * One object is registered however many times this is generated, so a stateful definition
+   * advances across the two keys `GenerateOrdering` generates. That predates this expression: a
+   * stateful `CodegenFallback` sort key behaves the same way with no `With` in the tree, since
+   * `freshCopyIfContainsStatefulExpression` does not reach a stateful leaf that leaves
+   * `LeafLike`'s default `withNewChildrenInternal` in place.
+   */
+  override protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+    if (refUnderCodegenFallback) {
+      return CodegenFallback.generate(this, ctx, ev)
+    }
+    ctx.withCommonExprs(defs) { slots =>
+      val clearFlags = slots.map(s => s"${s.computed} = false;").mkString("\n")
+      val childGen = child.genCode(ctx)
+      ev.copy(
+        code = code"""
+           |$clearFlags
+           |${childGen.code}
+         """.stripMargin,
+        isNull = childGen.isNull,
+        value = childGen.value)
+    }
+  }
+
   override protected def withNewChildrenInternal(
       newChildren: IndexedSeq[Expression]): Expression = {
     val newDefs = newChildren.tail.map(_.asInstanceOf[CommonExpressionDef])
     // If any `CommonExpressionDef` has been updated (data type or nullability), also update its
-    // `CommonExpressionRef` in the `child`.
+    // `CommonExpressionRef` in the `child`. This cannot be used to hand the new `With` its own
+    // reference objects: a rebuilt reference is `==` the one it replaces, since the binding it
+    // carries is not part of its equality, so `transform` keeps the original. `eval` rebinds
+    // instead of relying on the references being unshared -- see `refsToBind`.
     val newChild = newDefs.filter(_.resolved).foldLeft(newChildren.head) { (result, newDef) =>
       defs.find(_.id == newDef.id).map { oldDef =>
         if (newDef.dataType != oldDef.dataType || newDef.nullable != oldDef.nullable) {
@@ -149,9 +327,26 @@ object CommonExpressionId {
 
 /**
  * A wrapper of common expression to carry the id.
+ *
+ * The `cell` holds the value on the row being evaluated. It sits outside the case class parameters,
+ * so a definition still compares and canonicalizes by its id and child, and `copy` gives the copy a
+ * fresh one. The enclosing [[With]] binds each reference to the cell of the definition standing in
+ * the tree with it, so a cell that a transform left behind is never read.
+ *
+ * Staying `Unevaluable` is what keeps optimizer-time folding away from a `With` that survives in a
+ * conditional branch: `ConvertToLocalRelation` refuses a projection holding one, so a branch over a
+ * `LocalRelation` is not executed while the plan is still being optimized. Making a definition
+ * evaluable would start folding those branches.
  */
 case class CommonExpressionDef(child: Expression, id: CommonExpressionId = new CommonExpressionId())
   extends UnaryExpression with Unevaluable {
+  private[expressions] val cell: CommonExpressionCell = new CommonExpressionCell
+
+  // The definition owns the cell its references read, so a copy must own a different one. `copy`
+  // gives it one; declaring this is what makes `freshCopyIfContainsStatefulExpression` ask for the
+  // copy even when the definition's own child did not change.
+  override def stateful: Boolean = true
+
   override def dataType: DataType = child.dataType
   override protected def withNewChildInternal(newChild: Expression): Expression =
     copy(child = newChild)
@@ -162,7 +357,86 @@ case class CommonExpressionDef(child: Expression, id: CommonExpressionId = new C
  * referenced, so that we can determine the data type and nullable of the reference node.
  */
 case class CommonExpressionRef(id: CommonExpressionId, dataType: DataType, nullable: Boolean)
-  extends LeafExpression with Unevaluable {
+  extends LeafExpression {
   def this(exprDef: CommonExpressionDef) = this(exprDef.id, exprDef.dataType, exprDef.nullable)
+
+  /**
+   * The definition this reference names, and the cell holding its value for the current row. Both
+   * are wired by the enclosing [[With]] before it evaluates its child, and are left out of the case
+   * class parameters so that equality and canonicalization are unchanged -- and so that a rule
+   * comparing two references does not compare their cells.
+   *
+   * `@transient` for the reason [[CommonExpressionCell]]'s own fields are: a binding lives only for
+   * the duration of one `With.eval`, which restores it on the way out, so serializing a task sees
+   * null. A serialization that happens while an evaluation is still on the stack would otherwise
+   * capture a live binding, and the deserialized reference would evaluate that definition rather
+   * than raise, dragging the definition's whole subtree along with it.
+   */
+  @transient private var definition: Expression = _
+  @transient private var cell: CommonExpressionCell = _
+
+  private[expressions] def bindTo(exprDef: CommonExpressionDef): Unit = {
+    definition = exprDef.child
+    cell = exprDef.cell
+  }
+
+  private[expressions] def boundDefinition: Expression = definition
+  private[expressions] def boundCell: CommonExpressionCell = cell
+
+  private[expressions] def bindTo(
+      newDefinition: Expression,
+      newCell: CommonExpressionCell): Unit = {
+    definition = newDefinition
+    cell = newCell
+  }
+
   override val nodePatterns: Seq[TreePattern] = Seq(COMMON_EXPR_REF)
+
+  // The cell is cleared by the enclosing `With` on every entry, so this reads mutable state.
+  override def stateful: Boolean = true
+
+  /**
+   * A copy must not carry this reference's binding: the copy belongs to a different `With`, which
+   * wires it to its own cell. `LeafLike` returns `this` here, which would hand two `With`s one
+   * reference object and let whichever wires last decide what both of them read --
+   * `NamedLambdaVariable` overrides this for the same reason.
+   */
+  override def withNewChildrenInternal(
+      newChildren: IndexedSeq[Expression]): CommonExpressionRef = copy()
+
+  override def eval(input: InternalRow): Any = {
+    if (cell == null) {
+      throw SparkException.internalError(
+        s"Cannot evaluate a common expression reference outside its With: $this")
+    }
+    cell.get(definition, input)
+  }
+
+  /**
+   * Computes the definition into the shared slots if this row has not done so yet, then reads them.
+   * The code that computes it is emitted here rather than by the enclosing `With`, so it runs where
+   * the first reference is reached -- behind a short-circuiting operator or a nested conditional,
+   * if that is where the reference sits.
+   *
+   * A second reference emits the same code again, which never runs because the flag is set. What
+   * that code is depends on the definition: a call, where the definition can be put in a method, so
+   * that a definition that is or holds another `With` is not pasted once per reference at every
+   * level; the body itself otherwise, whose locals are declared inside each guard. No copy of one
+   * body encloses another, so repeating it declares nothing twice in one scope: a definition
+   * reading a sibling is generated inside that sibling's guard, not inside its own, and one that
+   * reaches its own id -- directly or around a cycle -- re-enters `fill` and is refused before any
+   * Java exists. See `CommonExprSlots.fill`, which also says what bounds the code when a method is
+   * not possible.
+   */
+  override protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+    val slots = ctx.getCommonExpr(id.id)
+    ev.copy(
+      code = code"""
+         |if (!${slots.computed}) {
+         |  ${slots.fill}
+         |}
+       """.stripMargin,
+      isNull = slots.value.isNull,
+      value = slots.value.value)
+  }
 }
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodeGenerator.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodeGenerator.scala
index 57864957bc13..4cacc6efc055 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodeGenerator.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodeGenerator.scala
@@ -31,6 +31,7 @@ import org.apache.spark.sql.catalyst.InternalRow
 import org.apache.spark.sql.catalyst.encoders.HashableWeakReference
 import org.apache.spark.sql.catalyst.expressions._
 import org.apache.spark.sql.catalyst.expressions.codegen.Block._
+import org.apache.spark.sql.catalyst.trees.TreePattern.WITH_EXPRESSION
 import org.apache.spark.sql.catalyst.types._
 import org.apache.spark.sql.catalyst.types.ops.TypeOps
 import org.apache.spark.sql.catalyst.util.{ArrayData, MapData, SQLOrderingUtil, UnsafeRowUtils}
@@ -207,6 +208,163 @@ class CodegenContext extends Logging {
       throw QueryExecutionErrors.lambdaVariableNotDefinedError(id))
   }
 
+  /**
+   * The slots a `CommonExpressionRef` reads: the value and its nullness, plus the flag saying
+   * whether this row has computed them yet, and the definition to compute them from.
+   */
+  case class CommonExprSlots(
+      value: ExprCode,
+      computed: String,
+      definition: Expression) {
+
+    // Not constructor parameters: a mutable one takes part in `equals`/`hashCode`/`copy`, so a
+    // slot's hash would change as it is filled and a `copy` would carry another scope's code.
+    private var fillCode: Option[Block] = None
+    private var filling: Boolean = false
+
+    /**
+     * The code that computes the definition into the slots and sets `computed`, which a reference
+     * emits behind that flag. Cached, so every reference shares whatever mutable state the
+     * definition allocated, such as an RNG.
+     *
+     * The cache lives on the slot, so it lasts exactly as long as the scope: the code names the
+     * `INPUT_ROW` and `currentVars` in effect when it was generated. `GenerateOrdering` generates
+     * its key once per comparison side under a different row variable, so a slot shared between the
+     * sides would read the wrong row, or not compile where `Expression.reduceCodeSize` has hoisted
+     * the reference into a method taking one row.
+     *
+     * `filling` catches a definition that references its own id, which would otherwise re-enter and
+     * recurse, since `fillCode` is set only after `definition.genCode` returns.
+     *
+     * The body goes into a method where it can and is worth it -- a definition that is or holds
+     * another `With`, or a body past the split threshold -- so it is emitted once per scope rather
+     * than once per reference, which for nested `With`s would double per level. A method is only
+     * possible where the definition reads the input row rather than local variables, the condition
+     * `reduceCodeSize` splits under. That is not the same as whole-stage codegen being off: a
+     * whole-stage `Project` or `Filter` passes local variables, while
+     * `SortMergeJoinExec.createJoinKey` and the aggregate output paths generate against a row.
+     */
+    def fill: Block = {
+      if (fillCode.isEmpty) {
+        if (filling) {
+          throw SparkException.internalError(
+            "Cannot generate a common expression whose definition references it: " +
+              definition.toString)
+        }
+        filling = true
+        try {
+          fillCode = Some(build)
+        } finally {
+          filling = false
+        }
+      }
+      fillCode.get
+    }
+
+    private def build: Block = {
+      val defGen = definition.genCode(CodegenContext.this)
+      // Whether the isNull slot exists is decided by the definition, so it is read off the slot
+      // rather than off a reference's own `nullable`: taking it from both would let the two
+      // disagree, and either emit `false = <isNull>;`, which does not compile, or leave the slot
+      // holding the previous row's nullness.
+      val assignIsNull = if (value.isNull == FalseLiteral) {
+        ""
+      } else {
+        s"${value.isNull} = ${defGen.isNull};"
+      }
+      val body = code"""
+         |${defGen.code}
+         |$assignIsNull
+         |${value.value} = ${defGen.value};
+         |$computed = true;
+       """.stripMargin
+      // TODO(SPARK-59295): cover the local-variable case too, by passing the `currentVars` values a
+      //   definition reads into the method as parameters, the way
+      //   `subexpressionEliminationForWholeStageCodegen` does. It needs a decision first:
+      //   `getLocalInputVariableValues` hoists an input variable that is not evaluated yet to
+      //   before the call, which for a reference behind a branch means evaluating it on rows that
+      //   never reach the reference.
+      val canPutInMethod = INPUT_ROW != null && currentVars == null
+      // A definition that is or holds another `With` is the shape whose code doubles per level,
+      // and what this is aimed at. It is not the only one -- a definition referencing a sibling
+      // definition of the same `With` doubles the same way, and codegen accepts that, since the
+      // sibling's slots are in scope while this definition is generated (`With.refsToBind` says
+      // why nothing builds that tree, and that evaluating one raises). What bounds those is not
+      // the length arm below: `body` is assembled after `definition.genCode` already ran
+      // `reduceCodeSize`, so the arm fires only in the band just under the threshold. It is
+      // `reduceCodeSize` itself, which hoists whichever node's code first passes the threshold as
+      // generation walks up, capping what one level contributes, so the code stays linear in the
+      // depth either way. The length arm just keeps the same body from being split once per
+      // reference, which leaves the methods small and the code as large.
+      val worthAMethod = definition.containsPattern(WITH_EXPRESSION) ||
+        body.length > SQLConf.get.methodSplitThreshold
+      if (canPutInMethod && worthAMethod) {
+        val funcName = freshName("computeCommonExpr")
+        val funcFullName = addNewFunction(funcName,
+          s"""
+             |private void $funcName(InternalRow $INPUT_ROW) {
+             |  $body
+             |}
+           """.stripMargin)
+        code"$funcFullName($INPUT_ROW);"
+      } else {
+        body
+      }
+    }
+  }
+
+  /**
+   * Holding a map of the common expressions of the `With` expressions currently being generated,
+   * the same way [[currentLambdaVars]] holds the variables of the enclosing lambdas.
+   */
+  var currentCommonExprs: mutable.Map[Long, CommonExprSlots] = mutable.HashMap.empty
+
+  /**
+   * Allocates a value slot and a `computed` flag per definition, generates `f` with them in scope,
+   * then takes them out of scope again. A reference generated inside `f` reads the slots back by
+   * id and fills them the first time it is reached on a row -- the enclosing `With` only clears the
+   * flags.
+   */
+  def withCommonExprs(defs: Seq[CommonExpressionDef])(f: Seq[CommonExprSlots] => ExprCode)
+    : ExprCode = {
+    // The ids this call registered, so the cleanup takes back exactly those: the duplicate-id check
+    // below throws partway, and removing by the whole `defs` list would take that duplicate out of
+    // the enclosing scope that still owns it. Allocating inside the `try` is what runs the cleanup
+    // at all -- otherwise the slots allocated before the throw stay registered, and a later
+    // `getCommonExpr` for one of those ids resolves an orphan instead of reporting it out of scope.
+    val added = mutable.ArrayBuffer.empty[Long]
+    try {
+      val slots = defs.map { d =>
+        val id = d.id.id
+        if (currentCommonExprs.contains(id)) {
+          throw SparkException.internalError(s"Common expression $id is already being generated")
+        }
+        val isNull = if (d.nullable) {
+          JavaCode.isNullGlobal(addMutableState(JAVA_BOOLEAN, "commonExprIsNull"))
+        } else {
+          FalseLiteral
+        }
+        val value = addMutableState(javaType(d.dataType), "commonExprValue")
+        val slot = CommonExprSlots(
+          ExprCode(isNull, JavaCode.global(value, d.dataType)),
+          addMutableState(JAVA_BOOLEAN, "commonExprComputed"),
+          d.child)
+        currentCommonExprs.put(id, slot)
+        added += id
+        slot
+      }
+      f(slots)
+    } finally {
+      added.foreach(currentCommonExprs.remove)
+    }
+  }
+
+  def getCommonExpr(id: Long): CommonExprSlots = {
+    currentCommonExprs.getOrElse(
+      id,
+      throw SparkException.internalError(s"Common expression $id is not in scope"))
+  }
+
   /**
    * Holding expressions' inlined mutable states like `MonotonicallyIncreasingID.count` as a
    * 2-tuple: java type, variable name.
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodegenFallback.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodegenFallback.scala
index 3f4704d287cb..6b7582fe885f 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodegenFallback.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/expressions/codegen/CodegenFallback.scala
@@ -25,13 +25,37 @@ import org.apache.spark.sql.catalyst.expressions.codegen.Block._
  */
 trait CodegenFallback extends Expression {
 
-  protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode = {
+  protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode =
+    CodegenFallback.generate(this, ctx, ev)
+}
+
+object CodegenFallback {
+
+  /**
+   * Generates code that evaluates `e` by calling its `eval`, rather than by generating code for it.
+   * This is what [[CodegenFallback]] gives the expressions that mix it in, and is also used by an
+   * expression that can generate code in general but has to fall back for a particular shape of
+   * its own tree -- see `With.doGenCode`.
+   *
+   * Three places reason about which subtrees run interpretively, and all of them dispatch on the
+   * trait. `CollapseCodegenStages.supportCodegen` walks whole expression trees, so it finds a
+   * non-leaf descendant `CodegenFallback` whatever node called `generate` -- that is how a `With`
+   * holding one gets whole-stage codegen turned off without being one itself. The other two
+   * dispatch on the node in hand: `EquivalentExpressions.childrenToRecurse`, which keeps a subtree
+   * that only `eval` reaches out of subexpression elimination, and
+   * `With.refUnderCodegenFallback`, which decides whether a memoized reference is reached that way.
+   * A caller that is not a `CodegenFallback` is invisible to those two and has to be named in each.
+   * One that falls back for a reason other than holding such a descendant would have to be named in
+   * `CollapseCodegenStages` as well, since nothing else would tell it that the input row this code
+   * needs is not there.
+   */
+  def generate(e: Expression, ctx: CodegenContext, ev: ExprCode): ExprCode = {
     // LeafNode does not need `input`
-    val input = if (this.isInstanceOf[LeafExpression]) "null" else ctx.INPUT_ROW
+    val input = if (e.isInstanceOf[LeafExpression]) "null" else ctx.INPUT_ROW
     val idx = ctx.references.length
-    ctx.references += this
+    ctx.references += e
     var childIndex = idx
-    this.foreach {
+    e.foreach {
       case n: Nondeterministic =>
         // This might add the current expression twice, but it won't hurt.
         ctx.references += n
@@ -44,22 +68,22 @@ trait CodegenFallback extends Expression {
       case _ =>
     }
     val objectTerm = ctx.freshName("obj")
-    val placeHolder = ctx.registerComment(this.toString)
-    val javaType = CodeGenerator.javaType(this.dataType)
-    if (nullable) {
+    val placeHolder = ctx.registerComment(e.toString)
+    val javaType = CodeGenerator.javaType(e.dataType)
+    if (e.nullable) {
       ev.copy(code = code"""
         $placeHolder
         Object $objectTerm = ((Expression) references[$idx]).eval($input);
         boolean ${ev.isNull} = $objectTerm == null;
-        $javaType ${ev.value} = ${CodeGenerator.defaultValue(this.dataType)};
+        $javaType ${ev.value} = ${CodeGenerator.defaultValue(e.dataType)};
         if (!${ev.isNull}) {
-          ${ev.value} = (${CodeGenerator.boxedType(this.dataType)}) $objectTerm;
+          ${ev.value} = (${CodeGenerator.boxedType(e.dataType)}) $objectTerm;
         }""")
     } else {
       ev.copy(code = code"""
         $placeHolder
         Object $objectTerm = ((Expression) references[$idx]).eval($input);
-        $javaType ${ev.value} = (${CodeGenerator.boxedType(this.dataType)}) $objectTerm;
+        $javaType ${ev.value} = (${CodeGenerator.boxedType(e.dataType)}) $objectTerm;
         """, isNull = FalseLiteral)
     }
   }
diff --git a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpression.scala b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpression.scala
index 08119798c9aa..29187b3e27d9 100644
--- a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpression.scala
+++ b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpression.scala
@@ -60,7 +60,13 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
         val agg = Aggregate(groupingExpressions, groupingExpressions ++ aggExprs, child)
         val rewrittenAgg = applyInternal(agg)
         val proj = Project(resExprs, rewrittenAgg)
-        applyInternal(proj)
+        val rewrittenProj = applyInternal(proj)
+        // A `With` in a conditional branch is left in the plan, so the guard above stays true for
+        // it on every iteration of this fixed-point batch, and restructuring unconditionally would
+        // add one `Project` per iteration. Hand back the original operator when neither rewrite
+        // changed anything: `mapExpressions` and `withNewChildren` preserve reference equality when
+        // they rewrite nothing, which is what makes this detectable.
+        if ((rewrittenAgg eq agg) && (rewrittenProj eq proj)) p else rewrittenProj
       case p if p.expressions.exists(_.containsPattern(WITH_EXPRESSION)) =>
         applyInternal(p)
     }
@@ -72,46 +78,38 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
    *
    * Inlining duplicates a definition at every reference, so a definition referenced more than once
    * must be safe to duplicate (see `isSafeToDuplicate`); anything else throws, as there is no plan
-   * here to pre-evaluate it into.
+   * here to pre-evaluate it into. That is a different question from the one the plan-level rewrite
+   * asks of a `With` in a conditional branch, which may keep it and memoize instead: whether
+   * inlining gains anything (see `canSubstitute`). Neither answer implies the other -- a definition
+   * that is cheap to evaluate twice need not evaluate to the same value twice.
    *
    * Does not descend into subquery plans (e.g. `ScalarSubquery`). A caller whose expression
    * may contain a subquery must rewrite those plans separately.
    */
-  private[sql] def applyForExpression(expression: Expression): Expression =
-    inlineWith(expression, checkDuplication = true)
-
-  // The plan-level rewrite shares this to inline `With` in conditional branches, which may not be
-  // evaluated and so can't be pulled into a Project; it passes false to inline unconditionally.
-  private def inlineWith(expression: Expression, checkDuplication: Boolean): Expression = {
+  private[sql] def applyForExpression(expression: Expression): Expression = {
     // Which definitions are safe to duplicate can only be decided outer-first, so it is collected
     // in a separate pass before inlining bottom-up.
-    val safeIds = if (checkDuplication) {
-      safeToDuplicateIds(expression)
-    } else {
-      Set.empty[CommonExpressionId]
-    }
+    val safeIds = safeToDuplicateIds(expression)
     expression.transformUpWithPruning(_.containsPattern(WITH_EXPRESSION)) {
       case With(child, defs) =>
-        if (checkDuplication) {
-          // Nested `With` is already rewritten, so a ref left in `child` belongs to `defs` or to
-          // an enclosing `With`. Only the ids defined here are checked.
-          val refCounts = child.collect { case ref: CommonExpressionRef => ref.id }
-            .groupBy(identity)
-            .transform((_, refs) => refs.size)
-          defs.foreach { commonExprDef =>
-            // Canonicalization re-numbers ids per `With`, so sibling `With`s reuse ids and break
-            // the global uniqueness `safeIds` relies on. Reject them, as the plan-level rewrite
-            // does.
-            if (commonExprDef.id.canonicalized) {
-              throw SparkException.internalError(
-                "Cannot inline canonicalized common expression definitions")
-            }
-            if (refCounts.getOrElse(commonExprDef.id, 0) > 1 &&
-              !safeIds.contains(commonExprDef.id)) {
-              throw SparkException.internalError(
-                "Cannot inline a common expression definition that is referenced more than " +
-                  s"once and is not safe to duplicate: ${commonExprDef.child.sql}")
-            }
+        // Nested `With` is already rewritten, so a ref left in `child` belongs to `defs` or to
+        // an enclosing `With`. Only the ids defined here are checked.
+        val refCounts = child.collect { case ref: CommonExpressionRef => ref.id }
+          .groupBy(identity)
+          .transform((_, refs) => refs.size)
+        defs.foreach { commonExprDef =>
+          // Canonicalization re-numbers ids per `With`, so sibling `With`s reuse ids and break
+          // the global uniqueness `safeIds` relies on. Reject them, as the plan-level rewrite
+          // does.
+          if (commonExprDef.id.canonicalized) {
+            throw SparkException.internalError(
+              "Cannot inline canonicalized common expression definitions")
+          }
+          if (refCounts.getOrElse(commonExprDef.id, 0) > 1 &&
+            !safeIds.contains(commonExprDef.id)) {
+            throw SparkException.internalError(
+              "Cannot inline a common expression definition that is referenced more than " +
+                s"once and is not safe to duplicate: ${commonExprDef.child.sql}")
           }
         }
         val refToExpr = defs.map(commonExprDef => commonExprDef.id -> commonExprDef.child).toMap
@@ -187,15 +185,9 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
 
   private def applyInternal(p: LogicalPlan): LogicalPlan = {
     val inputPlans = p.children
-    val commonExprIdSet = p.expressions
-      .flatMap(_.collect { case r: CommonExpressionRef => r.id })
-      .groupBy(identity)
-      .transform((_, v) => v.size)
-      .filter(_._2 > 1)
-      .keySet
     val commonExprsPerChild = Array.fill(inputPlans.length)(mutable.ListBuffer.empty[(Alias, Long)])
     var newPlan: LogicalPlan = p.mapExpressions { expr =>
-      rewriteWithExprAndInputPlans(expr, inputPlans, commonExprsPerChild, commonExprIdSet)
+      rewriteWithExprAndInputPlans(expr, inputPlans, commonExprsPerChild)
     }
     val newChildren = inputPlans.zip(commonExprsPerChild).map { case (inputPlan, commonExprs) =>
       if (commonExprs.isEmpty) {
@@ -217,11 +209,89 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
     }
   }
 
+  /**
+   * Whether substituting this definition into its references is as good as evaluating it once: it
+   * is referenced at most once anyway, or it is cheap to evaluate twice and deterministic.
+   *
+   * `CollapseProject.isCheap` answers what one evaluation costs, not whether a second is allowed --
+   * it admits a `PythonUDF`, which may be nondeterministic and is still in the tree here, since
+   * `SparkOptimizer` extracts it in a later batch. So determinism is asked separately.
+   *
+   * It is asked of the expression, which is weaker than `isSafeToDuplicate` above: `isCheap` admits
+   * anything foldable and `InvokeLike.foldable` implies `deterministic`, so an impure foldable such
+   * as an `aes_encrypt` with no IV still gets substituted and folded per copy. That predates this
+   * rule keeping a `With` -- the condition it replaced was no stricter -- and belongs either on
+   * those expressions or in one purity predicate shared with `isSafeToDuplicate`.
+   */
+  private def canSubstitute(
+      child: Expression,
+      id: CommonExpressionId,
+      multiplyReferenced: Set[CommonExpressionId]): Boolean = {
+    !multiplyReferenced.contains(id) || (CollapseProject.isCheap(child) && child.deterministic)
+  }
+
+  /**
+   * The ids the given `With` reads more than once, counted from the node in hand rather than once
+   * for the whole plan: substituting an inner definition duplicates the outer references it holds,
+   * and this rule works bottom-up, so a count taken before reads one where there are now two -- and
+   * a nondeterministic outer definition then gets inlined into both.
+   */
+  private def multiplyReferencedIds(child: Expression, defs: Seq[Expression]) = {
+    val counts = mutable.HashMap.empty[CommonExpressionId, Int]
+    child.foreach {
+      case r: CommonExpressionRef => counts(r.id) = counts.getOrElse(r.id, 0) + 1
+      case _ =>
+    }
+    // A reference found inside a definition counts as more than one read whatever its multiplicity
+    // there, because substituting that definition duplicates it at every reference the definition
+    // has, and that is decided in this same pass. Over-counting only withholds inlining, which is
+    // always semantically valid.
+    defs.foreach(_.foreach {
+      case r: CommonExpressionRef => counts(r.id) = counts.getOrElse(r.id, 0) + 2
+      case _ =>
+    })
+    counts.filter(_._2 > 1).keys.toSet
+  }
+
+  /**
+   * `w` with every definition that gains nothing from being memoized inlined into its references:
+   * one cheap enough to evaluate twice, and one referenced at most once anyway. This is the test
+   * the main rewrite already applies before it hoists a definition into a project.
+   *
+   * Inlining matters beyond the per-entry bookkeeping it saves. A `With` is not foldable, so it
+   * hides whatever it wraps from `ConstantFolding`, `PushFoldableIntoBranches`,
+   * `SimplifyConditionals` and `ReplaceNullWithFalseInPredicate`, all of which run in later
+   * batches. Dropping the `With` once nothing is left to memoize keeps
+   * `CASE WHEN c THEN nullif(1, 1) END` folding as it did before this rule learned to leave one
+   * behind.
+   */
+  private def inlineDefsThatGainNothing(w: With): Expression = {
+    val multiplyReferenced = multiplyReferencedIds(w.child, w.defs)
+    val (toInline, toKeep) = w.defs.partition { d =>
+      canSubstitute(d.child, d.id, multiplyReferenced)
+    }
+    if (toInline.isEmpty) {
+      w
+    } else {
+      val refToExpr = toInline.map(d => d.id -> d.child).toMap
+      val newChild = w.child.transformWithPruning(_.containsPattern(COMMON_EXPR_REF)) {
+        // A ref of a definition kept here, or of an enclosing `With`, is left for its owner.
+        case ref: CommonExpressionRef if refToExpr.contains(ref.id) => refToExpr(ref.id)
+      }
+      // `copy` rather than `withNewChildren`, which requires the child count to be unchanged. The
+      // references of the kept definitions are carried over as they are. Discarding `w` here does
+      // not make them unshared -- the same `With` reached from two parent positions is rewritten
+      // once per position, and each copy keeps these reference objects -- which is safe because
+      // `With.eval` binds on entry and restores on exit, so whichever copy is evaluating owns them
+      // for the duration of its child.
+      if (toKeep.isEmpty) newChild else w.copy(child = newChild, defs = toKeep)
+    }
+  }
+
   private def rewriteWithExprAndInputPlans(
       e: Expression,
       inputPlans: Seq[LogicalPlan],
       commonExprsPerChild: Array[mutable.ListBuffer[(Alias, Long)]],
-      commonExprIdSet: Set[CommonExpressionId],
       isNestedWith: Boolean = false): Expression = {
     if (!e.containsPattern(WITH_EXPRESSION)) return e
     e match {
@@ -229,10 +299,11 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
       case w: With if !isNestedWith =>
         // Rewrite nested With expressions first
         val child = rewriteWithExprAndInputPlans(
-          w.child, inputPlans, commonExprsPerChild, commonExprIdSet, isNestedWith = true)
+          w.child, inputPlans, commonExprsPerChild, isNestedWith = true)
         val defs = w.defs.map(rewriteWithExprAndInputPlans(
-          _, inputPlans, commonExprsPerChild, commonExprIdSet, isNestedWith = true))
+          _, inputPlans, commonExprsPerChild, isNestedWith = true))
         val refToExpr = mutable.HashMap.empty[CommonExpressionId, Expression]
+        val multiplyReferenced = multiplyReferencedIds(child, defs)
 
         defs.zipWithIndex.foreach { case (CommonExpressionDef(child, id), index) =>
           if (id.canonicalized) {
@@ -240,7 +311,7 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
               "Cannot rewrite canonicalized Common expression definitions")
           }
 
-          if (CollapseProject.isCheap(child) || !commonExprIdSet.contains(id)) {
+          if (canSubstitute(child, id, multiplyReferenced)) {
             refToExpr(id) = child
           } else {
             val childPlanIndex = inputPlans.indexWhere(
@@ -298,16 +369,19 @@ object RewriteWithExpression extends Rule[LogicalPlan] {
       case c: ConditionalExpression =>
         val newAlwaysEvaluatedInputs = c.alwaysEvaluatedInputs.map(
           rewriteWithExprAndInputPlans(
-            _, inputPlans, commonExprsPerChild, commonExprIdSet, isNestedWith))
+            _, inputPlans, commonExprsPerChild, isNestedWith))
         val newExpr = c.withNewAlwaysEvaluatedInputs(newAlwaysEvaluatedInputs)
-        // For With in the conditional branches, they may not be evaluated at all and we can't
-        // pull the common expressions into a project which will always be evaluated. Inline it
-        // unconditionally. Use transformUp to handle nested With.
-        inlineWith(newExpr, checkDuplication = false)
+        // A `With` in a conditional branch cannot go into a project, which is always evaluated
+        // while the branch may not be. It stays where it is and memoizes its definition per entry
+        // instead, but only the definitions that gain something from it. Use transformUp to handle
+        // nested With.
+        newExpr.transformUpWithPruning(_.containsPattern(WITH_EXPRESSION)) {
+          case w: With => inlineDefsThatGainNothing(w)
+        }
 
       case other => other.mapChildren(
         rewriteWithExprAndInputPlans(
-          _, inputPlans, commonExprsPerChild, commonExprIdSet, isNestedWith)
+          _, inputPlans, commonExprsPerChild, isNestedWith)
       )
     }
   }
diff --git a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
index e12086615d5d..f2da221acd30 100644
--- a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
+++ b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/SubexpressionEliminationSuite.scala
@@ -545,6 +545,57 @@ class SubexpressionEliminationSuite extends SparkFunSuite with ExpressionEvalHel
     equivalence1.addExprTree(caseWhenExpr1)
     assert(equivalence1.getCommonSubexpressions.size == 1)
   }
+
+  test("SPARK-58902: no candidate below a With, with or without the short-circuit peel") {
+    // A `CommonExpressionRef` can only be evaluated inside the `With` that binds it: the codegen
+    // slots exist only while that `With` is being generated, and `getCommonExpr` throws otherwise.
+    // Subexpression elimination generates its candidates outside every `With` scope, so a candidate
+    // holding a reference would fail the query. `childrenToRecurse` therefore stops at a `With`,
+    // including after `skipForShortcut` has peeled an `And`/`Or` down to one.
+    val a = AttributeReference("a", IntegerType)()
+    val memoized = With(Add(a, a)) { case Seq(ref) =>
+      And(GreaterThan(ref, Literal(0)), LessThan(ref, Literal(10)))
+    }
+    // The bare `With`; one behind an `And`, which is where the peel lands on it; and one in every
+    // branch of a `CaseWhen`, which reaches the map through `commonChildrenToRecurse` instead.
+    val shapes = Seq[Expression](
+      memoized,
+      And(memoized, GreaterThan(a, Literal(0))),
+      CaseWhen(Seq((GreaterThan(a, Literal(0)), memoized)), memoized))
+    Seq(false, true).foreach { peel =>
+      shapes.foreach { expr =>
+        val equivalence = new EquivalentExpressions(skipForShortcutEnable = peel)
+        equivalence.addExprTree(expr)
+        val states = equivalence.getAllExprStates()
+        // Without this, an implementation that recorded nothing at all would satisfy every
+        // assertion below by iterating over an empty list.
+        assert(states.nonEmpty, s"nothing was recorded for $expr (peel = $peel)")
+        // The `With` itself stays a candidate wherever it is reached: deduplicating it as a whole
+        // is safe, since it carries its own definitions and brings their slots into scope wherever
+        // it is generated. The exception is an `And` root with the peel on, where the peel lands on
+        // the `With` and the guard drops it along with its subtree -- no opportunity is lost there,
+        // because the peel never hands back the node it lands on, only that node's children.
+        if (!(peel && expr.isInstanceOf[And])) {
+          assert(states.exists(_.expr.isInstanceOf[With]),
+            s"the With itself stopped being a candidate for $expr (peel = $peel)")
+        }
+        states.foreach { state =>
+          // A candidate may hold a reference only if it also holds the `With` that binds it -- the
+          // whole `With`, or something above it, is a legal candidate; anything below it is not.
+          // The ids are collected over the whole candidate rather than per reference, so a
+          // reference sitting beside its binder rather than under it would pass; `With.apply`
+          // cannot build that shape.
+          val refIds = state.expr.collect { case r: CommonExpressionRef => r.id }.toSet
+          val boundIds =
+            state.expr.collect { case inScope: With => inScope.defs.map(_.id) }.flatten.toSet
+          assert(refIds.subsetOf(boundIds),
+            s"a candidate below the With was added for $expr (peel = $peel): ${state.expr}")
+          assert(!state.expr.isInstanceOf[CommonExpressionDef],
+            s"an unevaluable definition was added for $expr (peel = $peel): ${state.expr}")
+        }
+      }
+    }
+  }
 }
 
 case class CodegenFallbackExpression(child: Expression)
diff --git a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/WithExpressionEvalSuite.scala b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/WithExpressionEvalSuite.scala
new file mode 100644
index 000000000000..a19f6e987adb
--- /dev/null
+++ b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/expressions/WithExpressionEvalSuite.scala
@@ -0,0 +1,373 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements.  See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License.  You may obtain a copy of the License at
+ *
+ *    http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.catalyst.expressions
+
+import org.apache.spark.{SparkException, SparkFunSuite}
+import org.apache.spark.sql.catalyst.InternalRow
+import org.apache.spark.sql.catalyst.expressions.codegen.{CodegenContext, CodegenFallback, ExprCode, GenerateMutableProjection}
+import org.apache.spark.sql.catalyst.plans.SQLHelper
+import org.apache.spark.sql.internal.SQLConf
+import org.apache.spark.sql.types.{BooleanType, DataType, IntegerType}
+
+/**
+ * Evaluation of [[With]] and the memoization it gives a [[CommonExpressionRef]]. The rewrite that
+ * decides which `With`s reach evaluation at all is covered by `RewriteWithExpressionSuite`.
+ */
+class WithExpressionEvalSuite extends SparkFunSuite with SQLHelper {
+
+  /**
+   * A stand-in for a stateful generator: every evaluation returns the next integer, so a second
+   * evaluation within one row is directly observable. Only used on the interpreted path.
+   */
+  private case class Counter() extends LeafExpression with Nondeterministic {
+    @transient private var n = 0
+    override def stateful: Boolean = true
+    override def dataType: DataType = IntegerType
+    override def nullable: Boolean = false
+    override protected def initializeInternal(partitionIndex: Int): Unit = {}
+    override protected def evalInternal(input: InternalRow): Any = { n += 1; n }
+    override protected def doGenCode(ctx: CodegenContext, ev: ExprCode): ExprCode =
+      throw new UnsupportedOperationException
+  }
+
+  private def counter(): Counter = {
+    val c = Counter()
+    c.initialize(0)
+    c
+  }
+
+  /**
+   * A node that has to be evaluated interpretively even when its parent is generated, so that a
+   * reference below it takes the interpreted path out of generated code.
+   */
+  private case class Fallback(child: Expression) extends UnaryExpression with CodegenFallback {
+    override def dataType: DataType = child.dataType
+    override def eval(input: InternalRow): Any = child.eval(input)
+    override protected def withNewChildInternal(newChild: Expression): Fallback =
+      copy(child = newChild)
+  }
+
+  test("a definition is evaluated once per row however many references read it") {
+    // `ref + ref` is the shape `BETWEEN` produces. Memoized, both references read one value, so the
+    // sum is 2n on the nth row; inlined it would be n + (n + 1).
+    val w = With(counter()) { case Seq(ref) => Add(ref, ref) }
+    assert((1 to 4).map(_ => w.eval(InternalRow.empty)) == Seq(2, 4, 6, 8))
+  }
+
+  test("a definition is not evaluated on a row that reaches no reference") {
+    val c = counter()
+    // The branch is inside the `With`, so the `With` is entered on every row and does clear its
+    // cells. What it must not do is evaluate the definition before a reference is reached; putting
+    // the branch outside would only test that `If` does not evaluate the arm it did not take.
+    val w = With(c) { case Seq(ref) => If(Literal.TrueLiteral, Literal(-1), Add(ref, ref)) }
+    // -1 whatever the definition does, since the taken arm is a literal: the assertion below is the
+    // load-bearing one, and this only says the evaluation ran.
+    assert((1 to 3).map(_ => w.eval(InternalRow.empty)) == Seq(-1, -1, -1))
+    // The counter is still at 0, so the first row that does reach a reference sees 1. Eager filling
+    // would have consumed three values and this would read 8.
+    assert(With(c) { case Seq(ref) => Add(ref, ref) }.eval(InternalRow.empty) == 2)
+  }
+
+  test("a reference behind a short-circuiting operator is not read when the left side is false") {
+    // Neither pre-evaluating the definition into a project nor guarding that column by the branch
+    // can express this: both evaluate on every row the branch is reached on, while `And`
+    // short-circuits before the reference. The `And` is inside the `With` so that the `With` is
+    // entered and only the reference is skipped.
+    val c = counter()
+    val w = With(c) { case Seq(ref) =>
+      And(Literal.FalseLiteral, GreaterThanOrEqual(ref, Literal(1)))
+    }
+    // False whatever the definition does, as in the case above: the counter read is what bites.
+    // This is not that case repeated -- there the arm is skipped by `If`, here by `And`'s short
+    // circuit, and the two are separate paths in both evaluation and codegen.
+    assert((1 to 3).map(_ => w.eval(InternalRow.empty)) == Seq(false, false, false))
+    assert(With(c) { case Seq(ref) => Add(ref, ref) }.eval(InternalRow.empty) == 2)
+  }
+
+  test("a nested With memoizes each scope separately") {
+    val outer = counter()
+    val inner = counter()
+    // The outer reference is read twice, and one of its uses wraps an inner `With` whose own
+    // reference is also read twice, so each row is `o + (2i + o)` with `o` and `i` both n.
+    val w = With(outer) { case Seq(o) =>
+      Add(o, With(inner) { case Seq(i) => Add(Add(i, i), o) })
+    }
+    assert((1 to 3).map(_ => w.eval(InternalRow.empty)) == Seq(4, 8, 12))
+  }
+
+  test("a With rebuilt by a rule still memoizes") {
+    val w = With(counter()) { case Seq(ref) => Add(ref, ref) }
+    // Evaluate the original first. A rule rebuilds the definition, and therefore its cell, while
+    // handing the new `With` the original's reference objects, so an implementation that bound the
+    // references once would leave the rebuilt `With` reading this evaluation's cell.
+    assert(w.eval(InternalRow.empty) == 2)
+    // The rule has to hand back a node that is not `==` the one it replaces, or `transformUp` keeps
+    // the original -- `Counter()` is a case class with no parameters, so a fresh one compares equal
+    // to the old one. Wrapping it changes the tree while leaving the definition's value sequence,
+    // its data type and its nullability alone, so the references are carried over rather than
+    // rebuilt, which is the shape that needs the per-evaluation rebinding.
+    val rewritten = w.transformUp { case _: Counter => Add(counter(), Literal(0)) }
+      .asInstanceOf[With]
+    assert(rewritten ne w, "the rule has to have rebuilt something")
+    assert((1 to 3).map(_ => rewritten.eval(InternalRow.empty)) == Seq(2, 4, 6))
+  }
+
+  test("SPARK-58902: a copy of a With owns its references and its cells") {
+    // A deliberately non-stateful definition, which is what makes `CommonExpressionDef.stateful`
+    // load-bearing: `mapChildren` finds nothing changed below it, so without the override the copy
+    // gets the original definition object, cell included. (A `Rand` definition would hide that.)
+    // Likewise `CommonExpressionRef.stateful`, since `LeafLike.withNewChildrenInternal` returns
+    // `this` and the two `With`s would otherwise share references while owning two cells.
+    val w1 = With(Literal(1)) { case Seq(ref) => Add(ref, ref) }
+    val w2 = w1.freshCopyIfContainsStatefulExpression().asInstanceOf[With]
+    def refOf(e: Expression): CommonExpressionRef =
+      e.collect { case r: CommonExpressionRef => r }.head
+    assert(w1 ne w2, "a stateful With has to be copied")
+    assert(refOf(w1.child) ne refOf(w2.child), "the copy has to own its references")
+    assert(w1.defs.head.cell ne w2.defs.head.cell, "the copy has to own its cell")
+  }
+
+  test("SPARK-58902: two Withs over one set of references each read their own definition") {
+    // The shape a rule produces when it rewrites only the definition: the new `With` is built over
+    // the original's references, since a rebuilt reference compares equal to the one it replaces.
+    // Visibly different definitions show which cell the references actually read.
+    val w1 = With(counter()) { case Seq(ref) => Add(ref, ref) }
+    val w2 = w1.withNewChildren(
+      IndexedSeq(w1.child, CommonExpressionDef(Literal(100), w1.defs.head.id))).asInstanceOf[With]
+
+    assert(w1.eval(InternalRow.empty) == 2, "w1 reads its own counter")
+    assert(w2.eval(InternalRow.empty) == 200, "w2 reads its own literal")
+    assert(w1.eval(InternalRow.empty) == 4, "w1 read the value w2 memoized")
+  }
+
+  test("SPARK-58902: a definition's code is generated once however many references read it") {
+    // Short and holding no `With`, so the body is emitted inline at each reference. It has to be
+    // the same text, generated once: otherwise each copy calls `addMutableState` again and the
+    // definition owns one counter per reference, which for references in mutually exclusive
+    // positions hands out one value on two rows.
+    val ctx = new CodegenContext
+    With(MonotonicallyIncreasingID()) { case Seq(ref) => Add(ref, ref) }.genCode(ctx)
+    val counters = ctx.inlinedMutableStates.count { case (_, name) => name.startsWith("count") }
+    assert(counters == 1, s"the definition was generated $counters times")
+  }
+
+  test("SPARK-58902: nesting does not multiply a definition's body when it can go in a method") {
+    // Each level reads its definition twice, so pasting the body doubles it per level;
+    // `CommonExprSlots.fill` putting it in a method makes it 2 at any depth. Not covered here: the
+    // shape where the input arrives as local variables, as a whole-stage `Project` or `Filter`
+    // passes it, where no method is possible and the count is 2, 4, 8, ... 256 at depths 1 to 8 --
+    // see SPARK-59295. A bare `CodegenContext` has `INPUT_ROW` set and `currentVars` null.
+    val marker = 1234567
+    def nested(depth: Int): Expression = {
+      val leaf: Expression = Add(BoundReference(0, IntegerType, nullable = false), Literal(marker))
+      (1 to depth).foldLeft(leaf) { (inner, _) =>
+        With(inner) { case Seq(ref) => Add(ref, ref) }
+      }
+    }
+    def markerCount(depth: Int): Int = {
+      val ctx = new CodegenContext
+      val source = nested(depth).genCode(ctx).code.toString + ctx.declareAddedFunctions()
+      marker.toString.r.findAllMatchIn(source).size
+    }
+    // Pin the threshold: below the innermost body's length the fill would go into a method of its
+    // own and the count would be 1, for a reason unrelated to nesting.
+    withSQLConf(SQLConf.CODEGEN_METHOD_SPLIT_THRESHOLD.key -> "1024") {
+      (1 to 6).foreach { depth =>
+        val count = markerCount(depth)
+        assert(count == 2, s"the innermost body was emitted $count times at depth $depth")
+      }
+      // The 2 is the innermost body pasted at its two references, at every depth; what stops the
+      // doubling from depth 2 on is that each enclosing definition is itself a `With` and so goes
+      // into a method, whose call sites carry no marker.
+      //
+      // The values double per level, which a deterministic leaf does whether a reference reads a
+      // slot or recomputes -- an arithmetic and compile check, not a second reading of the count.
+      // Four levels keeps the product inside Int, which ANSI `Add` would raise on past depth 10.
+      val proj = GenerateMutableProjection.generate(Seq(nested(4)))
+      assert(proj(InternalRow(1)).getInt(0) == (1 + marker) * 16)
+    }
+  }
+
+  test("SPARK-58902: a nested With sharing a reference object restores the outer binding") {
+    // Two `With`s over one reference object, the inner one nested in the outer one's child and
+    // redefining the id the outer one defines. Only a caller building the case class directly
+    // produces this -- `withNewChildrenInternal` shares references between a `With` and its
+    // replacement, which are siblings, and no rule nests a redefinition of a live id -- so this is
+    // hardening rather than a reachable wrong answer. Binding on entry alone is not enough: the
+    // inner `With` rebinds the shared reference to its own definition, so a read after the inner
+    // one returned would answer with the inner definition unless the outer binding is put back.
+    val id = new CommonExpressionId()
+    val outerDef = CommonExpressionDef(counter(), id)
+    val innerDef = CommonExpressionDef(Literal(10), id)
+    val ref = new CommonExpressionRef(outerDef)
+    val inner = With(Add(ref, ref), Seq(innerDef))
+    val outer = With(Add(Add(ref, inner), ref), Seq(outerDef))
+    // The outer definition counts, the inner one does not, so row n is n + (10 + 10) + n. A counter
+    // is what makes the repetition worth something: leaving the inner binding in place gives
+    // n + 20 + 10, and losing memoization of the outer definition gives n + 20 + (n + 1).
+    assert((1 to 3).map(_ => outer.eval(InternalRow.empty)) == Seq(22, 24, 26))
+
+    // The generated path never has to answer this: one id in two nested scopes is refused while
+    // generating, so it cannot quietly disagree with the values above.
+    val literalOuter = CommonExpressionDef(Literal(1), new CommonExpressionId())
+    val literalRef = new CommonExpressionRef(literalOuter)
+    val nested = With(
+      Add(literalRef, With(Add(literalRef, literalRef),
+        Seq(CommonExpressionDef(Literal(10), literalOuter.id)))),
+      Seq(literalOuter))
+    val generated = intercept[SparkException](GenerateMutableProjection.generate(Seq(nested)))
+    assert(generated.getMessage.contains("is already being generated"))
+  }
+
+  test("SPARK-58902: a definition that references its own id fails without recursing") {
+    // Only a caller building the case class directly can produce this, and the two paths failed
+    // differently before the check. Generating it re-enters the same slot either way. Evaluating it
+    // depends on the reference objects: here they are distinct, so the scan over `child` binds only
+    // the one in `child` and the one inside `selfDef` fails as unbound.
+    val id = new CommonExpressionId()
+    val proto = CommonExpressionDef(Literal(1), id)
+    val selfDef = CommonExpressionDef(Add(new CommonExpressionRef(proto), Literal(1)), id)
+    val w = With(new CommonExpressionRef(proto), Seq(selfDef))
+
+    val generated = intercept[SparkException] {
+      GenerateMutableProjection.generate(Seq(w))
+    }
+    assert(generated.getMessage.contains("references it"))
+    val interpreted = intercept[SparkException](w.eval(InternalRow.empty))
+    assert(interpreted.getMessage.contains("references an id its own With defines"))
+
+    // One reference object in both places is the variant that recursed: the scan binds that object,
+    // so the definition's read of it found a cell still being filled -- StackOverflowError,
+    // measured before the check.
+    val shared = new CommonExpressionRef(proto)
+    val sharedSelfDef = CommonExpressionDef(Add(shared, Literal(1)), id)
+    val sharedFailure =
+      intercept[SparkException](With(shared, Seq(sharedSelfDef)).eval(InternalRow.empty))
+    assert(sharedFailure.getMessage.contains("references an id its own With defines"))
+  }
+
+  test("SPARK-58902: the generated path does not compute a definition on a row that skips it") {
+    // The interpreted no-reference tests use `Counter`, which has no codegen, and the end-to-end
+    // skip case never enters the `With` at all. Here the `With` is entered on every row and the
+    // branch inside it decides whether a reference is reached, so an eager fill would show up as
+    // ids consumed on the rows that take the other arm.
+    val id = MonotonicallyIncreasingID()
+    val w = With(id) { case Seq(ref) =>
+      If(BoundReference(0, BooleanType, nullable = false), ref, Literal(-1L))
+    }
+    val proj = GenerateMutableProjection.generate(Seq(w))
+    proj.initialize(0)
+    val got = Seq(false, true, false, true).map { reached =>
+      proj(InternalRow(reached)).getLong(0)
+    }
+    // Only the rows that reach the reference take an id, so the ids stay 0 and 1.
+    assert(got == Seq(-1L, 0L, -1L, 1L))
+  }
+
+  test("SPARK-58902: two surviving definitions in one With keep their own state") {
+    // Every other runtime case has a single definition, so a slot that aliased two definitions, or
+    // a clear that reset the wrong one, would go unnoticed. The two are scaled differently to make
+    // which slot answered visible in the value.
+    def build(): Expression = With(
+      MonotonicallyIncreasingID(),
+      Multiply(MonotonicallyIncreasingID(), Literal(100L))) { case Seq(a, b) =>
+        Add(Add(a, a), Add(b, b))
+      }
+    // Row n reads a = n and b = 100n once each, so the sum is 2n + 200n. Aliasing the two slots
+    // would give 4n or 400n, and clearing only one of them would drift after the first row.
+    val proj = GenerateMutableProjection.generate(Seq(build()))
+    proj.initialize(0)
+    assert((0 until 3).map(_ => proj(InternalRow.empty).getLong(0)) == Seq(0L, 202L, 404L))
+
+    val interpreted = build()
+    interpreted.foreach {
+      case n: Nondeterministic => n.initialize(0)
+      case _ =>
+    }
+    assert((0 until 3).map(_ => interpreted.eval(InternalRow.empty)) == Seq(0L, 202L, 404L))
+  }
+
+  test("SPARK-58902: eval refuses the two shapes whose bindings it could not keep straight") {
+    // Both need the case class constructor, and both were answered by `eval` before this check --
+    // with a wrong value, while `GenerateMutableProjection` raised. Refusing them keeps the two
+    // paths saying the same thing about the same tree.
+    val id = new CommonExpressionId()
+    val first = CommonExpressionDef(Literal(1), id)
+    val ref = new CommonExpressionRef(first)
+    // Two definitions with one id: `defs.map(d => d.id -> d).toMap` kept the last, so both
+    // references read 2 and the answer was 4 where the first definition says 2.
+    val duplicateIds = With(Add(ref, ref), Seq(first, CommonExpressionDef(Literal(2), id)))
+    val duplicate = intercept[SparkException](duplicateIds.eval(InternalRow.empty))
+    assert(duplicate.getMessage.contains("Duplicate common expression ids"))
+
+    // One definition object in two scopes: the inner `With` clears the cell the outer one had
+    // already filled, so the definition answered twice inside one entry -- 1, then 2 from the
+    // counter, giving 3 where the memoization contract says 1 + 0 + 1.
+    val counterDef = CommonExpressionDef(counter(), new CommonExpressionId())
+    val counterRef = new CommonExpressionRef(counterDef)
+    val shared = With(
+      Add(Add(counterRef, With(Literal(0), Seq(counterDef))), counterRef),
+      Seq(counterDef))
+    val sharedFailure = intercept[SparkException](shared.eval(InternalRow.empty))
+    assert(sharedFailure.getMessage.contains("shares a common expression definition object"))
+  }
+
+  test("SPARK-58902: a refused scope leaves no slot behind in the context") {
+    // The duplicate-id check throws partway through allocating, after earlier definitions of the
+    // same `With` are already in scope. If those were left there, a later reference to one of those
+    // ids in the same context would resolve an orphan and generate code from it instead of saying
+    // the id is not in scope.
+    val ctx = new CodegenContext
+    val id = new CommonExpressionId()
+    val w = With(Literal(0), Seq(CommonExpressionDef(Literal(1), id), CommonExpressionDef(
+      Literal(2), id)))
+    val refused = intercept[SparkException](w.genCode(ctx))
+    assert(refused.getMessage.contains("is already being generated"))
+    val gone = intercept[SparkException](ctx.getCommonExpr(id.id))
+    assert(gone.getMessage.contains("is not in scope"))
+  }
+
+  test("SPARK-58902: a reference under a CodegenFallback still memoizes") {
+    // The generated code clears the codegen flags, not the cells, so a reference reached through a
+    // `CodegenFallback`'s `eval` cannot use them: the whole `With` falls back to `eval`, which
+    // binds and clears the cells itself. Generating part of it would be worse than either -- a
+    // definition reached from both sides would hold one value in the slots and another in the cell.
+    // The definition is left uninitialized on purpose, so `proj.initialize(0)` has to reach it:
+    // falling back registers every `Nondeterministic` in the subtree for partition initialization,
+    // and `Nondeterministic.eval` raises if that did not happen.
+    val w = With(Counter()) { case Seq(ref) => Add(Fallback(ref), Fallback(ref)) }
+    val proj = GenerateMutableProjection.generate(Seq(w))
+    proj.initialize(0)
+    // Both references read one value per row, so the sum is 2n rather than n + (n + 1).
+    assert((1 to 4).map(_ => proj(InternalRow.empty).getInt(0)) == Seq(2, 4, 6, 8))
+  }
+
+  test("SPARK-58902: a reference under a nested With that falls back still memoizes") {
+    // The inner `With` would fall back on its own, because one of its own references sits under a
+    // `Fallback`. The outer one holds no `CodegenFallback` of its own, so it can only notice by
+    // asking the inner `With` whether it fell back -- and it has to, since its reference `o` sits
+    // inside the inner subtree and would be reached interpretively with no cell bound.
+    val w = With(Counter()) { case Seq(o) =>
+      Add(o, With(Counter()) { case Seq(i) => Add(Fallback(i), o) })
+    }
+    val proj = GenerateMutableProjection.generate(Seq(w))
+    proj.initialize(0)
+    // `o` and `i` are both n on the nth row and `o` is read twice, so each row is o + (i + o).
+    assert((1 to 3).map(_ => proj(InternalRow.empty).getInt(0)) == Seq(3, 6, 9))
+  }
+}
diff --git a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpressionSuite.scala b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpressionSuite.scala
index e0930afc801e..11bd8623033c 100644
--- a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpressionSuite.scala
+++ b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/RewriteWithExpressionSuite.scala
@@ -20,18 +20,21 @@ package org.apache.spark.sql.catalyst.optimizer
 import java.time.Instant
 
 import org.apache.spark.SparkException
+import org.apache.spark.api.python.PythonEvalType
+import org.apache.spark.sql.catalyst.InternalRow
 import org.apache.spark.sql.catalyst.analysis.{EmptyFunctionRegistry, EmptyTableFunctionRegistry, FakeV2SessionCatalog, TempResolvedColumn}
 import org.apache.spark.sql.catalyst.catalog.{InMemoryCatalog, SessionCatalog}
 import org.apache.spark.sql.catalyst.dsl.expressions._
 import org.apache.spark.sql.catalyst.dsl.plans._
 import org.apache.spark.sql.catalyst.expressions._
 import org.apache.spark.sql.catalyst.plans.PlanTest
-import org.apache.spark.sql.catalyst.plans.logical.{LocalRelation, LogicalPlan}
+import org.apache.spark.sql.catalyst.plans.logical.{LocalRelation, LogicalPlan, Project}
 import org.apache.spark.sql.catalyst.rules.RuleExecutor
 import org.apache.spark.sql.catalyst.util.DateTimeUtils
 import org.apache.spark.sql.connector.catalog.CatalogV2Implicits._
 import org.apache.spark.sql.connector.catalog.DefaultCatalogManager
-import org.apache.spark.sql.types.{DateType, StringType, TimestampNTZType, TimestampType, TimeType}
+import org.apache.spark.sql.internal.SQLConf
+import org.apache.spark.sql.types.{DateType, IntegerType, StringType, TimestampNTZType, TimestampType, TimeType}
 
 class RewriteWithExpressionSuite extends PlanTest {
 
@@ -483,15 +486,191 @@ class RewriteWithExpressionSuite extends PlanTest {
     )
   }
 
+  test("SPARK-58902: a With left in a conditional branch of an aggregate still converges") {
+    val Seq(a, b) = testRelation.output
+    // Not cheap and referenced twice, so it stays a memoizing `With` rather than being inlined.
+    val inBranch = With(a + b) { case Seq(ref) => ref * ref }
+    val plan = testRelation.groupBy(a)(max(Coalesce(Seq(a, inBranch))).as("col"))
+    // The `PhysicalAggregation` arm restructures the aggregate into a `Project` above it, and its
+    // guard is "the expressions contain a `With`", which a surviving one keeps true on every
+    // iteration of this fixed-point batch. Without the eq check in the rule this raises
+    // `Max iterations (5) reached for batch Rewrite With expression`, one `Project` per iteration.
+    val rewritten = Optimizer.execute(plan)
+    // Idempotent: running the batch again changes nothing.
+    comparePlans(Optimizer.execute(rewritten), rewritten)
+    assert(rewritten.collect { case p: Project => p }.size <= 1,
+      s"the rule stacked a Project per iteration:\n$rewritten")
+  }
+
+  test("SPARK-58902: a cheap or single-reference definition in a branch is still inlined") {
+    val Seq(a, b) = testRelation.output
+    // A bare attribute is cheap, so inlining it costs nothing.
+    val cheap = With(a) { case Seq(ref) => ref * ref }
+    comparePlans(
+      Optimizer.execute(testRelation.select(Coalesce(Seq(b, cheap)).as("col"))),
+      testRelation.select(Coalesce(Seq(b, a * a)).as("col")))
+
+    // Referenced once, so memoizing it would save nothing.
+    val singleRef = With(a + b) { case Seq(ref) => ref * Literal(2) }
+    comparePlans(
+      Optimizer.execute(testRelation.select(Coalesce(Seq(b, singleRef)).as("col"))),
+      testRelation.select(Coalesce(Seq(b, (a + b) * Literal(2))).as("col")))
+
+    // Expensive and referenced twice: this is the one worth a `With`.
+    val kept = With(a + b) { case Seq(ref) => ref * ref }
+    val keptPlan = testRelation.select(Coalesce(Seq(b, kept)).as("col"))
+    comparePlans(Optimizer.execute(keptPlan), keptPlan)
+  }
+
+  test("SPARK-58902: an inner substitution that duplicates an outer reference is counted") {
+    val Seq(a, b) = testRelation.output
+    def udf(e: Expression, deterministic: Boolean): PythonUDF =
+      PythonUDF("udf", null, IntegerType, Seq(e), PythonEvalType.SQL_BATCHED_UDF, deterministic)
+
+    // With this conf off, `CollapseProject.isCheap` calls any `PythonUDF` cheap whatever its
+    // children are, which is what lets an inner definition carrying an outer reference be
+    // substituted at both of its references. Counting the outer reference before that happens says
+    // once, and the branch path runs bottom-up, so a plan-wide count taken up front would inline
+    // the nondeterministic outer definition into both copies -- two draws where there must be one.
+    withSQLConf(SQLConf.AVOID_COLLAPSE_UDF_WITH_EXPENSIVE_EXPR.key -> "false") {
+      val outerDef = CommonExpressionDef(udf(a, deterministic = false))
+      val outerRef = new CommonExpressionRef(outerDef)
+      val innerDef = CommonExpressionDef(udf(outerRef, deterministic = true))
+      val innerRef = new CommonExpressionRef(innerDef)
+      val inner = With(Add(innerRef, innerRef), Seq(innerDef))
+      val outer = With(inner, Seq(outerDef))
+      val rewritten = Optimizer.execute(testRelation.select(Coalesce(Seq(b, outer)).as("col")))
+
+      val nondet = rewritten.expressions.flatMap(_.collect {
+        case u: PythonUDF if !u.udfDeterministic => u
+      })
+      assert(nondet.length == 1, s"the nondeterministic definition was inlined twice:\n$rewritten")
+      // It stayed memoized: the surviving `With` still defines it, and both reads go through a
+      // reference to it.
+      val withs = rewritten.expressions.flatMap(_.collect { case w: With => w })
+      assert(withs.length == 1, s"expected one surviving With:\n$rewritten")
+      assert(withs.head.defs.map(_.child) == nondet, s"the wrong definition survived:\n$rewritten")
+      assert(withs.head.child.collect { case r: CommonExpressionRef => r }.length == 2,
+        s"expected two references to the surviving definition:\n$rewritten")
+    }
+  }
+
+  test("SPARK-58902: a reference inside a sibling definition keeps that definition memoized") {
+    val Seq(a, b) = testRelation.output
+    def udf(e: Expression, deterministic: Boolean): PythonUDF =
+      PythonUDF("udf", null, IntegerType, Seq(e), PythonEvalType.SQL_BATCHED_UDF, deterministic)
+
+    // The reference to the first definition sits inside the second one, once. Substituting the
+    // second definition at both of its references would duplicate it, so counting it as read once
+    // would inline the nondeterministic first definition into both copies. Nothing builds this
+    // shape -- the helper puts references only in `child` -- but the rewrite is what would have to
+    // survive it, and it cannot fall back on evaluation failing.
+    withSQLConf(SQLConf.AVOID_COLLAPSE_UDF_WITH_EXPENSIVE_EXPR.key -> "false") {
+      val firstDef = CommonExpressionDef(udf(a, deterministic = false))
+      val firstRef = new CommonExpressionRef(firstDef)
+      val secondDef = CommonExpressionDef(udf(firstRef, deterministic = true))
+      val secondRef = new CommonExpressionRef(secondDef)
+      val w = With(Add(secondRef, secondRef), Seq(firstDef, secondDef))
+      val rewritten = Optimizer.execute(testRelation.select(Coalesce(Seq(b, w)).as("col")))
+
+      val nondet = rewritten.expressions.flatMap(_.collect {
+        case u: PythonUDF if !u.udfDeterministic => u
+      })
+      assert(nondet.length == 1,
+        s"the nondeterministic definition was inlined more than once:\n$rewritten")
+      // The count alone would also hold on a plan that kept nothing, or that kept the definition
+      // with references the rebuilt `With` does not bind, so pin the structure the memoization
+      // needs: one surviving `With`, the nondeterministic definition inside it, and every reference
+      // left in the tree naming an id that `With` defines.
+      val withs = rewritten.expressions.flatMap(_.collect { case w: With => w })
+      assert(withs.length == 1, s"expected one surviving With, got ${withs.length}:\n$rewritten")
+      assert(withs.head.defs.exists(d => d.child.exists {
+        case u: PythonUDF => !u.udfDeterministic
+        case _ => false
+      }), s"the surviving With does not hold the nondeterministic definition:\n$rewritten")
+      val definedIds = withs.head.defs.map(_.id).toSet
+      val refIds = rewritten.expressions.flatMap(_.collect { case r: CommonExpressionRef => r.id })
+      assert(refIds.nonEmpty && refIds.forall(definedIds.contains),
+        s"a reference is left without a With that defines it:\n$rewritten")
+    }
+  }
+
+  test("SPARK-58902: a branch-local With keeps only the definitions worth memoizing") {
+    val Seq(a, b) = testRelation.output
+    // Two definitions in one `With`, one of each kind, so the rule has to rebuild the `With` around
+    // what is left rather than inline all of them or keep all of them. The other branch-local tests
+    // each use a single definition, which only exercises those two ends.
+    val expr = With(a, a + b) { case Seq(cheap, expensive) =>
+      Add(cheap * cheap, expensive * expensive)
+    }
+    val plan = testRelation.select(Coalesce(Seq(b, expr)).as("col"))
+    val rewritten = Optimizer.execute(plan)
+
+    val withs = rewritten.expressions.flatMap(_.collect { case w: With => w })
+    assert(withs.length == 1, s"expected one surviving With:\n$rewritten")
+    val kept = withs.head
+    assert(kept.defs.map(_.child) == Seq(a + b), s"the wrong definition was kept:\n$rewritten")
+    // The inlined definition's id is gone from the tree, not left as a reference nobody binds.
+    val keptIds = kept.defs.map(_.id).toSet
+    val refIds = rewritten.expressions.flatMap(_.collect { case r: CommonExpressionRef => r.id })
+    assert(refIds.nonEmpty && refIds.forall(keptIds.contains),
+      s"a reference to an inlined definition survived:\n$rewritten")
+    // The cheap definition was substituted at both of its references, not just the first.
+    assert(kept.child.collectFirst { case Add(l, _, _) => l }.contains(a * a),
+      s"the cheap definition was not inlined at every reference:\n$rewritten")
+    // The rebuilt `With` binds the references it carried over from the one it replaced, which is
+    // what the value proves: a = 2 inlined twice, a + b = 5 memoized and squared.
+    val bound = BindReferences.bindReference(
+      rewritten.expressions.head.children.head.asInstanceOf[Coalesce].children.last,
+      testRelation.output)
+    assert(bound.eval(InternalRow(2, 3)) == 2 * 2 + 5 * 5)
+    // Running the batch again changes nothing: the rebuilt `With` is a fixed point.
+    comparePlans(Optimizer.execute(rewritten), rewritten)
+  }
+
+  test("SPARK-58902: a cheap definition is only inlined if it is also deterministic") {
+    val Seq(a, b) = testRelation.output
+    def udf(e: Expression, deterministic: Boolean): PythonUDF =
+      PythonUDF("udf", null, IntegerType, Seq(e), PythonEvalType.SQL_BATCHED_UDF, deterministic)
+
+    // `CollapseProject.isCheap` admits a `PythonUDF` whose arguments are cheap, but it answers what
+    // one evaluation costs, not whether a second one would agree with the first. A nondeterministic
+    // one referenced twice has to stay memoized.
+    val nondet = With(udf(a, deterministic = false)) { case Seq(ref) => ref * ref }
+    val nondetPlan = testRelation.select(Coalesce(Seq(b, nondet)).as("col"))
+    comparePlans(Optimizer.execute(nondetPlan), nondetPlan)
+
+    // The deterministic one is inlined, as cheapness alone would have it.
+    val det = With(udf(a, deterministic = true)) { case Seq(ref) => ref * ref }
+    comparePlans(
+      Optimizer.execute(testRelation.select(Coalesce(Seq(b, det)).as("col"))),
+      testRelation.select(
+        Coalesce(Seq(b, udf(a, deterministic = true) * udf(a, deterministic = true))).as("col")))
+
+    // The same conjunct governs the main rewrite path, which has no `Coalesce` above it: there the
+    // definition is hoisted into a child `Project` instead of being substituted. Nothing in this
+    // batch sends it back -- `PlanHelper.specialExpressionsInUnsupportedOperator` collects only
+    // window, aggregate and generator expressions, so the `fakeProj` check does not force the
+    // substitution. What keeps `CollapseProject` from copying the alias back into its two consumers
+    // is that it requires a deterministic producer, which this suite's batch does not exercise.
+    val nondetMainPath = With(udf(a, deterministic = false)) { case Seq(ref) => ref * ref }
+    comparePlans(
+      Optimizer.execute(testRelation.select(nondetMainPath.as("col"))),
+      testRelation
+        .select((testRelation.output :+ udf(a, deterministic = false).as("_common_expr_0")): _*)
+        .select(($"_common_expr_0" * $"_common_expr_0").as("col"))
+        .analyze)
+  }
+
   test("WITH expression inside conditional expression") {
     val a = testRelation.output.head
-    val expr = Coalesce(Seq(a, With(a + a) { case Seq(ref) =>
-      ref * ref
-    }))
-    val inlinedExpr = Coalesce(Seq(a, (a + a) * (a + a)))
+    val inBranch = With(a + a) { case Seq(ref) => ref * ref }
+    val expr = Coalesce(Seq(a, inBranch))
     val plan = testRelation.select(expr.as("col"))
-    // With in the conditional branches is always inlined.
-    comparePlans(Optimizer.execute(plan), testRelation.select(inlinedExpr.as("col")))
+    // A `With` in a conditional branch is left where it is: it cannot go into a project, which is
+    // always evaluated, and it memoizes its definition per row itself, so the definition is still
+    // evaluated once rather than once per reference.
+    comparePlans(Optimizer.execute(plan), testRelation.select(expr.as("col")))
 
     val expr2 = Coalesce(Seq(With(a + a) { case Seq(ref) =>
       ref * ref
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/ColumnExpressionSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/ColumnExpressionSuite.scala
index 379b7320a299..c79fd0878ce2 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/ColumnExpressionSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/ColumnExpressionSuite.scala
@@ -28,7 +28,7 @@ import org.scalatest.matchers.should.Matchers._
 
 import org.apache.spark.{SparkException, SparkRuntimeException}
 import org.apache.spark.sql.UpdateFieldsBenchmark._
-import org.apache.spark.sql.catalyst.expressions.{InSet, Literal, NamedExpression}
+import org.apache.spark.sql.catalyst.expressions.{InSet, Literal, NamedExpression, With}
 import org.apache.spark.sql.catalyst.util.DateTimeTestUtils.{outstandingTimezonesIds, outstandingZoneIds}
 import org.apache.spark.sql.catalyst.util.DateTimeUtils
 import org.apache.spark.sql.catalyst.util.TimestampNanosTestUtils.foreachNanosPrecision
@@ -430,6 +430,221 @@ class ColumnExpressionSuite extends SharedSparkSession {
     checkAnswer(testData.filter($"a".between($"b", $"c")), expectAnswer)
   }
 
+  // Runs `f` on each of the three evaluation paths, since a `With` left in a conditional branch is
+  // evaluated by all three and the memoization is implemented separately for interpretation and for
+  // codegen.
+  private def onEachEvalPath(f: => Unit): Unit = {
+    withSQLConf(
+      SQLConf.WHOLESTAGE_CODEGEN_ENABLED.key -> "false",
+      SQLConf.CODEGEN_FACTORY_MODE.key -> "NO_CODEGEN")(f)
+    withSQLConf(
+      SQLConf.WHOLESTAGE_CODEGEN_ENABLED.key -> "false",
+      SQLConf.CODEGEN_FACTORY_MODE.key -> "CODEGEN_ONLY")(f)
+    withSQLConf(
+      SQLConf.WHOLESTAGE_CODEGEN_ENABLED.key -> "true",
+      SQLConf.CODEGEN_FACTORY_MODE.key -> "CODEGEN_ONLY")(f)
+  }
+
+  test("SPARK-58902: BETWEEN on a nondeterministic input inside a conditional branch") {
+    onEachEvalPath {
+      // `BETWEEN` reads its input twice. Inlining the common expression into a branch gave each
+      // read its own value, so the two comparisons saw two different ids and 6 of the 10 rows came
+      // back true where 3 is correct. A single partition makes the id sequence 0, 1, 2, ... `id` is
+      // selected alongside because `checkAnswer` compares rows as a bag: without it the assertion
+      // would only count trues, and an off-by-one in the sequence would still pass.
+      val df = spark.range(0, 10, 1, 1)
+      checkAnswer(
+        df.selectExpr(
+          "id",
+          "CASE WHEN id < 0 THEN false " +
+            "ELSE monotonically_increasing_id() BETWEEN 3 AND 5 END"),
+        (0 until 10).map(i => Row(i.toLong, i >= 3 && i <= 5)))
+    }
+  }
+
+  test("SPARK-58902: a definition in a branch is evaluated only on the rows that reach it") {
+    onEachEvalPath {
+      // Rows 0 to 4 take the first branch, so the five rows that reach the ELSE see ids 0 to 4 --
+      // the same values they would see if the branch were the whole expression. `id` is selected
+      // alongside for the reason given in the case above.
+      val df = spark.range(0, 10, 1, 1)
+      checkAnswer(
+        df.selectExpr(
+          "id",
+          "CASE WHEN id < 5 THEN NULL " +
+            "ELSE monotonically_increasing_id() BETWEEN 1 AND 2 END"),
+        (0 until 10).map { i =>
+          if (i < 5) Row(i.toLong, null) else Row(i.toLong, i - 5 >= 1 && i - 5 <= 2)
+        })
+    }
+  }
+
+  test("SPARK-58902: a branch condition that can raise is not evaluated on other rows") {
+    onEachEvalPath {
+      withSQLConf(SQLConf.ANSI_ENABLED.key -> "true") {
+        // Nothing is relocated, so a condition is evaluated only where it always was. `a` runs
+        // -2, -1, 0, 1, 2, 3: the first two take the third branch, 0 the first, 1 and 2 the second,
+        // and 3 falls through. `rand` is in [0, 1), so a row reaching a BETWEEN is true whatever it
+        // draws -- the answers here do not depend on memoization. What this rules out is the
+        // alternative that was measured and rejected: hoisting the definition into a `Project` and
+        // guarding that column with the branch condition, which puts `6 / a` outside conditional
+        // evaluation and raises on the `a = 0` row under ANSI.
+        val df = spark.range(0, 6, 1, 1).selectExpr("cast(id as int) - 2 as a")
+        checkAnswer(
+          df.selectExpr(
+            "a",
+            "CASE WHEN a = 0 THEN false " +
+              "WHEN 6 / a > 2 THEN rand(1) BETWEEN 0 AND 1 " +
+              "WHEN 6 / a < -2 THEN rand(2) BETWEEN 0 AND 1 " +
+              "ELSE false END"),
+          Seq(Row(-2, true), Row(-1, true), Row(0, false),
+            Row(1, true), Row(2, true), Row(3, false)))
+      }
+    }
+  }
+
+  test("SPARK-58902: a nondeterministic input a branch cannot pre-evaluate is still read once") {
+    onEachEvalPath {
+      // 20 rows so the two copies an inlining implementation makes fall out of step: each owns an
+      // identically seeded generator, and they diverge once a failed first comparison skips the
+      // second. Both bounds therefore have to be failable, which the assertion below pins: with an
+      // upper bound no 3-character draw can miss, the answer is the first comparison's alone and
+      // inlining is invisible. The value is a string, so this also covers a non-primitive slot, and
+      // `id` is selected alongside because `checkAnswer` compares as a bag.
+      val df = spark.range(0, 20, 1, 1)
+      val inBranch = df.selectExpr(
+        "id", "CASE WHEN id < 0 THEN false ELSE randstr(3, 0) BETWEEN 'a' AND 'm' END")
+      val draws = df.selectExpr("randstr(3, 0) as s").collect().map(_.getString(0))
+      assert(draws.exists(_ < "a") && draws.exists(_ > "m"),
+        s"a bound is not failable over these rows: ${draws.mkString(", ")}")
+      val branchFreeStr = df.selectExpr("id", "randstr(3, 0) BETWEEN 'a' AND 'm'").collect()
+      checkAnswer(inBranch, branchFreeStr.toSeq)
+
+      // The same for a nondeterministic input wrapped in arithmetic, with the same requirement on
+      // the window: `BETWEEN 0 AND 1` over `rand` is satisfied by every draw, which would keep the
+      // two copies in lockstep.
+      val branchFree = df.selectExpr("id", "(rand(7) / 1.0) BETWEEN 0.3 AND 0.6").collect()
+      assert(branchFree.exists(!_.getBoolean(1)) && branchFree.exists(_.getBoolean(1)),
+        s"the window is not selective over these rows: ${branchFree.mkString(", ")}")
+      val inBranchRand = df.selectExpr(
+        "id", "CASE WHEN id < 0 THEN false ELSE (rand(7) / 1.0) BETWEEN 0.3 AND 0.6 END")
+      checkAnswer(inBranchRand, branchFree.toSeq)
+    }
+  }
+
+  test("SPARK-58902: a nested With agrees across the evaluation paths") {
+    // The outer `nullif`'s definition is the inner `nullif`, itself a `With`, and neither is cheap
+    // or read once, so both survive inside the branch. This is about the two evaluation paths
+    // agreeing on nested scopes, not about code size -- see `CommonExprSlots.fill` for that. `a` is
+    // selected alongside so `checkAnswer`, which compares as a bag, compares per row.
+    val query = "SELECT a, CASE WHEN a < 0 THEN NULL ELSE nullif(nullif(a + b, b), c) END AS r " +
+      "FROM VALUES (0, 5, 3), (2, 5, 7), (4, 5, 6), (-1, 1, 1) AS t(a, b, c)"
+    // The shape assertion keeps a rewrite change from leaving this with no `With` at all and still
+    // passing on the answers. It survives `ConvertToLocalRelation` only because
+    // `CommonExpressionDef` is `Unevaluable`; otherwise the whole `VALUES` projection would fold.
+    // The conf block pins the default `NullIf` builds under, so a suite-level override cannot turn
+    // this into a test of the inlining path.
+    withSQLConf(SQLConf.ALWAYS_INLINE_COMMON_EXPR.key -> "false") {
+      val withs = spark.sql(query).queryExecution.optimizedPlan.collect {
+        case p => p.expressions.flatMap(_.collect { case w: With => w })
+      }.flatten
+      assert(withs.size == 2, s"expected two surviving With nodes, got ${withs.size}")
+      onEachEvalPath {
+        // a = 0 makes `a + b` equal b, a = 2 makes it equal c, so both are null; a = 4 differs from
+        // both and gives 9; a = -1 takes the first branch.
+        checkAnswer(
+          spark.sql(query),
+          Seq(Row(0, null), Row(2, null), Row(4, 9), Row(-1, null)))
+      }
+    }
+  }
+
+  test("SPARK-58902: a surviving With in a Filter predicate reads its definition once per row") {
+    // Every other end-to-end case goes through a Project. A `With` survives in a Filter predicate
+    // the same way, and `FilterExec`'s whole-stage `doConsume` generates common state lazily, at
+    // the first predicate that reads it, so the lazy fill and the in-place clearing land next to
+    // machinery with its own ordering contract.
+    withSQLConf(SQLConf.ALWAYS_INLINE_COMMON_EXPR.key -> "false") {
+      onEachEvalPath {
+        val df = spark.range(0, 10, 1, 1).toDF()
+        // One id per row, so the ids are the row numbers and rows 3 to 5 pass. Inlining would let
+        // the second comparison draw again and a different set of rows would come through.
+        checkAnswer(
+          df.filter("CASE WHEN id < 0 THEN false " +
+            "ELSE monotonically_increasing_id() BETWEEN 3 AND 5 END"),
+          Seq(Row(3L), Row(4L), Row(5L)))
+      }
+    }
+  }
+
+  test("SPARK-58902: a surviving With in a Sort key is generated once per comparison side") {
+    // `GenerateOrdering` generates the key once per comparison side, each in its own scope with its
+    // own slots. A slot shared between the sides would read the wrong row, and here, where
+    // `Expression.reduceCodeSize` has hoisted each side's key into a method taking one row, would
+    // not compile. What this does not cover is a comparison the ordering performs: the keys are
+    // distinct, so `UnsafeInMemorySorter` settles them on their prefixes.
+    withSQLConf(SQLConf.ALWAYS_INLINE_COMMON_EXPR.key -> "false") {
+      onEachEvalPath {
+        // The DataFrame is built inside, not outside: `QueryExecution.executedPlan` is a lazy val,
+        // so one built ahead of these blocks would be planned under the first block's confs and the
+        // whole-stage block would re-run that same physical plan.
+        val df = spark.range(0, 5, 1, 1).toDF()
+        val sorted = df.orderBy(expr("CASE WHEN id < 0 THEN 0 ELSE nullif(id * 2, -1) END").desc)
+        val withs = sorted.queryExecution.optimizedPlan.collect {
+          case p => p.expressions.flatMap(_.collect { case w: With => w })
+        }.flatten
+        assert(withs.size == 1, s"expected one surviving With node, got ${withs.size}")
+        // `checkAnswer` compares in order when the plan holds a `Sort`.
+        checkAnswer(sorted, Seq(Row(4L), Row(3L), Row(2L), Row(1L), Row(0L)))
+      }
+    }
+  }
+
+  test("SPARK-58902: a definition that has to fall back to eval works on every path") {
+    // The only case whose definition is a real `CodegenFallback`, which covers it being generated
+    // inside `fill`, its `Nondeterministic` state being initialized, and `INPUT_ROW` reaching it. A
+    // regression there is a compile failure or an uninitialized-state error, not a wrong value.
+    // These are two paths, not three: `CollapseCodegenStages` rejects an operator holding a
+    // non-leaf `CodegenFallback`, which is what guarantees `With.doGenCode` an `INPUT_ROW`.
+    withSQLConf(SQLConf.ALWAYS_INLINE_COMMON_EXPR.key -> "false") {
+      val query = "SELECT CASE WHEN id < 0 THEN 'skipped' " +
+        "ELSE nullif(reflect('java.util.UUID', 'randomUUID'), 'never') END AS r " +
+        "FROM range(0, 3, 1, 1)"
+      val withs = spark.sql(query).queryExecution.optimizedPlan.collect {
+        case p => p.expressions.flatMap(_.collect { case w: With => w })
+      }.flatten
+      assert(withs.size == 1, s"expected one surviving With node, got ${withs.size}")
+      onEachEvalPath {
+        val got = spark.sql(query).collect().map(_.getString(0))
+        assert(got.length == 3, s"expected three rows, got ${got.mkString(", ")}")
+        assert(got.forall(_.length == 36), s"expected UUIDs, got ${got.mkString(", ")}")
+        assert(got.distinct.length == 3, s"expected a UUID per row, got ${got.mkString(", ")}")
+      }
+    }
+  }
+
+  test("SPARK-58902: a surviving With inside a window expression is evaluated once per row") {
+    // `ExtractWindowExpressions` moves the window function's argument into a `_w0` alias in the
+    // `Project` it synthesizes below the `Window`, so the host is `ProjectExec` as above and what
+    // this adds is that analyzer relocation. The definition is deterministic, so the values pin
+    // per-row clearing rather than memoization; the shape assertion is what keeps the test from
+    // passing on a plan that dropped the `With`.
+    withSQLConf(SQLConf.ALWAYS_INLINE_COMMON_EXPR.key -> "false") {
+      val query = "SELECT id, sum(CASE WHEN id < 0 THEN 0 ELSE nullif(id * 2, -1) END) " +
+        "OVER (ORDER BY id) AS s FROM range(0, 4, 1, 1)"
+      val withs = spark.sql(query).queryExecution.optimizedPlan.collect {
+        case p => p.expressions.flatMap(_.collect { case w: With => w })
+      }.flatten
+      assert(withs.size == 1, s"expected one surviving With node, got ${withs.size}")
+      onEachEvalPath {
+        // Keys are 0, 2, 4, 6, so the running sums are 0, 2, 6, 12.
+        checkAnswer(
+          spark.sql(query),
+          Seq(Row(0L, 0L), Row(1L, 2L), Row(2L, 6L), Row(3L, 12L)))
+      }
+    }
+  }
+
   test("in") {
     val df = Seq((1, "x"), (2, "y"), (3, "z")).toDF("a", "b")
     checkAnswer(df.filter($"a".isin(1, 2)),


---------------------------------------------------------------------
To unsubscribe, e-mail: commits-unsubscribe@spark.apache.org
For additional commands, e-mail: commits-help@spark.apache.org