You are viewing a plain text version of this content. The canonical link for it is here.
Posted to commits@spark.apache.org by su...@apache.org on 2026/05/06 18:12:14 UTC

(spark) branch branch-4.2 updated: [SPARK-36082][SQL] Restrict null-aware anti joins to broadcastable right sides

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

sunchao pushed a commit to branch branch-4.2
in repository https://gitbox.apache.org/repos/asf/spark.git


The following commit(s) were added to refs/heads/branch-4.2 by this push:
     new fe506a7eb81b [SPARK-36082][SQL] Restrict null-aware anti joins to broadcastable right sides
fe506a7eb81b is described below

commit fe506a7eb81b8a5a2d6c7f5a65814d0d49828dcb
Author: jbharadw-oai <jb...@openai.com>
AuthorDate: Tue May 5 20:39:17 2026 -0700

    [SPARK-36082][SQL] Restrict null-aware anti joins to broadcastable right sides
    
    ### What changes were proposed in this pull request?
    
    This PR restricts the single-column null-aware anti join optimization to cases where the right
    side can actually be broadcast, following up on the earlier proposal in #33289.
    
    It also makes adaptive query stage reuse mode-aware for hashed broadcast exchanges:
    - regular equi joins only reuse non-null-aware hashed broadcast stages
    - null-aware anti joins only reuse null-aware hashed broadcast stages
    
    ### Why are the changes needed?
    
    Single-column null-aware anti joins build the right side as a broadcast hash relation, but the
    planner currently selects that path unconditionally once the logical pattern matches. That can
    choose a broadcast hash join even when the right side is above the broadcast threshold.
    
    In addition, adaptive planning was treating hashed broadcast stages as interchangeable without
    checking whether they were null-aware. Null-aware and regular hashed relations have different
    semantics, so they should not be reused across each other.
    
    ### Does this PR introduce _any_ user-facing change?
    
    Yes. Queries that match the single-column null-aware anti join optimization no longer force a
    broadcast hash join when the right side exceeds the broadcast threshold; they fall back to normal
    join planning instead.
    
    ### How was this patch tested?
    
    Added regression coverage for:
    - `JoinSelectionHelper.canPlanAsBroadcastHashJoin`
    - physical planning when a null-aware anti join right side is above the broadcast threshold
    - adaptive query stage reuse for null-aware vs regular hashed broadcast modes
    
    Ran:
    - `./build/sbt "catalyst/testOnly org.apache.spark.sql.catalyst.optimizer.JoinSelectionHelperSuite -- -z single-column"`
    - `./build/sbt "sql/testOnly org.apache.spark.sql.execution.adaptive.AdaptiveQueryExecSuite -- -z hashed"`
    - `./build/sbt "sql/testOnly org.apache.spark.sql.JoinSuite -- -z SPARK-36082"`
    - `./build/sbt "sql/testOnly org.apache.spark.sql.SparkSessionExtensionSuite"`
    - `./build/sbt "sql/testOnly org.apache.spark.sql.SubquerySuite -- -z SingleColumn"`
    
    ### Was this patch authored or co-authored using generative AI tooling?
    
    Generated-by: Codex GPT-5
    
    Closes #55678 from jbharadw-oai/dev/jbharadw/spark-36082-null-aware-anti-join-oss.
    
    Authored-by: jbharadw-oai <jb...@openai.com>
    Signed-off-by: Chao Sun <ch...@openai.com>
---
 .../spark/sql/catalyst/optimizer/joins.scala       |  3 +-
 .../optimizer/JoinSelectionHelperSuite.scala       | 19 ++++++++-
 .../spark/sql/execution/SparkStrategies.scala      |  3 +-
 .../adaptive/LogicalQueryStageStrategy.scala       | 41 ++++++++++++++----
 .../execution/exchange/BroadcastExchangeExec.scala |  2 +
 .../scala/org/apache/spark/sql/JoinSuite.scala     | 11 +++++
 .../spark/sql/SparkSessionExtensionSuite.scala     |  3 +-
 .../adaptive/AdaptiveQueryExecSuite.scala          | 48 ++++++++++++++++++++--
 8 files changed, 113 insertions(+), 17 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 be07b440a118..13e3cb76805d 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
