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

cloud-fan pushed a commit to branch master
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/master by this push:
     new 498b36dfc84e [SPARK-60941][SQL] Move JoinSelection's choice for 
non-equi joins into JoinSelectionHelper
498b36dfc84e is described below

commit 498b36dfc84e6ea6b0f78bed52aca9bbc0a0bec6
Author: Prashanth Menon <[email protected]>
AuthorDate: Fri Nov 6 16:14:15 2026 +0000

    [SPARK-60941][SQL] Move JoinSelection's choice for non-equi joins into 
JoinSelectionHelper
    
    ### What changes were proposed in this pull request?
    
    This PR moves `JoinSelection`'s choice of strategy for a join without 
equi-join keys into a new `JoinSelectionHelper.getNonEquiJoinBuildSide(join, 
conf)`. It returns the side a broadcast nested loop join builds, or `None` for 
a Cartesian product. `JoinSelection` now plans from its answer. The rules and 
their order are unchanged.
    
    ### Why are the changes needed?
    
    `JoinSelectionHelper` already lets rules ask what `JoinSelection` would do 
with an equi-join without planning it: `getBroadcastBuildSide`, 
`getShuffleHashJoinBuildSide` and `getBroadcastHashJoinBuildSide`. Non-equi 
joins have no equivalent. A rule that needs to know which side a nested loop 
would build, for example to decide whether rewriting the join pays off, has to 
copy the branch's logic, and the copy drifts. Extracting the choice also lets 
it be unit-tested without planning a query.
    
    ### Does this PR introduce _any_ user-facing change?
    
    No.
    
    ### How was this patch tested?
    
    New unit tests in `JoinSelectionHelperSuite`, one per rule: a side small 
enough to broadcast, the Cartesian product of an inner join that can't 
broadcast, the side an outer join prefers however large, broadcast hints 
(including on an outer join's preserved side), the shuffle-replicate hint, and 
`NO_BROADCAST_AND_REPLICATION`. Existing planner suites, such as 
`JoinHintSuite` and `JoinSuite`, cover `JoinSelection` itself.
    
    ### Was this patch authored or co-authored using generative AI tooling?
    
    Generated-by: Claude Opus 5.5
    
    Closes #60144 from pmenon/join-selection-helper.
    
    Authored-by: Prashanth Menon <[email protected]>
    Signed-off-by: Wenchen Fan <[email protected]>
---
 .../spark/sql/catalyst/optimizer/joins.scala       | 73 ++++++++++++++++++++++
 .../optimizer/JoinSelectionHelperSuite.scala       | 58 ++++++++++++++++-
 .../spark/sql/execution/SparkStrategies.scala      | 73 ++--------------------
 3 files changed, 135 insertions(+), 69 deletions(-)

diff --git 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/joins.scala
 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/joins.scala
index b1cb873509fc..669868bdc482 100644
--- 
a/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/joins.scala
+++ 
b/sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/joins.scala
@@ -353,6 +353,79 @@ trait JoinSelectionHelper extends Logging {
     }
   }
 
