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/08/13 08:58:10 UTC

[PR] [SPARK-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

ulysses-you opened a new pull request, #57986:
URL: https://github.com/apache/spark/pull/57986

   ### What changes were proposed in this pull request?
   
   Currently, `CollapseWindow` collapses two adjacent `Window` operators only when their partition specs and order specs are identical. This PR relaxes it to also merge two windows with the same partition spec when **one of them has an empty order spec**, as long as every window expression of the empty-order window is order-insensitive.
   
   A window expression is treated as order-insensitive when its frame is the whole partition (`ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING`): such a frame always covers every row of the partition regardless of the ordering, so aggregates like `count`/`sum`/`min`/`max` give the same value under any ordering, and functions whose result does depend on the row order (e.g. `collect_list`, `first`) are non-deterministic when the order spec is empty, so evaluating them under any ordering yields a valid result. Windows with a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) are order-sensitive and are never merged.
   
   The merged window keeps the non-empty order spec of the other window.
   
   ### Why are the changes needed?
   
   For queries that mix an ordered window function with an unordered aggregate over the same partition, e.g.:
   
   ```sql
   SELECT c2, c1,
          row_number() OVER (PARTITION BY c1 ORDER BY c2) AS rk,
          count(1)     OVER (PARTITION BY c1)
   FROM t3
   ```
   
   the current rule keeps two `Window` operators even though they share `PARTITION BY c1`. After this change they are collapsed into a single window operator, saving one `WindowExec` pass (the `[c1, c2]` sort is already shared in both plans). A local benchmark on 4M rows showed roughly 16% faster runtime in the non-spill case and 20% in the spill case.
   
   ### Does this PR introduce _any_ user-facing change?
   
   The query result is unchanged for the common shape (the empty-order window written after the ordered one), where the merge does not change the input order of any window expression. When the empty-order window appears before an ordered sibling in the SELECT list, the merge evaluates its expressions under the sibling's order; for functions documented as non-deterministic without an order (`first`, `last`, `collect_list`) the value may differ, which is already allowed by their contract. FP `sum`/`avg` may also differ at the bit level, consistent with Spark's existing treatment of FP aggregation as order-sensitive (`EliminateSorts.isOrderIrrelevantAggs`).
   
   ### How was this patch tested?
   
   Added tests to `CollapseWindowSuite` covering:
   
   - collapse when the empty-order window has a whole-partition frame (`row_number` + `count`), including the case where it is the inner window;
   - collapse when the empty-order window has multiple window expressions;
   - collapse when the empty-order window has `first` over the whole partition;
   - the SPARK-34565 shape with a `Project` between the windows;
   - no collapse when the empty-order window has a bounded frame.
   
   Ran `CollapseWindowSuite` (13 tests) and `TransposeWindowSuite` (8 tests), all pass.
   
   ### Was this patch authored or co-authored using generative AI tooling?
   
   Yes, developed with assistance from Claude Code.
   
   Generated-by: Claude Code
   


-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "uros-b (via GitHub)" <gi...@apache.org>.
uros-b commented on PR #57986:
URL: https://github.com/apache/spark/pull/57986#issuecomment-5278897303

   LGTM, thank you @ulysses-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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you closed pull request #57986: [SPARK-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec
URL: https://github.com/apache/spark/pull/57986


-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57986:
URL: https://github.com/apache/spark/pull/57986#issuecomment-5289023971

   thank you @uros-b !, also cc @cloud-fan  @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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "zml1206 (via GitHub)" <gi...@apache.org>.
zml1206 commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3780381325


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   This check seems too broad. A whole-partition frame guarantees that the same rows are included, but it does not guarantee that every aggregate produces the same result under a different input order.
   In particular, floating-point Sum, Average, and CentralMomentAgg are order-sensitive because IEEE-754 arithmetic is not associative. For example:
   (1e16 + -1e16) + 1.0 = 1.0
   (1e16 + 1.0) + -1e16 = 0.0
   Merging an unordered window into an ordered one changes the order in which rows are fed to these aggregates, so it can change a deterministic query result. EliminateSorts.isOrderIrrelevantAggs already handles this by excluding Float/Double variants of these aggregates.
   Could we inspect the window function here instead of treating every whole-partition frame as order-insensitive, and add an execution-level regression test for floating-point sum?



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3780586185


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   I do not think we should concern that, otherwise we can not optimize any ordering related plan, such as eliminate sort,  a smj -> bhj/shj when the join is the child of a containing floating-point arithmetic Agg, also the result of sort-based agg is different with hash-based. So if people require an accurate result, they should use decimal type.



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3795076530


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =

Review Comment:
   Agreed a physical merge beside `PushDownLocalSort` would be architecturally cleaner — it runs after `InferWindowGroupLimit` and needs no order-insensitivity judgment. But that means moving the entire `CollapseWindow` rule to the physical plan (rebuilding `windowFrameExpressionFactoryPairs`, rewiring outputs), which is a much larger change. The WindowGroupLimit interaction it avoids is, like Finding 1, a pre-existing property of the logical rule (already present for same-order-spec merges), so I've kept the logical rule with the config as a targeted escape hatch.
   



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on PR #57986:
URL: https://github.com/apache/spark/pull/57986#issuecomment-5350610012

   **Merge Summary:**
   - merged into master https://github.com/apache/spark/commit/8565f0d2a6887e15f55c48b7a2d0e433f0beeaaa
   - merged into branch-4.x https://github.com/apache/spark/commit/14e89c142f94a0633c86150cfd1f7bd28cb240aa
   
   *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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3784879544


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are safe to evaluate under any row order. In that
+      // case, they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||

Review Comment:
   **Finding 1.** `InferWindowGroupLimit.isExpandingWindow` requires *every* window expression to carry `(RowFrame, UnboundedPreceding, CurrentRow)`:
   
   ```scala
   // InferWindowGroupLimit.scala:78
   case Alias(WindowExpression(windowFunction, WindowSpecDefinition(_, _,
   SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))), _)
     if !windowFunction.isInstanceOf[SizeBasedWindowFunction] => true
   ```
   
   `canEvaluateUnderAnyOrder` admits exactly the opposite upper bound, so any window this relaxation produces necessarily fails `windowExpressions.forall(isExpandingWindow)` at `InferWindowGroupLimit.scala:95` -- and that rule runs in `SparkOptimizer`'s "Infer window group limit" batch, i.e. after this one.
   
   The shape is reachable. `ExtractWindowExpressions` folds its `LinkedHashMap` in insertion order (`Analyzer.scala:3677`), so the first window spec in the select list becomes the innermost `Window`; writing the unordered aggregate first makes the ordered window the parent, which is what the `Filter` sits on. Measured on this head with a catalyst-only `RuleExecutor` over `Filter(rn <= 2, Window(rn, [c], [a desc], Window(cnt, [c], Nil, t)))`:
   
   ```
   CollapseWindow excluded:  WindowGroupLimit [c#2], [a#0 DESC], row_number(), 2
   CollapseWindow enabled:   <no WindowGroupLimit>
   ```
   
   Trading a per-partition early stop for one saved `WindowExec` pass is the wrong way round on a large partition. Relaxing `isExpandingWindow` is not the fix -- `WindowGroupLimit` drops rows *below* the window, which would change `count(1) OVER (PARTITION BY k)`.
   
   The cheap fix is to drop the child-empty branch and keep only the parent-empty one:
   
   ```scala
         (specCompatible(w1.orderSpec, w2.orderSpec) ||
           (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
             w1.windowExpressions.forall(canEvaluateUnderAnyOrder))) &&
   ```
   
   That direction cannot lose a `WindowGroupLimit`: the `Filter` then sits on the empty-order window, which already fails `orderSpec.nonEmpty` on base, so there is nothing to lose. It keeps the motivating example and the benchmark (`row_number()` written before `count(1)` puts the empty-order window on top), and it also settles the order-change question in @zml1206's thread -- see finding 3. If you want the child-empty direction too, it needs a conf so a regressed query has an escape hatch.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**

Review Comment:
   **Finding 6.** The object scaladoc just above (`Optimizer.scala:1753-1757`) still states the old precondition:
   
   ```
    * Collapse Adjacent Window Expression.
    * - If the partition specs and order specs are the same and the window expression are
    *   independent and are of the same window function type, collapse into the parent.
   ```
   
   Worth extending with the empty-order case -- that is the doc a reader hits first.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true

