comphead opened a new issue, #26538: URL: https://github.com/apache/datafusion/issues/26538
### Describe the bug `NTH_VALUE(expr, -n) IGNORE NULLS` takes time quadratic in the number of rows in a window partition when the frame starts at the first row of the partition, as the default frame does. On 1M rows in 300K-row partitions it takes 11.5 s, against 0.13 s for `NTH_VALUE(expr, 2) IGNORE NULLS` and 0.04 s for `NTH_VALUE(expr, -2)` with `RESPECT NULLS`. For every row, `NthValueEvaluator` counts the valid rows in the frame and then walks them from the start of the frame to the one it returns ([nth_value.rs#L539-L549](https://github.com/apache/datafusion/blob/3ee3e394c19c97ccc7cca7ed3becb75cf364746a/datafusion/functions-window/src/nth_value.rs#L539-L549)). The frame grows with every row, and `memoize` returns early for `NTH_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. #26533 fixes the same pattern for `LAST_VALUE` (#26532) and leaves this case as it is. ### To Reproduce In `datafusion-cli`, 1M rows with every other value NULL, in partitions of `N` rows: ```sql SELECT count(x) FROM ( SELECT nth_value(CASE WHEN value % 2 = 0 THEN value END, -2) IGNORE NULLS OVER (PARTITION BY value / N ORDER BY value) AS x FROM generate_series(1, 1000000) ); ``` | Rows per partition (`N`) | `nth_value(v, -2) IGNORE NULLS` | `nth_value(v, 2) IGNORE NULLS` | `nth_value(v, -2)` | |---:|---:|---:|---:| | 10,000 | 0.16 s | 0.03 s | 0.02 s | | 100,000 | 2.65 s | 0.06 s | 0.03 s | | 300,000 | 11.5 s | 0.13 s | 0.04 s | ### Expected behavior Time linear in the number of rows, as with a positive `n` or `RESPECT NULLS`. Reading the frame's validity bitmap backward from the end of the frame finds the n-th valid row from the end after passing n valid rows, which is what `last_set_bit` in #26533 does for n = 1. ### Additional context The timings are from `datafusion-cli` built from 3ee3e394c with the `release-nonlto` profile on an Apple M5 Max. With #26533 applied they are the same. -- 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]
