return pre-sorted value on IntermediateResultsBlock
- Dominant language
- Java
- Stars
- 6.1k
- Forks
- 1.5k
- Avg merge
- 1d 21h
- Merged PRs (30d)
- 189
Description
Currently, if a query is run with the ORDER BY clause. data is
- in selection only, data is sorted and trimmed to the limit
- in aggregation/group-by/distinct, data is unsorted but trimmed to the limit
This means that broker needs to do a full sorting algorithm. Where as if the data is pre-sorted in IntermediateResultsBlock. broke can do a simple k-sorted merge algorithm. which reduces order by time from O(N*logN) to O(N * logK) where K is number of data tables returned.
The PRO for this is:
- reduce the time complexity of the broker reduce
- reduce the space complexity so broker only need to maintain a top-K instead of a top-N heap
The CON
- servers need to pop data in O(N * logN) instead of O(N) loop through the priority queue.
- implement sorting for agg/group-by/distinct as well.
Contributor guide
Research direction
Start by tracing the IntermediateResultsBlock and the broker's ORDER BY reduction path, then compare the selection and aggregation/group-by/distinct cases described in the issue. Done means the relevant results are pre-sorted where applicable and the broker can use the proposed k-sorted merge without changing query results.
Written by the indexing model from the issue text.
Assessment
- Tech stack
- java
- Domain
- databases, distributed-systems
- Issue type
- Feature
- Difficulty
- 5/5
- Estimated time
- Over a week
- Activity status
- Stale
- Clarity
- Needs clarification
- Newbie friendliness
- 25/100