tanmay442 opened a new pull request, #26536:
URL: https://github.com/apache/datafusion/pull/26536
## Which issue does this PR close?
- N/A
## Rationale for this change
This is a performance change only. The rows a query returns, the error
messages, the log lines and the row ordering are all unchanged.
`first_value(x ORDER BY y)` and `last_value(x ORDER BY y)` get slow as the
number of groups in the query grows. The grouped accumulator keeps a
scoreboard
with one bit per group to record which group already has a winning row in the
current batch (`datafusion/functions-aggregate/src/first_last.rs:414`). At
the
end of the batch it tested every one of those bits to find the groups that
had
a winner, so the work per batch grew with the number of groups in the query
rather than with the number of groups the batch touched.
The scan was over `total_num_groups` bits per batch. A group-by over a
million
groups spends most of its aggregate time in it, even though each input batch
touches only a few thousand groups.
## What changes are included in this PR?
1. `get_filtered_extreme_of_each_group`
(`datafusion/functions-aggregate/src/first_last.rs:586`) collected the
winners by walking the whole winner index array and testing the scoreboard
bit of every group. It now calls `scoreboard_winners`
(`datafusion/functions-aggregate/src/first_last.rs:668`), which reads the
scoreboard a word at a time and takes the trailing zeros of each word. The
scan goes from one bit test per group to one word read per 64 groups, plus
one extraction per group that has a winner.
2. `update_bench_many_groups`
(`datafusion/functions-aggregate/benches/first_last.rs:270`) is a new
criterion case that allocates a million groups and touches a few thousand
of
them per batch. The existing cases in this file touch every group in every
batch, so they cannot show this change. The contributor guide suggests a
separate pull request for a new benchmark, and I will split it if that is
preferred.
The numbers come from criterion with interleaved ABBA runs and 20 samples
per side. The intervals are percentile bootstraps over the median difference.
On the new `update_bench_many_groups` benchmark:
| case | before | after | delta | 95% CI |
|---|---|---|---|---|
| `groups=1000000, touched=64`, first_value | 62.73 ms | 16.80 ms | -73.2% |
[-73.6%, -73.0%] |
| `groups=1000000, touched=64`, last_value | 63.65 ms | 17.63 ms | -72.3% |
[-72.6%, -71.9%] |
| `groups=1000000, touched=8192`, first_value | 91.52 ms | 45.69 ms | -50.1%
| [-50.4%, -49.5%] |
| `groups=1000000, touched=8192`, last_value | 91.75 ms | 45.68 ms | -50.2%
| [-50.6%, -49.6%] |
The benchmarks that touch every group in the batch are unchanged. Over the
eight update and merge cases the median delta is -1.4%, the range is -3.4% to
+0.6%. The eight `evaluate_bench` cases do not touch the changed code, run at
14 to 17 us, and scatter between -5.6% and +2.7%. The same binary run against
a copy of itself measures +0.02% median, so that scatter is measurement
noise.
The saving per batch is proportional to the number of allocated groups and
does
not depend on how many groups the batch touches. The bytes read are the same
either way, so this is an instruction-count win and not a memory-traffic win.
### Why the behaviour is unchanged
- The scoreboard reset, the row loop, the comparator and the state updates
are
untouched. Only the collection of the winners changed.
- The old code walked the winner index array in order and kept the groups
whose scoreboard bit was set. The new code walks the scoreboard in the same
order and finds the same groups, so both return the winners in ascending
group order.
- The scoreboard is a `BooleanBufferBuilder`, so its bytes are reachable
through `as_slice()`. The bits past the logical length of the scoreboard
are
zero, because the scoreboard is rebuilt with `append_n(len, false)` before
each batch, so the scan cannot find a group past the end.
- The result does not depend on the byte order. `u64::from_le_bytes` puts the
first byte in the low bits on every platform, and arrow packs bits least
significant first within a byte, so bit `i` of the scoreboard is bit `i %
64`
of word `i / 64` on every platform.
- The callers update the state per group, so the order of the winners does
not
affect the result.
No public API change. `scoreboard_winners` is a private method on a private
struct, and the accumulator gains no field and no allocation.
## What is the testing strategy for this PR?
`cargo test -p datafusion-functions-aggregate --lib` passes, 254 tests, and
`cargo test --profile=ci --test sqllogictests` passes, 535 of 535 test files.
`ci/scripts/rust_fmt.sh` and `ci/scripts/rust_clippy.sh` are clean.
`cargo doc --document-private-items --no-deps -p
datafusion-functions-aggregate`
with `RUSTDOCFLAGS="-D warnings"` is clean. `typos` and the `hawkeye` license
header check pass on the two changed files, and
`ci/scripts/check_large_files.sh --base origin/main --head HEAD` passes for
this commit range.
One test is added, `scoreboard_winners_cover_every_word`
(`datafusion/functions-aggregate/src/first_last.rs:3004`). It puts groups at
index 0, 63, 64 and 99,999, so it covers the first word of the scoreboard,
the
second word and the last partial word, which holds fewer than 64 groups. It
asserts the winning value of each group after two batches, and that a group
that was never seen stays null. Removing the partial word handling makes the
test fail, so it covers the new code.
The full workspace suite takes about 40 minutes and I did not run it. I have
no
query level benchmark for this change yet, so the numbers above are at the
accumulator level.
## Are there any user-facing changes?
No. The winners are collected in the same ascending order as before, so every
query returns the same rows. There is no public API change.
--
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]
