[
https://issues.apache.org/jira/browse/CALCITE-3920?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17175363#comment-17175363
]
Thomas Rebele commented on CALCITE-3920:
----------------------------------------
Thank you for all your feedback. I found out that in some cases TreeMap is
better, and in others an algorithm that uses Arrays.sort(...), see [my
comment|https://issues.apache.org/jira/browse/CALCITE-4157?focusedCommentId=17175349#comment-17175349].
To be on the safe side, I'll add the TreeMap based implementation of a sort
with limit, so that there are no surprises. We can always add another sort
operator later.
[~zabetak], thanks for the hint, I've seen that option somewhere, but never
tried it. The additional counters are just for the number of comparisons and
stability checks. At least the latter cannot be done with a profiler ;)
> Improve ORDER BY computation in Enumerable convention by exploiting LIMIT
> -------------------------------------------------------------------------
>
> Key: CALCITE-3920
> URL: https://issues.apache.org/jira/browse/CALCITE-3920
> Project: Calcite
> Issue Type: Improvement
> Components: core
> Affects Versions: 1.22.0
> Reporter: Stamatis Zampetakis
> Assignee: Thomas Rebele
> Priority: Major
> Labels: pull-request-available
> Time Spent: 3h 20m
> Remaining Estimate: 0h
>
> There are many use-cases (pagination, top-k) relying on queries with an ORDER
> BY clause followed by a LIMIT.
> At the moment, the two operations are implemented independently the one from
> the other
> in the Enumerable convention. Even when we know that consumer needs only the
> top-10 results the sort operation will try to maintain its entire input
> sorted. The complexity of the sorting operation is O( n ) space and O( nlogn
> ) time, where n is the size of the input.
> By implementing ORDER BY and LIMIT together there are various optimizations
> that can be applied to reduce the space and time complexity of the sorting
> algorithm.
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
