Skip to content

Commit 3ff0939

Browse files
committed
fix: sort the input of a Spark window over a doubted order
Spark plans no sort below a window whose child reports the order it needs, and its window trusts that order. Over a Comet operator that may not keep it, such as a native nested loop join (#6898), a window that stays in Spark grouped rows out of order. CometExecRule now sorts that input again. With that, a window with a collated key falls back in every case, and so does a window with ORDER BY but no PARTITION BY over a doubted order, since the native window checks no order there. The compatibility guide lists collated keys among the window's fallbacks.
1 parent 4eb2548 commit 3ff0939

6 files changed

Lines changed: 95 additions & 12 deletions

File tree

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

Lines changed: 4 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -373,9 +373,10 @@ by returning `true` from `maintains_input_order` for that child, as DataFusion's
373373
projection do. The planner declares the order through an operator only when the operator says it
374374
keeps it. An operator that cannot keep the order natively must not report it, or has to be added to
375375
`mayReportFalseOrder` in `operators.scala`. The hash join and window serdes then send no order over
376-
it, and an outer hash join above it that has to keep that order falls back to Spark. Comet's hash
377-
joins are the exception within one native plan: an outer hash join over one of them stays native,
378-
even over one that declared no order, since DataFusion keeps the order it can see there.
376+
it, an outer hash join above it that has to keep that order falls back to Spark, and a window that
377+
runs in Spark above it gets its input sorted again. Comet's hash joins are the exception within one
378+
native plan: an outer hash join over one of them stays native, even over one that declared no order,
379+
since DataFusion keeps the order it can see there.
379380

380381
A leaf that reports an ordering is where the order starts, so the planner has to know that the
381382
native operator produces its rows in that order. It knows that of an input from the JVM and of a

‎docs/source/user-guide/latest/compatibility/operators.md‎

Lines changed: 3 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -219,6 +219,9 @@ incorrect result. When any single window expression in a `WindowExec` falls back
219219
- `lag` / `lead` with a non-literal default value ([#4268](https://github.com/apache/datafusion-comet/issues/4268)).
220220
- A `ROWS` offset that is not an integer or long, or a `RANGE` offset that is not numeric.
221221
- Any `PARTITION BY` or `ORDER BY` expression that Comet cannot serialize.
222+
- Any `PARTITION BY` or `ORDER BY` key whose type carries a non-default `StringType` collation (e.g.
223+
`UTF8_LCASE`). The native window finds partitions and peers by comparing keys byte by byte, which splits values
224+
that the collation ties.
222225

223226
A `RANGE` frame with an explicit offset on a `DATE` `ORDER BY` runs natively, but over a date outside Spark's
224227
supported range of 0001-01-01 to 9999-12-31, such as one produced by `date_add` with a very large day count, the

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

Lines changed: 15 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -1082,6 +1082,20 @@ case class CometExecRule(session: SparkSession, queryStagePrep: Boolean = false)
10821082
visit(plan, requiresRowConsumption = true)
10831083
}
10841084

1085+
/**
1086+
* Sorts the input of a window that runs in Spark when its order may be false. Spark plans no
1087+
* sort below a window whose child reports the order it needs, and its window trusts that order.
1088+
* A Comet operator that may not keep the order it reports, such as a native nested loop join
1089+
* (#6898), then hands the window rows out of order, and it groups them wrongly.
1090+
*/
1091+
private def sortDoubtedWindowInputs(plan: SparkPlan): SparkPlan = plan.transformUp {
1092+
case window: WindowExec
1093+
if window.requiredChildOrdering.head.nonEmpty &&
1094+
CometHashJoinExec.mayReportFalseInputOrder(window.child) =>
1095+
window.withNewChildren(
1096+
Seq(SortExec(window.requiredChildOrdering.head, global = false, child = window.child)))
1097+
}
1098+
10851099
private def _apply(plan: SparkPlan): SparkPlan = {
10861100
// We shouldn't transform Spark query plan if Comet is not loaded.
10871101
if (!isCometLoaded(conf)) {
@@ -1133,7 +1147,7 @@ case class CometExecRule(session: SparkSession, queryStagePrep: Boolean = false)
11331147
if (clearWastedBuildSideBridges(transformed)) {
11341148
transformed = transform(planWithJoinRewritten)
11351149
}
1136-
var newPlan = revertUnsafePartialAggregates(transformed)
1150+
var newPlan = sortDoubtedWindowInputs(revertUnsafePartialAggregates(transformed))
11371151

11381152
// if the plan cannot be run fully natively then explain why (when appropriate
11391153
// config is enabled)

‎spark/src/main/scala/org/apache/spark/sql/comet/CometWindowExec.scala‎

Lines changed: 14 additions & 4 deletions
Original file line numberDiff line numberDiff line change
@@ -76,9 +76,9 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
7676
}
7777

7878
// Spark plans no sort below the window when its input already reports the order the window
79-
// needs. That order is relied on, by declaring it natively or by handing the rows to Spark's
80-
// window, only when mayReportFalseOrder trusts it: Spark's window would group the rows of a
81-
// false order wrongly, while the native one rejects an input whose order it cannot see.
79+
// needs. The native window relies on that order only when mayReportFalseOrder trusts it. A
80+
// window that runs in Spark over a doubted order gets its input sorted again by
81+
// CometExecRule, since Spark's window would trust that order too.
8282
val requiredOrdering = op.requiredChildOrdering.head
8383
val trustsInputOrder =
8484
SortOrder.orderingSatisfies(op.child.outputOrdering, requiredOrdering) &&
@@ -88,7 +88,7 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
8888
// tell apart collated strings that Spark treats as equal, as CometWindowGroupLimitExec notes.
8989
val collated = (op.partitionSpec ++ op.orderSpec.map(_.child))
9090
.filter(key => hasNonDefaultStringCollation(key.dataType))
91-
if (collated.nonEmpty && trustsInputOrder) {
91+
if (collated.nonEmpty) {
9292
withFallbackReason(
9393
op,
9494
collated
@@ -97,6 +97,16 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
9797
return None
9898
}
9999

100+
// Without partition keys the native window checks no order at all, so over a doubted order it
101+
// would compute over rows that may be out of order. With partition keys it rejects an input
102+
// whose order it cannot see.
103+
if (op.partitionSpec.isEmpty && op.orderSpec.nonEmpty && !trustsInputOrder) {
104+
withFallbackReason(
105+
op,
106+
"the order of the window's input, which Spark relies on, may be false")
107+
return None
108+
}
109+
100110
val partitionExprs = op.partitionSpec.map(exprToProto(_, op.child.output))
101111

102112
val sortOrders = op.orderSpec.map(exprToProto(_, op.child.output))

‎spark/src/main/scala/org/apache/spark/sql/comet/operators.scala‎

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -3033,8 +3033,9 @@ trait CometHashJoin {
30333033
}
30343034
}
30353035

3036-
// mayReportFalseOrder for a window's input, checked before CometWindowExec sends its order.
3037-
private[comet] def mayReportFalseInputOrder(plan: SparkPlan): Boolean =
3036+
// mayReportFalseOrder for a window's input, checked by CometWindowExec before it relies on that
3037+
// order and by CometExecRule before a window that stays in Spark does.
3038+
private[apache] def mayReportFalseInputOrder(plan: SparkPlan): Boolean =
30383039
mayReportFalseOrder(plan, countInPlan = true)
30393040

30403041
// Whether the order that `plan` reports may be false, because something that feeds it with no

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

Lines changed: 56 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -40,15 +40,16 @@ import org.apache.spark.sql.catalyst.expressions.{And, Ascending, Attribute, Att
4040
import org.apache.spark.sql.catalyst.optimizer.{BuildLeft, BuildRight, BuildSide}
4141
import org.apache.spark.sql.catalyst.plans.{LeftOuter, RightOuter}
4242
import org.apache.spark.sql.columnar.{CachedBatch, SimpleMetricsCachedBatch}
43-
import org.apache.spark.sql.comet.{CometBroadcastHashJoinExec, CometHashAggregateExec, CometHashJoin, CometHashJoinExec, CometInMemoryTableScanExec, CometNativeScanExec, CometSortAggregateExec, CometSortExec, CometSortMergeJoinExec, CometSparkToColumnarExec, CometWindowExec}
43+
import org.apache.spark.sql.comet.{CometBroadcastHashJoinExec, CometBroadcastNestedLoopJoinExec, CometHashAggregateExec, CometHashJoin, CometHashJoinExec, CometInMemoryTableScanExec, CometNativeScanExec, CometSortAggregateExec, CometSortExec, CometSortMergeJoinExec, CometSparkToColumnarExec, CometWindowExec}
4444
import org.apache.spark.sql.comet.execution.arrow.{ArrowCachedBatchSerializer, CometCachedBatchHelper}
4545
import org.apache.spark.sql.comet.execution.shuffle.CometCelebornShuffleManager
4646
import org.apache.spark.sql.comet.util.Utils
47-
import org.apache.spark.sql.execution.{ColumnarToRowExec, CometSparkPlanInfoHelper, FileSourceScanExec, FilterExec, FormattedMode, RowToColumnarExec, SortExec, SparkPlan, SparkPlanInfo}
47+
import org.apache.spark.sql.execution.{ColumnarToRowExec, CometSparkPlanInfoHelper, FileSourceScanExec, FilterExec, FormattedMode, RowToColumnarExec, SortExec, SparkPlan, SparkPlanInfo, WholeStageCodegenExec}
4848
import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanExec, AQEShuffleReadExec, QueryStageExec, ShuffleQueryStageExec}
4949
import org.apache.spark.sql.execution.columnar.{CometInMemoryRelationHelper, InMemoryRelation, InMemoryTableScanExec}
5050
import org.apache.spark.sql.execution.exchange.{Exchange, ReusedExchangeExec, ShuffleExchangeLike}
5151
import org.apache.spark.sql.execution.joins.{BroadcastHashJoinExec, SortMergeJoinExec}
52+
import org.apache.spark.sql.execution.window.WindowExec
5253
import org.apache.spark.sql.functions.{col, count, lit, max, min, sum}
5354
import org.apache.spark.sql.internal.{SQLConf, StaticSQLConf}
5455
import org.apache.spark.sql.types._
@@ -3920,6 +3921,59 @@ class CometInMemoryCacheSuite extends CometTestBase {
39203921
}
39213922
}
39223923

3924+
test("a window that stays in Spark over a nested loop join sorts the join's rows again") {
3925+
// A native nested loop join emits its rows build row by build row, out of the streamed side's
3926+
// order that it reports (#6898), and Spark plans no sort above it. A window that runs in Spark
3927+
// there, one without partition keys or one with a collated key, gets its input sorted again.
3928+
// One partition, so no exchange comes between the join and the window.
3929+
withConversions(SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false") {
3930+
try {
3931+
val pairs = spark.range(2).toDF("z").hint("broadcast")
3932+
val sorted = (columns: Seq[String], keys: Seq[String]) =>
3933+
spark
3934+
.range(0, 12, 1, 1)
3935+
.selectExpr(columns: _*)
3936+
.sortWithinPartitions(keys.map(col): _*)
3937+
.cache()
3938+
.join(pairs, col("v") % 2 <= col("z"))
3939+
val queries = Seq(
3940+
sorted(Seq("id AS v"), Seq("v"))
3941+
.selectExpr("v", "dense_rank() OVER (ORDER BY v) AS r")) ++
3942+
(if (isSpark40Plus) {
3943+
val collated = Seq(
3944+
"id % 3 AS k",
3945+
"id AS v",
3946+
"CASE id % 4 WHEN 0 THEN 'A' WHEN 1 THEN 'a' WHEN 2 THEN 'B' ELSE 'b' END " +
3947+
"COLLATE UTF8_LCASE AS s")
3948+
Seq(
3949+
// lower(s) leaves the case-insensitive peers equal in the output, whose order among
3950+
// themselves the comparison would otherwise see.
3951+
sorted(collated, Seq("s"))
3952+
.selectExpr("lower(s) AS s", "dense_rank() OVER (ORDER BY s) AS r"),
3953+
sorted(collated, Seq("k", "s")).selectExpr(
3954+
"k",
3955+
"count(*) OVER (PARTITION BY k ORDER BY s " +
3956+
"ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING) AS c"))
3957+
} else {
3958+
Nil
3959+
})
3960+
queries.foreach { df =>
3961+
val (_, plan) = checkSparkAnswer(df)
3962+
withClue(s"$plan\n") {
3963+
assert(collect(plan) { case j: CometBroadcastNestedLoopJoinExec => j }.nonEmpty)
3964+
val windows = collect(plan) { case w: WindowExec => w }
3965+
assert(windows.nonEmpty && windows.forall(_.child match {
3966+
case _: SortExec | WholeStageCodegenExec(_: SortExec) => true
3967+
case _ => false
3968+
}))
3969+
}
3970+
}
3971+
} finally {
3972+
spark.catalog.clearCache()
3973+
}
3974+
}
3975+
}
3976+
39233977
test("an aggregate on the key above a hash join over a sorted cache groups each key once") {
39243978
// The order the join declares on its probe input reaches past the join, so the aggregate
39253979
// above it in the same native plan groups in sorted, streaming mode. That is right while

0 commit comments

Comments
 (0)