jayzhan211 opened a new issue, #27422: URL: https://github.com/apache/datafusion/issues/27422
### Describe the bug Sorting on `MAX` or `MIN` over a sliding window frame (e.g. `ROWS BETWEEN 1 PRECEDING AND CURRENT ROW`) can return rows in the wrong order: the physical optimizer thinks the window output is already sorted and removes the final sort. It happens when the window is ordered `DESC` for `MAX` or `ASC` for `MIN`, when the frame skips the current row, or when NULL inputs sort first. Reproduced on main at ac1a63d2ce; the rule has been there since 46.0.0. ### To Reproduce ```sql CREATE TABLE u(x INT NOT NULL) AS VALUES (3), (1), (5); -- case A SELECT x, m FROM (SELECT x, MAX(x) OVER (ORDER BY x DESC ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS m FROM u) ORDER BY m ASC NULLS LAST; ``` <details><summary>SQL for cases B, C, D</summary> ```sql CREATE TABLE u(x INT NOT NULL) AS VALUES (3), (1), (5); CREATE TABLE t(x INT) AS VALUES (3), (NULL), (1), (5); -- B SELECT x, m FROM (SELECT x, MIN(x) OVER (ORDER BY x ASC ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS m FROM u) ORDER BY m DESC NULLS LAST; -- C SELECT x, m FROM (SELECT x, MAX(x) OVER (ORDER BY x ASC ROWS BETWEEN 2 PRECEDING AND 1 PRECEDING) AS m FROM u) ORDER BY m ASC NULLS LAST; -- D SELECT x, m FROM (SELECT x, MAX(x) OVER (ORDER BY x ASC NULLS FIRST ROWS BETWEEN 1 PRECEDING AND CURRENT ROW) AS m FROM t) ORDER BY m ASC NULLS LAST; ``` </details> | Case | What differs | `m` returned | `m` expected | |---|---|---|---| | A | `MAX`, window ordered `x DESC` | 5, 5, 3 | 3, 5, 5 | | B | `MIN`, window ordered `x ASC` | 1, 1, 3 | 3, 1, 1 | | C | frame skips the current row | NULL, 1, 3 | 1, 3, NULL | | D | NULL input sorted first | NULL, 1, 3, 5 | 1, 3, 5, NULL | `MAX` with the window ordered `x ASC` and a frame that includes the current row returns the right order. ### Expected behavior Rows come back in the order of the final `ORDER BY` (the "expected" column). ### Additional context `window_equivalence_properties` (`datafusion/physical-plan/src/windows/mod.rs:509-570`) declares an output ordering for set-monotonic aggregates over sliding frames, and that ordering is what lets the final sort be removed. Two parts of it are wrong: - **Direction.** Without `PARTITION BY` it declares `MAX` ascending and `MIN` descending (`increasing && (asc || no_partitioning)`, line 560). But `MAX` over input ordered `x DESC`, like `MIN` over `x ASC`, takes the oldest row in the frame, so the result follows the input's order (A, B). - **NULLs.** It always declares NULLS LAST (lines 563, 568). A frame with no non-NULL input gives NULL: at the start when the frame skips the current row (C) or NULL inputs sort first (D), and at the end when enough NULL inputs sort last. With `2 PRECEDING AND 1 PRECEDING` over `1, 3, NULL, NULL, NULL` the window returns `NULL, 1, 3, 3, NULL`, so no NULL placement is safe there. The rule came in #14813 and is unchanged from 46.0.0 through branch-56. #27267 is the same NULL mistake in the rules for frames that only grow or only shrink, a separate code path. Anyone is welcome to take this; please ping me for 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: [email protected] For queries about this service, please contact Infrastructure at: [email protected] --------------------------------------------------------------------- To unsubscribe, e-mail: [email protected] For additional commands, e-mail: [email protected]