Review Comment:
   **Finding 7.** The frame type is left free here, so `RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING` merges as well. That is legal with an empty order spec -- `WindowSpecDefinition.checkInputDataTypes` only rejects a `RangeFrame` that is *not* unbounded (`windowExpressions.scala:74`) -- and it is correct, because `WindowEvaluatorFactoryBase` maps `("AGGREGATE", _, UnboundedPreceding, UnboundedFollowing, _)` to `UnboundedWindowFunctionFrame` regardless of frame type. But both the PR description and the scaladoc describe the case as `ROWS ...`, and no test covers `RANGE`. One extra case in the suite and a word in the doc would pin it down.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1776,13 +1806,19 @@ object CollapseWindow extends Rule[LogicalPlan] {
     _.containsPattern(WINDOW), ruleId) {
     case w1 @ Window(we1, _, _, w2 @ Window(we2, _, _, grandChild, _), _)
         if windowsCompatible(w1, w2) =>
-      w1.copy(windowExpressions = we2 ++ we1, child = grandChild)
+      w1.copy(
+        orderSpec = if (w1.orderSpec.nonEmpty) w1.orderSpec else w2.orderSpec,

Review Comment:
   **Finding 4.** After this the operator's `orderSpec` is non-empty while the merged-in expressions still carry `WindowSpecDefinition(partitionSpec, Nil, frame)`. That drops an invariant `ExtractWindowExpressions` sets up -- it keys the grouping on the *expression's* own `(partitionSpec, orderSpec, functionType)` (`Analyzer.scala:3667`), so until now the operator's spec always matched its expressions'. The sibling rule keeps the analogous field in sync rather than letting it drift:
   
   ```scala
   // EliminateWindowPartitions.scala:36 -- rewrites the expression's spec, not just the operator's
   val newWsd = wsd.copy(partitionSpec = ps.filter(!_.foldable))
   ```
   
   I traced the readers and nothing breaks today: only `WindowResolution` (analyzer, already run) and `OptimizeWindowFunctions` (`Optimizer.scala:1745`, which needs `orderSpec.nonEmpty` and so stays a no-op on the merged-in expression) look at a window expression's own order spec. So this is a "say why", not a "fix" -- a line in the rule comment noting the divergence is deliberate would help, because it is surprising in `EXPLAIN`. Worth knowing the flip side if you ever do sync them: `OptimizeWindowFunctions` would then rewrite an empty-order `first` to `nth_value(_, 1)`, which is the same value under the merged order.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =

Review Comment:
   **Finding 5.** (Alternative design, not a defect -- take it or leave it.)
   
   The safety argument is much easier to make one layer down. `PushDownLocalSort` (`spark.sql.execution.pushDownLocalSort`, default on since 4.3.0) already widens the lower local sort through an empty-order `WindowExec` and drops the upper one; its `isOrderPreserving` has `case _: WindowExecBase => true`, with a comment making essentially the argument this scaladoc makes. I confirmed on this head that the base plan for the child-empty shape is already a single `Sort [c1 ASC, c2 ASC]` feeding both windows, and that base and merged results are identical under the default conf.
   
   So a physical rule beside it could merge two adjacent `WindowExec`s whenever the lower one's `requiredChildOrdering` is already satisfied by what is actually below it. That shape:
   
   - needs no order-insensitivity judgement at all -- the orderings provably coincide, so `canEvaluateUnderAnyOrder` and the whole frame check disappear;
   - runs after `InferWindowGroupLimit`, so finding 1 does not arise (a `WindowGroupLimitExec` between the two windows simply blocks it);
   - gets the `Project`-between case for free, since `PushDownLocalSort` already walks through a deterministic `ProjectExec`.
   
   Counter-argument, and it is a real one: far more work than this two-line change -- `windowFrameExpressionFactoryPairs` has to be rebuilt for the merged operator and the output attributes rewired, and physical rules are harder to follow. I mainly wanted the option on record.
   



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/CollapseWindowSuite.scala:
##########
@@ -168,4 +173,164 @@ class CollapseWindowSuite extends PlanTest {
 
     comparePlans(optimized, correctAnswer)
   }
+
+  test("collapse windows when one has an empty order spec " +

Review Comment:
   **Finding 2.** All six new tests run `Optimize` = `CollapseWindow` + `CollapseProject`, so they assert that the merge happens and nothing about what the merged shape does to the rules that run after it -- which is where finding 1 lives. Two gaps:
   
   1. A case that runs `InferWindowGroupLimit` on the merged plan. `InferWindowGroupLimitSuite` already has the relation and the rule set to copy:
   
   ```scala
   val batches = Batch("...", FixedPoint(10),
     CollapseWindow, CollapseProject, RemoveNoopOperators, PushDownPredicates,
     InferWindowGroupLimit) :: Nil
   ```
   
   driven by `testRelation.window(Seq(cnt), Seq(c), Nil).window(Seq(rn), Seq(c), Seq(a.desc)).where($"rn" <= 2)`, asserting a `WindowGroupLimit` is still there.
   
   2. An execution-level result test, e.g. in `DataFrameWindowFunctionsSuite`. This rule now changes the row order an aggregate sees, and `CollapseWindowSuite` is a `PlanTest`, so nothing in this PR ever runs a merged window.
   



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3780764073


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   thank you, addressed!



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3784891087


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   Late here, and I'm not re-opening this -- @ulysses-you's answer on FP arithmetic reads fine to me. Two things I measured on this head that seem worth having on record.
   
   First, in @ulysses-you's favour: the exposure is narrower than it looks. `PushDownLocalSort` (`spark.sql.execution.pushDownLocalSort`, default on since 4.3.0) already widens the lower local sort through an empty-order `WindowExec`, so the base plan for the inner-window shape is already a single `Sort [c1 ASC, c2 ASC]` feeding both windows. With default confs I get identical results before and after this PR in both merge directions. `PushDownLocalSort.isOrderPreserving` even has `case _: WindowExecBase => true` with a comment making this PR's argument. That, rather than `EliminateSorts.isOrderIrrelevantAggs`, is the precedent I'd cite in the description -- as written, the description cites a helper that argues the other way.
   
   Second, a case the "use decimal type" answer doesn't cover. With `spark.sql.execution.pushDownLocalSort=false`, a *deterministic* Scala UDAF changes value:
   
   ```scala
   case class FirstBuf(seen: Boolean, value: Int)
   object FirstIntAgg extends Aggregator[Int, FirstBuf, Int] { /* returns the first row it sees */ }
   spark.udf.register("udaf_first", udaf(FirstIntAgg))
   ```
   
   ```sql
   SELECT DISTINCT c1, cl, fst, udafFst FROM (
     SELECT c1,
       collect_list(c2) OVER (PARTITION BY c1) AS cl,
       first(c2)        OVER (PARTITION BY c1) AS fst,
       udaf_first(c2)   OVER (PARTITION BY c1) AS udafFst,
       row_number() OVER (PARTITION BY c1 ORDER BY c2) AS rk
     FROM t3) WHERE rk >= 1
   ```
   
   ```
   base: [0, [8, 4, 2, 10, 6], 8, 8]
   PR:   [0, [2, 4, 6, 8, 10], 2, 2]
   ```
   
   `isOrderIrrelevantAggs` has `case _: UserDefinedExpression => false` for precisely this, and a user cannot switch a UDAF to decimal. Same for a pandas `GROUPED_AGG` UDF, which is deterministic unless marked otherwise.
   
   Worth noting the two merge directions are not equally exposed. When the empty-order window is the *parent* -- the shape in the PR description and the one the benchmark measures -- the merge cannot change anything: `WindowExecBase.requiredChildOrdering` for an empty order spec is just `[partitionSpec]`, which the ordered child window's `[partitionSpec ++ orderSpec]` output ordering already satisfies, so no sort is inserted and the row order is identical. I measured that direction as unchanged even with `pushDownLocalSort=false`. Everything above is the *child*-empty direction. So restricting the relaxation to the parent-empty case removes this question entirely -- and it also fixes a `WindowGroupLimit` regression I raised separately as finding 1.
   



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3795075763


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are safe to evaluate under any row order. In that
+      // case, they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||

Review Comment:
   Agreed the two directions are not equally safe, and that the child-empty merge is the one that can drop `WindowGroupLimit`. I've added `spark.sql.optimizer.collapseWindowWithEmptyOrderSpecInChild` (default false) as the escape hatch you suggested, so top-k queries keep `WindowGroupLimit` by default. I'm neutral on keeping that config, though — this interaction is pre-existing rather than new: `CollapseWindow` never checks frames, so the same loss already happens when merging two windows with the *same* order spec, e.g. `row_number() OVER (ORDER BY c)` + `count() OVER (ORDER BY c ROWS BETWEEN U..U)` under `WHERE rn <= 2`. The child-empty case is also narrow: the `count` window below already forces a full `[k]` shuffle + `[k,a]` sort.
   



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/CollapseWindowSuite.scala:
##########
@@ -168,4 +173,164 @@ class CollapseWindowSuite extends PlanTest {
 
     comparePlans(optimized, correctAnswer)
   }
+
+  test("collapse windows when one has an empty order spec " +

Review Comment:
   Added an execution-level test in `DataFrameWindowFunctionsSuite`, and a test in `InferWindowGroupLimitSuite` asserting the child-empty direction keeps `WindowGroupLimit` by default and drops it with the config on.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   Updated the description to cite `PushDownLocalSort.isOrderPreserving`.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1776,13 +1806,19 @@ object CollapseWindow extends Rule[LogicalPlan] {
     _.containsPattern(WINDOW), ruleId) {
     case w1 @ Window(we1, _, _, w2 @ Window(we2, _, _, grandChild, _), _)
         if windowsCompatible(w1, w2) =>
-      w1.copy(windowExpressions = we2 ++ we1, child = grandChild)
+      w1.copy(
+        orderSpec = if (w1.orderSpec.nonEmpty) w1.orderSpec else w2.orderSpec,

Review Comment:
   Added a comment noting the divergence is deliberate and why it's safe.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =

Review Comment:
   Agreed a physical merge beside `PushDownLocalSort` would be architecturally cleaner — it runs after `InferWindowGroupLimit` and needs no order-insensitivity judgment. But that means moving the entire `CollapseWindow` rule to the physical plan (rebuilding `windowFrameExpressionFactoryPairs`, rewiring outputs), which is a much larger change. The WindowGroupLimit interaction it avoids is, like Finding 1, a pre-existing property of the logical rule (already present for same-order-spec merges), so I've kept the logical rule with the config as a targeted escape hatch. Open to a follow-up for the physical merge.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**

Review Comment:
   Updated.
   



##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,39 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can still be evaluated correctly when the rows
+   * of the partition are reordered, so that it can be merged into another window with a different
+   * (non-empty) order spec.
+   *
+   * The frame determines whether reordering is safe. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so reordering changes only the order in which the rows
+   * are seen, never which rows are in the frame. Since the order spec of the window is empty,
+   * the query does not fix the row order, so evaluating its expressions under any ordering
+   * yields a valid result, even though the value may differ for order-dependent expressions
+   * such as `first`, `collect_list`, or floating-point `sum`/`avg`. On the other hand, a bounded
+   * frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is order-sensitive: which
+   * rows are in the frame depends on the ordering, so even `count` or `sum` would change value,
+   * and such a window must not be merged.
+   */
+  private def canEvaluateUnderAnyOrder(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true

Review Comment:
   Added a `RANGE BETWEEN U..U` plan test.
   



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "zml1206 (via GitHub)" <gi...@apache.org>.
zml1206 commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3780654296


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/catalyst/optimizer/Optimizer.scala:
##########
@@ -1761,9 +1761,38 @@ object CollapseWindow extends Rule[LogicalPlan] {
       s1.zip(s2).forall(e => e._1.semanticEquals(e._2))
   }
 
+  /**
+   * Returns true if the given window expression can be evaluated under any ordering of the rows
+   * within a partition without changing the result, so that it can be merged into another window
+   * with a different (non-empty) order spec.
+   *
+   * The frame determines whether the ordering matters. When the frame is the whole partition
+   * (`UNBOUNDED PRECEDING` to `UNBOUNDED FOLLOWING`), it always covers all the rows of the
+   * partition regardless of the ordering, so the ordering does not affect the result: aggregates
+   * such as `count` or `sum` give the same value under any ordering, and functions whose result
+   * does depend on the row order, such as `collect_list` or `first`, are non-deterministic when
+   * the order spec is empty, so evaluating them under any ordering yields a valid result. On the
+   * other hand, a bounded frame (e.g. `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`) is
+   * order-sensitive: which rows are in the frame depends on the ordering, so even `count` or
+   * `sum` would change value, and such a window must not be merged.
+   */
+  private def orderInsensitive(windowExpression: NamedExpression): Boolean =
+    windowExpression match {
+      case Alias(WindowExpression(_, WindowSpecDefinition(_, _,
+          SpecifiedWindowFrame(_, UnboundedPreceding, UnboundedFollowing))), _) => true
+      case _ => false
+    }
+
   private def windowsCompatible(w1: Window, w2: Window): Boolean = {
     specCompatible(w1.partitionSpec, w2.partitionSpec) &&
-      specCompatible(w1.orderSpec, w2.orderSpec) &&
+      // The order specs can differ when one of them is empty, as long as the window expressions
+      // of the window with the empty order spec are insensitive to the row order. In that case,
+      // they can be evaluated under the non-empty order spec of the other window.
+      (specCompatible(w1.orderSpec, w2.orderSpec) ||
+        (w1.orderSpec.isEmpty && w2.orderSpec.nonEmpty &&
+          w1.windowExpressions.forall(orderInsensitive)) ||
+        (w2.orderSpec.isEmpty && w1.orderSpec.nonEmpty &&
+          w2.windowExpressions.forall(orderInsensitive))) &&

Review Comment:
   Thanks, that makes sense. 
   Could we adjust the comment of `orderInsensitive`? The statement that sum gives the same value under any ordering is technically incorrect for floating-point inputs, and orderInsensitive is also slightly misleading for functions such as first and collect_list, whose values may change but remain valid under their nondeterministic contract. 



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "peter-toth (via GitHub)" <gi...@apache.org>.
peter-toth commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3805517394


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala:
##########
@@ -4761,6 +4761,17 @@ object SQLConf {
         "The threshold of window group limit must be -1, 0 or positive integer.")
       .createWithDefault(1000)
 
+  val COLLAPSE_WINDOW_WITH_EMPTY_ORDER_SPEC_IN_CHILD =
+    buildConf("spark.sql.optimizer.collapseWindowWithEmptyOrderSpecInChild")
+      .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+      .doc("When true, the optimizer collapses two adjacent windows with the same partition " +
+        "spec into one when the window with the empty order spec is the child (inner) window. " +
+        "This saves a WindowExec pass but can disable the WindowGroupLimit optimization for " +

Review Comment:
   **Finding 8.** The doc names only `WindowGroupLimit`, but the flag also costs `LimitPushDownThroughWindow`. Measured on this head with `SELECT c1, count(1) OVER () cnt, row_number() OVER (ORDER BY c2) rk FROM t3 LIMIT 5`:
   
   flag off (default):
   
       Project [c1, cnt, rk]
       +- Window [row_number() ... AS rk], [c2 ASC]
          +- GlobalLimit 5
             +- LocalLimit 5
                +- Sort [c2 ASC], true
                   +- Window [count(1) ... AS cnt]
   
   flag on:
   
       GlobalLimit 5
       +- LocalLimit 5
          +- Project [c1, cnt, rk]
             +- Window [count(1) ..., row_number() ...], [c2 ASC]
   
   So the top-5 `Limit + Sort` below the window is gone and the merged window sorts and buffers the whole input in a single partition.
   
   `LimitPushDownThroughWindow` sits *earlier* than `CollapseWindow` in the operator-optimization rule list, which is why I ruled it out last round, but it loses the race: the analyzed plan is `LocalLimit(Project(Project(Window(Window(...)))))`, and neither of its patterns (`LocalLimit(_, Window)`, `LocalLimit(_, Project(_, Window))`) matches through two projects. `CollapseProject` and `CollapseWindow` both run later in that same iteration, so by iteration 2 the pattern finally matches but `supportsPushdownThroughWindow` fails on the merged-in `count`.
   
   Nothing to fix in the rule -- both losses are the same "merged window is no longer all-expanding" effect and the flag is off by default. Just worth naming both, here and in the rule comment at `Optimizer.scala:1799`, so someone flipping this for the saved `WindowExec` pass knows what else goes:
   
   ```suggestion
           "This saves a WindowExec pass but can disable the WindowGroupLimit and the LocalLimit " +
           "push-down optimizations for top-k queries. " +
   ```
   



##########
sql/core/src/test/scala/org/apache/spark/sql/DataFrameWindowFunctionsSuite.scala:
##########
@@ -79,6 +79,27 @@ class DataFrameWindowFunctionsSuite extends SharedSparkSession
       parameters = Map("wf_name" -> "row_number", "wf_expr" -> "row_number()"))
   }
 
+  test("SPARK-58757: collapse window with an empty order spec into an ordered sibling") {
+    val df = Seq(
+      (0, 0), (0, 2), (0, 4),
+      (1, 1), (1, 3), (1, 5)).toDF("k", "v")
+    val ordered = Window.partitionBy("k").orderBy("v")
+    val unordered = Window.partitionBy("k")
+    checkAnswer(

Review Comment:
   **Finding 9.** `row_number` and `count` over a whole-partition frame are both order-insensitive, and there is no plan assertion, so this test cannot tell a merged plan from an unmerged one -- with `spark.sql.optimizer.excludedRules=org.apache.spark.sql.catalyst.optimizer.CollapseWindow` it still passes, on a plan that has two `Window` operators. As a regression test for this PR it can only catch a crash.
   
   The sibling collapse test in this file already has the idiom (`DataFrameWindowFunctionsSuite.scala:1716`):
   
   ```scala
   val windows = df.queryExecution.optimizedPlan.collect { case w: LogicalWindow => w }
   assert(windows.size === 1)
   ```
   
   Adding that plus an order-dependent function makes the test pin both the merge and the row order the merged-in expressions now see -- which is the interesting property, since the parent-empty direction is supposed to preserve it exactly. Verified this passes on this head:
   
   ```scala
       val res = df.select(
         $"k",
         $"v",
         row_number().over(ordered).as("rn"),
         collect_list($"v").over(unordered).as("vs"),
         first($"v").over(unordered).as("f"))
       assert(res.queryExecution.optimizedPlan.collect { case w: LogicalWindow => w }.size === 1)
       checkAnswer(res, Seq(
         Row(0, 0, 1, Array(0, 2, 4), 0),
         Row(0, 2, 2, Array(0, 2, 4), 0),
         Row(0, 4, 3, Array(0, 2, 4), 0),
         Row(1, 1, 1, Array(1, 3, 5), 1),
         Row(1, 3, 2, Array(1, 3, 5), 1),
         Row(1, 5, 3, Array(1, 3, 5), 1)))
   ```
   



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/CollapseWindowSuite.scala:
##########
@@ -168,4 +174,220 @@ class CollapseWindowSuite extends PlanTest {
 
     comparePlans(optimized, correctAnswer)
   }
+
+  test("collapse windows when one has an empty order spec " +
+    "(row_number + count over the whole partition)") {
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has multiple window expressions") {
+    // Every window expression of the empty-order window must be order-insensitive for the merge.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+    val sm = windowExpr(
+      AggregateExpression(Sum(b), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("sm")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt, sm), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt, sm), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has first() over the whole partition") {
+    // `first` is non-deterministic when the order is not determined by the query, so evaluating it
+    // under the other window's order spec yields a valid result.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val fr = windowExpr(
+      First(a, ignoreNulls = true).toAggregateExpression(),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("fr")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(fr), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, fr), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("don't collapse windows when the empty-order window has a bounded frame") {
+    // The frame `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW` is order-sensitive: which rows
+    // fall in the frame depends on the ordering, so the window cannot be evaluated under the other
+    // window's order spec.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val optimized = Optimize.execute(query.analyze)
+    val correctAnswer = query.analyze
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has a RANGE whole-partition frame") {
+    // `RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING` covers the whole partition just
+    // like `ROWS`, so it also collapses.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RangeFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window is the inner window") {
+    // The empty-order window can also be the child of the ordered window. In that case its
+    // expressions are evaluated under the ordered window's order spec, which is valid because all
+    // of them are order-insensitive. This direction can disable InferWindowGroupLimit, so it is
+    // gated by `spark.sql.optimizer.collapseWindowWithEmptyOrderSpecInChild`.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(cnt), partitionSpec1, Nil)
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+
+    val analyzed = query.analyze
+    val optimized = withSQLConf(
+        SQLConf.COLLAPSE_WINDOW_WITH_EMPTY_ORDER_SPEC_IN_CHILD.key -> "true") {
+      Optimize.execute(analyzed)
+    }
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(cnt, rk), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("don't collapse the inner empty-order window by default") {
+    // Merging an empty-order child into an ordered parent can disable InferWindowGroupLimit for
+    // top-k queries, so it is off by default.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(cnt), partitionSpec1, Nil)
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+
+    val optimized = Optimize.execute(query.analyze)
+    val correctAnswer = query.analyze
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows with a Project between them when one has an empty order spec") {

Review Comment:
   **Finding 10.** This covers the `Project`-between pattern only in the config-gated direction, so the direction that is on by default has no test for that second `apply` case. Worth mirroring it -- verified this merges on this head with no config set:
   
   ```scala
       val query = testRelation
         .window(Seq(rk), partitionSpec1, orderSpec1)
         .select($"a", $"b", $"c", $"rk")
         .window(Seq(cnt), partitionSpec1, Nil)
         .select($"a", $"b", $"c", $"rk", $"cnt")
   ```
   
       Project [a#0, b#1, c#2, rk#4, cnt#6L]
       +- Window [row_number() ... AS rk#4, count(c#2) ... AS cnt#6L], [c#2], [c#2 ASC NULLS FIRST]
          +- LocalRelation <empty>, [a#0, b#1, c#2]
   



-- 
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-58757][SQL] Allow CollapseWindow to merge windows with an empty order spec [spark]

Posted by "ulysses-you (via GitHub)" <gi...@apache.org>.
ulysses-you commented on code in PR #57986:
URL: https://github.com/apache/spark/pull/57986#discussion_r3809411974


##########
sql/catalyst/src/main/scala/org/apache/spark/sql/internal/SQLConf.scala:
##########
@@ -4761,6 +4761,17 @@ object SQLConf {
         "The threshold of window group limit must be -1, 0 or positive integer.")
       .createWithDefault(1000)
 
+  val COLLAPSE_WINDOW_WITH_EMPTY_ORDER_SPEC_IN_CHILD =
+    buildConf("spark.sql.optimizer.collapseWindowWithEmptyOrderSpecInChild")
+      .withBindingPolicy(ConfigBindingPolicy.NOT_APPLICABLE)
+      .doc("When true, the optimizer collapses two adjacent windows with the same partition " +
+        "spec into one when the window with the empty order spec is the child (inner) window. " +
+        "This saves a WindowExec pass but can disable the WindowGroupLimit optimization for " +

Review Comment:
   Updated the config doc and the rule comment to also name `LimitPushDownThroughWindow` alongside `WindowGroupLimit`. Thanks for catching the late one.



##########
sql/core/src/test/scala/org/apache/spark/sql/DataFrameWindowFunctionsSuite.scala:
##########
@@ -79,6 +79,27 @@ class DataFrameWindowFunctionsSuite extends SharedSparkSession
       parameters = Map("wf_name" -> "row_number", "wf_expr" -> "row_number()"))
   }
 
+  test("SPARK-58757: collapse window with an empty order spec into an ordered sibling") {
+    val df = Seq(
+      (0, 0), (0, 2), (0, 4),
+      (1, 1), (1, 3), (1, 5)).toDF("k", "v")
+    val ordered = Window.partitionBy("k").orderBy("v")
+    val unordered = Window.partitionBy("k")
+    checkAnswer(

Review Comment:
   Added the `LogicalWindow` count assertion and switched to `collect_list`/`first` so the test pins both the merge and the row order the merged-in expressions see.



##########
sql/catalyst/src/test/scala/org/apache/spark/sql/catalyst/optimizer/CollapseWindowSuite.scala:
##########
@@ -168,4 +174,220 @@ class CollapseWindowSuite extends PlanTest {
 
     comparePlans(optimized, correctAnswer)
   }
+
+  test("collapse windows when one has an empty order spec " +
+    "(row_number + count over the whole partition)") {
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has multiple window expressions") {
+    // Every window expression of the empty-order window must be order-insensitive for the merge.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+    val sm = windowExpr(
+      AggregateExpression(Sum(b), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("sm")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt, sm), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt, sm), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has first() over the whole partition") {
+    // `first` is non-deterministic when the order is not determined by the query, so evaluating it
+    // under the other window's order spec yields a valid result.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val fr = windowExpr(
+      First(a, ignoreNulls = true).toAggregateExpression(),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("fr")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(fr), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, fr), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("don't collapse windows when the empty-order window has a bounded frame") {
+    // The frame `ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW` is order-sensitive: which rows
+    // fall in the frame depends on the ordering, so the window cannot be evaluated under the other
+    // window's order spec.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val optimized = Optimize.execute(query.analyze)
+    val correctAnswer = query.analyze
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window has a RANGE whole-partition frame") {
+    // `RANGE BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING` covers the whole partition just
+    // like `ROWS`, so it also collapses.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RangeFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+      .window(Seq(cnt), partitionSpec1, Nil)
+
+    val analyzed = query.analyze
+    val optimized = Optimize.execute(analyzed)
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(rk, cnt), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows when the empty-order window is the inner window") {
+    // The empty-order window can also be the child of the ordered window. In that case its
+    // expressions are evaluated under the ordered window's order spec, which is valid because all
+    // of them are order-insensitive. This direction can disable InferWindowGroupLimit, so it is
+    // gated by `spark.sql.optimizer.collapseWindowWithEmptyOrderSpecInChild`.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(cnt), partitionSpec1, Nil)
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+
+    val analyzed = query.analyze
+    val optimized = withSQLConf(
+        SQLConf.COLLAPSE_WINDOW_WITH_EMPTY_ORDER_SPEC_IN_CHILD.key -> "true") {
+      Optimize.execute(analyzed)
+    }
+    assert(analyzed.output === optimized.output)
+
+    val correctAnswer = testRelation
+      .window(Seq(cnt, rk), partitionSpec1, orderSpec1)
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("don't collapse the inner empty-order window by default") {
+    // Merging an empty-order child into an ordered parent can disable InferWindowGroupLimit for
+    // top-k queries, so it is off by default.
+    val rk = windowExpr(
+      RowNumber(),
+      windowSpec(partitionSpec1, orderSpec1,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, CurrentRow))).as("rk")
+    val cnt = windowExpr(
+      AggregateExpression(Count(c), Complete, isDistinct = false, None),
+      windowSpec(partitionSpec1, Nil,
+        SpecifiedWindowFrame(RowFrame, UnboundedPreceding, UnboundedFollowing))).as("cnt")
+
+    val query = testRelation
+      .window(Seq(cnt), partitionSpec1, Nil)
+      .window(Seq(rk), partitionSpec1, orderSpec1)
+
+    val optimized = Optimize.execute(query.analyze)
+    val correctAnswer = query.analyze
+
+    comparePlans(optimized, correctAnswer)
+  }
+
+  test("collapse windows with a Project between them when one has an empty order spec") {

Review Comment:
   Added the mirrored case for the default parent-empty direction.



-- 
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