+  /**
+   * How `JoinSelection` plans `join` when it has no equi-join keys and
+   * `canPlanAsBroadcastHashJoin(join, conf)` is false: the side a broadcast 
nested loop join
+   * builds, or `None` for a Cartesian product. Rules that need to know or 
price the plan a non-equi
+   * join gets can share it. Without equi-join keys, only a single-column 
null-aware anti join can
+   * be a broadcast hash join.
+   *
+   * With hints, it builds a broadcast-hinted side, or else plans a Cartesian 
product under a
+   * shuffle-replicate hint. Otherwise, or if no hint applies, it builds a 
side small enough to
+   * broadcast, or else plans a Cartesian product for an inner join, or else 
builds the side the
+   * join requires or prefers, however large. A side hinted 
NO_BROADCAST_AND_REPLICATION is never
+   * broadcast by size, and the hint rules out a Cartesian product, so the 
other side is built. Of
+   * two candidate sides, it builds the smaller for an inner or full join, the 
left for a right
+   * join, and the right for a left join.
+   */
+  def getNonEquiJoinBuildSide(join: Join, conf: SQLConf): Option[BuildSide] = {
+    val Join(left, right, joinType, _, hint) = join
+    val desiredBuildSide = if (joinType.isInstanceOf[InnerLike] || joinType == 
FullOuter) {
+      getSmallerSide(left, right)
+    } else {
+      // For perf reasons, `BroadcastNestedLoopJoinExec` prefers to broadcast 
left side if
+      // it's a right join, and broadcast right side if it's a left join.
+      // TODO: revisit it. If left side is much smaller than the right side, 
it may be better
+      // to broadcast the left side even if it's a left join.
+      if (canBuildBroadcastLeft(joinType)) BuildLeft else BuildRight
+    }
+
+    // The side to broadcast by hint, or by size, if any.
+    def broadcastSide(onlyLookingAtHint: Boolean): Option[BuildSide] = {
+      val buildLeft = if (onlyLookingAtHint) {
+        hintToBroadcastLeft(hint)
+      } else {
+        canBroadcastBySize(left, conf) && 
!hintToNotBroadcastAndReplicateLeft(hint)
+      }
+      val buildRight = if (onlyLookingAtHint) {
+        hintToBroadcastRight(hint)
+      } else {
+        canBroadcastBySize(right, conf) && 
!hintToNotBroadcastAndReplicateRight(hint)
+      }
+      if (buildLeft && buildRight) {
+        Some(desiredBuildSide)
+      } else if (buildLeft) {
+        Some(BuildLeft)
+      } else if (buildRight) {
+        Some(BuildRight)
+      } else {
+        None
+      }
+    }
+
+    val cartesianProduct =
+      joinType.isInstanceOf[InnerLike] && !hintToNotBroadcastAndReplicate(hint)
+    // The last resort could be very slow or OOM. It builds the desired side 
unless the join
+    // requires a particular build side (e.g. NO_BROADCAST_AND_REPLICATION 
hint).
+    def withoutHint: Option[BuildSide] = broadcastSide(onlyLookingAtHint = 
false).orElse {
+      if (cartesianProduct) {
+        None
+      } else {
+        Some(getBroadcastNestedLoopJoinBuildSide(hint, 
joinType).getOrElse(desiredBuildSide))
+      }
+    }
+
+    if (hint.isEmpty) {
+      withoutHint
+    } else {
+      broadcastSide(onlyLookingAtHint = true) match {
+        case hinted @ Some(_) => hinted
+        case None if hintToShuffleReplicateNL(hint) && cartesianProduct => None
+        case None => withoutHint
+      }
+    }
+  }
+
   def getSmallerSide(left: LogicalPlan, right: LogicalPlan): BuildSide = {
     if (right.stats.sizeInBytes <= left.stats.sizeInBytes) BuildRight else 
BuildLeft
   }
diff --git 
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/JoinSelectionHelperSuite.scala
 
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/JoinSelectionHelperSuite.scala
index b3f74687329e..fc8de40dfb1f 100644
--- 
a/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/JoinSelectionHelperSuite.scala
+++ 
b/sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/JoinSelectionHelperSuite.scala
@@ -19,8 +19,8 @@ package org.apache.spark.sql.catalyst.optimizer
 
 import org.apache.spark.sql.catalyst.dsl.expressions._
 import org.apache.spark.sql.catalyst.expressions.{Attribute, AttributeMap, 
EqualTo, IsNull, Or}
-import org.apache.spark.sql.catalyst.plans.{Inner, LeftAnti, PlanTest}
-import org.apache.spark.sql.catalyst.plans.logical.{BROADCAST, HintInfo, Join, 
JoinHint, LeafNode, LogicalPlan, NO_BROADCAST_HASH, SHUFFLE_HASH, Statistics}
+import org.apache.spark.sql.catalyst.plans.{Inner, LeftAnti, LeftOuter, 
PlanTest, RightOuter}
+import org.apache.spark.sql.catalyst.plans.logical.{BROADCAST, HintInfo, Join, 
JoinHint, LeafNode, LogicalPlan, NO_BROADCAST_AND_REPLICATION, 
NO_BROADCAST_HASH, SHUFFLE_HASH, SHUFFLE_REPLICATE_NL, Statistics}
 import org.apache.spark.sql.catalyst.statsEstimation.StatsTestPlan
 import org.apache.spark.sql.internal.SQLConf
 
