This is an automated email from the ASF dual-hosted git repository.
zhztheplayer pushed a commit to branch main
in repository https://gitbox.apache.org/repos/asf/gluten.git
The following commit(s) were added to refs/heads/main by this push:
new 8a35c31ee2 [VL] Optimize the streamed side of native sort merge joins
(#13567)
8a35c31ee2 is described below
commit 8a35c31ee210d29bfde417b2618437f1c4a24fde
Author: kevinwilfong <[email protected]>
AuthorDate: Tue Nov 10 21:40:59 2026 -0800
[VL] Optimize the streamed side of native sort merge joins (#13567)
Add an opt-in native translation swap that reuses hash join size selection
to put the estimated larger input on Velox's streamed left side. Support
inner-like and left, right and full outer equijoins, reversing native outer
join types and restoring column order through JoinUtils when inputs swap.
Preserve Spark children, keys, join types and output metadata. Keep the
option disabled by default, preserve skew joins and joins without known
input sizes, and retain forced hash join precedence. Other backends keep
their existing conversion behavior.
Traverse scans in translated input order and align preprojection metrics
with streamed and buffered keys. Add conversion and native query coverage
for orientation, outer joins, computed keys and scans without an exchange.
Generated-by: OpenAI Codex GPT-6
---
.../backendsapi/velox/VeloxSparkPlanExecApi.scala | 32 +++-
.../org/apache/gluten/config/VeloxConfig.scala | 13 ++
.../execution/SortMergeJoinTranslationSuite.scala | 202 +++++++++++++++++++++
docs/backends/velox/velox-configuration.md | 1 +
.../gluten/backendsapi/SparkPlanExecApi.scala | 13 +-
.../execution/SortMergeJoinExecTransformer.scala | 30 ++-
.../gluten/execution/WholeStageTransformer.scala | 2 +
.../columnar/offload/OffloadSingleNodeRules.scala | 12 +-
.../GlutenSortMergeJoinStreamedSideSuite.scala | 194 ++++++++++++++++++++
9 files changed, 475 insertions(+), 24 deletions(-)
diff --git
a/backends-velox/src/main/scala/org/apache/gluten/backendsapi/velox/VeloxSparkPlanExecApi.scala
b/backends-velox/src/main/scala/org/apache/gluten/backendsapi/velox/VeloxSparkPlanExecApi.scala
index 087753c21f..b8b3dce549 100644
---
a/backends-velox/src/main/scala/org/apache/gluten/backendsapi/velox/VeloxSparkPlanExecApi.scala
+++
b/backends-velox/src/main/scala/org/apache/gluten/backendsapi/velox/VeloxSparkPlanExecApi.scala
@@ -24,6 +24,7 @@ import org.apache.gluten.expression._
import org.apache.gluten.expression.aggregate.{HLLAdapter,
VeloxBloomFilterAggregate, VeloxCollectList, VeloxCollectSet}
import org.apache.gluten.extension.{BroadcastJoinContextInfo,
BroadcastJoinContextTag}
import org.apache.gluten.extension.columnar.FallbackTags
+import org.apache.gluten.extension.columnar.offload.OffloadJoin
import org.apache.gluten.shuffle.NeedCustomColumnarBatchSerializer
import org.apache.gluten.sql.shims.SparkShimLoader
import org.apache.gluten.substrait.SubstraitContext
@@ -43,14 +44,15 @@ import
org.apache.spark.sql.catalyst.catalog.CatalogTypes.TablePartitionSpec
import org.apache.spark.sql.catalyst.expressions._
import
org.apache.spark.sql.catalyst.expressions.aggregate.{AggregateExpression,
CollectList, CollectSet}
import org.apache.spark.sql.catalyst.expressions.objects.{AssertNotNull,
StaticInvoke}
-import org.apache.spark.sql.catalyst.optimizer.BuildSide
+import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildSide}
import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, FullOuter,
InnerLike, JoinType, LeftAnti, LeftOuter, LeftSemi, RightOuter}
+import org.apache.spark.sql.catalyst.plans.logical.Join
import org.apache.spark.sql.catalyst.plans.physical._
import org.apache.spark.sql.execution._
import org.apache.spark.sql.execution.adaptive.AQEShuffleReadExec
import org.apache.spark.sql.execution.datasources.FileFormat
import org.apache.spark.sql.execution.exchange.ShuffleExchangeExec
-import org.apache.spark.sql.execution.joins.{BuildSideRelation,
HashedRelationBroadcastMode, SparkHashJoinUtils}
+import org.apache.spark.sql.execution.joins.{BuildSideRelation,
HashedRelationBroadcastMode, SortMergeJoinExec, SparkHashJoinUtils}
import org.apache.spark.sql.execution.metric.SQLMetric
import org.apache.spark.sql.execution.python.ArrowEvalPythonExec
import org.apache.spark.sql.execution.unsafe.UnsafeColumnarBuildSideRelation
@@ -541,6 +543,32 @@ class VeloxSparkPlanExecApi extends SparkPlanExecApi with
Logging {
SampleExecTransformer(lowerBound, upperBound, withReplacement, seed, child)
}
+ override def genSortMergeJoinExecTransformer(
+ plan: SortMergeJoinExec): SortMergeJoinExecTransformerBase = {
+ val swappable = plan.joinType match {
+ case _: InnerLike | LeftOuter | RightOuter | FullOuter => true
+ case _ => false
+ }
+ val switchChildren = VeloxConfig.get.optimizeSortMergeJoinStreamedSide &&
+ !GlutenConfig.get.forceShuffledHashJoin && swappable && !plan.isSkewJoin
&&
+ plan.leftKeys.nonEmpty && plan.logicalLink.exists {
+ case join: Join =>
+ val sizes = Seq(join.left.stats.sizeInBytes,
join.right.stats.sizeInBytes)
+ sizes.forall(size => size >= 0 && size !=
SQLConf.get.defaultSizeInBytes) &&
+ OffloadJoin.getOptimalBuildSide(join) == BuildLeft
+ case _ => false
+ }
+ SortMergeJoinExecTransformer(
+ plan.leftKeys,
+ plan.rightKeys,
+ plan.joinType,
+ plan.condition,
+ plan.left,
+ plan.right,
+ plan.isSkewJoin,
+ switchChildren = switchChildren)
+ }
+
override def genSortMergeJoinExecTransformer(
leftKeys: Seq[Expression],
rightKeys: Seq[Expression],
diff --git
a/backends-velox/src/main/scala/org/apache/gluten/config/VeloxConfig.scala
b/backends-velox/src/main/scala/org/apache/gluten/config/VeloxConfig.scala
index ff056dbabc..dc5ab215c1 100644
--- a/backends-velox/src/main/scala/org/apache/gluten/config/VeloxConfig.scala
+++ b/backends-velox/src/main/scala/org/apache/gluten/config/VeloxConfig.scala
@@ -79,6 +79,9 @@ class VeloxConfig(conf: SQLConf) extends GlutenConfig(conf) {
def broadcastNestedLoopJoinFullOuterRewriteThreshold: Long =
getConf(VELOX_BROADCAST_NESTED_LOOP_JOIN_FULL_OUTER_REWRITE_THRESHOLD)
+ def optimizeSortMergeJoinStreamedSide: Boolean =
+ getConf(SORT_MERGE_JOIN_OPTIMIZE_STREAMED_SIDE)
+
def veloxBroadcastHashTableBuildTargetBytes: Long =
getConf(COLUMNAR_VELOX_BROADCAST_HASH_TABLE_BUILD_TARGET_BYTES)
@@ -285,6 +288,16 @@ object VeloxConfig extends ConfigRegistry {
.bytesConf(ByteUnit.BYTE)
.createWithDefaultString("10MB")
+ val SORT_MERGE_JOIN_OPTIMIZE_STREAMED_SIDE =
+
buildConf("spark.gluten.sql.columnar.backend.velox.sortMergeJoin.optimizeStreamedSide")
+ .doc(
+ "Use input size statistics to put the larger input on the streamed
left side of " +
+ "native inner and outer sort merge joins. Skew joins and joins
without known input " +
+ "sizes keep their original orientation. Velox can buffer matching
groups from " +
+ "both sides.")
+ .booleanConf
+ .createWithDefault(false)
+
val COLUMNAR_VELOX_ASYNC_TIMEOUT_ON_TASK_STOPPING =
buildStaticConf("spark.gluten.sql.columnar.backend.velox.asyncTimeoutOnTaskStopping")
.doc("Timeout in milliseconds when waiting for runtime-scoped async work
to finish during" +
diff --git
a/backends-velox/src/test/scala/org/apache/spark/sql/execution/SortMergeJoinTranslationSuite.scala
b/backends-velox/src/test/scala/org/apache/spark/sql/execution/SortMergeJoinTranslationSuite.scala
new file mode 100644
index 0000000000..d3c119fcdd
--- /dev/null
+++
b/backends-velox/src/test/scala/org/apache/spark/sql/execution/SortMergeJoinTranslationSuite.scala
@@ -0,0 +1,202 @@
+/*
+ * 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.execution
+
+import org.apache.gluten.backendsapi.velox.VeloxSparkPlanExecApi
+import org.apache.gluten.config.{GlutenConfig, VeloxConfig}
+import org.apache.gluten.execution.SortMergeJoinExecTransformerBase
+
+import org.apache.spark.sql.GlutenQueryTest
+import org.apache.spark.sql.catalyst.expressions.{Attribute,
AttributeReference, EqualTo, SortOrder}
+import org.apache.spark.sql.catalyst.expressions.Ascending
+import org.apache.spark.sql.catalyst.plans._
+import org.apache.spark.sql.catalyst.plans.logical.{Join, JoinHint, LeafNode,
LocalRelation, Statistics}
+import org.apache.spark.sql.catalyst.plans.physical.HashPartitioning
+import org.apache.spark.sql.execution.exchange.ShuffleExchangeExec
+import org.apache.spark.sql.execution.joins.SortMergeJoinExec
+import org.apache.spark.sql.test.SharedSparkSession
+import org.apache.spark.sql.types.{BooleanType, LongType}
+
+class SortMergeJoinTranslationSuite extends GlutenQueryTest with
SharedSparkSession {
+ private val optimizeKey =
VeloxConfig.SORT_MERGE_JOIN_OPTIMIZE_STREAMED_SIDE.key
+
+ private case class SizedRelation(
+ override val output: Seq[Attribute],
+ bytes: BigInt,
+ rows: Option[BigInt] = None)
+ extends LeafNode {
+ override def computeStats(): Statistics = Statistics(sizeInBytes = bytes,
rowCount = rows)
+ }
+
+ private def localScan(attribute: Attribute): SparkPlan =
+ spark.sessionState.planner.plan(LocalRelation(Seq(attribute))).next()
+
+ private def mergeJoin(
+ leftBytes: BigInt = 16,
+ rightBytes: BigInt = 160,
+ joinType: JoinType = Inner,
+ skew: Boolean = false,
+ leftRows: Option[BigInt] = None,
+ rightRows: Option[BigInt] = None): SortMergeJoinExec = {
+ val l = AttributeReference("key", LongType, nullable = false)()
+ val r = AttributeReference("key", LongType, nullable = false)()
+ val left = SizedRelation(Seq(l), leftBytes, leftRows)
+ val right = SizedRelation(Seq(r), rightBytes, rightRows)
+ val condition = Some(EqualTo(l, r))
+ val logical = Join(left, right, joinType, condition, JoinHint.NONE)
+ val smj = SortMergeJoinExec(
+ Seq(l),
+ Seq(r),
+ joinType,
+ condition,
+ SortExec(
+ Seq(SortOrder(l, Ascending)),
+ global = false,
+ ShuffleExchangeExec(HashPartitioning(Seq(l), 2), localScan(l))),
+ SortExec(
+ Seq(SortOrder(r, Ascending)),
+ global = false,
+ ShuffleExchangeExec(HashPartitioning(Seq(r), 2), localScan(r))),
+ skew
+ )
+ smj.setLogicalLink(logical)
+ smj
+ }
+
+ private def withOptimization(f: => Unit): Unit = {
+ withSQLConf(
+ optimizeKey -> "true",
+ GlutenConfig.COLUMNAR_FORCE_SHUFFLED_HASH_JOIN_ENABLED.key -> "false")(f)
+ }
+
+ private def convert(smj: SortMergeJoinExec):
SortMergeJoinExecTransformerBase =
+ new VeloxSparkPlanExecApi().genSortMergeJoinExecTransformer(smj)
+
+ private def assertOriginalLayout(
+ result: SortMergeJoinExecTransformerBase,
+ smj: SortMergeJoinExec): Unit = {
+ assert(result.left eq smj.left)
+ assert(result.right eq smj.right)
+ assert(result.leftKeys == smj.leftKeys)
+ assert(result.rightKeys == smj.rightKeys)
+ assert(result.joinType == smj.joinType)
+ assert(result.condition == smj.condition)
+ assert(result.output == smj.output)
+ assert(result.requiredChildOrdering == smj.requiredChildOrdering)
+ assert(result.outputPartitioning == smj.outputPartitioning)
+ assert(SortOrder.orderingSatisfies(result.outputOrdering,
smj.outputOrdering))
+ }
+
+ test("merge join streamed side optimization is disabled by default") {
+ assert(!VeloxConfig.get.optimizeSortMergeJoinStreamedSide)
+ val smj = mergeJoin()
+ assert(convert(smj).streamedPlan eq smj.left)
+ }
+
+ test("swap native inputs while preserving the Spark plan layout") {
+ withOptimization {
+ val smj = mergeJoin()
+ val result = convert(smj)
+ assertOriginalLayout(result, smj)
+ assert(result.streamedPlan eq smj.right)
+ assert(result.bufferedPlan eq smj.left)
+ assert(result.streamedKeys == smj.rightKeys)
+ assert(result.bufferedKeys == smj.leftKeys)
+ val copied = result.withNewChildren(result.children)
+ .asInstanceOf[SortMergeJoinExecTransformerBase]
+ assert(copied.streamedPlan eq smj.right)
+ }
+ }
+
+ test("swap inner-like equijoins but preserve joins without equality keys") {
+ withOptimization {
+ val smj = mergeJoin(joinType = Cross)
+ assertOriginalLayout(convert(smj), smj)
+ assert(convert(smj).streamedPlan eq smj.right)
+ val withoutKeys = smj.copy(leftKeys = Nil, rightKeys = Nil)
+ withoutKeys.setLogicalLink(smj.logicalLink.get)
+ assert(convert(withoutKeys).streamedPlan eq smj.left)
+ }
+ }
+
+ test("preserve a larger left input and ties without row counts") {
+ withOptimization {
+ Seq(mergeJoin(160, 16), mergeJoin(16, 16)).foreach {
+ smj => assert(convert(smj).streamedPlan eq smj.left)
+ }
+ }
+ }
+
+ test("reuse hash join row count tie breaking") {
+ withOptimization {
+ val smj = mergeJoin(160, 160, leftRows = Some(BigInt(2)), rightRows =
Some(BigInt(20)))
+ assert(convert(smj).streamedPlan eq smj.right)
+ }
+ }
+
+ test("preserve joins with missing or unknown statistics") {
+ withOptimization {
+ val noLink = mergeJoin()
+ noLink.unsetTagValue(SparkPlan.LOGICAL_PLAN_TAG)
+ val unknown = spark.sessionState.conf.defaultSizeInBytes
+ Seq(noLink, mergeJoin(unknown, 160), mergeJoin(16, unknown),
mergeJoin(-1, 160))
+ .foreach(smj => assert(convert(smj).streamedPlan eq smj.left))
+ }
+ }
+
+ Seq(LeftOuter, RightOuter, FullOuter).foreach {
+ joinType =>
+ test(s"swap native $joinType inputs while preserving Spark output
properties") {
+ withOptimization {
+ val smj = mergeJoin(joinType = joinType)
+ val result = convert(smj)
+ assertOriginalLayout(result, smj)
+ assert(result.output.map(_.nullable) == smj.output.map(_.nullable))
+ assert(result.streamedPlan eq smj.right)
+ assert(result.bufferedPlan eq smj.left)
+ val largerLeft = mergeJoin(160, 16, joinType = joinType)
+ assert(convert(largerLeft).streamedPlan eq largerLeft.left)
+ }
+ }
+ }
+
+ test("preserve semi, anti and existence join orientations") {
+ withOptimization {
+ Seq(LeftSemi, LeftAnti, ExistenceJoin(AttributeReference("exists",
BooleanType)())).foreach {
+ joinType =>
+ val smj = mergeJoin(joinType = joinType)
+ assert(convert(smj).streamedPlan eq smj.left)
+ }
+ }
+ }
+
+ test("preserve skew joins") {
+ withOptimization {
+ val smj = mergeJoin(skew = true)
+ assert(convert(smj).streamedPlan eq smj.left)
+ }
+ }
+
+ test("preserve the forced shuffled hash join path") {
+ withOptimization {
+ withSQLConf(GlutenConfig.COLUMNAR_FORCE_SHUFFLED_HASH_JOIN_ENABLED.key
-> "true") {
+ val smj = mergeJoin()
+ assert(convert(smj).streamedPlan eq smj.left)
+ }
+ }
+ }
+}
diff --git a/docs/backends/velox/velox-configuration.md
b/docs/backends/velox/velox-configuration.md
index c721ea9ccb..0e069e7a38 100644
--- a/docs/backends/velox/velox-configuration.md
+++ b/docs/backends/velox/velox-configuration.md
@@ -84,6 +84,7 @@ Type: ⚓ Static - can only be set before the Spark application
starts; 🔄 Dyn
| spark.gluten.sql.columnar.backend.velox.scan.bloomFilterPushdown.enabled
| ⚓ | false | Whether to push Bloom filters into Velox
scans.
[...]
| spark.gluten.sql.columnar.backend.velox.scanMapKeyPruningEnabled
| 🔄 | false | When true, a map column read by a native
Parquet scan is declared to Velox with only the constant keys the query looks
up (m['k'], element_at(m, 'k'), null checks), so the reader skips the other
entries. Applies when every use of the map sits in the filters and projections
directly above the scan and the map is dropped before any other operator sees
it; otherwise the map is read [...]
| spark.gluten.sql.columnar.backend.velox.showTaskMetricsWhenFinished
| 🔄 | false | Show velox full task metrics when finished.
[...]
+| spark.gluten.sql.columnar.backend.velox.sortMergeJoin.optimizeStreamedSide
| 🔄 | false | Use input size statistics to put the larger
input on the streamed left side of native inner and outer sort merge joins.
Skew joins and joins without known input sizes keep their original orientation.
Velox can buffer matching groups from both sides.
[...]
| spark.gluten.sql.columnar.backend.velox.spillFileSystem
| 🔄 | local | The filesystem used to store spill data. local:
The local file system. heap-over-local: Write file to JVM heap if having extra
heap space. Otherwise write to local file system.
[...]
| spark.gluten.sql.columnar.backend.velox.spillNumMaxMergeFiles
| 🔄 | 0 | The max number of files to merge at a time when
merging sorted files into a single ordered stream. 0 means unlimited.
[...]
| spark.gluten.sql.columnar.backend.velox.spillStrategy
| 🔄 | auto | none: Disable spill on Velox backend; auto: Let
Spark memory manager manage Velox's spilling
[...]
diff --git
a/gluten-substrait/src/main/scala/org/apache/gluten/backendsapi/SparkPlanExecApi.scala
b/gluten-substrait/src/main/scala/org/apache/gluten/backendsapi/SparkPlanExecApi.scala
index 110ba9f78a..b25f2f2e87 100644
---
a/gluten-substrait/src/main/scala/org/apache/gluten/backendsapi/SparkPlanExecApi.scala
+++
b/gluten-substrait/src/main/scala/org/apache/gluten/backendsapi/SparkPlanExecApi.scala
@@ -39,7 +39,7 @@ import
org.apache.spark.sql.catalyst.plans.physical.{BroadcastMode, Partitioning
import org.apache.spark.sql.execution._
import org.apache.spark.sql.execution.datasources.FileFormat
import org.apache.spark.sql.execution.exchange.ShuffleExchangeExec
-import org.apache.spark.sql.execution.joins.BuildSideRelation
+import org.apache.spark.sql.execution.joins.{BuildSideRelation,
SortMergeJoinExec}
import org.apache.spark.sql.execution.metric.SQLMetric
import org.apache.spark.sql.execution.python.ArrowEvalPythonExec
import org.apache.spark.sql.execution.window._
@@ -150,6 +150,17 @@ trait SparkPlanExecApi {
isSkewJoin: Boolean = false,
projectList: Seq[NamedExpression] = null):
SortMergeJoinExecTransformerBase
+ /** Convert the original merge join, including its logical statistics. */
+ def genSortMergeJoinExecTransformer(plan: SortMergeJoinExec):
SortMergeJoinExecTransformerBase =
+ genSortMergeJoinExecTransformer(
+ plan.leftKeys,
+ plan.rightKeys,
+ plan.joinType,
+ plan.condition,
+ plan.left,
+ plan.right,
+ plan.isSkewJoin)
+
/** Generate CartesianProductExecTransformer. */
def genCartesianProductExecTransformer(
left: SparkPlan,
diff --git
a/gluten-substrait/src/main/scala/org/apache/gluten/execution/SortMergeJoinExecTransformer.scala
b/gluten-substrait/src/main/scala/org/apache/gluten/execution/SortMergeJoinExecTransformer.scala
index bc6a1d3e7b..0640155f98 100644
---
a/gluten-substrait/src/main/scala/org/apache/gluten/execution/SortMergeJoinExecTransformer.scala
+++
b/gluten-substrait/src/main/scala/org/apache/gluten/execution/SortMergeJoinExecTransformer.scala
@@ -51,8 +51,11 @@ abstract class SortMergeJoinExecTransformerBase(
override def metricsUpdater(): MetricsUpdater =
BackendsApiManager.getMetricsApiInstance.genSortMergeJoinTransformerMetricsUpdater(metrics)
- val (bufferedKeys, streamedKeys, bufferedPlan, streamedPlan) =
- (rightKeys, leftKeys, right, left)
+ protected def needSwitchChildren: Boolean = false
+
+ lazy val (bufferedKeys, streamedKeys, bufferedPlan, streamedPlan) =
+ if (needSwitchChildren) (leftKeys, rightKeys, left, right)
+ else (rightKeys, leftKeys, right, left)
override def verboseStringWithOperatorId(): String = {
val joinCondStr = if (condition.isDefined) {
@@ -139,15 +142,17 @@ abstract class SortMergeJoinExecTransformerBase(
}
// Direct output order of substrait join operation
- protected val substraitJoinType = joinType match {
+ protected lazy val substraitJoinType = joinType match {
case _: InnerLike =>
JoinRel.JoinType.JOIN_TYPE_INNER
case FullOuter =>
JoinRel.JoinType.JOIN_TYPE_OUTER
case LeftOuter =>
- JoinRel.JoinType.JOIN_TYPE_LEFT
+ if (needSwitchChildren) JoinRel.JoinType.JOIN_TYPE_RIGHT
+ else JoinRel.JoinType.JOIN_TYPE_LEFT
case RightOuter =>
- JoinRel.JoinType.JOIN_TYPE_RIGHT
+ if (needSwitchChildren) JoinRel.JoinType.JOIN_TYPE_LEFT
+ else JoinRel.JoinType.JOIN_TYPE_RIGHT
case LeftSemi =>
JoinRel.JoinType.JOIN_TYPE_LEFT_SEMI
case LeftAnti =>
@@ -170,7 +175,7 @@ abstract class SortMergeJoinExecTransformerBase(
bufferedKeys,
condition,
substraitJoinType,
- false,
+ needSwitchChildren,
joinType,
genJoinParameters(),
null,
@@ -198,10 +203,10 @@ abstract class SortMergeJoinExecTransformerBase(
val operatorId = context.nextOperatorId(this.nodeName)
val joinParams = new JoinParams
- if (JoinUtils.preProjectionNeeded(leftKeys)) {
+ if (JoinUtils.preProjectionNeeded(streamedKeys)) {
joinParams.streamPreProjectionNeeded = true
}
- if (JoinUtils.preProjectionNeeded(rightKeys)) {
+ if (JoinUtils.preProjectionNeeded(bufferedKeys)) {
joinParams.buildPreProjectionNeeded = true
}
@@ -210,7 +215,7 @@ abstract class SortMergeJoinExecTransformerBase(
bufferedKeys,
condition,
substraitJoinType,
- false,
+ needSwitchChildren,
joinType,
genJoinParameters(),
inputStreamedRelNode,
@@ -235,7 +240,8 @@ case class SortMergeJoinExecTransformer(
left: SparkPlan,
right: SparkPlan,
isSkewJoin: Boolean = false,
- projectList: Seq[NamedExpression] = null)
+ projectList: Seq[NamedExpression] = null,
+ switchChildren: Boolean = false)
extends SortMergeJoinExecTransformerBase(
leftKeys,
rightKeys,
@@ -246,6 +252,10 @@ case class SortMergeJoinExecTransformer(
isSkewJoin,
projectList) {
+ override protected def needSwitchChildren: Boolean = switchChildren
+
+ override def stringArgs: Iterator[scala.Any] =
super.stringArgs.toSeq.dropRight(1).iterator
+
override protected def doValidateInternal(): ValidationResult = {
super.doValidateInternal()
}
diff --git
a/gluten-substrait/src/main/scala/org/apache/gluten/execution/WholeStageTransformer.scala
b/gluten-substrait/src/main/scala/org/apache/gluten/execution/WholeStageTransformer.scala
index d7a3999217..5abbba512c 100644
---
a/gluten-substrait/src/main/scala/org/apache/gluten/execution/WholeStageTransformer.scala
+++
b/gluten-substrait/src/main/scala/org/apache/gluten/execution/WholeStageTransformer.scala
@@ -304,6 +304,8 @@ case class WholeStageTransformer(child: SparkPlan,
materializeInput: Boolean = f
Seq(transformer)
case shj: HashJoinLikeExecTransformer =>
collectLeafTransformers(shj.streamedPlan) ++
collectLeafTransformers(shj.buildPlan)
+ case smj: SortMergeJoinExecTransformerBase =>
+ collectLeafTransformers(smj.streamedPlan) ++
collectLeafTransformers(smj.bufferedPlan)
case t: TransformSupport =>
t.children.flatMap(collectLeafTransformers)
case _ =>
diff --git
a/gluten-substrait/src/main/scala/org/apache/gluten/extension/columnar/offload/OffloadSingleNodeRules.scala
b/gluten-substrait/src/main/scala/org/apache/gluten/extension/columnar/offload/OffloadSingleNodeRules.scala
index 140e047704..e87e3a8c49 100644
---
a/gluten-substrait/src/main/scala/org/apache/gluten/extension/columnar/offload/OffloadSingleNodeRules.scala
+++
b/gluten-substrait/src/main/scala/org/apache/gluten/extension/columnar/offload/OffloadSingleNodeRules.scala
@@ -75,17 +75,7 @@ case class OffloadJoin() extends OffloadSingleNode with
LogLevelUtil {
right,
plan.isSkewJoin)
case plan: SortMergeJoinExec =>
- val left = plan.left
- val right = plan.right
- BackendsApiManager.getSparkPlanExecApiInstance
- .genSortMergeJoinExecTransformer(
- plan.leftKeys,
- plan.rightKeys,
- plan.joinType,
- plan.condition,
- left,
- right,
- plan.isSkewJoin)
+
BackendsApiManager.getSparkPlanExecApiInstance.genSortMergeJoinExecTransformer(plan)
case plan: BroadcastHashJoinExec =>
val left = plan.left
val right = plan.right
diff --git
a/gluten-ut/test/src/test/scala/org/apache/spark/sql/execution/GlutenSortMergeJoinStreamedSideSuite.scala
b/gluten-ut/test/src/test/scala/org/apache/spark/sql/execution/GlutenSortMergeJoinStreamedSideSuite.scala
new file mode 100644
index 0000000000..57edf7feab
--- /dev/null
+++
b/gluten-ut/test/src/test/scala/org/apache/spark/sql/execution/GlutenSortMergeJoinStreamedSideSuite.scala
@@ -0,0 +1,194 @@
+/*
+ * 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.execution
+
+import org.apache.gluten.config.GlutenConfig
+import org.apache.gluten.execution.{ShuffledHashJoinExecTransformerBase,
SortMergeJoinExecTransformer}
+import org.apache.gluten.utils.BackendTestUtils
+
+import org.apache.spark.SparkConf
+import org.apache.spark.sql.{GlutenQueryTest, Row}
+import org.apache.spark.sql.catalyst.plans.{FullOuter, LeftOuter, RightOuter}
+import org.apache.spark.sql.test.SharedSparkSession
+
+class GlutenSortMergeJoinStreamedSideSuite extends GlutenQueryTest with
SharedSparkSession {
+ private val optimizeKey =
+
"spark.gluten.sql.columnar.backend.velox.sortMergeJoin.optimizeStreamedSide"
+
+ override protected def sparkConf: SparkConf = super.sparkConf
+ .set("spark.plugins", "org.apache.gluten.GlutenPlugin")
+ .set("spark.shuffle.manager",
"org.apache.spark.shuffle.sort.ColumnarShuffleManager")
+ .set("spark.memory.offHeap.enabled", "true")
+ .set("spark.memory.offHeap.size", "1g")
+ .set("spark.ui.enabled", "false")
+ .set("spark.sql.adaptive.enabled", "false")
+ .set("spark.sql.autoBroadcastJoinThreshold", "-1")
+ .set("spark.sql.shuffle.partitions", "2")
+ .set(GlutenConfig.COLUMNAR_FORCE_SHUFFLED_HASH_JOIN_ENABLED.key, "false")
+
+ private def withInputs(f: => Unit): Unit = {
+ assume(BackendTestUtils.isVeloxBackendLoaded())
+ withTempPath {
+ path =>
+ withTempView("small_merge_input", "large_merge_input") {
+ val small = new java.io.File(path, "small").getAbsolutePath
+ val large = new java.io.File(path, "large").getAbsolutePath
+ spark.range(4).selectExpr("IF(id = 3, NULL, id) as k", "id as
v").write.parquet(small)
+ spark
+ .range(20)
+ .selectExpr(
+ "CASE WHEN id = 18 THEN NULL WHEN id = 19 THEN 4 ELSE id % 2 END
as k",
+ "id + 10 as v")
+ .write
+ .parquet(large)
+
spark.read.parquet(small).createOrReplaceTempView("small_merge_input")
+
spark.read.parquet(large).createOrReplaceTempView("large_merge_input")
+ f
+ }
+ }
+ }
+
+ private val query =
+ """
+ |SELECT /*+ MERGE(s, l) */ s.k, s.v, l.v
+ |FROM small_merge_input s JOIN large_merge_input l
+ |ON s.k = l.k AND l.v < s.v + 15
+ |ORDER BY l.v
+ |""".stripMargin
+
+ test("native merge join streams the larger input and preserves duplicate-key
results") {
+ withInputs {
+ Seq(false, true).foreach {
+ enabled =>
+ withSQLConf(optimizeKey -> enabled.toString) {
+ val df = spark.sql(query)
+ val plan = df.queryExecution.executedPlan
+ val joins = plan.collect { case smj: SortMergeJoinExecTransformer
=> smj }
+ assert(joins.size == 1, plan.treeString)
+ val smj = joins.head
+ val expectedLeft = if (enabled) "l" else "s"
+ val expectedRight = if (enabled) "s" else "l"
+ assert(smj.streamedKeys.head.references.head.qualifier.last ==
expectedLeft)
+ assert(smj.bufferedKeys.head.references.head.qualifier.last ==
expectedRight)
+ checkAnswer(df, (10L until 16L).map(v => Row(v % 2, v % 2, v)))
+ }
+ }
+ }
+ }
+
+ Seq(
+ ("LEFT OUTER", LeftOuter),
+ ("RIGHT OUTER", RightOuter),
+ ("FULL OUTER", FullOuter)).foreach {
+ case (sqlType, originalType) =>
+ test(s"native $sqlType merge join preserves unmatched rows and nulls
when swapped") {
+ withInputs {
+ val matched = (10L until 16L).map(v => Row(v % 2, v % 2, v % 2, v))
+ val unmatchedLeft = Seq(Row(2L, 2L, null, null), Row(null, 3L, null,
null))
+ val unmatchedRight = (16L until 30L).map {
+ v =>
+ val key: java.lang.Long = if (v == 28) null else if (v == 29) 4L
else v % 2
+ Row(null, null, key, v)
+ }
+ val expected = (matched ++
+ (if (originalType != RightOuter) unmatchedLeft else Nil) ++
+ (if (originalType != LeftOuter) unmatchedRight else Nil)).sortBy {
+ row =>
+ (
+ if (row.isNullAt(1)) Long.MinValue else row.getLong(1),
+ if (row.isNullAt(3)) Long.MinValue else row.getLong(3))
+ }
+ Seq(false, true).foreach {
+ enabled =>
+ withSQLConf(optimizeKey -> enabled.toString) {
+ val df = spark.sql(s"""
+ |SELECT /*+ MERGE(s, l) */ s.k, s.v,
l.k, l.v
+ |FROM small_merge_input s $sqlType JOIN
large_merge_input l
+ |ON s.k = l.k AND l.v < s.v + 15
+ |ORDER BY s.v, l.v
+ |""".stripMargin)
+ val plan = df.queryExecution.executedPlan
+ val joins = plan.collect { case smj:
SortMergeJoinExecTransformer => smj }
+ assert(joins.size == 1, plan.treeString)
+ val smj = joins.head
+ assert(smj.joinType == originalType)
+ assert(smj.streamedKeys.head.references.head.qualifier.last ==
+ (if (enabled) "l" else "s"))
+ assert(smj.bufferedKeys.head.references.head.qualifier.last ==
+ (if (enabled) "s" else "l"))
+ checkAnswer(df, expected)
+ }
+ }
+ }
+ }
+ }
+
+ test("native merge join swaps computed keys with the correct input metrics")
{
+ withInputs {
+ withSQLConf(optimizeKey -> "true") {
+ // Avoid the range exchange's sampling execution when asserting
metrics.
+ val df = spark.sql(query
+ .replace("s.k = l.k", "s.k + 1 = l.k + 1")
+ .replace("ORDER BY l.v", ""))
+ val joins = df.queryExecution.executedPlan.collect {
+ case smj: SortMergeJoinExecTransformer => smj
+ }
+ assert(joins.size == 1)
+ assert(joins.head.switchChildren)
+ // Collect once so the metrics describe one execution.
+ assert(df.collect().toSeq.sortBy(_.getLong(2)) ==
+ (10L until 16L).map(v => Row(v % 2, v % 2, v)))
+ assert(joins.head.metrics("numOutputRows").value == 6)
+ }
+ }
+ }
+
+ test("native merge join swaps scan inputs without an exchange") {
+ assume(BackendTestUtils.isVeloxBackendLoaded())
+ withSQLConf(optimizeKey -> "true") {
+ withTable("small_merge_bucketed", "large_merge_bucketed") {
+ spark.range(2).selectExpr("id as k", "id as v")
+ .write.bucketBy(1,
"k").sortBy("k").saveAsTable("small_merge_bucketed")
+ spark.range(12).selectExpr("id % 2 as k", "id + 10 as v")
+ .write.bucketBy(1,
"k").sortBy("k").saveAsTable("large_merge_bucketed")
+ val df = spark.sql(query
+ .replace("small_merge_input", "small_merge_bucketed")
+ .replace("large_merge_input", "large_merge_bucketed"))
+ val plan = df.queryExecution.executedPlan
+ val joins = plan.collect { case smj: SortMergeJoinExecTransformer =>
smj }
+ assert(joins.size == 1, plan.treeString)
+ assert(joins.head.columnarInputRDDs.isEmpty, plan.treeString)
+ assert(joins.head.streamedKeys.head.references.head.qualifier.last ==
"l")
+ checkAnswer(df, (10L until 16L).map(v => Row(v % 2, v % 2, v)))
+ }
+ }
+ }
+
+ test("streamed side optimization preserves the forced native hash join
path") {
+ withInputs {
+ withSQLConf(
+ optimizeKey -> "true",
+ GlutenConfig.COLUMNAR_FORCE_SHUFFLED_HASH_JOIN_ENABLED.key -> "true") {
+ val df = spark.sql(query)
+ val plan = df.queryExecution.executedPlan
+ assert(plan.collect { case _: ShuffledHashJoinExecTransformerBase => 1
}.size == 1)
+ assert(plan.collect { case _: SortMergeJoinExecTransformer => 1
}.isEmpty)
+ checkAnswer(df, (10L until 16L).map(v => Row(v % 2, v % 2, v)))
+ }
+ }
+ }
+}
---------------------------------------------------------------------
To unsubscribe, e-mail: [email protected]
For additional commands, e-mail: [email protected]