comphead opened a new pull request, #26533: URL: https://github.com/apache/datafusion/pull/26533
## Which issue does this PR close? - Closes #26532. ## Rationale for this change `LAST_VALUE(expr) IGNORE NULLS` over a frame that starts at the first row of the partition, such as the default `RANGE BETWEEN UNBOUNDED PRECEDING AND CURRENT ROW`, took time quadratic in the partition size. A 1M-row partition took 89 s, against 0.1 s with `RESPECT NULLS`. The issue has the reproducer. ## What changes are included in this PR? `NthValueEvaluator::valid_index` no longer slices the argument array for every row. It reads the frame's validity bits in place, since `BooleanBuffer::slice` is O(1), and for `LAST_VALUE` it finds the last valid row with a new `last_set_bit`. That function reads the bitmap a 64-bit word at a time from the end of the frame, so the cost per row is the distance back to the last non-NULL row instead of the size of the frame. `FIRST_VALUE` and `NTH_VALUE` keep their forward scans, but they also skip the per-row slice and null count. The results are unchanged: a frame without NULLs still resolves to its first, last or nth row. Two related costs are not changed here: - `memoize` still returns early for `LAST_VALUE` with `IGNORE NULLS`, so the frame start never moves and `BoundedWindowAggExec` keeps the whole partition buffered. - `NTH_VALUE(expr, -n) IGNORE NULLS` still counts the frame's valid rows for every row. Both could be follow-ups. ## What is the testing strategy for this PR? New `window.slt` cases cover `LAST_VALUE`, `FIRST_VALUE` and `NTH_VALUE` with `IGNORE NULLS` over partitions that span many 100-row batches. The partitions hold alternating NULLs, NULL runs across several bitmap words, only NULLs, or no NULLs. The cases use growing, sliding, whole-partition and peer-group frames. `v` increases within each partition, so every case is checked against `max` or `min` over the same frame, which computes the same value through the aggregate path. A unit test checks `last_set_bit` against a scan from the end for every bit offset up to 70 and every length up to 200. Both kinds of test fail if `last_set_bit` ignores the lead padding. `cargo bench -p datafusion-functions-window --bench nth_value`, `main` against this branch on an Apple M5 Max: | Benchmark | `main` | This PR | |---|---:|---:| | `last_value_expanding/30%_nulls` | 13.15 ms | 111 µs | | `last_value_expanding/50%_nulls` | 8.96 ms | 109 µs | | `last_value_expanding/80%_nulls` | 2.51 ms | 109 µs | | `last_value_sliding_100/50%_nulls` | 602 µs | 113 µs | | `first_value_expanding/50%_nulls` | 364 µs | 119 µs | | `nth_value_10_expanding/50%_nulls` | 379 µs | 137 µs | | `nth_value_neg10_expanding/50%_nulls` | 7.95 ms | 7.65 ms | | `first_value/respect_nulls` | 47.8 µs | 46.5 µs | The issue's query in `datafusion-cli` (`release-nonlto` profile), 1M rows: | Rows per partition | `main` | This PR | |---:|---:|---:| | 10,000 | 0.13 s | 0.03 s | | 100,000 | 1.90 s | 0.04 s | | 1,000,000 | 89.2 s | 0.16 s | ## Are there any user-facing changes? No, apart from the speed-up. -- 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]
