sunchao commented on code in PR #6785: URL: https://github.com/apache/datafusion-comet/pull/6785#discussion_r4368087541
########## spark/src/main/scala/org/apache/comet/rules/CometShuffledHashJoinStrategy.scala: ########## @@ -0,0 +1,175 @@ +/* + * 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.comet.rules + +import org.apache.spark.sql.SparkSession +import org.apache.spark.sql.catalyst.expressions.RowOrdering +import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide} +import org.apache.spark.sql.catalyst.planning.ExtractEquiJoinKeys +import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, LeftSemi} +import org.apache.spark.sql.catalyst.plans.logical.{Join, JoinHint, JoinStrategyHint, LogicalPlan} +import org.apache.spark.sql.execution.{SparkPlan, SparkStrategy} +import org.apache.spark.sql.execution.adaptive.{BroadcastQueryStageExec, LogicalQueryStage} +import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec} +import org.apache.spark.sql.internal.SQLConf + +import org.apache.comet.CometConf +import org.apache.comet.CometSparkSessionExtensions.{isCometLoaded, withFallbackReason, withInfo} +import org.apache.comet.shims.ShimJoinSelection + +/** + * Plans a ShuffledHashJoinExec in place of a SortMergeJoinExec, before EnsureRequirements and + * RemoveRedundantSorts, so the sorts above the join survive. Adapted from Apache Gluten. + */ +case class CometShuffledHashJoinStrategy(session: SparkSession) + extends SparkStrategy + with ShimJoinSelection { + + override def apply(plan: LogicalPlan): Seq[SparkPlan] = plan match { + case join: Join if isEnabled(join) => planJoin(join) + case _ => Nil + } + + private def sqlConf: SQLConf = session.sessionState.conf + + // Planner strategies run with Comet off and before CometRule, which applies plan-only mode. + private def isEnabled(join: Join): Boolean = + CometConf.COMET_FORCE_SHJ.get(sqlConf) && + CometConf.COMET_EXEC_ENABLED.get(sqlConf) && + !CometConf.COMET_EXPLAIN_PLAN_ONLY_ENABLED.get(sqlConf) && + !join.isStreaming && + isCometLoaded(sqlConf) + + private def planJoin(join: Join): Seq[SparkPlan] = join match { + case ExtractEquiJoinKeys(joinType, leftKeys, rightKeys, condition, _, left, right, hint) + if !isLeftToSpark(join, hint) && canSortMergeJoin(joinType) && + RowOrdering.isOrderable(leftKeys) && hashJoinSupportedShim(leftKeys, rightKeys) => + buildSide(join) match { + case Some(BuildRight) if joinType == LeftSemi || joinType.isInstanceOf[ExistenceJoin] => + // LeftSemi https://github.com/apache/datafusion-comet/issues/2667 + // ExistenceJoin https://github.com/apache/datafusion-comet/issues/2697 + planBySpark(join) { smj => + withFallbackReason(smj, declineReason(s"BuildRight with $joinType is not supported")) + } + case Some(side) => + buildSideOverLimit(join, side) match { + case Some(reason) => + // Not a fallback: the kept sort-merge join still runs natively. + planBySpark(join)(smj => withInfo(smj, declineReason(reason))) + case None => + Seq( + ShuffledHashJoinExec( Review Comment: [P1] Preserve the requested sort when a multirow native broadcast nested-loop join feeds this forced inner hash join. Spark’s `ShuffledHashJoinExec` advertises the probe’s full ordering, so Spark removes `ORDER BY x`. The native nested-loop producer emits matches grouped by broadcast build row, and `x` decreases in the final result. The base retained the sort because its initially planned sort-merge join advertised ordering on `x % 4`. Keep the nested-loop producer on Spark when its streamed order is required, or retain a real sort above it. Evidence: On Spark 4.1.3, enable native range and `forceShuffledHashJoin`, disable AQE and automatic broadcasts, and use one shuffle partition. Run `SELECT j.x, j.z, b.id AS w FROM (SELECT /*+ BROADCAST(n) */ p.id AS x, n.id AS z FROM range(0,20,1,1) p JOIN range(0,2,1,1) n ON p.id % 2 <= n.id) j JOIN range(0,2,1,1) b ON j.x % 4 = b.id * 2 ORDER BY x`. Spark and the base returned `[0,0,2,2,…,18,18]`. The head returned `[0,2,…,18,0,2,…,18]`. Disabling only `spark.comet.exec.broadcastNestedLoopJoin.enabled` on the head restored the expected order. `SORT BY x` reproduced the same failure. ########## spark/src/main/scala/org/apache/comet/rules/CometShuffledHashJoinStrategy.scala: ########## @@ -0,0 +1,175 @@ +/* + * 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.comet.rules + +import org.apache.spark.sql.SparkSession +import org.apache.spark.sql.catalyst.expressions.RowOrdering +import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide} +import org.apache.spark.sql.catalyst.planning.ExtractEquiJoinKeys +import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, LeftSemi} +import org.apache.spark.sql.catalyst.plans.logical.{Join, JoinHint, JoinStrategyHint, LogicalPlan} +import org.apache.spark.sql.execution.{SparkPlan, SparkStrategy} +import org.apache.spark.sql.execution.adaptive.{BroadcastQueryStageExec, LogicalQueryStage} +import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec} +import org.apache.spark.sql.internal.SQLConf + +import org.apache.comet.CometConf +import org.apache.comet.CometSparkSessionExtensions.{isCometLoaded, withFallbackReason, withInfo} +import org.apache.comet.shims.ShimJoinSelection + +/** + * Plans a ShuffledHashJoinExec in place of a SortMergeJoinExec, before EnsureRequirements and + * RemoveRedundantSorts, so the sorts above the join survive. Adapted from Apache Gluten. + */ +case class CometShuffledHashJoinStrategy(session: SparkSession) + extends SparkStrategy + with ShimJoinSelection { + + override def apply(plan: LogicalPlan): Seq[SparkPlan] = plan match { + case join: Join if isEnabled(join) => planJoin(join) + case _ => Nil + } + + private def sqlConf: SQLConf = session.sessionState.conf + + // Planner strategies run with Comet off and before CometRule, which applies plan-only mode. + private def isEnabled(join: Join): Boolean = + CometConf.COMET_FORCE_SHJ.get(sqlConf) && + CometConf.COMET_EXEC_ENABLED.get(sqlConf) && + !CometConf.COMET_EXPLAIN_PLAN_ONLY_ENABLED.get(sqlConf) && + !join.isStreaming && + isCometLoaded(sqlConf) + + private def planJoin(join: Join): Seq[SparkPlan] = join match { + case ExtractEquiJoinKeys(joinType, leftKeys, rightKeys, condition, _, left, right, hint) + if !isLeftToSpark(join, hint) && canSortMergeJoin(joinType) && + RowOrdering.isOrderable(leftKeys) && hashJoinSupportedShim(leftKeys, rightKeys) => + buildSide(join) match { + case Some(BuildRight) if joinType == LeftSemi || joinType.isInstanceOf[ExistenceJoin] => + // LeftSemi https://github.com/apache/datafusion-comet/issues/2667 + // ExistenceJoin https://github.com/apache/datafusion-comet/issues/2697 + planBySpark(join) { smj => + withFallbackReason(smj, declineReason(s"BuildRight with $joinType is not supported")) + } + case Some(side) => + buildSideOverLimit(join, side) match { + case Some(reason) => + // Not a fallback: the kept sort-merge join still runs natively. + planBySpark(join)(smj => withInfo(smj, declineReason(reason))) + case None => + Seq( + ShuffledHashJoinExec( + leftKeys, + rightKeys, + joinType, + side, + condition, + planLater(left), Review Comment: [P1] A sorted cached left child can make a native window abort above a forced build-right inner join. Spark sees the cache’s `(k, v)` ordering through the hash join and omits the window’s sort. The rows are sorted, but the native cache scan carries no ordering metadata, and `CometHashJoin` sends `streamedSortOrders` only for the relevant outer joins. Propagate verified ordering for this inner probe, retain the sort, or run the window in Spark when its native input cannot establish the required order. Evidence: On Spark 4.1.3, disable AQE and broadcasts, enable forcing, native range and `spark.comet.convert.inMemoryCache.enabled`, and disable `spark.comet.exec.inMemoryCache.enabled`. Materialize `spark.range(2000).selectExpr("id % 20 AS k", "id AS v").repartition(2, col("k")).sortWithinPartitions("k", "v").cache()`. Inner-join to `range(20)` on `k = id` and collect `dense_rank() OVER (PARTITION BY k ORDER BY v)`. The base retained a `CometSort` below `CometWindowExec` and returned the same 2,000 ranked rows as Spark. The head omitted the sort and raised `CometNativeException: Expects PARTITION BY expression to be ordered`. Disabling only the native window on the head restored all 2,000 correct ranks. ########## spark/src/main/scala/org/apache/comet/rules/CometShuffledHashJoinStrategy.scala: ########## @@ -0,0 +1,175 @@ +/* + * 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.comet.rules + +import org.apache.spark.sql.SparkSession +import org.apache.spark.sql.catalyst.expressions.RowOrdering +import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide} +import org.apache.spark.sql.catalyst.planning.ExtractEquiJoinKeys +import org.apache.spark.sql.catalyst.plans.{ExistenceJoin, LeftSemi} +import org.apache.spark.sql.catalyst.plans.logical.{Join, JoinHint, JoinStrategyHint, LogicalPlan} +import org.apache.spark.sql.execution.{SparkPlan, SparkStrategy} +import org.apache.spark.sql.execution.adaptive.{BroadcastQueryStageExec, LogicalQueryStage} +import org.apache.spark.sql.execution.joins.{ShuffledHashJoinExec, SortMergeJoinExec} +import org.apache.spark.sql.internal.SQLConf + +import org.apache.comet.CometConf +import org.apache.comet.CometSparkSessionExtensions.{isCometLoaded, withFallbackReason, withInfo} +import org.apache.comet.shims.ShimJoinSelection + +/** + * Plans a ShuffledHashJoinExec in place of a SortMergeJoinExec, before EnsureRequirements and + * RemoveRedundantSorts, so the sorts above the join survive. Adapted from Apache Gluten. + */ +case class CometShuffledHashJoinStrategy(session: SparkSession) + extends SparkStrategy + with ShimJoinSelection { + + override def apply(plan: LogicalPlan): Seq[SparkPlan] = plan match { + case join: Join if isEnabled(join) => planJoin(join) + case _ => Nil + } + + private def sqlConf: SQLConf = session.sessionState.conf + + // Planner strategies run with Comet off and before CometRule, which applies plan-only mode. + private def isEnabled(join: Join): Boolean = + CometConf.COMET_FORCE_SHJ.get(sqlConf) && + CometConf.COMET_EXEC_ENABLED.get(sqlConf) && + !CometConf.COMET_EXPLAIN_PLAN_ONLY_ENABLED.get(sqlConf) && + !join.isStreaming && + isCometLoaded(sqlConf) + + private def planJoin(join: Join): Seq[SparkPlan] = join match { + case ExtractEquiJoinKeys(joinType, leftKeys, rightKeys, condition, _, left, right, hint) + if !isLeftToSpark(join, hint) && canSortMergeJoin(joinType) && + RowOrdering.isOrderable(leftKeys) && hashJoinSupportedShim(leftKeys, rightKeys) => + buildSide(join) match { + case Some(BuildRight) if joinType == LeftSemi || joinType.isInstanceOf[ExistenceJoin] => + // LeftSemi https://github.com/apache/datafusion-comet/issues/2667 + // ExistenceJoin https://github.com/apache/datafusion-comet/issues/2697 + planBySpark(join) { smj => + withFallbackReason(smj, declineReason(s"BuildRight with $joinType is not supported")) + } + case Some(side) => + buildSideOverLimit(join, side) match { + case Some(reason) => + // Not a fallback: the kept sort-merge join still runs natively. + planBySpark(join)(smj => withInfo(smj, declineReason(reason))) + case None => + Seq( + ShuffledHashJoinExec( + leftKeys, + rightKeys, + joinType, + side, + condition, + planLater(left), + planLater(right))) + } + case None => Nil + } + case _ => Nil + } + + private def isLeftToSpark(join: Join, hint: JoinHint): Boolean = + isBroadcastStage(join.left) || isBroadcastStage(join.right) || + canPlanAsBroadcastHashJoin(join, sqlConf) || hasStrategyHint(hint) + + // canPlanAsBroadcastHashJoin misses a broadcast stage when the adaptive threshold is lower or + // off, and AQE discards a re-plan that hash joins one. + private def isBroadcastStage(plan: LogicalPlan): Boolean = plan match { + case LogicalQueryStage(_, _: BroadcastQueryStageExec) => true + case _ => false + } + + // AQE's NO_BROADCAST_HASH and PREFER_SHUFFLE_HASH are outside JoinStrategyHint.strategies. + private def hasStrategyHint(hint: JoinHint): Boolean = + Seq(hint.leftHint, hint.rightHint).exists( + _.exists(_.strategy.exists(JoinStrategyHint.strategies.contains))) Review Comment: [P2] Honor AQE’s side-specific `PREFER_SHUFFLE_HASH` when that side is buildable. This hint falls outside `JoinStrategyHint.strategies`, so the new strategy can replace Spark’s preferred build side with the smaller relation by total bytes. One skewed partition on that relation can exhaust the non-spillable hash build. The base preserved Spark’s choice because it rewrote only sort-merge joins. Defer to Spark for this preference while retaining the existing handling of a lone `NO_BROADCAST_HASH`. Evidence: On Spark 4.1.3, enable forcing, native range and AQE. Disable broadcasts, coalescing and skew splitting. Use 16 shuffle partitions, a 128 KiB advisory size and a 1,536 KiB local-map threshold. Join `range(90000)` keyed by `IF(id < 60000, 0L, id)` to `range(200000)` keyed by `id`, retaining `sha2(cast(id AS string), 256)` from both sides by summing their lengths. The largest left and right shuffle partitions were 4,367,889 and 937,190 bytes. AQE set `rightHint=(strategy=prefer_shuffle_hash)`. The base used `BuildRight`; the head used `BuildLeft`. With `spark.memory.offHeap.size=64m` and `spark.comet.exec.memoryPool.fraction=0.0625`, the base returned `[5760000,5760000]`. The head failed to reserve another 624,704 bytes for `HashJoinInput[0]` against the 4,194,304-byte limit. -- This is an automated message from the Apache Git Service. To respond to the message, please log on to GitHub and use the URL above to go to the specific comment. To unsubscribe, e-mail: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
