xudong963 opened a new pull request, #23711: URL: https://github.com/apache/datafusion/pull/23711
## Which issue does this PR close? - Performance follow-up to #23705 and #23706. ## Rationale for this change The whole-partition evaluation path for `LEAD` and `LAG` with `IGNORE NULLS` currently collects every valid row index, performs a binary search for every output row, converts every selected value to a `ScalarValue`, and finally rebuilds an Arrow array from those scalars. This makes index selection `O(n log m)` for `n` rows and `m` non-null rows, and the per-row scalar materialization is particularly expensive for strings and nested values. A local Criterion microbenchmark with 100,000 rows and 50% nulls measured the following speedups across the tested offsets: | Data type | Speedup | | --- | ---: | | `Int64` | 6.7–6.9x | | `Utf8View` | 10.5–11.6x | | `List` | 21.7–21.8x | ## What changes are included in this PR? - Generate nullable Arrow gather indices with a single linear scan and bounded `VecDeque` state instead of collecting all valid indices and binary-searching for every row. - Materialize the result with Arrow's `take` kernel. - Use Arrow's `zip` kernel to fill non-null default values without constructing one `ScalarValue` per row. - Keep dictionary arrays with non-null defaults on scalar materialization because `zip` concatenates dictionaries and can overflow bounded dictionary key types. - Preserve the no-null-bitmap fast path added by #23706. The index generation and output materialization are now `O(n)`. There are no public API changes. ## Are these changes tested? Yes. The following checks pass: - `cargo fmt --all` - `cargo clippy --all-targets --all-features -- -D warnings` - `cargo test -p datafusion-functions-window --lib` (16 tests) - A local exhaustive differential check of 51,150 null-pattern/offset combinations produced identical target indices to the previous implementation. - A focused local check covers a full `UInt8` dictionary key space with a non-null default and verifies the compatibility fallback avoids `DictionaryKeyOverflowError`. The extended workspace test command was also attempted, but the local run exhausted disk space while linking the workspace test binaries (`errno=28`) before tests started. CI will provide the full workspace result. ## Are there any user-facing changes? No. This changes the implementation of whole-partition `LEAD`/`LAG ... IGNORE NULLS` evaluation without changing the SQL behavior or public API. -- 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]
