You are viewing a plain text version of this content. The canonical link for it is here.
Posted to reviews@spark.apache.org by "ulysses-you (via GitHub)" <gi...@apache.org> on 2026/07/21 06:49:23 UTC
[PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
ulysses-you opened a new pull request, #57396:
URL: https://github.com/apache/spark/pull/57396
### What changes were proposed in this pull request?
Adds a new physical rule `PushDownLocalSort`, wired into both the AQE `queryStagePreparationRules` and the non-AQE `QueryExecution` preparations (right after `EnsureRequirements`, before `CombineAdjacentAggregation`), gated by a new internal config `spark.sql.execution.pushDownLocalSort` (default `true`).
`EnsureRequirements` inserts one local `SortExec(global = false)` above every operator whose `requiredChildOrdering` is not satisfied. When two such requirements are in a prefix-cover relationship, a stage computes multiple local sorts that only differ in width. The rule pushes the wider local sort down through order-preserving operators onto the narrower one below, widening it so a single sort serves both operators and the redundant upper sort is dropped.
For example, a sort aggregate stacked on a window over the same clustering keys:
```
SortAggregate(key = [a, b, c])
Sort([a, b, c], global = false) <- upper, wider
Window([a], [b])
Sort([a, b], global = false) <- lower, narrower
Exchange(hashpartitioning([a]))
```
becomes:
```
SortAggregate(key = [a, b, c])
Window([a], [b]) requiredChildOrdering [a, b] satisfied by [a, b, c]
Sort([a, b, c], global = false) <- single sort now serves both operators
Exchange(hashpartitioning([a]))
```
Order-preserving operators traversed: `ProjectExec`, `FilterExec`, `SortAggregateExec`, `WindowExecBase`, `WindowGroupLimitExec`. When one renames an ordering column in its output (`b AS x`), the ordering is rewritten from the operator's output space back to its child's space as it is pushed through (plain renames only). The rule never crosses a shuffle or a non-order-preserving operator.
`CollectMetricsExec` is intentionally excluded: it observes rows in input order, so widening a sort under it would silently change order-sensitive observed metrics (`first`/`last`/`collect_list`).
This is complementary to `RemoveRedundantSorts`, which only removes a sort already satisfied by its child; it never moves a wider sort down to absorb a narrower one.
### Why are the changes needed?
Stacked windows, or a sort aggregate over a window with prefix-compatible ordering requirements, compute several local sorts that a single wider sort could satisfy. Reusing the widest sort saves the redundant sorting work in the stage.
### Does this PR introduce _any_ user-facing change?
No. It only removes redundant local sorts from physical plans; query results are unchanged. Guarded by `spark.sql.execution.pushDownLocalSort`.
### How was this patch tested?
New `PushDownLocalSortSuite` (AQE on/off variants) with:
- positive SQL cases: stacked windows, filter above the sorts, window to sort aggregate, renaming project;
- negative SQL cases: disjoint orderings, a shuffle between the sorts, sort-direction mismatch, a project that computes the ordering column;
- plan-level cases: multi-operator chain, renaming-project rewrite, three stacked sorts in one pass.
Verified the TPCDS/TPCH `PlanStability` golden plans are unchanged.
### Was this patch authored or co-authored using generative AI tooling?
Generated-by: Claude Code (Opus 4.8)
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3626874935
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.aggregate.SortAggregateExec
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When an operator on the path renames an ordering column in its output (a `ProjectExec` with
+ * `b AS x`, or a `SortAggregateExec` whose result renames a grouping key), the ordering is
+ * rewritten from the operator's output space back to its child's space (`x` -> `b`) as it is
+ * pushed through, so a sort over the renamed column is still matched below. Only plain renames
+ * are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // Some order-preserving operators rename ordering columns in their output (a `ProjectExec`
+ // with `b AS x`, or a `SortAggregateExec` whose result renames a grouping key). Rewrite
+ // `upperOrder` from the operator's output space back to its child's space before pushing
+ // further down. Only plain renames are followed; an expression alias leaves the sort key
+ // referencing an output attribute the child does not produce, so the check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case a: SortAggregateExec => a.resultExpressions
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
+ case _: SortAggregateExec => true
Review Comment:
Agreed, and thanks for the careful trace — your reasoning is exactly right. I verified it three ways (constructed plans, a plan-level probe with the window and aggregate co-partitioned so no shuffle separates them, and the general argument): to push through a `SortAggregateExec`, line 118 forces the ordering to prefix-cover the grouping keys and line 119 forces every key to be a child column, but the aggregate’s child is already sorted by the full grouping keys, and any extra column would be an aggregate result absent from `child.outputSet`. So the pushed ordering can never be strictly wider than the sort `EnsureRequirements` places directly beneath the aggregate — the branch never fires.
Dropped `SortAggregateExec` from `isOrderPreserving` and removed the `resultExpressions` rename path. The canonical window-to-sort-aggregate test still passes: there the aggregate is the top consumer and the push-down traverses the `Window`, so the aggregate itself is never traversed.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5043938042
Thanks for addressing the review, @ulysses-you — re-checked through `b6503d817a0`; my findings 1-3 (window order-sensitivity documented, the neutralized window test, the dead `SortAggregateExec` branch) are all resolved, nothing new from me.
<!-- ai-code-review -->
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b closed pull request #57396: [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage
URL: https://github.com/apache/spark/pull/57396
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3622038437
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.aggregate.SortAggregateExec
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When an operator on the path renames an ordering column in its output (a `ProjectExec` with
+ * `b AS x`, or a `SortAggregateExec` whose result renames a grouping key), the ordering is
+ * rewritten from the operator's output space back to its child's space (`x` -> `b`) as it is
+ * pushed through, so a sort over the renamed column is still matched below. Only plain renames
+ * are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // Some order-preserving operators rename ordering columns in their output (a `ProjectExec`
+ // with `b AS x`, or a `SortAggregateExec` whose result renames a grouping key). Rewrite
+ // `upperOrder` from the operator's output space back to its child's space before pushing
+ // further down. Only plain renames are followed; an expression alias leaves the sort key
+ // referencing an output attribute the child does not produce, so the check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case a: SortAggregateExec => a.resultExpressions
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
+ case _: SortAggregateExec => true
+ case _: WindowExecBase => true
Review Comment:
Widening the sort that feeds a window changes the row order the window sees *within ties of its own `ORDER BY`*. For order-sensitive window functions that's observable:
- `collect_list`/`collect_set`/`first_value`/`last_value`/`nth_value` collect/pick in input order;
- `lead`/`lag` and aggregates with a `ROWS` frame depend on physical adjacency;
- a `row_number()`-based `WindowGroupLimitExec` keeps a *different set* of rows when ties reorder.
Example: `collect_list(c) OVER (PARTITION BY a ORDER BY b)` stacked under a wider window that needs `[a, b, c]`. Today the collect_list window sorts by `[a, b]`; after this rule it sorts by `[a, b, c]`, so within equal `b` the list follows `c`.
These are all non-deterministic over a non-unique `ORDER BY`, so it isn't *wrong* per Spark's contract -- but it's exactly the order-sensitivity you use to keep `CollectMetricsExec` out of `isOrderPreserving` (and the reason cited in the PR description). So the description's "query results are unchanged" holds for deterministic queries but not for these, and the line between "exclude CollectMetrics" and "push through a window carrying `first`/`last`/`collect_list`" is hard to defend.
Two asks: (1) soften that claim in the description; (2) decide whether a window carrying an order-sensitive function should be treated like `CollectMetricsExec`. If you deliberately keep them in (they're non-deterministic anyway), a one-line comment here explaining why the window case is acceptable while CollectMetrics isn't would settle it for the next reader.
##########
sql/core/src/test/scala/org/apache/spark/sql/execution/PushDownLocalSortSuite.scala:
##########
@@ -0,0 +1,320 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.DataFrame
+import org.apache.spark.sql.catalyst.expressions.{Alias, Ascending, AttributeReference, IsNotNull, SortOrder}
+import org.apache.spark.sql.catalyst.plans.physical.UnspecifiedDistribution
+import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanHelper, DisableAdaptiveExecutionSuite, EnableAdaptiveExecutionSuite}
+import org.apache.spark.sql.execution.exchange.ValidateRequirements
+import org.apache.spark.sql.internal.SQLConf
+import org.apache.spark.sql.test.SharedSparkSession
+import org.apache.spark.sql.types.IntegerType
+
+
+abstract class PushDownLocalSortSuiteBase
+ extends SharedSparkSession
+ with AdaptiveSparkPlanHelper {
+
+ private def checkNumSorts(df: DataFrame, count: Int): Unit = {
+ val plan = df.queryExecution.executedPlan
+ assert(collectWithSubqueries(plan) { case s: SortExec => s }.length == count)
+ }
+
+ private def checkSorts(query: String, enabledCount: Int, disabledCount: Int): Unit = {
+ withSQLConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED.key -> "true") {
+ val df = sql(query)
+ checkNumSorts(df, enabledCount)
+ val result = df.collect()
+ withSQLConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED.key -> "false") {
+ val df = sql(query)
+ checkNumSorts(df, disabledCount)
+ checkAnswer(df, result)
+ }
+ }
+ }
+
+ test("Push a wider local sort down across stacked windows with prefix-compatible order specs") {
+ withTempView("t") {
+ spark.range(100).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ // The narrower window (order by b) is listed first, so it is planned closest to the leaf and
+ // the wider window (order by b, c) ends up above it. Without the rule two local sorts
+ // ([a, b] below the inner window, [a, b, c] above it) are computed. The rule widens the
+ // lower sort to [a, b, c] so it serves both windows and drops the upper sort, leaving a
+ // single [a, b, c] sort.
+ val query =
+ """
+ |SELECT a, b, c,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn
+ |FROM t
+ |""".stripMargin
+ checkSorts(query, 1, 2)
+ }
+ }
+
+ test("No-op when the wider sort is already below the narrower one") {
+ withTempView("t") {
+ spark.range(100).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ // The wider window (order by b, c) is listed first, so it is planned closest to the leaf and
+ // the narrower window (order by b) ends up above it. `EnsureRequirements` inserts only one
+ // sort here: the wider window's [a, b, c] sort already satisfies the narrower window's
+ // [a, b] requirement, so no second sort is added. This rule only pushes a wider sort down,
+ // so it does not fire; the single sort is unchanged whether it is on or off.
+ val query =
+ """
+ |SELECT a, b, c,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk
+ |FROM t
+ |""".stripMargin
+ checkSorts(query, 1, 1)
+ }
+ }
+
+ test("Push-down still applies and stays correct with a filter on a window output") {
+ withTempView("t") {
+ spark.range(200).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ val query =
+ """
+ |SELECT * FROM (
+ | SELECT a, b, c,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn
+ | FROM t
+ |) WHERE rn > 1
+ |""".stripMargin
+ // The filter on rn sits above both windows and does not affect the two sorts that feed them,
+ // so the push-down still reduces 2 sorts to 1 and the results are unchanged.
+ checkSorts(query, 1, 2)
+ }
+ }
+
+ test("Push a wider sort down through a window to feed a sort aggregate above it") {
+ withTempView("t") {
+ spark.range(200).selectExpr("id % 10 as a", "id % 7 as b", "id % 5 as c")
Review Comment:
Good case, but the data neutralizes the risk it looks like it's testing. Within any `(a, b)` group every row has the same `c`: ids sharing `(id%10, id%7)` differ by multiples of `lcm(10,7)=70`, and `70 % 5 == 0`, so `id % 5` is constant per `(a, b)`. Widening the window's sort from `[a, b]` to `[a, b, c]` therefore can't reorder within-`(a,b)` ties, so `row_number` comes out identical with the rule on and off and `checkAnswer` passes by construction.
If `c` actually varied within `(a, b)`, the `[a,b,c]` sort would reorder ties and `row_number` would differ between the two configs -- which would make this comparison flaky rather than catch a bug. So this test can't observe the order change from the window comment. Worth either a note here, or a companion test that asserts the sort count drops while using a tie-safe function (`rank`/`dense_rank`) or a unique key, so the result stays stable even when ties genuinely reorder.
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.aggregate.SortAggregateExec
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When an operator on the path renames an ordering column in its output (a `ProjectExec` with
+ * `b AS x`, or a `SortAggregateExec` whose result renames a grouping key), the ordering is
+ * rewritten from the operator's output space back to its child's space (`x` -> `b`) as it is
+ * pushed through, so a sort over the renamed column is still matched below. Only plain renames
+ * are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // Some order-preserving operators rename ordering columns in their output (a `ProjectExec`
+ // with `b AS x`, or a `SortAggregateExec` whose result renames a grouping key). Rewrite
+ // `upperOrder` from the operator's output space back to its child's space before pushing
+ // further down. Only plain renames are followed; an expression alias leaves the sort key
+ // referencing an output attribute the child does not produce, so the check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case a: SortAggregateExec => a.resultExpressions
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
+ case _: SortAggregateExec => true
Review Comment:
I couldn't construct a plan where traversing a `SortAggregateExec` here actually enables a widening. To push `upperOrder` through it, line 118 requires it to satisfy the grouping-key ordering and line 119 requires every key to be a child column -- together that forces `upperOrder` to be a prefix-cover of the grouping keys and nothing wider, because any extra output column is an aggregate result that fails the `subsetOf(child.outputSet)` check. But the aggregate already requires its input sorted by the full grouping keys, so `EnsureRequirements` places that sort directly beneath it; there's no strictly-narrower lower sort left for `upperOrder` to widen.
If that's right, the `SortAggregateExec` branch (here, plus the `resultExpressions` rewrite at line 104) never contributes to a real push-down, and dropping it would shrink the surface the rule must be trusted over. If you do have a firing case in mind, could you add a test? The `resultExpressions` rename path and the `WindowGroupLimitExec` traversal are both currently uncovered.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5041981661
Thanks for the approval @sunchao! Addressed both non-blocking [P3] follow-ups:
- **Synced the PR description with the final code** — removed `SortAggregateExec` from the traversed operators, and documented that `FilterExec`/`WindowGroupLimitExec` are crossed only when `spark.sql.execution.pushDownLocalSort.throughCardinalityReducer` (default `false`) is enabled, plus the determinism guard on project/filter.
- **Strengthened the AQE assertion** (`b6503d817a0`) — `checkNumSorts` now executes the query before inspecting the plan, so under AQE it checks the final adaptive plan (after query-stage materialization/replanning) rather than the initial plan.
The `WindowGroupLimitExec` coverage suggestion from the earlier thread: it is now gated behind the reducer config and covered indirectly by the reducer-gating test; happy to add a dedicated `WindowGroupLimitExec` traversal test if you think it is worth it.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3626874013
##########
sql/core/src/test/scala/org/apache/spark/sql/execution/PushDownLocalSortSuite.scala:
##########
@@ -0,0 +1,320 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.DataFrame
+import org.apache.spark.sql.catalyst.expressions.{Alias, Ascending, AttributeReference, IsNotNull, SortOrder}
+import org.apache.spark.sql.catalyst.plans.physical.UnspecifiedDistribution
+import org.apache.spark.sql.execution.adaptive.{AdaptiveSparkPlanHelper, DisableAdaptiveExecutionSuite, EnableAdaptiveExecutionSuite}
+import org.apache.spark.sql.execution.exchange.ValidateRequirements
+import org.apache.spark.sql.internal.SQLConf
+import org.apache.spark.sql.test.SharedSparkSession
+import org.apache.spark.sql.types.IntegerType
+
+
+abstract class PushDownLocalSortSuiteBase
+ extends SharedSparkSession
+ with AdaptiveSparkPlanHelper {
+
+ private def checkNumSorts(df: DataFrame, count: Int): Unit = {
+ val plan = df.queryExecution.executedPlan
+ assert(collectWithSubqueries(plan) { case s: SortExec => s }.length == count)
+ }
+
+ private def checkSorts(query: String, enabledCount: Int, disabledCount: Int): Unit = {
+ withSQLConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED.key -> "true") {
+ val df = sql(query)
+ checkNumSorts(df, enabledCount)
+ val result = df.collect()
+ withSQLConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED.key -> "false") {
+ val df = sql(query)
+ checkNumSorts(df, disabledCount)
+ checkAnswer(df, result)
+ }
+ }
+ }
+
+ test("Push a wider local sort down across stacked windows with prefix-compatible order specs") {
+ withTempView("t") {
+ spark.range(100).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ // The narrower window (order by b) is listed first, so it is planned closest to the leaf and
+ // the wider window (order by b, c) ends up above it. Without the rule two local sorts
+ // ([a, b] below the inner window, [a, b, c] above it) are computed. The rule widens the
+ // lower sort to [a, b, c] so it serves both windows and drops the upper sort, leaving a
+ // single [a, b, c] sort.
+ val query =
+ """
+ |SELECT a, b, c,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn
+ |FROM t
+ |""".stripMargin
+ checkSorts(query, 1, 2)
+ }
+ }
+
+ test("No-op when the wider sort is already below the narrower one") {
+ withTempView("t") {
+ spark.range(100).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ // The wider window (order by b, c) is listed first, so it is planned closest to the leaf and
+ // the narrower window (order by b) ends up above it. `EnsureRequirements` inserts only one
+ // sort here: the wider window's [a, b, c] sort already satisfies the narrower window's
+ // [a, b] requirement, so no second sort is added. This rule only pushes a wider sort down,
+ // so it does not fire; the single sort is unchanged whether it is on or off.
+ val query =
+ """
+ |SELECT a, b, c,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk
+ |FROM t
+ |""".stripMargin
+ checkSorts(query, 1, 1)
+ }
+ }
+
+ test("Push-down still applies and stays correct with a filter on a window output") {
+ withTempView("t") {
+ spark.range(200).selectExpr("id % 10 as a", "id % 7 as b", "id as c")
+ .createOrReplaceTempView("t")
+ val query =
+ """
+ |SELECT * FROM (
+ | SELECT a, b, c,
+ | RANK() OVER (PARTITION BY a ORDER BY b) AS rk,
+ | ROW_NUMBER() OVER (PARTITION BY a ORDER BY b, c) AS rn
+ | FROM t
+ |) WHERE rn > 1
+ |""".stripMargin
+ // The filter on rn sits above both windows and does not affect the two sorts that feed them,
+ // so the push-down still reduces 2 sorts to 1 and the results are unchanged.
+ checkSorts(query, 1, 2)
+ }
+ }
+
+ test("Push a wider sort down through a window to feed a sort aggregate above it") {
+ withTempView("t") {
+ spark.range(200).selectExpr("id % 10 as a", "id % 7 as b", "id % 5 as c")
Review Comment:
You are right — I confirmed `count(distinct c)` per `(a, b)` is `1` for that data (`lcm(10,7)=70`, `70 % 5 == 0`), so the widening could not reorder any tie and the check passed trivially. Fixed: switched to `id % 13` for `c`, which varies within `(a, b)` (`70 % 13 != 0`), and changed the window function to the tie-safe `RANK()`. Now the `[a,b]`->`[a,b,c]` widening genuinely reorders rows within the window's `ORDER BY b` ties, while `RANK()` keeps the result stable — so the test exercises the reorder and still verifies correctness plus the sort-count drop. Added a comment explaining the data choice.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5048256210
Thank you @ulysses-you and @sunchao @peter-toth!
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5040957969
Thanks for the thorough review @peter-toth! Addressed all three in `2b05aa93ee0`:
1. **Window order-sensitivity** — kept on purpose (only refines tie order for a non-unique window `ORDER BY`, already non-deterministic), documented the distinction from `CollectMetricsExec` at the `isOrderPreserving` entries, and softened the PR description.
2. **Window-to-sort-aggregate test** — the old data had `c` constant within `(a, b)`; switched to `id % 13` + tie-safe `RANK()` so the widening genuinely reorders window ties while the result stays stable.
3. **`SortAggregateExec` branch** — confirmed unreachable and removed it (and the `resultExpressions` rename path); the canonical case traverses the `Window`, not the aggregate.
Replied inline with details on each.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5041715547
Thanks @sunchao! Addressed both in `dd42f7318f7`:
- **[P1] Non-deterministic project/filter** — reproduced (the sort was pushed below `Project[..., rand(0)]`). Now gated on determinism, mirroring `EliminateSorts.canEliminateSort`: `ProjectExec` on `projectList.forall(_.deterministic)`, `FilterExec` on `condition.deterministic`.
- **[P2] Cardinality reducers** — made crossing `FilterExec`/`WindowGroupLimitExec` opt-in via a new internal config `spark.sql.execution.pushDownLocalSort.throughCardinalityReducer` (default `false`), so by default the rule never moves the wider sort below a selective reducer.
Added plan-level tests for both (non-deterministic project/filter left unchanged; filter crossed only when the reducer config is on). Replied inline with details.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5032677443
cc @viirya @cloud-fan @peter-toth @sunchao if you have time to take a look, thank you
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #57396:
URL: https://github.com/apache/spark/pull/57396#issuecomment-5048264864
**Merge Summary:**
- merged into master https://github.com/apache/spark/commit/589adcb9b0b4ee247d37acadd851baac776a5a91
- merged into branch-4.x https://github.com/apache/spark/commit/6567619c0205f16d94633840eca5454fac70c9a0
*Posted by `merge_spark_pr.py`*
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3627387267
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When a `ProjectExec` on the path renames an ordering column in its output (`b AS x`), the
+ * ordering is rewritten from the project's output space back to its child's space (`x` -> `b`) as
+ * it is pushed through, so a sort over the renamed column is still matched below. Only plain
+ * renames are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // A `ProjectExec` may rename ordering columns in its output (`b AS x`). Rewrite `upperOrder`
+ // from the operator's output space back to its child's space before pushing further down, so
+ // a sort over the renamed column is still matched below. Only plain renames are followed; an
+ // expression alias leaves the sort key referencing an output attribute the child does not
+ // produce, so the `subsetOf(op.child.outputSet)` check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
Review Comment:
Great catch — reproduced it (`Sort[a,b] -> Project[a,b,rand(0)] -> Sort[a]` did push the sort below the project). Fixed by mirroring `EliminateSorts.canEliminateSort`: `ProjectExec` is now gated on `projectList.forall(_.deterministic)` and `FilterExec` on `condition.deterministic`. Added plan-level tests that a non-deterministic project and a non-deterministic filter are both left unchanged.
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When a `ProjectExec` on the path renames an ordering column in its output (`b AS x`), the
+ * ordering is rewritten from the project's output space back to its child's space (`x` -> `b`) as
+ * it is pushed through, so a sort over the renamed column is still matched below. Only plain
+ * renames are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // A `ProjectExec` may rename ordering columns in its output (`b AS x`). Rewrite `upperOrder`
+ // from the operator's output space back to its child's space before pushing further down, so
+ // a sort over the renamed column is still matched below. Only plain renames are followed; an
+ // expression alias leaves the sort key referencing an output attribute the child does not
+ // produce, so the `subsetOf(op.child.outputSet)` check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
Review Comment:
Agreed. I made crossing the cardinality reducers opt-in: `FilterExec` and `WindowGroupLimitExec` are now only traversed when a new internal config `spark.sql.execution.pushDownLocalSort.throughCardinalityReducer` is enabled (default `false`), so by default the rule stops at them and never moves the wider sort below a selective reducer. Added tests that a filter is not crossed by default and is crossed only when the config is on.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "sunchao (via GitHub)" <gi...@apache.org>.
sunchao commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3627223677
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When a `ProjectExec` on the path renames an ordering column in its output (`b AS x`), the
+ * ordering is rewritten from the project's output space back to its child's space (`x` -> `b`) as
+ * it is pushed through, so a sort over the renamed column is still matched below. Only plain
+ * renames are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // A `ProjectExec` may rename ordering columns in its output (`b AS x`). Rewrite `upperOrder`
+ // from the operator's output space back to its child's space before pushing further down, so
+ // a sort over the renamed column is still matched below. Only plain renames are followed; an
+ // expression alias leaves the sort key referencing an output attribute the child does not
+ // produce, so the `subsetOf(op.child.outputSet)` check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
Review Comment:
**[P1] Keep the sort above nondeterministic projects and filters**
These two cases are treated as order-preserving regardless of expression determinism. A reachable shape is `Sort[a,b] -> Project[a,b,rand(0)] -> Sort[a]`: with this rule disabled, the seeded random stream is evaluated after the narrow sort; with it enabled, the `[a,b]` sort moves below the project, so different rows consume each random value. The analogous `Filter(rand(0) < 0.5)` shape can retain a different set of rows.
This is the same semantic hazard that `EliminateSorts.canEliminateSort` guards with `p.projectList.forall(_.deterministic)` and `f.condition.deterministic`. Please mirror those checks here (or exclude `FilterExec` as suggested separately) and add enabled/disabled result tests using a seeded nondeterministic expression.
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,140 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When a `ProjectExec` on the path renames an ordering column in its output (`b AS x`), the
+ * ordering is rewritten from the project's output space back to its child's space (`x` -> `b`) as
+ * it is pushed through, so a sort over the renamed column is still matched below. Only plain
+ * renames are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // A `ProjectExec` may rename ordering columns in its output (`b AS x`). Rewrite `upperOrder`
+ // from the operator's output space back to its child's space before pushing further down, so
+ // a sort over the renamed column is still matched below. Only plain renames are followed; an
+ // expression alias leaves the sort key referencing an output attribute the child does not
+ // produce, so the `subsetOf(op.child.outputSet)` check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
Review Comment:
**[P2] Avoid widening the large-input sort below a selective reducer**
Crossing `FilterExec` here (and `WindowGroupLimitExec` below) can reverse the intended cost improvement. For stacked windows, the disabled plan can sort `N` rows by narrow `[a,b]`, reduce to `R` rows, and sort only those survivors by `[a,b,c]`; this rewrite instead sorts all `N` rows by `[a,b,c]` before the reduction. With `rn = 1` or a selective rank predicate, `R << N`, and suffix width plus reduction ratio can make the default-on regression arbitrarily large relative to the removed survivor sort.
Please initially stop at `FilterExec` and `WindowGroupLimitExec`, or require a reliable cardinality/cost proof before crossing them. Negative plan tests for a selective predicate and `rn = 1` would cover both paths.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org
Re: [PR] [SPARK-58233][SQL] Push down local sort to reduce redundant sorts within a stage [spark]
Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57396:
URL: https://github.com/apache/spark/pull/57396#discussion_r3626873262
##########
sql/core/src/main/scala/org/apache/spark/sql/execution/PushDownLocalSort.scala:
##########
@@ -0,0 +1,136 @@
+/*
+ * Licensed to the Apache Software Foundation (ASF) under one or more
+ * contributor license agreements. See the NOTICE file distributed with
+ * this work for additional information regarding copyright ownership.
+ * The ASF licenses this file to You under the Apache License, Version 2.0
+ * (the "License"); you may not use this file except in compliance with
+ * the License. You may obtain a copy of the License at
+ *
+ * http://www.apache.org/licenses/LICENSE-2.0
+ *
+ * Unless required by applicable law or agreed to in writing, software
+ * distributed under the License is distributed on an "AS IS" BASIS,
+ * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
+ * See the License for the specific language governing permissions and
+ * limitations under the License.
+ */
+
+package org.apache.spark.sql.execution
+
+import org.apache.spark.sql.catalyst.expressions.{Alias, Attribute, AttributeMap, AttributeReference, AttributeSet, SortOrder}
+import org.apache.spark.sql.catalyst.rules.Rule
+import org.apache.spark.sql.execution.aggregate.SortAggregateExec
+import org.apache.spark.sql.execution.window.{WindowExecBase, WindowGroupLimitExec}
+import org.apache.spark.sql.internal.SQLConf
+
+/**
+ * Pushes a wider local sort down through order-preserving operators onto a narrower local sort
+ * below, widening it so that a single sort satisfies several operators' ordering requirements
+ * instead of re-sorting once per operator.
+ *
+ * `EnsureRequirements` adds one local `SortExec` (`global = false`) above every operator whose
+ * `requiredChildOrdering` is not already satisfied. When such requirements are in a prefix-cover
+ * relationship, this produces multiple local sorts that only differ in width. A canonical case is a
+ * sort aggregate stacked on a window over the same clustering keys, where the aggregate needs a
+ * wider ordering than the window:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Sort([a, b, c], global = false) <- upper, wider
+ * Window([a], [b])
+ * Sort([a, b], global = false) <- lower, narrower
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * Because every operator between the two sorts is order-preserving and the upper ordering
+ * prefix-covers everything required along the way, the wider ordering can be pushed down to widen
+ * the lower sort, and the upper sort then dropped entirely:
+ *
+ * {{{
+ * SortAggregate(key = [a, b, c])
+ * Window([a], [b]) requiredChildOrdering [a, b] is satisfied by [a, b, c]
+ * Sort([a, b, c], global = false) <- single sort now serves both operators
+ * Exchange(hashpartitioning([a]))
+ * }}}
+ *
+ * When an operator on the path renames an ordering column in its output (a `ProjectExec` with
+ * `b AS x`, or a `SortAggregateExec` whose result renames a grouping key), the ordering is
+ * rewritten from the operator's output space back to its child's space (`x` -> `b`) as it is
+ * pushed through, so a sort over the renamed column is still matched below. Only plain renames
+ * are followed, and the rule never crosses a shuffle or a non-order-preserving operator.
+ */
+object PushDownLocalSort extends Rule[SparkPlan] {
+
+ def apply(plan: SparkPlan): SparkPlan = {
+ if (!conf.getConf(SQLConf.PUSH_DOWN_LOCAL_SORT_ENABLED)) {
+ return plan
+ }
+
+ plan.transform {
+ case upper @ SortExec(upperOrder, false, child, _) =>
+ pushDown(child, upperOrder).getOrElse(upper)
+ }
+ }
+
+ /**
+ * Walks down from `plan` through a chain of order-preserving unary operators, looking for a
+ * lower local `SortExec` that `upperOrder` strictly covers. When found, widens that lower sort
+ * to `upperOrder` and returns the rebuilt subtree (which re-exposes `upperOrder` at its top);
+ * returns `None` if no safe widening applies, leaving the plan untouched. As it crosses an
+ * operator that renames ordering columns, `upperOrder` is rewritten into that operator's child
+ * space so the search continues against the child's own attributes.
+ */
+ private def pushDown(
+ plan: SparkPlan,
+ upperOrder: Seq[SortOrder]): Option[SparkPlan] = plan match {
+ case lower @ SortExec(lowerOrder, false, _, _)
+ // Only widen when the upper ordering strictly covers the lower one. When they are
+ // equivalent the upper sort is plainly redundant and is left to `RemoveRedundantSorts`; a
+ // non-covering ordering cannot serve the lower requirement. The column check keeps the
+ // widened sort well-formed (every key of `upperOrder` is available below the lower sort).
+ if SortOrder.orderingSatisfies(upperOrder, lowerOrder) &&
+ !SortOrder.orderingSatisfies(lowerOrder, upperOrder) &&
+ AttributeSet(upperOrder.flatMap(_.references)).subsetOf(lower.child.outputSet) =>
+ Some(SortExec(upperOrder, global = false, child = lower.child))
+
+ case op: UnaryExecNode if isOrderPreserving(op) =>
+ // Some order-preserving operators rename ordering columns in their output (a `ProjectExec`
+ // with `b AS x`, or a `SortAggregateExec` whose result renames a grouping key). Rewrite
+ // `upperOrder` from the operator's output space back to its child's space before pushing
+ // further down. Only plain renames are followed; an expression alias leaves the sort key
+ // referencing an output attribute the child does not produce, so the check below rejects it.
+ val outputExprs = plan match {
+ case p: ProjectExec => p.projectList
+ case a: SortAggregateExec => a.resultExpressions
+ case _ => Nil
+ }
+ val rewrittenUpperOrder = if (outputExprs.isEmpty) {
+ upperOrder
+ } else {
+ val aliasToAttributeMap = AttributeMap(outputExprs.collect {
+ case a @ Alias(child: AttributeReference, _) => (a.toAttribute, child: Attribute)
+ })
+ upperOrder.map { _.transformUp {
+ case a: Attribute => aliasToAttributeMap.getOrElse(a, a)
+ }.asInstanceOf[SortOrder]
+ }
+ }
+ if (SortOrder.orderingSatisfies(rewrittenUpperOrder, op.requiredChildOrdering.head) &&
+ AttributeSet(rewrittenUpperOrder.flatMap(_.references)).subsetOf(op.child.outputSet)) {
+ pushDown(op.child, rewrittenUpperOrder).map(newChild => op.withNewChildren(Seq(newChild)))
+ } else {
+ None
+ }
+
+ case _ => None
+ }
+
+ private def isOrderPreserving(plan: UnaryExecNode): Boolean = plan match {
+ case _: ProjectExec => true
+ case _: FilterExec => true
+ case _: SortAggregateExec => true
+ case _: WindowExecBase => true
Review Comment:
Good point, thanks. I kept pushing through windows on purpose: it only refines the tie order for a non-unique window `ORDER BY`, which is already non-deterministic per Spark's contract, so no deterministic result changes. That is genuinely different from `CollectMetricsExec`, whose observed metric is an expected-stable side output rather than a non-deterministic query result — so I keep that one excluded.
I added a comment at the `WindowExecBase`/`WindowGroupLimitExec` entries in `isOrderPreserving` spelling out exactly this distinction, and softened the PR description: "query results are unchanged" -> "the result of a deterministic query is unchanged", plus an explicit note that order-sensitive window functions over a non-unique `ORDER BY` may return a different (still valid) non-deterministic result.
--
This is an automated message from the Apache Git Service.
To respond to the message, please log on to GitHub and use the
URL above to go to the specific comment.
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For queries about this service, please contact Infrastructure at:
users@infra.apache.org
---------------------------------------------------------------------
To unsubscribe, e-mail: reviews-unsubscribe@spark.apache.org
For additional commands, e-mail: reviews-help@spark.apache.org