You are viewing a plain text version of this content. The canonical link for it is here.
Posted to issues-all@impala.apache.org by "Tim Armstrong (Jira)" <ji...@apache.org> on 2021/01/09 02:07:00 UTC
[jira] [Resolved] (IMPALA-9958) Implement Introsort by adding a
heapsort case
[ https://issues.apache.org/jira/browse/IMPALA-9958?page=com.atlassian.jira.plugin.system.issuetabpanels:all-tabpanel ]
Tim Armstrong resolved IMPALA-9958.
-----------------------------------
Resolution: Won't Do
This isn't an obvious win - we do a randomized median of three pivot selection that's fairly robust. I think we should look at the sort holistically instead of assuming this is the right solution.
> Implement Introsort by adding a heapsort case
> ----------------------------------------------
>
> Key: IMPALA-9958
> URL: https://issues.apache.org/jira/browse/IMPALA-9958
> Project: IMPALA
> Issue Type: Improvement
> Components: Backend
> Reporter: Shant Hovsepian
> Priority: Minor
>
> Introsort is the standard hybrid sort implementation [https://en.wikipedia.org/wiki/Introsort] which chooses between quicksort, heapsort, and insertion sort given the current sort run size.
>
> Currently the Sorter uses quicksort with insertion sort for batches smaller than 16. With introsort in cases where the quisksort partitions the data above a threshold 2*log(N), then the algorithm switches to using heapsort.
> This should help mitigate worse case pivot selections.
>
--
This message was sent by Atlassian Jira
(v8.3.4#803005)
---------------------------------------------------------------------
To unsubscribe, e-mail: issues-all-unsubscribe@impala.apache.org
For additional commands, e-mail: issues-all-help@impala.apache.org