comphead opened a new pull request, #26664:
URL: https://github.com/apache/datafusion/pull/26664
## Which issue does this PR close?
- Closes #26537.
- Closes #26538.
- Closes #26539.
- Closes #26540.
## Rationale for this change
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 (#26537, #26539). A 10M-row partition of `LAST_VALUE ...
IGNORE NULLS` took 5.6 s and 363 MiB, against 0.75 s and 43 MiB with `RESPECT
NULLS`. The quadratic scan of #26538 was fixed by `nth_set_bit_from_end` in
#26533, except over long runs of NULLs, which every row still scanned.
Forward-filling a 1M-row partition that holds a single non-NULL value took 3.7
s.
`FIRST_VALUE`, `LAST_VALUE` and `NTH_VALUE` also created a `ScalarValue` for
every row, which is slow for nested types (#26540).
## What changes are included in this PR?
- `NthValueEvaluator::memoize` moves the frame start with `IGNORE NULLS` too.
- `LAST_VALUE` keeps its last non-NULL result, which it returns for later
frames without valid rows, and drops the whole frame.
- `NTH_VALUE(expr, -n)` keeps the rows from the one it selects.
- `FIRST_VALUE` and `NTH_VALUE(expr, n)` are final once they select a row.
- A frame with too few valid rows keeps them, but not the NULLs before
them.
- The new `PartitionEvaluator::evaluate_ranges` evaluates the frames of
consecutive rows in one call. Its default calls `evaluate` for each frame.
`StandardWindowExpr` calls it for functions that use the window frame, in both
`WindowAggExec` and `BoundedWindowAggExec`.
- `NthValueEvaluator::evaluate_ranges` gathers the selected rows with one
`take`, or repeats its final result. A single frame still goes through
`evaluate`, which is cheaper for one-row partitions.
#26540 suggests a method that returns the row index. A method over all
frames also covers a final `FIRST_VALUE` result, whose row may already be
pruned.
`NTH_VALUE(expr, n)` and `NTH_VALUE(expr, -n)` with `n > 1` still keep every
row from the first of the valid rows they need. Runs of NULLs among those rows
stay buffered and are scanned for every row. Unlike `LAST_VALUE`, they would
need to know how many rows `BoundedWindowAggExec` actually prunes.
## What is the testing strategy for this PR?
New `window.slt` cases cover `NTH_VALUE(v, 4)` and `NTH_VALUE(v, -4)` with
`IGNORE NULLS` over growing frames that span many batches, struct arguments,
and empty frames. The `IGNORE NULLS` cases from #26533, with runs of 497 NULLs,
now run with pruning. A unit test checks where `memoize` moves the frame start
for each function. These tests fail if `memoize` keeps one row too few, drops
the valid rows of a frame that has too few of them, never finalizes
`NTH_VALUE(expr, n)`, or loses the last valid value of `LAST_VALUE`, and if an
empty frame returns a row.
Locally, 312 queries over 12 frame shapes and 13 functions, with both NULL
treatments and batch sizes of 7, 100 and 8192, returned the same results as
`main`.
The queries in `datafusion-cli` (`release-nonlto` profile, Apple M5 Max):
| Query | `main` | This PR |
|---|---:|---:|
| `last_value(v) IGNORE NULLS`, one 10M-row partition, every other value
NULL (#26539) | 5.63 s, 363 MiB | 0.67 s, 43 MiB |
| `nth_value(v, -2) IGNORE NULLS`, 300K-row partitions of NULLs (#26538) |
0.38 s | 0.04 s |
| `last_value(v) IGNORE NULLS`, a 1M-row partition with one non-NULL value |
3.67 s | 0.13 s |
| `last_value(st)`, 64-row partitions of a struct (#26540) | 0.25 s | 0.10 s
|
| `nth_value(st, 2)`, 64-row partitions of a struct (#26540) | 0.27 s | 0.11
s |
`cargo bench -p datafusion --bench window_query_sql -- built-in`, change
against `main`:
| Benchmark | Change |
|---|---:|
| `window empty over` | -74% |
| `window order by` | -12% |
| `window partition by, u64_wide` | -4% to -6% |
| `window partition by, u64_narrow` | -49% |
| `window partition and order by, u64_wide` | -2% to -9% |
| `window partition and order by, u64_narrow` | -13% |
## Are there any user-facing changes?
`PartitionEvaluator` has a new method, `evaluate_ranges`, with a default
implementation, so existing implementations keep working.
--
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]
