capistrant opened a new pull request, #20828:
URL: https://github.com/apache/druid/pull/20828
### Description
Introduces a new path for `SuperSorter` to stay in memory under certain
conditions. Prior to this PR `SuperSorter` executed in one of two modes:
* direct: all input fits within the allocated `inputBuffer` of size `B` and
the sort happens fully in memory.
* external: not all input fits within `inputBuffer`. frames in the
`inputBuffer` are merged and written to intermediate storage so further input
can be processed. Eventually the sort produces final output frames.
The new path aims to keep the sort in memory even when not all input frames
can fit within the `inputBuffer`. This path is taken when the `SuperSorter` has
a `limitHint` and the intermediate sort result frames fit within a `B / 4`
sized reservation of the original `inputBuffer` size.
#### in-memory top-k memory management
For our purposes we will assume super sorter has capacity for 12 frames in
this example.
For the in memory top-k mode we partition up the `inputBuffer` allocation of
`B` into 3 pieces
* `ibf` - input buffer frames. The buffer that input frames are read into
consumes `B - r - tm`
* `r` - retained result. The intermediate result frames of the last merge
consume up to `B / 4`
* `tm` - truncate merge space. The space to write the new retained set after
merging fixed at `B / 4`
below shows the buffer frames split between the three groups when a retained
result of size `B / 4` exists -
```
[ r ] [ r ] [ r ] [ tm ] [ tm ] [ tm ] [ ibf ] [ ibf ] [ ibf ] [ ibf ] [ ibf
] [ ibf ]
```
#### in-memory top-k activation
In memory top-k mode is an option iff the sorter has a limit hint and `max
buffer frames / 4 > 0`. Failure of either assertion rules out in-memory top-k
from the start.
During the initial frame buffer fill we will read up to `3/4 * B` frames and
then make a rough estimate of the intermediate output size based on the frame
size and average row size in this sample of frames. If `avg bytes per row *
limitHint <= (B / 4) * frameSize`, we go ahead with trying the in memory sort.
There is an escape hatch back to external merge sort that you will see below.
Again, if the estimate fails, we do not even try in-memory top-k.
#### truncating merge execution (and potential fallback)
We call the new in-memory path truncating merge. We merge the existing
retained result with the input frames in the input buffer. This writes result
frames to a new `ListWritableFrameChannel` sized at `B/4`. The result, if it
fits, becomes the new retained set. We repeat the process until we overflow an
intermediate sort and fallback to external sort, or hit a terminal state where
the final input buffer frames merge with the existing retained set and the
output frames are created.
##### Fallback on truncating merge overflow
during any truncating merge run, if the intermediate result overflows the
list frame channel, we mark it accordingly and complete, throwing out all the
overflowed rows.
On completion of processing, `SuperSorter` sees that the channel overflowed
and that we need to abort in-memory top k. The overflowed channel is thrown out
and `SuperSorter` disables further truncating merge runs. Instead it will
proceed with direct or external code paths that already exist today. If there
is not a lot of input frames left, it could finish in memory with the direct
mode. Otherwise, external mode will begin running using the current input
buffer frames and the last complete retained result.
#### Benchmark (master vs branch)
5M rows (~100 B each, random 20-char sort key), 1 MB frames,
`maxChannelsPerMerger=200`, `maxActiveProcessors=1` (buffer ~200 MB,
retained-run cap ~50 MB). 3 warmup + 5 measured 10 s iterations, 1 fork,
`-Xmx8g`, JDK 25. Spill and output channels are files on local SSD.
| Limit | Master (ms/op) | Branch (ms/op) | Speedup | Spill files (master /
branch) | Alloc/op (master / branch) |
|---|---|---|---|---|---|
| none | 3,046.8 ± 50.7 | 3,110.9 ± 60.7 | control | 6 / 6 | 2,527.0 MB /
2,527.0 MB |
| 100 | 2.33 ± 0.19 | 1.06 ± 0.04 | 2.2× | 6 / 0 | 15.9 MB / 10.8 MB |
| 10,000 | 32.9 ± 2.23 | 20.2 ± 0.42 | 1.6× | 6 / 0 | 29.6 MB / 22.5 MB |
| 100,000 | 286.0 ± 28.7 | 196.4 ± 2.60 | 1.5× | 6 / 0 | 134.7 MB / 140.7 MB
|
Regarding the control row. The above table indicates potential regression,
but re-running the benchmark locally multiple times alternating between runs on
master and this branch indicated that this is noise. 3 runs each: means of
3,079 vs 3,078 ms. respectively.
#### Release note
MSQ and Dart queries with `ORDER BY ... LIMIT` now sort in memory instead of
spilling to disk when `OFFSET + LIMIT` rows fit into about a quarter of the
sorter's memory.
<hr>
##### Key changed/added classes in this PR
* `SuperSorter`
* `ListWritableFrameChannel`
<hr>
<!-- Check the items by putting "x" in the brackets for the done things. Not
all of these items apply to every PR. Remove the items which are not done or
not relevant to the PR. None of the items from the checklist below are strictly
necessary, but it would be very helpful if you at least self-review the PR. -->
This PR has:
- [ ] been self-reviewed.
- [ ] using the [concurrency
checklist](https://github.com/apache/druid/blob/master/dev/code-review/concurrency.md)
(Remove this item if the PR doesn't have any relation to concurrency.)
- [ ] added documentation for new or modified features or behaviors.
- [x] a release note entry in the PR description.
- [x] added Javadocs for most classes and all non-trivial methods. Linked
related entities via Javadoc links.
- [ ] added or updated version, license, or notice information in
[licenses.yaml](https://github.com/apache/druid/blob/master/dev/license.md)
- [x] added comments explaining the "why" and the intent of the code
wherever would not be obvious for an unfamiliar reader.
- [x] added unit tests or modified existing tests to cover new code paths,
ensuring the threshold for [code
coverage](https://github.com/apache/druid/blob/master/dev/code-review/code-coverage.md)
is met.
- [ ] added integration tests.
- [x] been tested in a test Druid cluster.
--
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]
