[jira] [Created] (CALCITE-3920) Improve ORDER BY computation in Enumerable convention by exploiting LIMIT

["Stamatis Zampetakis (Jira)" <ji...@apache.org>]

Stamatis Zampetakis created CALCITE-3920:
--------------------------------------------

             Summary: 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: Stamatis Zampetakis
             Fix For: 1.23.0


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)