comphead opened a new issue, #26532: URL: https://github.com/apache/datafusion/issues/26532
### Describe the bug `LAST_VALUE(expr) IGNORE NULLS` over a frame that starts at the first row of the partition, which includes the default `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`, takes time quadratic in the number of rows in the partition. A single 1M-row partition takes about 89 s, against 0.1 s for the same query with `RESPECT NULLS`. For every row, `NthValueEvaluator::valid_index` slices the argument to the frame and finds the last non-NULL row with `valid_indices().last()` ([nth_value.rs#L488-L498](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/functions-window/src/nth_value.rs#L488-L498), [#L531](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/functions-window/src/nth_value.rs#L531)), which walks every valid row from the start of the frame. With an unbounded start the frame holds every row of the partition seen so far, and `memoize` returns early for `LAST_VALUE` with `IGNORE NULLS` ([#L414-L415](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/functions-window/src/nth_value.rs#L414-L415)), so the frame start never moves. ### To Reproduce In `datafusion-cli`, 1M rows with every other value NULL, in partitions of `N` rows: ```sql SELECT count(lv) FROM ( SELECT last_value(CASE WHEN value % 2 = 0 THEN value END) IGNORE NULLS OVER (PARTITION BY value / N ORDER BY value) AS lv FROM generate_series(1, 1000000) ); ``` | Rows per partition (`N`) | `IGNORE NULLS` | `RESPECT NULLS` | |---:|---:|---:| | 1,000 | 0.03 s | 0.02 s | | 10,000 | 0.13 s | 0.02 s | | 100,000 | 1.9 s | 0.03 s | | 1,000,000 | 85-89 s | 0.10 s | The existing `nth_value` bench has the same shape: `last_value_expanding/30%_nulls` takes 13.1 ms against 0.37 ms for `first_value_expanding/30%_nulls`. ### Expected behavior Time linear in the number of rows, as with `RESPECT NULLS`, `FIRST_VALUE ... IGNORE NULLS` or `max`. The last valid row of a frame can be found by reading the validity bitmap backward from the end of the frame, stopping at the first valid row. ### Additional context Found through Apache DataFusion Comet, which runs Spark's `last(expr, true)` over the default frame as `last_value` with `IGNORE NULLS` in `BoundedWindowAggExec`. The timings above are from `datafusion-cli` built from 3ee3e394c with the `release-nonlto` profile on an Apple M5 Max. `NTH_VALUE(expr, -n) IGNORE NULLS` counts the frame's valid rows for every row, so its cost per row also grows with the frame (`nth_value_neg10_expanding` in the same bench). -- 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]
