Skip to content

Commit dc94ccf

Browse files
committed
fix: declare a window's order next to a partial one its input declares
Two aliases of one sorted column share an order in Spark, so a window over the window for one alias may need the other alias's order with no sort in between. with_declared_order now returns early only when the input's declared order already satisfies the one sent, and otherwise declares it next to the input's when keeps_source_order trusts the input. The serde checks only a suffix key's child against the child's output, since its same-order expressions are not sent and may name pruned columns.
1 parent 16b1add commit dc94ccf

4 files changed

Lines changed: 134 additions & 10 deletions

File tree

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

Lines changed: 42 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -4294,6 +4294,48 @@ mod tests {
42944294
);
42954295
}
42964296

4297+
#[test]
4298+
fn declared_order_extends_an_order_the_input_declares() {
4299+
// Two aliases of one column share an order, so a window over the window for one alias can
4300+
// need the other's order while its input declares only the first. That order is declared
4301+
// next to the input's, unless an operator in between may have moved rows.
4302+
let schema = Arc::new(Schema::new(vec![
4303+
Field::new("col_0", DataType::Int32, true),
4304+
Field::new("col_1", DataType::Int32, true),
4305+
]));
4306+
let planner = PhysicalPlanner::default();
4307+
let declare = |plan: &Arc<dyn ExecutionPlan>, index: i32| {
4308+
planner
4309+
.with_declared_order(
4310+
Arc::clone(plan),
4311+
&[create_sort_order(index, 3, false, true)],
4312+
)
4313+
.unwrap()
4314+
};
4315+
let empty: Arc<dyn ExecutionPlan> =
4316+
Arc::new(datafusion::physical_plan::empty::EmptyExec::new(schema));
4317+
let by_col_0 = declare(&empty, 0);
4318+
assert!(Arc::ptr_eq(&declare(&by_col_0, 0), &by_col_0));
4319+
4320+
let both = declare(&by_col_0, 1);
4321+
assert!(Arc::ptr_eq(both.children()[0], &by_col_0));
4322+
for index in 0..2 {
4323+
let partition_by: Vec<Arc<dyn PhysicalExpr>> =
4324+
vec![Arc::new(Column::new(&format!("col_{index}"), index))];
4325+
let ordered = get_ordered_partition_by_indices(&partition_by, &both).unwrap();
4326+
assert_eq!(1, ordered.len(), "col_{index}");
4327+
}
4328+
4329+
let sort: Arc<dyn ExecutionPlan> = Arc::new(SortExec::new(
4330+
LexOrdering::new(vec![PhysicalSortExpr::new_default(Arc::new(Column::new(
4331+
"col_0", 0,
4332+
)))])
4333+
.unwrap(),
4334+
empty,
4335+
));
4336+
assert!(Arc::ptr_eq(&declare(&sort, 1), &sort));
4337+
}
4338+
42974339
#[tokio::test]
42984340
async fn spark_plan_dynamic_filter_preserves_metrics() {
42994341
use crate::execution::metrics::utils::to_native_metric_node;

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

Lines changed: 19 additions & 8 deletions
Original file line numberDiff line numberDiff line change
@@ -403,11 +403,16 @@ impl PhysicalPlanner {
403403
Ok(Arc::new(prepared))
404404
}
405405

406-
/// `plan`, declaring `sort_orders` as the order its rows arrive in, unless it already
407-
/// declares one. Spark's plan knows the order of an input that enters the native plan from
408-
/// the JVM, and of a scan of sorted files, but the `ScanExec` or the file scan the rows
409-
/// arrive through declares none. Only that order is declared: when an operator in between may
410-
/// have moved rows, `plan` is left as it is.
406+
/// `plan`, declaring `sort_orders` as the order its rows arrive in, unless the order it
407+
/// declares already satisfies them. Spark's plan knows the order of an input that enters the
408+
/// native plan from the JVM, and of a scan of sorted files, but the `ScanExec` or the file
409+
/// scan the rows arrive through declares none. Only that order is declared: when an operator
410+
/// in between may have moved rows, `plan` is left as it is.
411+
///
412+
/// An input can declare part of the order already, as a window does over an input declared
413+
/// for the window below it. Spark may know more than that declaration: two aliases of one
414+
/// column share an order, so the window above may need the other alias's order. The rest is
415+
/// declared next to what `plan` declares.
411416
///
412417
/// The serde sends an order only when the Comet operators of a join's streamed side or of a
413418
/// window's input report it, and it checks that nothing under them moves rows
@@ -424,16 +429,22 @@ impl PhysicalPlanner {
424429
plan: Arc<dyn ExecutionPlan>,
425430
sort_orders: &[Expr],
426431
) -> Result<Arc<dyn ExecutionPlan>, ExecutionError> {
427-
if plan.output_ordering().is_some() || !Self::keeps_source_order(&plan) {
432+
if !Self::keeps_source_order(&plan) {
428433
return Ok(plan);
429434
}
430435
let exprs = sort_orders
431436
.iter()
432437
.map(|expr| self.create_sort_expr(expr, plan.schema()))
433438
.collect::<Result<Vec<_>, _>>()?;
434439
match LexOrdering::new(exprs) {
435-
Some(ordering) => Ok(Arc::new(SortedInputExec::new(plan, ordering))),
436-
None => Ok(plan),
440+
Some(ordering)
441+
if !plan
442+
.equivalence_properties()
443+
.ordering_satisfy(ordering.iter().cloned())? =>
444+
{
445+
Ok(Arc::new(SortedInputExec::new(plan, ordering)))
446+
}
447+
_ => Ok(plan),
437448
}
438449
}
439450

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -106,13 +106,14 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
106106
// The keys the child reports past the required ones hold too, and this window reports
107107
// them, so a window above in the same native plan may rely on them. Send them up to the
108108
// first one that cannot be expressed, in a scope of their own, so that a key left out
109-
// records no fallback reason.
109+
// records no fallback reason. Only a key's child is sent, and its same-order
110+
// expressions may name columns the child no longer outputs.
110111
val rest = op.child.outputOrdering
111112
.drop(requiredOrdering.length)
112113
.iterator
113114
.map { order =>
114115
if (hasNonDefaultStringCollation(order.dataType) ||
115-
!order.references.subsetOf(op.child.outputSet)) {
116+
!order.child.references.subsetOf(op.child.outputSet)) {
116117
None
117118
} else {
118119
exprToProtoWithFallbackReasons(order, op.child.output)._1

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

Lines changed: 70 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -3798,6 +3798,76 @@ class CometInMemoryCacheSuite extends CometTestBase {
37983798
}
37993799
}
38003800

3801+
test("stacked native windows over a sorted cache with aliases of a sort key") {
3802+
// Spark knows that two aliases of one sorted column share its order, so a window over the
3803+
// window for one alias needs no sort for the other. The upper window's input declares the
3804+
// order the lower one needed, so the planner declares the rest next to it (#7223). In the
3805+
// second query the scan drops alias a, which only the order's same-order expressions name.
3806+
// One partition, so no exchange comes between the windows.
3807+
val ids = 0L until 24L
3808+
val key = (id: Long) => if (id % 4 == 0) None else Some(id % 3)
3809+
val nullable = (k: Option[Long]) => k.map(Long.box).orNull
3810+
val keySums = ids.groupBy(key).map { case (k, group) => k -> group.sum }
3811+
val keyCounts = ids.groupBy(key).map { case (k, group) => k -> group.size }
3812+
val pairCounts =
3813+
ids.groupBy(id => (key(id), id % 2)).map { case (p, group) => p -> group.size }
3814+
val source = () =>
3815+
spark
3816+
.range(0, 24, 1, 1)
3817+
.selectExpr(
3818+
"CASE WHEN id % 4 = 0 THEN NULL ELSE id % 3 END AS k",
3819+
"id % 2 AS x",
3820+
"id AS v")
3821+
Seq(true, false).foreach { nativeCache =>
3822+
withConversions(
3823+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
3824+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
3825+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> nativeCache.toString) {
3826+
val check = (df: DataFrame, rows: Seq[Row], orders: Seq[Seq[String]]) => {
3827+
QueryTest.sameRows(rows, df.collect().toSeq).foreach(fail(_))
3828+
val plan = df.queryExecution.executedPlan
3829+
withClue(s"nativeCache=$nativeCache\n$plan\n") {
3830+
val windows = collect(plan) { case w: CometWindowExec => w }
3831+
assert(windows.map(windowInputOrder) == orders)
3832+
assert(collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty)
3833+
}
3834+
}
3835+
try {
3836+
val byKey =
3837+
source().sortWithinPartitions("k").selectExpr("k AS a", "k AS b", "v").cache()
3838+
byKey.count()
3839+
check(
3840+
byKey
3841+
.selectExpr("a", "b", "v", "sum(v) OVER (PARTITION BY a) AS s")
3842+
.selectExpr("a", "b", "v", "sum(s) OVER (PARTITION BY b) AS t"),
3843+
ids.map { id =>
3844+
val k = key(id)
3845+
Row(nullable(k), nullable(k), id, keySums(k) * keyCounts(k))
3846+
},
3847+
Seq(Seq("1 Ascending NullsFirst"), Seq("0 Ascending NullsFirst")))
3848+
3849+
val byPair = source()
3850+
.sortWithinPartitions("k", "x")
3851+
.selectExpr("k", "x AS a", "x AS b", "v")
3852+
.cache()
3853+
byPair.count()
3854+
val both = Seq("0 Ascending NullsFirst", "1 Ascending NullsFirst")
3855+
check(
3856+
byPair
3857+
.selectExpr("k", "b", "v", "sum(v) OVER (PARTITION BY k) AS s")
3858+
.selectExpr("k", "b", "v", "sum(s) OVER (PARTITION BY k, b) AS t"),
3859+
ids.map { id =>
3860+
val k = key(id)
3861+
Row(nullable(k), id % 2, id, keySums(k) * pairCounts((k, id % 2)))
3862+
},
3863+
Seq(both, both))
3864+
} finally {
3865+
spark.catalog.clearCache()
3866+
}
3867+
}
3868+
}
3869+
}
3870+
38013871
test("a window over a cache sorted by a collated string key stays in Spark") {
38023872
assume(isSpark40Plus, "collated string types require Spark 4.0+")
38033873
// The native side would declare the order of a collated key in raw byte order, which is not

0 commit comments

Comments
 (0)