Skip to content

Commit 6f7b639

Browse files
committed
fix: restore the sort a kept sort-merge join needs after a hash join rewrite
When RewriteJoin keeps a sort-merge join above a join it has already turned into a hash join on the same key, the kept join reads unsorted input. EnsureRequirements placed no sort between the two because the inner sort-merge join's ordering satisfied the outer one, and the rewrite then removed the inner join's sorts. The native sort-merge join does not check its input ordering, so matches were silently dropped. After the rewrite, add a local SortExec wherever a child no longer satisfies its parent's required ordering, the same check EnsureRequirements makes. This covers joins kept by the build-size limit and the LeftSemi and ExistenceJoin joins the rewrite already keeps, which lost rows the same way.
1 parent 9f7a615 commit 6f7b639

3 files changed

Lines changed: 134 additions & 4 deletions

File tree

‎spark/src/main/scala/org/apache/comet/rules/CometExecRule.scala‎

Lines changed: 5 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -937,10 +937,13 @@ case class CometExecRule(session: SparkSession)
937937
} else {
938938
val normalizedPlan = normalizePlan(plan)
939939

940+
// The rewrite removes the sorts of each join it converts, so put back any sort a kept
941+
// operator above still needs. This runs before transform(), which converts the sorts it
942+
// adds like any other SortExec.
940943
val planWithJoinRewritten = if (CometConf.COMET_FORCE_SHJ.get()) {
941-
normalizedPlan.transformUp { case p =>
944+
RewriteJoin.restoreRequiredOrdering(normalizedPlan.transformUp { case p =>
942945
RewriteJoin.rewrite(p, conf)
943-
}
946+
})
944947
} else {
945948
normalizedPlan
946949
}

‎spark/src/main/scala/org/apache/comet/rules/RewriteJoin.scala‎

Lines changed: 17 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -19,6 +19,7 @@
1919

2020
package org.apache.comet.rules
2121

22+
import org.apache.spark.sql.catalyst.expressions.SortOrder
2223
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide, JoinSelectionHelper}
2324
import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, LeftSemi}
2425
import org.apache.spark.sql.catalyst.plans.logical.Join
@@ -66,6 +67,22 @@ object RewriteJoin extends JoinSelectionHelper {
6667
case _ => plan
6768
}
6869