@@ -427,7 +427,7 @@ trait JoinSelectionHelper extends Logging {
       getBroadcastBuildSide(join, hintOnly = true, conf).isDefined ||
         (noShufflePlannedBefore &&
           getBroadcastBuildSide(join, hintOnly = false, conf).isDefined)
-    case ExtractSingleColumnNullAwareAntiJoin(_, _) => true
+    case j @ ExtractSingleColumnNullAwareAntiJoin(_, _) => canBroadcastBySize(j.right, conf)
     case _ => false
   }
 
@@ -560,4 +560,3 @@ trait JoinSelectionHelper extends Logging {
       conf.getConfString("spark.sql.join.forceApplyShuffledHashJoin", "false") == "true"
   }
 }
-
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 61fb68cfba86..bac20c6ed353 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
@@ -18,8 +18,8 @@
 package org.apache.spark.sql.catalyst.optimizer
 
 import org.apache.spark.sql.catalyst.dsl.expressions._
-import org.apache.spark.sql.catalyst.expressions.AttributeMap
-import org.apache.spark.sql.catalyst.plans.{Inner, PlanTest}
+import org.apache.spark.sql.catalyst.expressions.{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, NO_BROADCAST_HASH, SHUFFLE_HASH}
 import org.apache.spark.sql.catalyst.statsEstimation.StatsTestPlan
 import org.apache.spark.sql.internal.SQLConf
@@ -156,4 +156,19 @@ class JoinSelectionHelperSuite extends PlanTest with JoinSelectionHelper {
     }
   }
 
+  test("canPlanAsBroadcastHashJoin should respect size for single-column null-aware anti join") {
+    val leftKey = left.output.head
+    val rightKey = right.output.head
+    val condition = Or(EqualTo(leftKey, rightKey), IsNull(EqualTo(leftKey, rightKey)))
+    val nullAwareAntiJoin = Join(left, right, LeftAnti, Some(condition), JoinHint.NONE)
+    val largeRight = right.copy(rowCount = 20000000, size = Some(20000000))
+
+    withSQLConf(
+      SQLConf.OPTIMIZE_NULL_AWARE_ANTI_JOIN.key -> "true",
+      SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "10MB") {
+      assert(canPlanAsBroadcastHashJoin(nullAwareAntiJoin, SQLConf.get))
+      assert(!canPlanAsBroadcastHashJoin(nullAwareAntiJoin.copy(right = largeRight), SQLConf.get))
+    }
+  }
+
 }
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 919c1b97fd0f..2c060aa3f9a5 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
@@ -328,7 +328,8 @@ abstract class SparkStrategies extends QueryPlanner[SparkPlan] {
             .getOrElse(createJoinWithoutHint())
         }
 
-      case j @ ExtractSingleColumnNullAwareAntiJoin(leftKeys, rightKeys) =>
+      case j @ ExtractSingleColumnNullAwareAntiJoin(leftKeys, rightKeys)
+          if canBroadcastBySize(j.right, conf) =>
         Seq(joins.BroadcastHashJoinExec(leftKeys, rightKeys, LeftAnti, BuildRight,
           None, planLater(j.left), planLater(j.right), isNullAwareAntiJoin = true))
 
diff --git a/sql/core/src/main/scala/org/apache/spark/sql/execution/adaptive/LogicalQueryStageStrategy.scala b/sql/core/src/main/scala/org/apache/spark/sql/execution/adaptive/LogicalQueryStageStrategy.scala
index d59fe8222c7f..af16c41f2ee3 100644
--- a/sql/core/src/main/scala/org/apache/spark/sql/execution/adaptive/LogicalQueryStageStrategy.scala
+++ b/sql/core/src/main/scala/org/apache/spark/sql/execution/adaptive/LogicalQueryStageStrategy.scala
@@ -21,9 +21,10 @@ import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight}
 import org.apache.spark.sql.catalyst.planning.{ExtractEquiJoinKeys, ExtractSingleColumnNullAwareAntiJoin}
 import org.apache.spark.sql.catalyst.plans.LeftAnti
 import org.apache.spark.sql.catalyst.plans.logical.{Join, LogicalPlan}
