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

   ### Describe the bug
   
   A window function with `PARTITION BY` and a `ROWS` frame returns wrong 
values under a `LIMIT` without `ORDER BY` when its input has more than one 
partition. Below, `(5, 2)` comes back with `rn = 1`, although `(5, 1)` comes 
before it. `LimitPushPastWindows` turns the `LIMIT` into a fetch on the 
`SortExec` under the window, but that sort does not keep each partition's own 
first rows.
   
   ### To Reproduce
   
   ```sql
   SET datafusion.execution.target_partitions = 4;
   -- the result depends on timing; these two make the wrong row show up more 
often
   SET datafusion.execution.batch_size = 1;
   SET datafusion.optimizer.repartition_file_scans = false;
   
   CREATE TABLE t1 (a INT, b INT) AS VALUES (5, 1), (0, 1), (0, 2), (0, 3);
   CREATE TABLE t2 (a INT, b INT) AS VALUES (5, 2);
   
   SELECT a, b, row_number() OVER (PARTITION BY a ORDER BY b ROWS UNBOUNDED 
PRECEDING) AS rn
   FROM (SELECT * FROM t1 UNION ALL SELECT * FROM t2)
   LIMIT 3;
   ```
   
   ### Expected behavior
   
   | Query | DataFusion returns | Expected |
   |---|---|---|
   | with `LIMIT 3` | 3 rows, one of them `(5, 2, 1)` (10 of 10 runs) | any 3 
rows of the full result |
   | without `LIMIT` | `(0,1,1) (0,2,2) (0,3,3) (5,1,1) (5,2,2)` | the same |
   
   With `SET datafusion.optimizer.enable_window_limits = false`, the `LIMIT 3` 
query returns correct rows.
   
   ### Additional context
   
   <details>
   <summary>EXPLAIN of the <code>LIMIT 3</code> query: two <code>SortExec: 
TopK(fetch=3), preserve_partitioning=[true]</code> under the window</summary>
   
   ```text
   ProjectionExec: expr=[a@0 as a, b@1 as b, row_number() PARTITION BY [a] 
ORDER BY [b ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW@2 
as rn]
     CoalescePartitionsExec: fetch=3
       LocalLimitExec: fetch=3
         BoundedWindowAggExec: wdw=[row_number() PARTITION BY [a] ORDER BY [b 
ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
           SortExec: TopK(fetch=3), expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS 
LAST], preserve_partitioning=[true]
             RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=2
               SortExec: TopK(fetch=3), expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS 
LAST], preserve_partitioning=[true]
                 UnionExec
                   DataSourceExec: partitions=1, partition_sizes=[4]
                   DataSourceExec: partitions=1, partition_sizes=[1]
   ```
   
   </details>
   
   - `LimitPushPastWindows` sets `fetch=3` on the `SortExec` below the window 
(`datafusion/physical-optimizer/src/limit_pushdown_past_window.rs:186`). The 
window reads each partition by itself, so each needs its own first 3 rows. Two 
things break that:
     1. `TopKRepartition` copies the TopK below the hash repartition 
(`datafusion/physical-optimizer/src/topk_repartition.rs:128-133`). The copy 
keeps the first 3 rows of each *input* partition, so `t1` drops `(5,1)` and 
window partition `a = 5` only gets `(5,2)`.
     2. The partitions of one `SortExec` share one TopK threshold 
(`datafusion/physical-plan/src/sorts/sort.rs:1513-1524`), so a partition can 
drop `(5,1)` and still emit the earlier `(5,2)`. This fails with 
`TopKRepartition` off too (see below), so `enable_topk_repartition = false` is 
not a workaround.
   - #26454 was another wrong result from the shared threshold; its fix #26455 
does not cover this case.
   - Fix direction: push the fetch only into a sort with one output partition.
   - Tested on main at 73e0b0339e; line numbers are from that commit.
   
   <details>
   <summary>Same wrong value from the shared threshold alone, with 
<code>TopKRepartition</code> off (7 of 10 runs)</summary>
   
   A partition drops new rows worse than the tightest threshold any partition 
has set (`datafusion/physical-plan/src/topk/mod.rs:413`, set at `:597`), but 
still emits rows that entered its heap earlier (`:836-871`). Here the partition 
for `a = 0` sets the threshold to `(0,3)` before `(5,1)` reaches the partition 
for `a = 5`, which drops it and keeps the earlier `(5,2)`.
   
   ```sql
   SET datafusion.execution.target_partitions = 1;
   SET datafusion.execution.batch_size = 1;
   -- one partition, read in this order: (5,2), (0,1), (0,2), (0,3), 1000 x 
(9,9), (5,1)
   CREATE TABLE t3 AS SELECT a, b FROM (
               SELECT 1 AS seq, 5 AS a, 2 AS b
     UNION ALL SELECT 2, 0, 1
     UNION ALL SELECT 3, 0, 2
     UNION ALL SELECT 4, 0, 3
     UNION ALL SELECT 4 + value, 9, 9 FROM generate_series(1, 1000)
     UNION ALL SELECT 2000, 5, 1
   ) ORDER BY seq;
   SET datafusion.execution.target_partitions = 4;
   SET datafusion.optimizer.repartition_file_scans = false;
   SET datafusion.optimizer.enable_topk_repartition = false;
   
   -- returns a row (5, 2, 1)
   SELECT a, b, row_number() OVER (PARTITION BY a ORDER BY b ROWS UNBOUNDED 
PRECEDING) AS rn
   FROM t3 LIMIT 3;
   ```
   
   ```text
   CoalescePartitionsExec: fetch=3
     BoundedWindowAggExec: wdw=[row_number() PARTITION BY [t3.a] ORDER BY [t3.b 
ASC NULLS LAST] ROWS BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW], mode=[Sorted]
       SortExec: TopK(fetch=3), expr=[a@0 ASC NULLS LAST, b@1 ASC NULLS LAST], 
preserve_partitioning=[true]
         RepartitionExec: partitioning=Hash([a@0], 4), input_partitions=1
           DataSourceExec: partitions=1, partition_sizes=[1005]
   ```
   
   </details>
   
   ### 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