No problems at all, thanks for your interest. On Fri, Aug 4, 2017 at 9:07 PM, [email protected] <[email protected]> wrote:
> oh, there is an assignment to low. thanks for patience:) > > ---Original--- > *From:* "Tim Armstrong "<[email protected]> > *Date:* 2017/8/5 11:27:21 > *To:* "dev@impala"<[email protected]>; > *Subject:* Re: Impala Sorter just sort small partition? > > It does sort both left and right partitions - it just recurses on the small > partition and the next iteration of the loop processes the large partition. > > This is a pretty common optimisation. This page has a nice > explanation:http://www.geeksforgeeks.org/quicksort-tail-call-optimization-reducing-worst-case-space-log-n/ > > On Fri, Aug 4, 2017 at 6:12 PM, 俊杰陈 <[email protected]> wrote: > > > Thanks for your detail description. > > > > My question should be more specific to quicksort part. This line > > <https://github.com/apache/incubator-impala/blob/master/ > > be/src/runtime/sorter.cc#L1258> > > say > > recurse on the small partition due to stack consideration, while as my > > understanding quicksort should recurse on both left partition and right > > partition, so I'm curious how it keep one run sorted, does it sort in later > > merge sort or somewhere else? But the merge process should take sorted > > runs as input. > > > > 2017-08-05 0:18 GMT+08:00 Tim Armstrong <[email protected]>: > > > > > The Sorter does a 3-level hybrid sort with merge sort, quicksort and > > > insertion sort. > > > > > > SortHelper implements a 2-level hybrid in-memory sort. It fully sorts an > > > arbitrarily sized in-memory input. E.g. if 'begin' and 'end' point to the > > > begin and end of the sorted run, it will sort the full run. It does > > > quicksort recursively then switches to insertion sort once the partitions > > > are less than INSERTION_THRESHOLD = 16. > > > > > > Sorter also supports an external merge sort - if the full input doesn't > > fit > > > in memory, it sorts in-memory runs with SortHelper() then does merge sort > > > with the sorted runs. > > > > > > On Thu, Aug 3, 2017 at 11:13 PM, 俊杰陈 <[email protected] > > wrote: > > > > > > > Hi > > > > I'm looking Sorter.cc and found that Sorter::SortHelper just sort > > smaller > > > > partition. Is there anything I missed? > > > > > > > > -- > > > > Thanks & Best Regards > > > > > > > > > > > > > > > -- > > Thanks & Best Regards > > > >
