Re: Using quicksort for every external sort run

On Thu, Nov 19, 2015 at 12:35 PM, Greg Stark <stark@mit.edu> wrote:
> On Thu, Nov 19, 2015 at 6:56 PM, Peter Geoghegan <pg@heroku.com> wrote:
>> Yes, I really do mean it when I say that the DBA is not supposed to
>> see this message, no matter how much or how little memory or data is
>> involved. There is no nuance intended here; it isn't sensible to allow
>> a multi-pass sort, just as it isn't sensible to allow checkpoints
>> every 5 seconds. Both of those things can be thought of as thrashing.
>
> Hm. So a bit of back-of-envelope calculation. If we have want to
> buffer at least 1MB for each run -- I think we currently do more
> actually -- and say that a 1GB work_mem ought to be enough to run
> reasonably (that's per sort after all and there might be multiple
> sorts to say nothing of other users on the system). That means we can
> merge about 1,000 runs in the final merge. Each run will be about 2GB
> currently but 1GB if we quicksort the runs. So the largest table we
> can sort in a single pass is 1-2 TB.
>
> If we go above those limits we have the choice of buffering less per
> run or doing a whole second pass through the data.

If we only go slightly above the limits, it is much more graceful.  It
will happily do a 3 way merge followed by a 1023 way final merge (or
something like that) so only 0.3 percent of the data needs a second
pass, not all of it.  If course by the time you get a factor of 2 over
the limit, you are making an entire second pass one way or another.

Cheers,

Jeff