You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues@calcite.apache.org by "Ruben Q L (Jira)" <ji...@apache.org> on 2020/08/05 08:11:00 UTC
[jira] [Comment Edited] (CALCITE-3920) Improve ORDER BY computation
in Enumerable convention by exploiting LIMIT
[ https://issues.apache.org/jira/browse/CALCITE-3920?page=com.atlassian.jira.plugin.system.issuetabpanels:comment-tabpanel&focusedCommentId=17170682#comment-17170682 ]
Ruben Q L edited comment on CALCITE-3920 at 8/5/20, 8:10 AM:
-------------------------------------------------------------
Thanks for the clarification [~thomas.rebele], sorry for the misunderstanding (even if a certain test execution with PriorityQueue can be stable, depending on the input set, generally there is no guarantee for that).
I guess we must decide if it is required to have a stable solution (via an ad-hoc algorithm, I guess) or not (via PriorityQueue). In my opinion it is desirable to have a stable algorithm, it will help with the predictability of the operator (and will simplify testing).
was (Author: rubenql):
Thanks for the clarification [~thomas.rebele], sorry for the misunderstanding (even if a certain test execution with PriorityQueue can be stable, depending on the input set, generally there is no guarantee for that).
I guess we must decide if it is required to have a stable solution (via an ad-hoc algorithm, I guess) or not (via PriorityQueue, ). In my opinion it is desirable to have a stable algorithm, it will help with the predictability of the operator (and will simplify testing).
> 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)