+import org.apache.spark.sql.catalyst.plans.physical.IdentityBroadcastMode
 import org.apache.spark.sql.classic.Strategy
 import org.apache.spark.sql.execution.{joins, SparkPlan}
-import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec}
+import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, HashedRelationBroadcastMode}
 
 /**
  * Strategy for plans containing [[LogicalQueryStage]] nodes:
@@ -36,28 +37,52 @@ import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, BroadcastNes
  */
 object LogicalQueryStageStrategy extends Strategy {
 
-  private def isBroadcastStage(plan: LogicalPlan): Boolean = plan match {
-    case LogicalQueryStage(_, _: BroadcastQueryStageExec) => true
+  private def isBroadcastStageWithHashedBroadcastMode(
+      plan: LogicalPlan,
+      isNullAware: Boolean): Boolean = plan match {
+    case LogicalQueryStage(_, bqs: BroadcastQueryStageExec) =>
+      bqs.broadcast.mode match {
+        case HashedRelationBroadcastMode(_, stageIsNullAware) =>
+          stageIsNullAware == isNullAware
+        case _ => false
+      }
+    case _ => false
+  }
+
+  private def isBroadcastStageWithIdentityBroadcastMode(plan: LogicalPlan): Boolean = plan match {
+    case LogicalQueryStage(_, bqs: BroadcastQueryStageExec) =>
+      bqs.broadcast.mode match {
+        case IdentityBroadcastMode => true
+        case _ => false
+      }
     case _ => false
   }
 
   def apply(plan: LogicalPlan): Seq[SparkPlan] = plan match {
     case ExtractEquiJoinKeys(joinType, leftKeys, rightKeys, otherCondition, _,
           left, right, hint)
-        if isBroadcastStage(left) || isBroadcastStage(right) =>
-      val buildSide = if (isBroadcastStage(left)) BuildLeft else BuildRight
+        if isBroadcastStageWithHashedBroadcastMode(left, isNullAware = false) ||
+            isBroadcastStageWithHashedBroadcastMode(right, isNullAware = false) =>
+      val buildSide =
+        if (isBroadcastStageWithHashedBroadcastMode(left, isNullAware = false)) {
+          BuildLeft
+        } else {
+          BuildRight
+        }
       Seq(BroadcastHashJoinExec(
         leftKeys, rightKeys, joinType, buildSide, otherCondition, planLater(left),
         planLater(right)))
 
     case j @ ExtractSingleColumnNullAwareAntiJoin(leftKeys, rightKeys)
-        if isBroadcastStage(j.right) =>
+        if isBroadcastStageWithHashedBroadcastMode(j.right, isNullAware = true) =>
       Seq(joins.BroadcastHashJoinExec(leftKeys, rightKeys, LeftAnti, BuildRight,
         None, planLater(j.left), planLater(j.right), isNullAwareAntiJoin = true))
 
     case j @ Join(left, right, joinType, condition, _)
-        if isBroadcastStage(left) || isBroadcastStage(right) =>
-      val buildSide = if (isBroadcastStage(left)) BuildLeft else BuildRight
+        if isBroadcastStageWithIdentityBroadcastMode(left) ||
+            isBroadcastStageWithIdentityBroadcastMode(right) =>
+      val buildSide =
+        if (isBroadcastStageWithIdentityBroadcastMode(left)) BuildLeft else BuildRight
       BroadcastNestedLoopJoinExec(
         planLater(left), planLater(right), buildSide, joinType, condition) :: Nil
 
diff --git a/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/BroadcastExchangeExec.scala b/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/BroadcastExchangeExec.scala
index 8c695f4f3958..614822813698 100644
--- a/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/BroadcastExchangeExec.scala
+++ b/sql/core/src/main/scala/org/apache/spark/sql/execution/exchange/BroadcastExchangeExec.scala
@@ -45,6 +45,8 @@ import org.apache.spark.util.{SparkFatalException, ThreadUtils}
  */
 trait BroadcastExchangeLike extends Exchange {
 
+  def mode: BroadcastMode
+
   /**
    * The broadcast run ID in job tag
    */
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/JoinSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/JoinSuite.scala
index 42aa2b46fb72..3ea77446f268 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/JoinSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/JoinSuite.scala
@@ -1288,6 +1288,17 @@ class JoinSuite extends SharedSparkSession with AdaptiveSparkPlanHelper
     }
   }
 
+  test("SPARK-36082: only use SingleColumn Null Aware Anti Join when right side " +
+      "can broadcast") {
+    withSQLConf(SQLConf.OPTIMIZE_NULL_AWARE_ANTI_JOIN.key -> "true",
+      SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "0") {
+      val joinExec = assertJoin((
+        "select * from testData where key not in (select b from testData3)",
+        classOf[BroadcastNestedLoopJoinExec]))
+      assert(!joinExec.isInstanceOf[BroadcastHashJoinExec])
+    }
+  }
+
   test("SPARK-32399: Full outer shuffled hash join") {
     val inputDFs = Seq(
       // Test unique join key
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/SparkSessionExtensionSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/SparkSessionExtensionSuite.scala
index bfcf583a7051..ebe6d8858a7e 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/SparkSessionExtensionSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/SparkSessionExtensionSuite.scala
@@ -34,7 +34,7 @@ import org.apache.spark.sql.catalyst.expressions.aggregate.{AggregateExpression,
 import org.apache.spark.sql.catalyst.parser.{CatalystSqlParser, ParserInterface}
 import org.apache.spark.sql.catalyst.plans.{PlanTest, SQLHelper}
 import org.apache.spark.sql.catalyst.plans.logical.{Aggregate, AggregateHint, ColumnStat, Limit, LocalRelation, LogicalPlan, Project, Range, Sort, SortHint, Statistics, UnresolvedHint}
-import org.apache.spark.sql.catalyst.plans.physical.{Partitioning, SinglePartition}
+import org.apache.spark.sql.catalyst.plans.physical.{BroadcastMode, Partitioning, SinglePartition}
 import org.apache.spark.sql.catalyst.rules.Rule
 import org.apache.spark.sql.catalyst.trees.TreeNodeTag
 import org.apache.spark.sql.classic.ClassicConversions._
@@ -1175,6 +1175,7 @@ case class MyShuffleExchangeExec(delegate: ShuffleExchangeExec) extends ShuffleE
  * whether AQE is enabled.
  */
 case class MyBroadcastExchangeExec(delegate: BroadcastExchangeExec) extends BroadcastExchangeLike {
+  override def mode: BroadcastMode = delegate.mode
   override val runId: UUID = delegate.runId
   override def relationFuture: java.util.concurrent.Future[Broadcast[Any]] =
     delegate.relationFuture
diff --git a/sql/core/src/test/scala/org/apache/spark/sql/execution/adaptive/AdaptiveQueryExecSuite.scala b/sql/core/src/test/scala/org/apache/spark/sql/execution/adaptive/AdaptiveQueryExecSuite.scala
index b2c7745d0a9a..50322905f29f 100644
--- a/sql/core/src/test/scala/org/apache/spark/sql/execution/adaptive/AdaptiveQueryExecSuite.scala
+++ b/sql/core/src/test/scala/org/apache/spark/sql/execution/adaptive/AdaptiveQueryExecSuite.scala
@@ -29,9 +29,10 @@ import org.apache.spark.scheduler.{SparkListener, SparkListenerEvent, SparkListe
 import org.apache.spark.shuffle.sort.SortShuffleManager
 import org.apache.spark.sql.{DataFrame, Dataset, Row, SparkSession}
 import org.apache.spark.sql.catalyst.InternalRow
-import org.apache.spark.sql.catalyst.expressions.Attribute
+import org.apache.spark.sql.catalyst.expressions.{Attribute, AttributeReference, EqualTo, IsNull, Or}
 import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight}
-import org.apache.spark.sql.catalyst.plans.logical.{Aggregate, LogicalPlan}
+import org.apache.spark.sql.catalyst.plans.{Inner, LeftAnti}
+import org.apache.spark.sql.catalyst.plans.logical.{Aggregate, Join, JoinHint, LocalRelation, LogicalPlan}
 import org.apache.spark.sql.classic.Strategy
 import org.apache.spark.sql.execution._
 import org.apache.spark.sql.execution.aggregate.BaseAggregateExec
@@ -40,7 +41,7 @@ import org.apache.spark.sql.execution.command.DataWritingCommandExec
 import org.apache.spark.sql.execution.datasources.noop.NoopDataSource
 import org.apache.spark.sql.execution.datasources.v2.V2TableWriteExec
 import org.apache.spark.sql.execution.exchange.{BroadcastExchangeExec, ENSURE_REQUIREMENTS, Exchange, REPARTITION_BY_COL, REPARTITION_BY_NUM, ReusedExchangeExec, ShuffleExchangeExec, ShuffleExchangeLike, ShuffleOrigin}
-import org.apache.spark.sql.execution.joins.{BaseJoinExec, BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, ShuffledHashJoinExec, ShuffledJoin, SortMergeJoinExec}
+import org.apache.spark.sql.execution.joins.{BaseJoinExec, BroadcastHashJoinExec, BroadcastNestedLoopJoinExec, HashedRelationBroadcastMode, ShuffledHashJoinExec, ShuffledJoin, SortMergeJoinExec}
 import org.apache.spark.sql.execution.metric.SQLShuffleReadMetricsReporter
 import org.apache.spark.sql.execution.streaming.runtime.{MemoryStream, StreamingQueryWrapper}
 import org.apache.spark.sql.execution.streaming.state.RocksDBStateStoreProvider
@@ -1634,6 +1635,47 @@ class AdaptiveQueryExecSuite
     }
   }
 
+  test("LogicalQueryStageStrategy keeps hashed broadcast modes separate") {
+    val left = LocalRelation(AttributeReference("l", IntegerType)())
+    val right = LocalRelation(AttributeReference("r", IntegerType)())
+
+    def broadcastStage(plan: LocalRelation, isNullAware: Boolean): LogicalQueryStage = {
+      val scan = LocalTableScanExec(plan.output, Nil, None)
+      val exchange = BroadcastExchangeExec(
+        HashedRelationBroadcastMode(plan.output, isNullAware), scan)
+      LogicalQueryStage(plan, BroadcastQueryStageExec(0, exchange, exchange))
+    }
+
+    val equiJoin = Join(
+      broadcastStage(left, isNullAware = false),
+      right,
+      Inner,
+      Some(EqualTo(left.output.head, right.output.head)),
+      JoinHint.NONE)
+    assert(LogicalQueryStageStrategy(equiJoin).head.isInstanceOf[BroadcastHashJoinExec])
+
+    val equiJoinWithNullAwareStage = equiJoin.copy(
+      left = broadcastStage(left, isNullAware = true))
+    assert(LogicalQueryStageStrategy(equiJoinWithNullAwareStage).isEmpty)
+
+    val naajCondition = Or(
+      EqualTo(left.output.head, right.output.head),
+      IsNull(EqualTo(left.output.head, right.output.head)))
+    val nullAwareAntiJoin = Join(
+      left,
+      broadcastStage(right, isNullAware = true),
+      LeftAnti,
+      Some(naajCondition),
+      JoinHint.NONE)
+    val naaj = LogicalQueryStageStrategy(nullAwareAntiJoin).head
+      .asInstanceOf[BroadcastHashJoinExec]
+    assert(naaj.isNullAwareAntiJoin)
+
+    val nullAwareAntiJoinWithRegularStage = nullAwareAntiJoin.copy(
+      right = broadcastStage(right, isNullAware = false))
+    assert(LogicalQueryStageStrategy(nullAwareAntiJoinWithRegularStage).isEmpty)
+  }
+
   test("SPARK-32717: AQEOptimizer should respect excludedRules configuration") {
     withSQLConf(
       SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "true",


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