Skip to content

Commit 136e5cf

Browse files
committed
fix: keep a window's doubted order native, fall back on collated keys
Falling back when the window's input order may be false handed the same rows to Spark's window, which trusts that order too and grouped them wrongly. The window again sends no order there, so the native window rejects its input as on main. A window whose partition or order key holds a collated string now stays in Spark, as WindowGroupLimit does, since the native window compares keys byte by byte. keeps_source_order accepts a right outer hash join whose probe declares an order, which is when DataFusion keeps its unmatched probe rows in place.
1 parent 8e0b8e0 commit 136e5cf

6 files changed

Lines changed: 92 additions & 112 deletions

File tree

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

Lines changed: 9 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -367,16 +367,15 @@ example, reports no order, so `CometSampleExec` must not report its child's.
367367
The claim has to hold at run time as well. A native hash join declares the order Spark reports for
368368
its streamed side to DataFusion, and a native window the order of its partition keys. An aggregate
369369
above may then run in sorted mode, or a top-k sort may stop reading early, on the strength of that
370-
order. If the order is false, the
371-
result is wrong groups or wrong rows, not only rows out of order. So an operator that reports an
372-
ordering must keep it natively, and the native operator must say so by returning `true` from
373-
`maintains_input_order` for that child, as DataFusion's filter and projection do. The planner
374-
declares the order through an operator only when the operator says it keeps it. An operator that
375-
cannot keep the order natively must not report it, or has to be added to `mayReportFalseOrder` in
376-
`operators.scala`. The hash join and window serdes then send no order over it, and an outer hash
377-
join or a window above it that needs that order falls back to Spark. Comet's hash joins are the
378-
exception within one native plan: a join or window over one of them stays native, even over one
379-
that declared no order, since DataFusion keeps the order it can see there.
370+
order. If the order is false, the result is wrong groups or wrong rows, not only rows out of order.
371+
So an operator that reports an ordering must keep it natively, and the native operator must say so
372+
by returning `true` from `maintains_input_order` for that child, as DataFusion's filter and
373+
projection do. The planner declares the order through an operator only when the operator says it
374+
keeps it. An operator that cannot keep the order natively must not report it, or has to be added to
375+
`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.
380379

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

‎native/core/src/execution/planner.rs‎

Lines changed: 3 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4101,8 +4101,10 @@ mod tests {
41014101
"col_0@0 ASC",
41024102
probe.properties().output_ordering().unwrap().to_string()
41034103
);
4104-
// The join keeps the order in its own output, so the operators above it see it too.
4104+
// The join keeps the order in its own output, so the operators above it see it too,
4105+
// and an order declared above it holds, such as a window's for an alias of the key.
41054106
assert!(planned.native_plan.properties().output_ordering().is_some());
4107+
assert!(PhysicalPlanner::keeps_source_order(&planned.native_plan));
41064108
}
41074109
}
41084110

‎native/core/src/execution/planner/join.rs‎

Lines changed: 13 additions & 10 deletions
Original file line numberDiff line numberDiff line change
@@ -465,18 +465,21 @@ impl PhysicalPlanner {
465465
.is_some_and(|config| config.file_groups.len() == 1);
466466
}
467467
// DataFusion reports every right hash join as keeping its probe order, but a right outer
468-
// join keeps it only when the probe declares one, and no input on this path declares an
469-
// order. An inner join emits its matches probe row by probe row, and a right semi, anti or
470-
// mark join builds its probe indices in ascending order, so none of them depends on a
471-
// declaration. Any other join type keeps no probe order at all.
468+
// join keeps its unmatched probe rows in place only when the probe declares an order, as
469+
// the planner does for the join's streamed side. An inner join emits its matches probe
470+
// row by probe row, and a right semi, anti or mark join builds its probe indices in
471+
// ascending order, so none of them depends on a declaration. Any other join type keeps no
472+
// probe order at all.
472473
if let Some(join) = plan.downcast_ref::<HashJoinExec>() {
473-
if !matches!(
474-
join.join_type(),
474+
let keeps_probe_order = match join.join_type() {
475475
DFJoinType::Inner
476-
| DFJoinType::RightSemi
477-
| DFJoinType::RightAnti
478-
| DFJoinType::RightMark
479-
) {
476+
| DFJoinType::RightSemi
477+
| DFJoinType::RightAnti
478+
| DFJoinType::RightMark => true,
479+
DFJoinType::Right => join.right().output_ordering().is_some(),
480+
_ => false,
481+
};
482+
if !keeps_probe_order {
480483
return false;
481484
}
482485
}

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

Lines changed: 25 additions & 29 deletions
Original file line numberDiff line numberDiff line change
@@ -40,13 +40,6 @@ import org.apache.comet.serde.QueryPlanSerde.{aggExprToProto, exprToProto, hasNo
4040

4141
object CometWindowExec extends CometOperatorSerde[WindowExec] {
4242

43-
private[apache] val inexpressibleInputOrderReason: String =
44-
"the order of the window's input, which Spark relies on, cannot be expressed natively"
45-
46-
private[apache] val uncheckedInputOrderReason: String =
47-
"the order of the window's input, which Spark relies on, cannot be checked, so the window " +
48-
"stays in Spark"
49-
5043
override def enabledConfig: Option[ConfigEntry[Boolean]] = Some(
5144
CometConf.COMET_EXEC_WINDOW_ENABLED)
5245

@@ -82,6 +75,19 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
8275
}
8376
}
8477

78+
// The native window finds partitions and peers by comparing keys byte by byte, so it would
79+
// tell apart collated strings that Spark treats as equal, as CometWindowGroupLimitExec notes.
80+
val collated = (op.partitionSpec ++ op.orderSpec.map(_.child))
81+
.filter(key => hasNonDefaultStringCollation(key.dataType))
82+
if (collated.nonEmpty) {
83+
withFallbackReason(
84+
op,
85+
collated
86+
.map(_.sql)
87+
.mkString("Window: non-default string collation on key(s): ", ", ", ""))
88+
return None
89+
}
90+
8591
val partitionExprs = op.partitionSpec.map(exprToProto(_, op.child.output))
8692

8793
val sortOrders = op.orderSpec.map(exprToProto(_, op.child.output))
@@ -91,33 +97,23 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
9197
// Spark plans no sort below the window when its input already reports the order the window
9298
// needs, but rows from the JVM arrive through a ScanExec that declares none. Send the
9399
// partition keys' order, the only one the native window checks, for the planner to declare
94-
// (see SortedInputExec). When the order may be false, nothing native can declare it, so the
95-
// window stays in Spark, unless the doubt is a Comet join in the same native plan, which
96-
// DataFusion sees itself. A key Comet cannot express, or a collated string key, sends the
97-
// window back to Spark too.
100+
// (see SortedInputExec). Nothing is sent when that order may be false. Falling back would
101+
// not help, since Spark's window trusts the order too.
98102
val requiredOrdering = op.requiredChildOrdering.head
99103
val inputSortOrders =
100104
if (op.partitionSpec.nonEmpty &&
101-
SortOrder.orderingSatisfies(op.child.outputOrdering, requiredOrdering)) {
102-
// The walk that counts Comet joins in the same native plan flags everything the other
103-
// one does, so the other runs only when this one flags the order.
104-
if (!CometHashJoinExec.mayReportFalseInputOrder(op.child, countInPlan = true)) {
105-
val partitionKeys = requiredOrdering.take(op.partitionSpec.length)
106-
val orders = partitionKeys.flatMap { order =>
107-
if (hasNonDefaultStringCollation(order.dataType)) None
108-
else exprToProto(order, op.child.output)
109-
}
110-
if (orders.length < partitionKeys.length) {
111-
withFallbackReason(op, inexpressibleInputOrderReason)
112-
return None
113-
}
114-
orders
115-
} else if (CometHashJoinExec.mayReportFalseInputOrder(op.child, countInPlan = false)) {
116-
withFallbackReason(op, uncheckedInputOrderReason)
105+
SortOrder.orderingSatisfies(op.child.outputOrdering, requiredOrdering) &&
106+
!CometHashJoinExec.mayReportFalseInputOrder(op.child)) {
107+
val partitionKeys = requiredOrdering.take(op.partitionSpec.length)
108+
val orders = partitionKeys.flatMap(exprToProto(_, op.child.output))
109+
if (orders.length < partitionKeys.length) {
110+
withFallbackReason(
111+
op,
112+
"the order of the window's input, which Spark relies on, cannot be expressed " +
113+
"natively")
117114
return None
118-
} else {
119-
Nil
120115
}
116+
orders
121117
} else {
122118
Nil
123119
}

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

Lines changed: 3 additions & 3 deletions
Original file line numberDiff line numberDiff line change
@@ -3017,9 +3017,9 @@ trait CometHashJoin {
30173017
}
30183018
}
30193019

3020-
// mayReportFalseOrder for a window's input, which CometWindowExec checks like a join does.
3021-
private[comet] def mayReportFalseInputOrder(plan: SparkPlan, countInPlan: Boolean): Boolean =
3022-
mayReportFalseOrder(plan, countInPlan)
3020+
// mayReportFalseOrder for a window's input, checked before CometWindowExec sends its order.
3021+
private[comet] def mayReportFalseInputOrder(plan: SparkPlan): Boolean =
3022+
mayReportFalseOrder(plan, countInPlan = true)
30233023

30243024
// Whether the order that `plan` reports may be false, because something that feeds it with no
30253025
// sort in between cannot be relied on to keep it. Comet's hash joins report the order of their

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

Lines changed: 39 additions & 59 deletions
Original file line numberDiff line numberDiff line change
@@ -3755,11 +3755,12 @@ class CometInMemoryCacheSuite extends CometTestBase {
37553755
}
37563756
}
37573757

3758-
test("stacked native windows over a sorted cache") {
3759-
// Spark plans no sort between two windows that the cache's order satisfies, so the upper
3760-
// window's input, which declares only the lower window's order, gets the rest declared next
3761-
// to it (#7223). Alias a of sort key k shares its order. One partition, so no exchange
3762-
// separates the windows.
3758+
test("a native window declares its order next to the order its input declares") {
3759+
// Spark plans no sort above an operator that keeps the cache's order, so a window's input may
3760+
// declare only the order that operator needed: an upper window's input the lower window's,
3761+
// and an outer join's output its streamed side's. The window's order is declared next to it
3762+
// (#7223). Alias a of sort key k shares its order. One partition, so no exchange comes in
3763+
// between.
37633764
val ids = 0L until 24L
37643765
val key = (id: Long) => if (id % 4 == 0) None else Some(id % 3)
37653766
val nullable = (k: Option[Long]) => k.map(Long.box).orNull
@@ -3802,6 +3803,18 @@ class CometInMemoryCacheSuite extends CometTestBase {
38023803
Row(nullable(k), nullable(k), id, keySums(k) * keyCounts(k))
38033804
},
38043805
Seq(Seq("1 Ascending NullsFirst"), Seq("0 Ascending NullsFirst")))
3806+
// The residual condition leaves rows of key 0 unmatched among matched ones, so the key
3807+
// stays together only if the join keeps its unmatched probe rows in place.
3808+
val one = spark.range(1).toDF("j").hint("broadcast")
3809+
checkWindows(
3810+
cached
3811+
.join(one, col("k") === col("j") && col("v") % 2 === 0, "left_outer")
3812+
.selectExpr("k", "a", "v", "sum(v) OVER (PARTITION BY a) AS s"),
3813+
ids.map { id =>
3814+
val k = key(id)
3815+
Row(nullable(k), nullable(k), id, keySums(k))
3816+
},
3817+
Seq(Seq("1 Ascending NullsFirst")))
38053818
} finally {
38063819
spark.catalog.clearCache()
38073820
}
@@ -3810,77 +3823,44 @@ class CometInMemoryCacheSuite extends CometTestBase {
38103823

38113824
test("a window over a cache sorted by a collated string key stays in Spark") {
38123825
assume(isSpark40Plus, "collated string types require Spark 4.0+")
3813-
// The native side would declare a collated key in raw byte order, not Spark's collation
3814-
// order, so the window falls back.
3826+
// The native window compares keys byte by byte, so it would split the UTF8_LCASE partition
3827+
// of '0a' and '0A' and rank them apart.
3828+
val key = (v: Long) => s"${v % 4}${if (v % 8 < 4) "a" else "A"}"
38153829
withConversions(
38163830
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
38173831
SQLConf.SHUFFLE_PARTITIONS.key -> "2") {
38183832
try {
3819-
val cached = spark
3833+
val source = spark
38203834
.range(200)
38213835
.selectExpr(
38223836
"CAST(id % 4 AS STRING) || CASE WHEN id % 8 < 4 THEN 'a' ELSE 'A' END " +
38233837
"COLLATE UTF8_LCASE AS k",
3838+
"id % 2 AS n",
38243839
"id AS v")
3825-
.repartition(2, col("k"))
3826-
.sortWithinPartitions("k", "v")
3827-
.cache()
3828-
cached.count()
3840+
val byKey = source.repartition(2, col("k")).sortWithinPartitions("k", "v").cache()
3841+
val byGroup = source.repartition(2, col("n")).sortWithinPartitions("n", "k").cache()
3842+
byKey.count()
3843+
byGroup.count()
38293844

3830-
val df = cached.selectExpr("k", "v", "dense_rank() OVER (PARTITION BY k ORDER BY v) AS r")
3831-
// UTF8_LCASE puts 'a' and 'A' in one partition, so each of the four keys holds 50 rows.
3832-
val rows = (0L until 200L).map { v =>
3833-
Row(s"${v % 4}${if (v % 8 < 4) "a" else "A"}", v, (v / 4 + 1).toInt)
3845+
Seq(
3846+
// Each of the four keys holds 50 rows.
3847+
byKey.selectExpr("k", "v", "dense_rank() OVER (PARTITION BY k ORDER BY v) AS r") ->
3848+
((v: Long) => Row(key(v), v, (v / 4 + 1).toInt)),
3849+
// Each group holds two keys, '0' and '2' or '1' and '3'.
3850+
byGroup.selectExpr("n", "k", "dense_rank() OVER (PARTITION BY n ORDER BY k) AS r") ->
3851+
((v: Long) => Row(v % 2, key(v), (v % 4 / 2 + 1).toInt))).foreach { case (df, row) =>
3852+
QueryTest.sameRows((0L until 200L).map(row), df.collect().toSeq).foreach(fail(_))
3853+
val plan = df.queryExecution.executedPlan
3854+
assert(collect(plan) { case w: CometWindowExec => w }.isEmpty, plan)
3855+
val reasons = new ExtendedExplainInfo().getFallbackReasons(plan)
3856+
assert(reasons.exists(_.startsWith("Window: non-default string collation")), reasons)
38343857
}
3835-
QueryTest.sameRows(rows, df.collect().toSeq).foreach(fail(_))
3836-
val plan = df.queryExecution.executedPlan
3837-
assert(collect(plan) { case w: CometWindowExec => w }.isEmpty, plan)
3838-
val reasons = new ExtendedExplainInfo().getFallbackReasons(plan)
3839-
assert(reasons.contains(CometWindowExec.inexpressibleInputOrderReason), reasons)
38403858
} finally {
38413859
spark.catalog.clearCache()
38423860
}
38433861
}
38443862
}
38453863

3846-
test("a window over a cache whose order cannot be checked stays in Spark") {
3847-
// The filter keeps the serde from seeing that the outer join declared its order, so the
3848-
// window, reading that join's cache from the JVM, cannot check it. Declaring nothing would
3849-
// fail the native window.
3850-
withSQLConf(
3851-
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
3852-
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
3853-
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> "true",
3854-
CometConf.COMET_CONVERT_FROM_IN_MEMORY_CACHE_ENABLED.key -> "false") {
3855-
withParquetTable((0 until 2000).map(i => ((i % 40) * 1000, i)), "big") {
3856-
withParquetTable((0 until 40 by 2).map(m => (m * 1000, m)), "small") {
3857-
withTempView("cached", "joined") {
3858-
try {
3859-
spark
3860-
.table("big")
3861-
.toDF("k", "v")
3862-
.repartition(2, $"k")
3863-
.sortWithinPartitions("k")
3864-
.cache()
3865-
.createOrReplaceTempView("cached")
3866-
spark.table("cached").count()
3867-
sql("SELECT /*+ BROADCAST(b) */ a.k, a.v, b._2 AS w FROM " +
3868-
"(SELECT * FROM cached WHERE v >= 0) a LEFT JOIN small b ON a.k = b._1")
3869-
.cache()
3870-
.createOrReplaceTempView("joined")
3871-
spark.table("joined").count()
3872-
checkSparkAnswerAndFallbackReason(
3873-
sql("SELECT k, v, sum(v) OVER (PARTITION BY k) AS s FROM joined"),
3874-
CometWindowExec.uncheckedInputOrderReason)
3875-
} finally {
3876-
spark.catalog.clearCache()
3877-
}
3878-
}
3879-
}
3880-
}
3881-
}
3882-
}
3883-
38843864
test("an aggregate on the key above a hash join over a sorted cache groups each key once") {
38853865
// The order the join declares on its probe input reaches past the join, so the aggregate
38863866
// above it in the same native plan groups in sorted, streaming mode. That is right while

0 commit comments

Comments
 (0)