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]