Skip to content

Commit 16b1add

Browse files
committed
fix: keep a stacked window's longer input order and declare it on empty buckets
The window now sends the rest of the order its child reports past the required keys, up to the first that cannot be expressed, so a window above it in the same native plan sees the longer order. An empty bucket of a sorted bucketed scan is planned as an EmptyExec, which now counts as a source whose order holds. The cache test checks the declared columns, directions and null placements.
1 parent 94aaa19 commit 16b1add

6 files changed

Lines changed: 145 additions & 10 deletions

File tree

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

Lines changed: 24 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -4270,6 +4270,30 @@ mod tests {
42704270
assert!(!PhysicalPlanner::keeps_source_order(&scan(2)));
42714271
}
42724272

4273+
#[test]
4274+
fn declared_order_reaches_an_empty_bucket() {
4275+
// A bucket with no file is planned as an `EmptyExec`. A window over it checks its input's
4276+
// order before polling it, so the order Spark reports has to be declared there as well.
4277+
let schema = Arc::new(Schema::new(vec![Field::new(
4278+
"col_0",
4279+
DataType::Int32,
4280+
true,
4281+
)]));
4282+
let empty: Arc<dyn ExecutionPlan> =
4283+
Arc::new(datafusion::physical_plan::empty::EmptyExec::new(schema));
4284+
let input = PhysicalPlanner::default()
4285+
.with_declared_order(empty, &[create_sort_order(0, 3, false, true)])
4286+
.unwrap();
4287+
assert_eq!("SortedInputExec", input.name());
4288+
let partition_by: Vec<Arc<dyn PhysicalExpr>> = vec![Arc::new(Column::new("col_0", 0))];
4289+
assert_eq!(
4290+
1,
4291+
get_ordered_partition_by_indices(&partition_by, &input)
4292+
.unwrap()
4293+
.len()
4294+
);
4295+
}
4296+
42734297
#[tokio::test]
42744298
async fn spark_plan_dynamic_filter_preserves_metrics() {
42754299
use crate::execution::metrics::utils::to_native_metric_node;
@@ -4461,7 +4485,6 @@ mod tests {
44614485
fn window_declares_input_order_on_a_scan() {
44624486
// Both window operators need their partition keys' order declared, and over a `ScanExec`
44634487
// only the order Spark sent declares it. `percent_rank` does not run with bounded memory.
4464-
use datafusion::physical_plan::windows::get_ordered_partition_by_indices;
44654488
let partition_by: Vec<Arc<dyn PhysicalExpr>> = vec![Arc::new(Column::new("col_0", 0))];
44664489
for (func, operator) in [
44674490
("row_number", "BoundedWindowAggExec"),

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

Lines changed: 4 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -35,6 +35,7 @@ use datafusion::{
3535
LexOrdering, PhysicalExpr,
3636
},
3737
physical_plan::{
38+
empty::EmptyExec,
3839
filter::FilterExec,
3940
joins::{
4041
utils::JoinFilter, HashJoinExec, NestedLoopJoinExec, PartitionMode, SortMergeJoinExec,
@@ -440,11 +441,12 @@ impl PhysicalPlanner {
440441
/// keep their input's order, so that the order Spark reports for them still holds. A source is
441442
/// an input from the JVM, or a scan of files, which reads the files of its one file group one
442443
/// after the other: Spark reports an order for a file scan only when every partition reads one
443-
/// sorted file, as for a sorted bucketed table with one file per bucket. Any other operator may
444+
/// sorted file, as for a sorted bucketed table with one file per bucket. A bucket with no file
445+
/// is planned as an `EmptyExec`, which has no rows to be out of order. Any other operator may
444446
/// have moved rows, such as the null-aware anti join, whose streamed side Comet builds on, and
445447
/// declaring Spark's order over it would be wrong.
446448
pub(super) fn keeps_source_order(plan: &Arc<dyn ExecutionPlan>) -> bool {
447-
if plan.is::<ScanExec>() || plan.is::<ShuffleScanExec>() {
449+
if plan.is::<ScanExec>() || plan.is::<ShuffleScanExec>() || plan.is::<EmptyExec>() {
448450
return true;
449451
}
450452
if let Some(scan) = plan.downcast_ref::<DataSourceExec>() {

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

Lines changed: 3 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -1233,8 +1233,9 @@ 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, then the order keys, then any further keys the input reports,
1237+
// when Spark planned no sort below the window because its input reports that order. Empty
1238+
// otherwise.
12381239
repeated spark.spark_expression.Expr input_sort_orders = 5;
12391240
}
12401241

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

Lines changed: 19 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -36,7 +36,7 @@ import org.apache.comet.{CometConf, ConfigEntry}
3636
import org.apache.comet.CometSparkSessionExtensions.withFallbackReason
3737
import org.apache.comet.serde.{AggSerde, CometOperatorSerde, CometSortOrder, LiteralOuterClass, OperatorOuterClass}
3838
import org.apache.comet.serde.OperatorOuterClass.Operator
39-
import org.apache.comet.serde.QueryPlanSerde.{aggExprToProto, exprToProto, hasNonDefaultStringCollation, liftFallbackReasons, scalarFunctionExprToProto, serializeDataType}
39+
import org.apache.comet.serde.QueryPlanSerde.{aggExprToProto, exprToProto, exprToProtoWithFallbackReasons, hasNonDefaultStringCollation, liftFallbackReasons, scalarFunctionExprToProto, serializeDataType}
4040

4141
object CometWindowExec extends CometOperatorSerde[WindowExec] {
4242

@@ -103,7 +103,24 @@ object CometWindowExec extends CometOperatorSerde[WindowExec] {
103103
"natively")
104104
return None
105105
}
106-
orders.flatten
106+
// The keys the child reports past the required ones hold too, and this window reports
107+
// them, so a window above in the same native plan may rely on them. Send them up to the
108+
// first one that cannot be expressed, in a scope of their own, so that a key left out
109+
// records no fallback reason.
110+
val rest = op.child.outputOrdering
111+
.drop(requiredOrdering.length)
112+
.iterator
113+
.map { order =>
114+
if (hasNonDefaultStringCollation(order.dataType) ||
115+
!order.references.subsetOf(op.child.outputSet)) {
116+
None
117+
} else {
118+
exprToProtoWithFallbackReasons(order, op.child.output)._1
119+
}
120+
}
121+
.takeWhile(_.isDefined)
122+
.flatten
123+
orders.flatten ++ rest
107124
} else {
108125
Nil
109126
}

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

Lines changed: 57 additions & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -3692,6 +3692,13 @@ class CometInMemoryCacheSuite extends CometTestBase {
36923692
}
36933693
}
36943694

3695+
// The order a native window declares on its input, one "index direction nulls" per key.
3696+
private def windowInputOrder(window: CometWindowExec): Seq[String] =
3697+
window.nativeOp.getWindow.getInputSortOrdersList.asScala.toSeq.map { expr =>
3698+
val order = expr.getSortOrder
3699+
s"${order.getChild.getBound.getIndex} ${order.getDirection} ${order.getNullOrdering}"
3700+
}
3701+
36953702
test("a native window over a sorted cache declares the cache's order") {
36963703
// Spark plans no sort below a window over the cache's sort keys, and the native window
36973704
// rejected the scan, which declares no order, with "Expects PARTITION BY expression to be
@@ -3731,7 +3738,10 @@ class CometInMemoryCacheSuite extends CometTestBase {
37313738
withClue(s"nativeCache=$nativeCache, $window\n$plan\n") {
37323739
val windows = collect(plan) { case w: CometWindowExec => w }
37333740
assert(windows.size == 1)
3734-
assert(windows.head.nativeOp.getWindow.getInputSortOrdersCount == 2)
3741+
assert(
3742+
windowInputOrder(windows.head) == Seq(
3743+
"0 Ascending NullsFirst",
3744+
"1 Descending NullsLast"))
37353745
assert(collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty)
37363746
}
37373747
}
@@ -3742,6 +3752,52 @@ class CometInMemoryCacheSuite extends CometTestBase {
37423752
}
37433753
}
37443754

3755+
test("stacked native windows over a sorted cache keep the cache's whole order") {
3756+
// The lower window needs only k ordered and the upper one k and v. Spark plans no sort
3757+
// between them, since the lower window reports the cache's order, so the lower window has to
3758+
// declare all of it for the upper one to start (#7223). Within a key, v = k + 20 * j for j
3759+
// in 0 until 100, and a NULL key holds the multiples of 20, so each key sums to
3760+
// 100 * k + 99000.
3761+
val key = (v: Long) => if (v % 20 == 0) null else v % 20
3762+
Seq(true, false).foreach { nativeCache =>
3763+
withConversions(
3764+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
3765+
SQLConf.AUTO_BROADCASTJOIN_THRESHOLD.key -> "-1",
3766+
SQLConf.SHUFFLE_PARTITIONS.key -> "2",
3767+
CometConf.COMET_EXEC_IN_MEMORY_CACHE_ENABLED.key -> nativeCache.toString) {
3768+
try {
3769+
val cached = spark
3770+
.range(2000)
3771+
.selectExpr("CASE WHEN id % 20 = 0 THEN NULL ELSE id % 20 END AS k", "id AS v")
3772+
.repartition(2, col("k"))
3773+
.sortWithinPartitions("k", "v")
3774+
.cache()
3775+
cached.count()
3776+
3777+
val df = cached
3778+
.selectExpr("k", "v", "sum(v) OVER (PARTITION BY k) AS s")
3779+
.selectExpr("k", "v", "sum(s) OVER (PARTITION BY k, v) AS t")
3780+
val rows = (0L until 2000L).map(v => Row(key(v), v, 100 * (v % 20) + 99000))
3781+
QueryTest.sameRows(rows, df.collect().toSeq).foreach(fail(_))
3782+
val plan = df.queryExecution.executedPlan
3783+
withClue(s"nativeCache=$nativeCache\n$plan\n") {
3784+
val windows = collect(plan) { case w: CometWindowExec => w }
3785+
assert(windows.size == 2)
3786+
windows.foreach { window =>
3787+
assert(
3788+
windowInputOrder(window) == Seq(
3789+
"0 Ascending NullsFirst",
3790+
"1 Ascending NullsFirst"))
3791+
}
3792+
assert(collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty)
3793+
}
3794+
} finally {
3795+
spark.catalog.clearCache()
3796+
}
3797+
}
3798+
}
3799+
}
3800+
37453801
test("a window over a cache sorted by a collated string key stays in Spark") {
37463802
assume(isSpark40Plus, "collated string types require Spark 4.0+")
37473803
// The native side would declare the order of a collated key in raw byte order, which is not

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

Lines changed: 38 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -27,8 +27,8 @@ import org.scalatest.Tag
2727
import org.apache.hadoop.fs.Path
2828
import org.apache.spark.sql.{CometTestBase, DataFrame, Row}
2929
import org.apache.spark.sql.catalyst.expressions.{Alias, Cast, Divide, Expression, MakeDecimal, WindowExpression}
30-
import org.apache.spark.sql.comet.{CometColumnarToRowExec, CometNativeExec, CometSortExec, CometWindowExec, CometWindowGroupLimitExec}
31-
import org.apache.spark.sql.execution.{InputAdapter, SparkPlan, WholeStageCodegenExec}
30+
import org.apache.spark.sql.comet.{CometColumnarToRowExec, CometNativeExec, CometNativeScanExec, CometSortExec, CometWindowExec, CometWindowGroupLimitExec}
31+
import org.apache.spark.sql.execution.{InputAdapter, SortExec, SparkPlan, WholeStageCodegenExec}
3232
import org.apache.spark.sql.execution.window.{WindowExec => SparkWindowExec}
3333
import org.apache.spark.sql.expressions.Window
3434
import org.apache.spark.sql.functions.{count, expr, lead, sum}
@@ -2073,4 +2073,40 @@ class CometWindowExecSuite extends CometTestBase {
20732073
}
20742074
}
20752075
}
2076+
2077+
test("window over a sorted bucketed table with empty buckets runs natively") {
2078+
// With spark.sql.legacy.bucketedTableScan.outputOrdering on, Spark reports a bucketed table's
2079+
// sort columns as the scan's order and plans no sort below the window. Two keys fill at most
2080+
// two of the eight buckets, and the native scan plans each of the others as an empty input,
2081+
// which has to declare the order as well, or the window rejects it before reading (#7223).
2082+
withTable("sorted_bucketed") {
2083+
// A single writer task writes one file per bucket.
2084+
(0 until 40)
2085+
.map(i => (i % 2, i))
2086+
.toDF("k", "v")
2087+
.coalesce(1)
2088+
.write
2089+
.format("parquet")
2090+
.bucketBy(8, "k")
2091+
.sortBy("k", "v")
2092+
.saveAsTable("sorted_bucketed")
2093+
withSQLConf(
2094+
SQLConf.ADAPTIVE_EXECUTION_ENABLED.key -> "false",
2095+
SQLConf.BUCKETING_ENABLED.key -> "true",
2096+
SQLConf.AUTO_BUCKETED_SCAN_ENABLED.key -> "false",
2097+
SQLConf.LEGACY_BUCKETED_TABLE_SCAN_OUTPUT_ORDERING.key -> "true") {
2098+
val df = sql(
2099+
"SELECT k, v, dense_rank() OVER (PARTITION BY k ORDER BY v) AS r " +
2100+
"FROM sorted_bucketed")
2101+
val (_, plan) = checkSparkAnswerAndOperator(df)
2102+
val windows = collect(plan) { case w: CometWindowExec => w }
2103+
assert(windows.size == 1, plan)
2104+
assert(windows.head.child.isInstanceOf[CometNativeScanExec], plan)
2105+
assert(windows.head.child.asInstanceOf[CometNativeScanExec].bucketedScan, plan)
2106+
assert(windows.head.nativeOp.getWindow.getInputSortOrdersCount == 2, plan)
2107+
assert(collect(plan) { case s @ (_: CometSortExec | _: SortExec) => s }.isEmpty, plan)
2108+
assert(df.collect().length == 40)
2109+
}
2110+
}
2111+
}
20762112
}

0 commit comments

Comments
 (0)