Skip to content

Commit 8e0b8e0

Browse files
committed
fix: declare only a window's partition keys and fall back on an unchecked order
The native window checks only its partition keys' order, so the serde sends only those, and a float order key that Spark sorts with -0.0 and 0.0 as equal is never declared. When the order the child reports may be false past the native plan, the window stays in Spark, as the outer hash join does, instead of failing the task. The SortedInputExec doc and the operator guide now cover the window.
1 parent 9c5dcd0 commit 8e0b8e0

8 files changed

Lines changed: 109 additions & 62 deletions

File tree

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

Lines changed: 7 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -365,17 +365,18 @@ the order satisfies. Report what the Spark operator reports and nothing more. `S
365365
example, reports no order, so `CometSampleExec` must not report its child's.
366366

367367
The claim has to hold at run time as well. A native hash join declares the order Spark reports for
368-
its streamed side to DataFusion, and an aggregate above the join may then run in sorted mode, or a
369-
top-k sort may stop reading early, on the strength of that order. If the order is false, the
368+
its streamed side to DataFusion, and a native window the order of its partition keys. An aggregate
369+
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
370371
result is wrong groups or wrong rows, not only rows out of order. So an operator that reports an
371372
ordering must keep it natively, and the native operator must say so by returning `true` from
372373
`maintains_input_order` for that child, as DataFusion's filter and projection do. The planner
373374
declares the order through an operator only when the operator says it keeps it. An operator that
374375
cannot keep the order natively must not report it, or has to be added to `mayReportFalseOrder` in
375-
`operators.scala`. The hash join serde then sends no order over it, and an outer hash join above it
376-
that has to keep that order falls back to Spark. Comet's hash joins are the exception within one
377-
native plan: an outer hash join over one of them stays native, even over one that declared no
378-
order, since DataFusion keeps the order it can see there.
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.
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

‎native/core/src/execution/operators/sorted_input.rs‎

Lines changed: 8 additions & 7 deletions
Original file line numberDiff line numberDiff line change
@@ -37,13 +37,14 @@ use datafusion::physical_plan::{
3737
/// sorted before it was cached for instance, but the `ScanExec` it arrives through declares none,
3838
/// and DataFusion's hash join keeps the unmatched probe rows of a right outer join in place only
3939
/// when the probe input declares an order. Otherwise it moves them after the matched rows of each
40-
/// batch, which loses an order Spark has already dropped a sort for. The planner puts this only
41-
/// on that join's probe input, with the order Spark reports for it, and only when the rows reach
42-
/// that input from the JVM through operators that keep their order. The join keeps the order in
43-
/// its own output, so the operators above it in the native plan see it too: an aggregate grouped
44-
/// by the key runs in sorted, streaming mode, a sort aggregate takes the order as already
45-
/// satisfied, and a top-k sort whose keys start with it stops reading early. A wrong order would
46-
/// therefore give wrong groups or wrong rows, not only rows out of order.
40+
/// batch, which loses an order Spark has already dropped a sort for. A window rejects an input
41+
/// that does not declare its partition keys' order. The planner puts this only on that join's
42+
/// probe input or that window's input, with the order Spark reports for it, and only when the
43+
/// rows reach that input from the JVM through operators that keep their order. Both keep the
44+
/// order in their own output, so the operators above them in the native plan see it too: an
45+
/// aggregate grouped by the key runs in sorted, streaming mode, a sort aggregate takes the order
46+
/// as already satisfied, and a top-k sort whose keys start with it stops reading early. A wrong
47+
/// order would therefore give wrong groups or wrong rows, not only rows out of order.
4748
#[derive(Debug)]
4849
pub struct SortedInputExec {
4950
input: Arc<dyn ExecutionPlan>,

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

Lines changed: 12 additions & 20 deletions
Original file line numberDiff line numberDiff line change
@@ -4484,21 +4484,6 @@ mod tests {
44844484
);
44854485
}
44864486

4487-
/// `func` over a window partitioned and ordered by `col_0` over `input`.
4488-
fn partitioned_window(func: &str, input: Operator, input_sort_orders: Vec<Expr>) -> Operator {
4489-
Operator {
4490-
children: vec![input],
4491-
op_struct: Some(OpStruct::Window(Box::new(spark_operator::Window {
4492-
window_expr: vec![window_function_expr(func, None)],
4493-
partition_by_list: vec![create_bound_reference(0)],
4494-
order_by_list: vec![create_sort_order(0, 3, false, true)],
4495-
input_sort_orders,
4496-
..Default::default()
4497-
}))),
4498-
..Default::default()
4499-
}
4500-
}
4501-
45024487
#[test]
45034488
fn window_declares_input_order_on_a_scan() {
45044489
// Both window operators need their partition keys' order, which a `ScanExec` declares
@@ -4509,12 +4494,19 @@ mod tests {
45094494
("percent_rank", "WindowAggExec"),
45104495
] {
45114496
let window_input = |input_sort_orders| {
4497+
let window = Operator {
4498+
children: vec![create_scan()],
4499+
op_struct: Some(OpStruct::Window(Box::new(spark_operator::Window {
4500+
window_expr: vec![window_function_expr(func, None)],
4501+
partition_by_list: vec![create_bound_reference(0)],
4502+
order_by_list: vec![create_sort_order(0, 3, false, true)],
4503+
input_sort_orders,
4504+
..Default::default()
4505+
}))),
4506+
..Default::default()
4507+
};
45124508
let (_, _, planned) = PhysicalPlanner::default()
4513-
.create_plan(
4514-
&partitioned_window(func, create_scan(), input_sort_orders),
4515-
&mut vec![],
4516-
1,
4517-
)
4509+
.create_plan(&window, &mut vec![], 1)
45184510
.unwrap();
45194511
assert_eq!(operator, planned.native_plan.name());
45204512
Arc::clone(planned.native_plan.children()[0])

‎native/proto/src/proto/operator.proto‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1233,8 +1233,8 @@ message Window {
12331233
repeated spark.spark_expression.Expr order_by_list = 2;
12341234
repeated spark.spark_expression.Expr partition_by_list = 3;
12351235
Operator child = 4;
1236-
// The partition keys ascending, then the order keys, when Spark planned no sort below the
1237-
// window because its input reports that order. Empty otherwise.
1236+
// The partition keys ascending, when Spark planned no sort below the window because its input
1237+
// reports that order. Empty otherwise.
12381238
repeated spark.spark_expression.Expr input_sort_orders = 5;
12391239
}
12401240

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

Lines changed: 32 additions & 17 deletions
Original file line numberDiff line numberDiff line change
@@ -40,6 +40,13 @@ 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+
4350
override def enabledConfig: Option[ConfigEntry[Boolean]] = Some(
4451
CometConf.COMET_EXEC_WINDOW_ENABLED)
4552

@@ -82,27 +89,35 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
8289
if (windowExprProto.forall(_.isDefined) && partitionExprs.forall(_.isDefined)
8390
&& sortOrders.forall(_.isDefined)) {
8491
// Spark plans no sort below the window when its input already reports the order the window
85-
// needs, but rows from the JVM arrive through a ScanExec that declares none. Send that order
86-
// for the planner to declare (see SortedInputExec), unless a native sort below declares it
87-
// or it may be false. A key Comet cannot express, or a collated string key, sends the window
88-
// back to Spark.
92+
// needs, but rows from the JVM arrive through a ScanExec that declares none. Send the
93+
// 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.
8998
val requiredOrdering = op.requiredChildOrdering.head
9099
val inputSortOrders =
91-
if (requiredOrdering.nonEmpty && !op.child.isInstanceOf[CometSortExec] &&
92-
SortOrder.orderingSatisfies(op.child.outputOrdering, requiredOrdering) &&
93-
!CometHashJoinExec.mayReportFalseInputOrder(op.child)) {
94-
val orders = requiredOrdering.map { order =>
95-
if (hasNonDefaultStringCollation(order.dataType)) None
96-
else exprToProto(order, op.child.output)
97-
}
98-
if (!orders.forall(_.isDefined)) {
99-
withFallbackReason(
100-
op,
101-
"the order of the window's input, which Spark relies on, cannot be expressed " +
102-
"natively")
100+
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)
103117
return None
118+
} else {
119+
Nil
104120
}
105-
orders.flatten
106121
} else {
107122
Nil
108123
}

‎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, checked before CometWindowExec sends its order.
3021-
private[comet] def mayReportFalseInputOrder(plan: SparkPlan): Boolean =
3022-
mayReportFalseOrder(plan, countInPlan = true)
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)
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: 44 additions & 6 deletions
Original file line numberDiff line numberDiff line change
@@ -3712,10 +3712,10 @@ class CometInMemoryCacheSuite extends CometTestBase {
37123712

37133713
test("a native window over a sorted cache declares the cache's order") {
37143714
// Spark plans no sort below a window over the cache's sort keys, so the scan has to declare
3715-
// the order (#7223). A nullable key and a descending order key check the direction and null
3716-
// placement. dense_rank runs in BoundedWindowAggExec and the UNBOUNDED FOLLOWING frame in
3717-
// WindowAggExec. Within a key, v = k + 20 * j for j in 0 until 100, and a NULL key holds the
3718-
// multiples of 20.
3715+
// the partition key's order (#7223). The key is nullable, so the null placement has to match,
3716+
// and the descending order key is not declared. dense_rank runs in BoundedWindowAggExec and
3717+
// the UNBOUNDED FOLLOWING frame in WindowAggExec. Within a key, v = k + 20 * j for j in
3718+
// 0 until 100, and a NULL key holds the multiples of 20.
37193719
val key = (v: Long) => if (v % 20 == 0) null else v % 20
37203720
val queries = Seq(
37213721
"dense_rank() OVER (PARTITION BY k ORDER BY v DESC)" ->
@@ -3745,7 +3745,7 @@ class CometInMemoryCacheSuite extends CometTestBase {
37453745
checkWindows(
37463746
cached.selectExpr("k", "v", s"$window AS w"),
37473747
(0L until 2000L).map(v => Row(key(v), v, expected(v))),
3748-
Seq(Seq("0 Ascending NullsFirst", "1 Descending NullsLast")))
3748+
Seq(Seq("0 Ascending NullsFirst")))
37493749
}
37503750
}
37513751
} finally {
@@ -3836,13 +3836,51 @@ class CometInMemoryCacheSuite extends CometTestBase {
38363836
val plan = df.queryExecution.executedPlan
38373837
assert(collect(plan) { case w: CometWindowExec => w }.isEmpty, plan)
38383838
val reasons = new ExtendedExplainInfo().getFallbackReasons(plan)
3839-
assert(reasons.exists(_.contains("the order of the window's input")), reasons)
3839+
assert(reasons.contains(CometWindowExec.inexpressibleInputOrderReason), reasons)
38403840
} finally {
38413841
spark.catalog.clearCache()
38423842
}
38433843
}
38443844
}
38453845

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+
38463884
test("an aggregate on the key above a hash join over a sorted cache groups each key once") {
38473885
// The order the join declares on its probe input reaches past the join, so the aggregate
38483886
// above it in the same native plan groups in sorted, streaming mode. That is right while

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

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -2105,7 +2105,7 @@ class CometWindowExecSuite extends CometTestBase {
21052105
case _ => false
21062106
},
21072107
plan)
2108-
assert(windows.head.nativeOp.getWindow.getInputSortOrdersCount == 2, plan)
2108+
assert(windows.head.nativeOp.getWindow.getInputSortOrdersCount == 1, plan)
21092109
}
21102110
}
21112111
}

0 commit comments

Comments
 (0)