Uploaded image for project: 'Calcite'
  1. Calcite
  2. CALCITE-3920

Improve ORDER BY computation in Enumerable convention by exploiting LIMIT

    XMLWordPrintableJSON

    Details

    • Type: Improvement
    • Status: Closed
    • Priority: Major
    • Resolution: Fixed
    • Affects Version/s: 1.22.0
    • Fix Version/s: 1.26.0
    • Component/s: core

      Description

      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.

        Attachments

          Issue Links

            Activity

              People

              • Assignee:
                thomas.rebele Thomas Rebele
                Reporter:
                zabetak Stamatis Zampetakis
              • Votes:
                0 Vote for this issue
                Watchers:
                5 Start watching this issue

                Dates

                • Created:
                  Updated:
                  Resolved:

                  Time Tracking

                  Estimated:
                  Original Estimate - Not Specified
                  Not Specified
                  Remaining:
                  Remaining Estimate - 0h
                  0h
                  Logged:
                  Time Spent - 7h 50m
                  7h 50m