@@ -200,6 +200,60 @@ class JoinSelectionHelperSuite extends PlanTest with 
JoinSelectionHelper {
     }
   }
 
+  test("getNonEquiJoinBuildSide builds a side small enough to broadcast") {
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "10MB") {
+      assert(getNonEquiJoinBuildSide(join, SQLConf.get) === Some(BuildRight))
+      // A left join builds its left side when only that side is small enough.
+      val smallLeft = Join(right, left, LeftOuter, None, JoinHint.NONE)
+      assert(getNonEquiJoinBuildSide(smallLeft, SQLConf.get) === 
Some(BuildLeft))
+    }
+  }
+
+  test("getNonEquiJoinBuildSide plans a Cartesian product when an inner join 
can't broadcast") {
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1") {
+      assert(getNonEquiJoinBuildSide(join, SQLConf.get).isEmpty)
+    }
+  }
+
+  test("getNonEquiJoinBuildSide builds the side an outer join prefers, however 
large") {
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1") {
+      assert(getNonEquiJoinBuildSide(join.copy(joinType = LeftOuter), 
SQLConf.get) ===
+        Some(BuildRight))
+      assert(getNonEquiJoinBuildSide(join.copy(joinType = RightOuter), 
SQLConf.get) ===
+        Some(BuildLeft))
+    }
+  }
+
+  test("getNonEquiJoinBuildSide builds a hinted side, even an outer join's 
preserved one") {
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "10MB") {
+      val hinted = join.copy(joinType = LeftOuter, hint = 
JoinHint(hintBroadcast, None))
+      assert(getNonEquiJoinBuildSide(hinted, SQLConf.get) === Some(BuildLeft))
+      // Both sides hinted: an inner join builds the smaller one.
+      val bothHinted = join.copy(hint = JoinHint(hintBroadcast, hintBroadcast))
+      assert(getNonEquiJoinBuildSide(bothHinted, SQLConf.get) === 
Some(BuildRight))
+    }
+  }
+
+  test("getNonEquiJoinBuildSide plans a Cartesian product under a 
shuffle-replicate hint") {
+    val hintShuffleReplicateNL = Some(HintInfo(Some(SHUFFLE_REPLICATE_NL)))
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "10MB") {
+      val inner = join.copy(hint = JoinHint(hintShuffleReplicateNL, None))
+      assert(getNonEquiJoinBuildSide(inner, SQLConf.get).isEmpty)
+      // A left join can't be a Cartesian product, so the hint doesn't apply.
+      val leftOuter = inner.copy(joinType = LeftOuter)
+      assert(getNonEquiJoinBuildSide(leftOuter, SQLConf.get) === 
Some(BuildRight))
+    }
+  }
+
+  test("getNonEquiJoinBuildSide builds the side NO_BROADCAST_AND_REPLICATION 
leaves") {
+    val hintNoBroadcastAndReplication = 
Some(HintInfo(Some(NO_BROADCAST_AND_REPLICATION)))
+    withSQLConf(SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "10MB") {
+      // The hint rules out both broadcasting the right side and a Cartesian 
product.
+      val hinted = join.copy(hint = JoinHint(None, 
hintNoBroadcastAndReplication))
+      assert(getNonEquiJoinBuildSide(hinted, SQLConf.get) === Some(BuildLeft))
+    }
+  }
+
   test("NAAJ broadcast threshold is floored by the automatic broadcast 
threshold") {
     val betweenThresholdsRight = right.copy(
       rowCount = 8 * 1024 * 1024,
diff --git 
a/sql/core/src/main/scala/org/apache/spark/sql/execution/SparkStrategies.scala 
b/sql/core/src/main/scala/org/apache/spark/sql/execution/SparkStrategies.scala
index 9a96e96c9a5f..647fb3a3b819 100644
--- 
a/sql/core/src/main/scala/org/apache/spark/sql/execution/SparkStrategies.scala
+++ 
b/sql/core/src/main/scala/org/apache/spark/sql/execution/SparkStrategies.scala
@@ -27,7 +27,7 @@ import org.apache.spark.sql.catalyst.InternalRow
 import org.apache.spark.sql.catalyst.analysis.{EliminateSubqueryAliases, 
NamedRelation}
 import org.apache.spark.sql.catalyst.encoders.ExpressionEncoder
 import org.apache.spark.sql.catalyst.expressions._
-import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, 
BuildSide, JoinSelectionHelper, NormalizeFloatingNumbers}
+import org.apache.spark.sql.catalyst.optimizer.{BuildRight, BuildSide, 
JoinSelectionHelper, NormalizeFloatingNumbers}
 import org.apache.spark.sql.catalyst.planning._
 import org.apache.spark.sql.catalyst.plans._
 import org.apache.spark.sql.catalyst.plans.logical._
@@ -367,75 +367,14 @@ abstract class SparkStrategies extends 
QueryPlanner[SparkPlan] {
       //   3. Pick broadcast nested loop join as the final solution. It may 
OOM but we don't have
       //      other choice. It broadcasts the smaller side for inner and full 
joins, broadcasts the
       //      left side for right join, and broadcasts right side for left 
join.
-      case logical.Join(left, right, joinType, condition, hint) =>
+      case j @ logical.Join(left, right, joinType, condition, hint) =>
         checkHintNonEquiJoin(hint)
-        val desiredBuildSide = if (joinType.isInstanceOf[InnerLike] || 
joinType == FullOuter) {
-          getSmallerSide(left, right)
-        } else {
-          // For perf reasons, `BroadcastNestedLoopJoinExec` prefers to 
broadcast left side if
-          // it's a right join, and broadcast right side if it's a left join.
-          // TODO: revisit it. If left side is much smaller than the right 
side, it may be better
-          // to broadcast the left side even if it's a left join.
-          if (canBuildBroadcastLeft(joinType)) BuildLeft else BuildRight
-        }
-
-        def createBroadcastNLJoin(onlyLookingAtHint: Boolean) = {
-          val buildLeft = if (onlyLookingAtHint) {
-            hintToBroadcastLeft(hint)
-          } else {
-            canBroadcastBySize(left, conf) && 
!hintToNotBroadcastAndReplicateLeft(hint)
-          }
-
-          val buildRight = if (onlyLookingAtHint) {
-            hintToBroadcastRight(hint)
-          } else {
-            canBroadcastBySize(right, conf) && 
!hintToNotBroadcastAndReplicateRight(hint)
-          }
-
-          val maybeBuildSide = if (buildLeft && buildRight) {
-            Some(desiredBuildSide)
-          } else if (buildLeft) {
-            Some(BuildLeft)
-          } else if (buildRight) {
-            Some(BuildRight)
-          } else {
-            None
-          }
-
-          maybeBuildSide.map { buildSide =>
+        getNonEquiJoinBuildSide(j, conf) match {
+          case Some(buildSide) =>
             Seq(joins.BroadcastNestedLoopJoinExec(
               planLater(left), planLater(right), buildSide, joinType, 
condition))
-          }
-        }
-
-        def createCartesianProduct() = {
-          if (joinType.isInstanceOf[InnerLike] && 
!hintToNotBroadcastAndReplicate(hint)) {
-            Some(Seq(joins.CartesianProductExec(planLater(left), 
planLater(right), condition)))
-          } else {
-            None
-          }
-        }
-
-        def createJoinWithoutHint() = {
-          createBroadcastNLJoin(false)
-            .orElse(createCartesianProduct())
-            .getOrElse {
-              // This join could be very slow or OOM
-              // Build the desired side unless the join requires a particular 
build side
-              // (e.g. NO_BROADCAST_AND_REPLICATION hint)
-              val requiredBuildSide = 
getBroadcastNestedLoopJoinBuildSide(hint, joinType)
-              val buildSide = requiredBuildSide.getOrElse(desiredBuildSide)
-              Seq(joins.BroadcastNestedLoopJoinExec(
-                planLater(left), planLater(right), buildSide, joinType, 
condition))
-            }
-        }
-
-        if (hint.isEmpty) {
-          createJoinWithoutHint()
-        } else {
-          createBroadcastNLJoin(true)
-            .orElse { if (hintToShuffleReplicateNL(hint)) 
createCartesianProduct() else None }
-            .getOrElse(createJoinWithoutHint())
+          case None =>
+            Seq(joins.CartesianProductExec(planLater(left), planLater(right), 
condition))
         }
 
       // --- Cases where this strategy does not apply 
---------------------------------------------


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

Reply via email to