70+
/**
71+
* Adds a local sort under any operator whose child no longer has the ordering the operator
72+
* requires, using the same check as EnsureRequirements. EnsureRequirements puts no sort above a
73+
* sort-merge join whose output ordering already satisfies its parent, so when rewrite turns
74+
* that join into a hash join and removes its sorts, a kept parent such as another sort-merge
75+
* join on the same key would read unsorted input. Plans that already satisfy their required
76+
* orderings are returned unchanged.
77+
*/
78+
def restoreRequiredOrdering(plan: SparkPlan): SparkPlan = plan.transformUp { case p =>
79+
p.withNewChildren(p.children.zip(p.requiredChildOrdering).map {
80+
case (child, required) if !SortOrder.orderingSatisfies(child.outputOrdering, required) =>
81+
SortExec(required, global = false, child = child)
82+
case (child, _) => child
83+
})
84+
}
85+
6986
/**
7087
* The largest build side the rewrite converts, or None when the limit is switched off. Unset
7188
* means Spark's own rule for choosing a shuffled hash join by size: the broadcast threshold

‎spark/src/test/scala/org/apache/comet/exec/CometJoinSuite.scala‎

Lines changed: 112 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -34,8 +34,8 @@ import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight}
3434
import org.apache.spark.sql.catalyst.plans.Inner
3535
import org.apache.spark.sql.catalyst.plans.logical.Join
3636
import org.apache.spark.sql.comet.{CometBroadcastExchangeExec, CometBroadcastHashJoinExec, CometBroadcastNestedLoopJoinExec, CometFilterExec, CometHashJoinExec, CometNativeScanExec, CometSortExec, CometSortMergeJoinExec, CometUnionExec}
37-
import org.apache.spark.sql.execution.{LocalTableScanExec, SparkPlan}
38-
import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanExec, AQEShuffleReadExec}
37+
import org.apache.spark.sql.execution.{ColumnarToRowTransition, InputAdapter, LocalTableScanExec, SortExec, SparkPlan, WholeStageCodegenExec}
38+
import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanExec, AQEShuffleReadExec, QueryStageExec}
3939
import org.apache.spark.sql.execution.datasources.SchemaColumnConvertNotSupportedException
4040
import org.apache.spark.sql.execution.exchange.{ReusedExchangeExec, ShuffleExchangeLike}
4141
import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec}
@@ -1087,6 +1087,116 @@ class CometJoinSuite extends CometTestBase {
10871087
}
10881088
}
10891089

1090+
// Both joins are on the same key, so EnsureRequirements puts no sort between them: the inner
1091+
// sort-merge join's output ordering satisfies the outer one. When the inner join is rewritten
1092+
// to a hash join and the outer one is kept, the outer join needs that ordering restored.
1093+
private def withChainedJoinTables(midRows: Int, midKeys: Int)(f: => Unit): Unit = {
1094+
withParquetTable((0 until 10000).map(i => (i % 100, i)), "big") {
1095+
withParquetTable((0 until 10).map(i => (i * 10, i)), "small") {
1096+
withParquetTable((0 until midRows).map(i => (i % midKeys, i)), "mid") {
1097+
f
1098+
}
1099+
}
1100+
}
1101+
}
1102+
1103+
// Whether a hash join is reachable without leaving the stage.
1104+
private def reachesHashJoinInStage(plan: SparkPlan): Boolean = plan match {
1105+
case _: CometHashJoinExec => true
1106+
case _: ShuffleExchangeLike | _: QueryStageExec => false
1107+
case p => p.children.exists(reachesHashJoinInStage)
1108+
}
1109+
1110+
// Whether a sort-merge join input is a sort over a hash join in the same stage. A Spark
1111+
// sort-merge join reads the sort through codegen wrappers and a columnar to row transition.
1112+
private def isSortOverHashJoin(input: SparkPlan): Boolean = input match {
1113+
case s: CometSortExec => reachesHashJoinInStage(s.child)
1114+
case s: SortExec => reachesHashJoinInStage(s.child)
1115+
case t: ColumnarToRowTransition => isSortOverHashJoin(t.child)
1116+
case w: WholeStageCodegenExec => isSortOverHashJoin(w.child)
1117+
case a: InputAdapter => isSortOverHashJoin(a.child)
1118+
case _ => false
1119+
}
1120+
1121+
// Checks the answer first, then that a kept sort-merge join reads the rewritten hash join
1122+
// through a sort.
1123+
private def checkSortRestoredOverHashJoin(query: String): Unit = {
1124+
val (_, cometPlan) = checkSparkAnswer(query)
1125+
val inputs = collect(cometPlan) {
1126+
case j: CometSortMergeJoinExec => j.children
1127+
case j: SortMergeJoinExec => j.children
1128+
}.flatten
1129+
assert(inputs.exists(isSortOverHashJoin), cometPlan)
1130+
}
1131+
1132+
private val chainedJoinQuery = "SELECT big._1, big._2, small._2, mid._2 FROM big " +
1133+
"JOIN small ON big._1 = small._1 JOIN mid ON big._1 = mid._1"
1134+
1135+
test("forceShuffledHashJoin restores ordering for a kept SortMergeJoin, AQE=false") {
1136+
// The default limit, 3000 bytes times two partitions, falls between the two build sides.
1137+
withSQLConf(
1138+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
1139+
CometConf.COMET_FORCE_SHJ.key -> "true",
1140+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
1141+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "3000") {
1142+
withChainedJoinTables(midRows = 3000, midKeys = 100) {
1143+
checkSortRestoredOverHashJoin(chainedJoinQuery)
1144+
}
1145+
}
1146+
}
1147+
1148+
test("forceShuffledHashJoin restores ordering for a kept SortMergeJoin, AQE=true") {
1149+
// Under AQE the decision uses the materialized shuffle sizes, so mid is made large enough
1150+
// to stay over the limit while small stays under it.
1151+
withSQLConf(
1152+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "true",
1153+
SQLConf.ADAPTIVE_AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
1154+
CometConf.COMET_FORCE_SHJ.key -> "true",
1155+
CometConf.COMET_FORCE_SHJ_MAX_BUILD_SIZE.key -> "1000000",
1156+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
1157+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "3000") {
1158+
withChainedJoinTables(midRows = 300000, midKeys = 30000) {
1159+
checkSortRestoredOverHashJoin(chainedJoinQuery)
1160+
}
1161+
}
1162+
}
1163+
1164+
// The rewrite never converts a LeftSemi or ExistenceJoin that builds on the right, whatever
1165+
// the build size, so these joins are kept above the rewritten inner join with no size limit.
1166+
// Each predicate also refers to small, so neither the filter nor the semi join is pushed below
1167+
// the inner join.
1168+
for (adaptive <- Seq(false, true)) {
1169+
def withKeptSemiJoinConf(f: => Unit): Unit = withSQLConf(
1170+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> adaptive.toString,
1171+
SQLConf.ADAPTIVE_AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
1172+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
1173+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
1174+
CometConf.COMET_FORCE_SHJ.key -> "true",
1175+
CometConf.COMET_FORCE_SHJ_MAX_BUILD_SIZE.key -> "-1") {
1176+
withChainedJoinTables(midRows = 3000, midKeys = 100)(f)
1177+
}
1178+
1179+
test(s"forceShuffledHashJoin restores ordering for a kept ExistenceJoin, AQE=$adaptive") {
1180+
withKeptSemiJoinConf {
1181+
checkSortRestoredOverHashJoin(
1182+
"SELECT big._1, big._2, small._2 FROM big JOIN small ON big._1 = small._1 " +
1183+
"WHERE small._2 < 0 OR EXISTS (SELECT 1 FROM mid WHERE mid._1 = big._1)")
1184+
}
1185+
}
1186+
1187+
test(s"forceShuffledHashJoin restores ordering for a kept LeftSemi join, AQE=$adaptive") {
1188+
withSQLConf(
1189+
SQLConf.OPTIMIZER_EXCLUDED_RULES.key ->
1190+
"org.apache.spark.sql.catalyst.optimizer.PushLeftSemiLeftAntiThroughJoin") {
1191+
withKeptSemiJoinConf {
1192+
checkSortRestoredOverHashJoin(
1193+
"SELECT big._1, big._2, small._2 FROM big JOIN small ON big._1 = small._1 " +
1194+
"WHERE EXISTS (SELECT 1 FROM mid WHERE mid._1 = big._1 AND mid._2 > small._2)")
1195+
}
1196+
}
1197+
}
1198+
}
1199+
10901200
test("BroadcastHashJoin with LeftAnti and NOT IN subquery (null-aware)") {
10911201
withSQLConf(
10921202
SQLConf.PREFER_SORTMERGEJOIN.key -> "false",

0 commit comments

Comments
 (0)