[
https://issues.apache.org/jira/browse/CALCITE-3920?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17169830#comment-17169830
]
Stamatis Zampetakis commented on CALCITE-3920:
----------------------------------------------
Thanks for pushing this forward [~thomas.rebele]. I didn't look in detail in
the new results but from what I recall from my own benchmarks I agree with your
findings.
Overall, I would prefer to use the existing JDK algorithms if their performance
(cpu/memory) is not far superior to the new proposed algorithm. The code would
need less maintenance from our side and most likely they have been bench-marked
against more use-cases than the LimitSort. Having that said, you looked more
into the problem so I leave the decision up to you.
Changing the implementation of existing EnumerableDefaults.orderBy makes sense
but maybe it would be better to do it in a separate issue.
> 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)
