Skip to content

Commit cb3e977

Browse files
authored
perf: Add experimental feature to replace SortMergeJoin with ShuffledHashJoin (apache#1007)
* experiment * fix and add credit * disable by default and make internal * remove sort * minor optimization * minor optimization * remove unused import * disable feature by default * fix dockerfile * Add section to tuning guide * update benchmarking guide * Revert "chore: Reserve memory for native shuffle writer per partition (apache#988)" This reverts commit e146cfa. * mark feature as experimental and explain risks * workaround for TPC-DS q14 hanging on a RightSemi join * revert a change * remove debug logging: * format * add link to tuning guide
1 parent 3df9d5c commit cb3e977

7 files changed

Lines changed: 110 additions & 2 deletions

File tree

‎NOTICE.txt‎

Lines changed: 6 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -5,4 +5,9 @@ This product includes software developed at
55
The Apache Software Foundation (http://www.apache.org/).
66

77
This product includes software from the twox-hash project (MIT License)
8-
https://github.com/shepmaster/twox-hash
8+
https://github.com/shepmaster/twox-hash
9+
10+
This product includes software developed at
11+
Apache Gluten (https://github.com/apache/incubator-gluten/)
12+
Specifically:
13+
- Optimizer rule to replace SortMergeJoin with ShuffleHashJoin

‎common/src/main/scala/org/apache/comet/CometConf.scala‎

Lines changed: 10 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -45,6 +45,9 @@ import org.apache.comet.shims.ShimCometConf
4545
*/
4646
object CometConf extends ShimCometConf {
4747

48+
private val TUNING_GUIDE = "For more information, refer to the Comet Tuning " +
49+
"Guide (https://datafusion.apache.org/comet/user-guide/tuning.html)"
50+
4851
/** List of all configs that is used for generating documentation */
4952
val allConfs = new ListBuffer[ConfigEntry[_]]
5053

@@ -263,6 +266,13 @@ object CometConf extends ShimCometConf {
263266
.booleanConf
264267
.createWithDefault(false)
265268

269+
val COMET_REPLACE_SMJ: ConfigEntry[Boolean] =
270+
conf(s"$COMET_EXEC_CONFIG_PREFIX.replaceSortMergeJoin")
271+
.doc("Experimental feature to force Spark to replace SortMergeJoin with ShuffledHashJoin " +
272+
s"for improved performance. This feature is not stable yet. $TUNING_GUIDE.")
273+
.booleanConf
274+
.createWithDefault(false)
275+
266276
val COMET_EXEC_SHUFFLE_CODEC: ConfigEntry[String] = conf(
267277
s"$COMET_EXEC_CONFIG_PREFIX.shuffle.codec")
268278
.doc(

‎docs/source/contributor-guide/benchmarking.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -64,6 +64,7 @@ $SPARK_HOME/bin/spark-submit \
6464
--conf spark.executor.extraClassPath=$COMET_JAR \
6565
--conf spark.plugins=org.apache.spark.CometPlugin \
6666
--conf spark.comet.cast.allowIncompatible=true \
67+
--conf spark.comet.exec.replaceSortMergeJoin=true \
6768
--conf spark.comet.exec.shuffle.enabled=true \
6869
--conf spark.shuffle.manager=org.apache.spark.sql.comet.execution.shuffle.CometShuffleManager \
6970
tpcbench.py \

‎docs/source/user-guide/configs.md‎

Lines changed: 1 addition & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -50,6 +50,7 @@ Comet provides the following configuration settings.
5050
| spark.comet.exec.localLimit.enabled | Whether to enable localLimit by default. | true |
5151
| spark.comet.exec.memoryFraction | The fraction of memory from Comet memory overhead that the native memory manager can use for execution. The purpose of this config is to set aside memory for untracked data structures, as well as imprecise size estimation during memory acquisition. Default value is 0.7. | 0.7 |
5252
| spark.comet.exec.project.enabled | Whether to enable project by default. | true |
53+
| spark.comet.exec.replaceSortMergeJoin | Experimental feature to force Spark to replace SortMergeJoin with ShuffledHashJoin for improved performance. This feature is not stable yet. For more information, refer to the Comet Tuning Guide (https://datafusion.apache.org/comet/user-guide/tuning.html). | false |
5354
| spark.comet.exec.shuffle.codec | The codec of Comet native shuffle used to compress shuffle data. Only zstd is supported. | zstd |
5455
| spark.comet.exec.shuffle.enabled | Whether to enable Comet native shuffle. Note that this requires setting 'spark.shuffle.manager' to 'org.apache.spark.sql.comet.execution.shuffle.CometShuffleManager'. 'spark.shuffle.manager' must be set before starting the Spark application and cannot be changed during the application. | true |
5556
| spark.comet.exec.sort.enabled | Whether to enable sort by default. | true |

‎docs/source/user-guide/tuning.md‎

Lines changed: 12 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -78,6 +78,18 @@ Note that there is currently a known issue where this will be inaccurate when us
7878
does not take executor concurrency into account. The tracking issue for this is
7979
https://github.com/apache/datafusion-comet/issues/949.
8080

81+
## Optimizing Joins
82+
83+
Spark often chooses `SortMergeJoin` over `ShuffledHashJoin` for stability reasons. If the build-side of a
84+
`ShuffledHashJoin` is very large then it could lead to OOM in Spark.
85+
86+
Vectorized query engines tend to perform better with `ShuffledHashJoin`, so for best performance it is often preferable
87+
to configure Comet to convert `SortMergeJoin` to `ShuffledHashJoin`. Comet does not yet provide spill-to-disk for
88+
`ShuffledHashJoin` so this could result in OOM. Also, `SortMergeJoin` may still be faster in some cases. It is best
89+
to test with both for your specific workloads.
90+
91+
To configure Comet to convert `SortMergeJoin` to `ShuffledHashJoin`, set `spark.comet.exec.replaceSortMergeJoin=true`.
92+
8193
## Shuffle
8294

8395
Comet provides accelerated shuffle implementations that can be used to improve the performance of your queries.

‎spark/src/main/scala/org/apache/comet/CometSparkSessionExtensions.scala‎

Lines changed: 10 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -55,6 +55,7 @@ import org.apache.comet.CometConf._
5555
import org.apache.comet.CometExplainInfo.getActualPlan
5656
import org.apache.comet.CometSparkSessionExtensions.{createMessage, getCometBroadcastNotEnabledReason, getCometShuffleNotEnabledReason, isANSIEnabled, isCometBroadCastForceEnabled, isCometEnabled, isCometExecEnabled, isCometJVMShuffleMode, isCometNativeShuffleMode, isCometScan, isCometScanEnabled, isCometShuffleEnabled, isSpark34Plus, isSpark40Plus, shouldApplySparkToColumnar, withInfo, withInfos}
5757
import org.apache.comet.parquet.{CometParquetScan, SupportsComet}
58+
import org.apache.comet.rules.RewriteJoin
5859
import org.apache.comet.serde.OperatorOuterClass.Operator
5960
import org.apache.comet.serde.QueryPlanSerde
6061
import org.apache.comet.shims.ShimCometSparkSessionExtensions
@@ -938,7 +939,15 @@ class CometSparkSessionExtensions
938939
plan
939940
}
940941
} else {
941-
var newPlan = transform(normalizePlan(plan))
942+
val normalizedPlan = if (CometConf.COMET_REPLACE_SMJ.get()) {
943+
normalizePlan(plan).transformUp { case p =>
944+
RewriteJoin.rewrite(p)
945+
}
946+
} else {
947+
normalizePlan(plan)
948+
}
949+
950+
var newPlan = transform(normalizedPlan)
942951

943952
// if the plan cannot be run fully natively then explain why (when appropriate
944953
// config is enabled)
Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,70 @@
1+
/*
2+
* Licensed to the Apache Software Foundation (ASF) under one
3+
* or more contributor license agreements. See the NOTICE file
4+
* distributed with this work for additional information
5+
* regarding copyright ownership. The ASF licenses this file
6+
* to you under the Apache License, Version 2.0 (the
7+
* "License"); you may not use this file except in compliance
8+
* with the License. You may obtain a copy of the License at
9+
*
10+
* http://www.apache.org/licenses/LICENSE-2.0
11+
*
12+
* Unless required by applicable law or agreed to in writing,
13+
* software distributed under the License is distributed on an
14+
* "AS IS" BASIS, WITHOUT WARRANTIES OR CONDITIONS OF ANY
15+
* KIND, either express or implied. See the License for the
16+
* specific language governing permissions and limitations
17+
* under the License.
18+
*/
19+
20+
package org.apache.comet.rules
21+
22+
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide, JoinSelectionHelper}
23+
import org.apache.spark.sql.catalyst.plans.{JoinType, LeftSemi}
24+
import org.apache.spark.sql.execution.{SortExec, SparkPlan}
25+
import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec}
26+
27+
/**
28+
* Adapted from equivalent rule in Apache Gluten.
29+
*
30+
* This rule replaces [[SortMergeJoinExec]] with [[ShuffledHashJoinExec]].
31+
*/
32+
object RewriteJoin extends JoinSelectionHelper {
33+
34+
private def getBuildSide(joinType: JoinType): Option[BuildSide] = {
35+
if (canBuildShuffledHashJoinRight(joinType)) {
36+
Some(BuildRight)
37+
} else if (canBuildShuffledHashJoinLeft(joinType)) {
38+
Some(BuildLeft)
39+
} else {
40+
None
41+
}
42+
}
43+
44+
private def removeSort(plan: SparkPlan) = plan match {
45+
case _: SortExec => plan.children.head
46+
case _ => plan
47+
}
48+
49+
def rewrite(plan: SparkPlan): SparkPlan = plan match {
50+
case smj: SortMergeJoinExec =>
51+
getBuildSide(smj.joinType) match {
52+
case Some(BuildRight) if smj.joinType == LeftSemi =>
53+
// TODO this was added as a workaround for TPC-DS q14 hanging and needs
54+
// further investigation
55+
plan
56+
case Some(buildSide) =>
57+
ShuffledHashJoinExec(
58+
smj.leftKeys,
59+
smj.rightKeys,
60+
smj.joinType,
61+
buildSide,
62+
smj.condition,
63+
removeSort(smj.left),
64+
removeSort(smj.right),
65+
smj.isSkewJoin)
66+
case _ => plan
67+
}
68+
case _ => plan
69+
}
70+
}

0 commit comments

Comments
 (0)