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

Hmm. You don't really need to merge the in-memory array into the tape, as you know that all the tuples in the in-memory must come after the tuples already on the tape. You can just return all the tuples from the tape first, and then all the tuples from the array.

So here's a shorter/different explanation of this optimization: When it's time to perform the sort, instead of draining the in-memory heap one tuple at a time to the last tape, you sort the heap with quicksort, and pretend that the sorted heap belongs to the last tape, after all the other tuples in the tape.

Some questions/thoughts on that:

Isn't that optimization applicable even when you have multiple runs? Quicksorting the heap and keeping it as an array in memory is surely always faster than heapsorting and pushing it to the tape.