wuwenw opened a new pull request #6875: URL: https://github.com/apache/incubator-pinot/pull/6875
## Description <!-- Add a description of your PR here. A good description should include pointers to an issue or design document, etc. --> Currently, we're using heap sort at the end of groupBy, whose big O time complexity is n+nlogk. Since it is only necessary to keep the number of records up to TRIM_SIZE (normally 5000), we can use the pivot selection algorithm to select topk elements. When the number of records is relatively low (i.e. smaller than 150k), pivot selection algorithm can boost the performance by around 30-40%, at the expanse of extra memory usage. However, current benchmark results show that this algorithm becomes super inefficient if the memory usage exceeds some limits, mainly because of GC overhead. The detailed results and discussion can be found in this [link](https://docs.google.com/document/d/1ogLjIDvN4nlIUPRuMXGZn7dw_1cthdhehFF-GjHw-CA/edit?usp=sharing). Note that this PR does not change the original API and method, but just brings in a second option for the groupBy sorting phase. ## Upgrade Notes Does this PR prevent a zero down-time upgrade? (Assume upgrade order: Controller, Broker, Server, Minion) * [ ] Yes (Please label as **<code>backward-incompat</code>**, and complete the section below on Release Notes) Does this PR fix a zero-downtime upgrade introduced earlier? * [ ] Yes (Please label this as **<code>backward-incompat</code>**, and complete the section below on Release Notes) Does this PR otherwise need attention when creating release notes? Things to consider: - New configuration options - Deprecation of configurations - Signature changes to public methods/interfaces - New plugins added or old plugins removed * [ ] Yes (Please label this PR as **<code>release-notes</code>** and complete the section on Release Notes) ## Release Notes <!-- If you have tagged this as either backward-incompat or release-notes, you MUST add text here that you would like to see appear in release notes of the next release. --> <!-- If you have a series of commits adding or enabling a feature, then add this section only in final commit that marks the feature completed. Refer to earlier release notes to see examples of text. --> ## Documentation <!-- If you have introduced a new feature or configuration, please add it to the documentation as well. See https://docs.pinot.apache.org/developers/developers-and-contributors/update-document --> -- 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. For queries about this service, please contact Infrastructure at: us...@infra.apache.org --------------------------------------------------------------------- To unsubscribe, e-mail: commits-unsubscr...@pinot.apache.org For additional commands, e-mail: commits-h...@pinot.apache.org
