jayzhan211 opened a new issue, #27459:
URL: https://github.com/apache/datafusion/issues/27459

   ### Describe the bug
   
   With `enable_window_topn` on (the default since #27197), `ORDER BY` returns 
rows out of order when a `row_number() ... <= K` filter is planned as 
`PartitionedTopKExec` over input that is already sorted by more columns than 
the window uses. Below, `ORDER BY pk, ok, x` returns `x` = 2, 3, 1. 
`PartitionedTopKExec` declares that it keeps the input order `[pk, ok, x]`, but 
it emits rows from a heap sorted only by the window's `ORDER BY ok`, so rows 
that tie on `ok` come out in heap order. The planner trusts the declared order 
and drops the sort.
   
   ### To Reproduce
   
   ```sql
   SET datafusion.optimizer.enable_window_topn = true;
   
   -- t is sorted by (pk, ok, x); all rows tie on ok
   COPY (SELECT * FROM (VALUES (1, 5, 1), (1, 5, 2), (1, 5, 3)) AS v(pk, ok, 
x)) TO 'topn/t.parquet';
   CREATE EXTERNAL TABLE t (pk INT NOT NULL, ok INT NOT NULL, x INT NOT NULL) 
STORED AS PARQUET
     WITH ORDER (pk, ok, x) LOCATION 'topn/t.parquet';
   
   SELECT pk, ok, x FROM (
     SELECT pk, ok, x, row_number() OVER (PARTITION BY pk ORDER BY ok) AS rn 
FROM t
   ) WHERE rn <= 3
   ORDER BY pk, ok, x;
   ```
   
   ### Expected behavior
   
   | Query | DataFusion returns | Expected |
   |---|---|---|
   | above | `(1,5,2) (1,5,3) (1,5,1)` | `(1,5,1) (1,5,2) (1,5,3)` |
   | above, `enable_window_topn = false` | `(1,5,1) (1,5,2) (1,5,3)` | the same 
|
   
   ### Additional context
   
   <details>
   <summary>EXPLAIN: no <code>SortExec</code> above 
<code>PartitionedTopKExec</code></summary>
   
   ```text
   ProjectionExec: expr=[pk@0 as pk, ok@1 as ok, x@2 as x]
     PartitionedTopKExec: fn=row_number, fetch=3, partition=[pk@0], order=[ok@1 
ASC NULLS LAST], emit=[row_number() PARTITION BY [t.pk] ORDER BY [t.ok ASC 
NULLS LAST] RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW]
       DataSourceExec: file_groups={1 group}, projection=[pk, ok, x], 
output_ordering=[pk@0 ASC NULLS LAST, ok@1 ASC NULLS LAST, x@2 ASC NULLS LAST], 
file_type=parquet
   ```
   
   </details>
   
   - `PartitionedTopKExec` builds its output properties with 
`eq_properties.reorder(sort_exprs)` 
(`datafusion/physical-plan/src/sorts/partitioned_topk.rs:350`). When the input 
already satisfies `[pk, ok]`, `reorder` keeps the input's longer orderings 
(`datafusion/physical-expr/src/equivalence/properties/mod.rs:993-999`), so the 
node declares `[pk, ok, x]`.
   - It emits each partition from a heap that compares only the window key 
(`datafusion/physical-plan/src/topk/mod.rs:1589-1593`, `:1703-1705`), so ties 
lose input order.
   - `SortExec` uses the same `reorder`, but it passes its input through 
unchanged when the input already satisfies the sort 
(`datafusion/physical-plan/src/sorts/sort.rs:1923-1934`), so the claim holds 
there.
   - Fix direction: declare only `[pk, ok]` (plus the ranking column), or break 
heap ties by input position.
   - This code dates from #21479.
   - Tested on main at 73e0b0339e, with and without the `SET` above; line 
numbers are from that commit.
   
   ### Willingness to contribute
   
   I'm not planning to fix this myself, so anyone is welcome to pick it up. 
Feel free to ping me with questions about the cause or when you'd like a 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]

Reply via email to