Re: Using quicksort and a merge step to significantly improve on tuplesort's single run "external sort"

On 07/31/2015 02:01 AM, Peter Geoghegan wrote:
> What prevents the tuple at the top of the in-memory heap at the point
> of tuplesort_performsort() (say, one of the ones added to the heap as
> our glut of memory was*partially*  consumed) being less than the
> last/greatest tuple on tape? If the answer is "nothing", a merge step
> is clearly required.

Oh, ok, I was confused on how the heap works. You could still abstract 
this as "in-memory tails" of the tapes, but it's more complicated than I 
thought at first:

When it's time to drain the heap, in performsort, divide the array into 
two arrays, based on the run number of each tuple, and then quicksort 
the arrays separately. The first array becomes the in-memory tail of the 
current tape, and the second array becomes the in-memory tail of the 
next tape.

You wouldn't want to actually allocate two arrays and copy SortTuples 
around, but keep using the single large array, just logically divided 
into two. So the bookkeeping isn't trivial, but seems doable.


Hmm, I can see another possible optimization here, in the way the heap 
is managed in TSS_BUILDRUNS state. Instead of keeping a single heap, 
with tupindex as the leading key, it would be more cache efficient to 
keep one heap for the currentRun, and an unsorted array of tuples 
belonging to currentRun + 1. When the heap becomes empty, and currentRun 
is incemented, quicksort the unsorted array to become the new heap.

That's a completely separate idea from your patch, although if you did 
it that way, you wouldn't need the extra step to divide the large array 
into two, as you'd maintain that division all the time.

- Heikki