Re: Impala Sorter just sort small partition?

Date:* 2017/8/5 11:27:21 > *To:* "dev@impala"<dev@impala.incubator.apache.org>; > *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 pro

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:

Re: Impala Sorter just sort small partition?

Thanks for your detail description. My question should be more specific to quicksort part. This line say recurse on the small partition due to stack consideration, while as my understanding quicksort should

Re: Impala Sorter just sort small partition?

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