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]