comphead opened a new issue, #26539: URL: https://github.com/apache/datafusion/issues/26539
### Describe the bug With `IGNORE NULLS`, `LAST_VALUE` and `NTH_VALUE` over a frame that starts at the first row of the partition never let `BoundedWindowAggExec` prune the partition's rows. Memory grows with the partition, and every input batch copies everything buffered for the partition so far. A single 10M-row partition of `LAST_VALUE ... IGNORE NULLS` takes 5.7 s and 296 MiB, against 0.75 s and 43 MiB with `RESPECT NULLS`. These numbers are with #26533 applied, since on `main` the quadratic scan of #26532 dominates. `NthValueEvaluator::memoize` returns early for `LAST_VALUE` and `NTH_VALUE` when nulls are ignored ([nth_value.rs#L414-L415](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/functions-window/src/nth_value.rs#L414-L415)), so the frame start stays at the partition's first row. `prune_partition_batches` prunes only up to the frame start ([bounded_window_agg_exec.rs#L1452-L1453](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/physical-plan/src/windows/bounded_window_agg_exec.rs#L1452-L1453)), and `PartitionBatchState::extend` concatenates the whole buffered partition with each new slice of it ([window_state.rs#L331-L334](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/expr/src/window_state.rs#L331-L334)). ### To Reproduce In `datafusion-cli`, `N` rows in one partition, every other value NULL: ```sql SELECT count(lv) FROM ( SELECT last_value(CASE WHEN value % 2 = 0 THEN value END) IGNORE NULLS OVER (ORDER BY value) AS lv FROM generate_series(1, N) ); ``` | Rows (`N`) | `IGNORE NULLS` | `RESPECT NULLS` | |---:|---:|---:| | 2M | 0.37 s, 91 MiB | 0.15 s, 42 MiB | | 5M | 1.65 s, 210 MiB | 0.39 s, 43 MiB | | 10M | 5.70 s, 296 MiB | 0.75 s, 43 MiB | The memory is the maximum resident set size of the process. ### Expected behavior Memory bounded by the rows that later frames can still use, as with `RESPECT NULLS`, and time linear in the number of rows. Over a frame that only grows, no row before the last valid one can change the result of `LAST_VALUE` again, and `NTH_VALUE` with a positive `n` is final once the frame holds `n` valid rows, as `FIRST_VALUE` already is. A negative `n` needs only the rows from its `n`-th valid row from the end. ### Additional context The timings are from `datafusion-cli` built from #26533 (ee5b4e3b7, on top of 3ee3e394c) with the `release-nonlto` profile on an Apple M5 Max. -- 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]
