capistrant opened a new pull request, #20805: URL: https://github.com/apache/druid/pull/20805
### Description This PR introduces changes to MSQ that aim to improve the performance of limited **scan** queries that are time ordered. It approaches the problem both in the `ReadableInputQueue` as well as in the frame processor. #### `ReadableInputQueue` The queue formerly handed out inputs (realtime servers, frames, and segments in that preferred order). It focused on handing out whatever was ready to process over everything else. While this makes sense in many cases, it can lead to processing rows that never stood a chance to be included in the stage output in others. My change to the queue adds an optional time ordering as well as an input pruner that can outright skip the processing of segments we know cannot contribute to the stage output. The new input pruner replaces, but does not change the behavior of, the existing mechanism in place that allowed the queue to skip segments during a limited scan with no ordering. If the queue is told that there is time ordering, it sorts the loadable segments and forgoes sending any already cached segments to the front of the line for consumption. do note that non time ordered queries will still prioritize these already loaded segments. The new input pruner aims to avoid loading and handing out any segment who it knows won't contribute to stage output. It can also all-together stop queue processing if it knows that everything stage output needs has been processed (only exercised by limited scan with no ordering). The upshot here is that we can now avoid known zero-value work on the processors. #### ScanLimitTracker The scan limit tracker implements the input pruner logic needed by the readable input queue and also provides the mechanism for query processing to skip rows or even outright stop a cursor when it finds rows who cannot contribute to stage output. ##### RowCountScanLimitTracker Contains the logic for the already existing optimizations for limited scans with no ordering. Uses a limit tracker shared across processors that allows them to stop their cursors early if the limit has been reached. The readable input queue sees the shared limit as well, allowing it to stop processing the queue early. ##### TimeOrderedScanLimitTracker The tracker for optimized limited scans with time order as the **first** order by. This one is a bit more resource intensive since we need to track the timestamps of the current best k rows. In this implementation I have chosen to use a buffered top k with quick select to track the best row timestamps. There is a hard cap on the offset + limit of 1 million, any query with higher offset + limit will not use this optimization. Along with the buffer of timestamps, we track the current worst row in the top k. we use that in multiple ways: The readable input queue uses it to skip entire segments when it knows that the interval of a prospect segment could not include a row with a timestamp that beats the threshold. The RowGate uses it to skip rows that don't beat it or outright stop the cursor if we know no future row in the cursor can beat it. We can only do the latter when we have a cursor in sorted order that matches our query time ordering. ###### commons-numbers for quick selection implementation This does pull in a new dependency to take advantage of the pre-rolled quick select implementation ###### why not a heap? My initial approach used a heap for the structure tracking the k best timestamps. I ended up abandoning that approach during early benchmarking that flagged poor performance due to excessive heap operations under a lock when segment time ordering worked against the query. such as a DESC query against a segment that was ordered by `dim1, dim2, __time`. The buffered top k approach in this PR benchmarked much better. ### Benchmarks coming soon with data using benchmark added in https://github.com/apache/druid/pull/20793 <hr> #### Release note `msq-dart` and `msq-task` limited scan queries with a time ordering as the first order by can now run more efficiently by skipping processing of entire segments that will not contribute to stage output as well as skipping row processing and/or stopping processing mid-flight if no further rows can contribute to stage output. <hr> ##### Key changed/added classes in this PR * `ReadableInputQueue` * `ScanQueryFrameProcessor` * `InputPruner` * `ScanLimitTracker` * `RowCountScanLimitTracker` * `TimeOrderedScanLimitTracker` <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. - [ ] a release note entry in the PR description. - [ ] 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) - [ ] added comments explaining the "why" and the intent of the code wherever would not be obvious for an unfamiliar reader. - [ ] 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. - [ ] 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]
