[
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)
