Re: Sorting Improvements for 8.4

On Mon, 2007-12-03 at 10:32 -0800, Jeff Davis wrote:

> If I understand correctly, we just keep track of the maximum value of
> the last block read from each run, and then always read from the run in
> which the last block read has the lowest maximum.

Yep, sounds like Algorithm F

> It seems as if this would allow a variable number of runs to be merged
> at once, but if the data really *is* random, we'd want it to degrade
> gracefully something resembling the current implementation.

If we also keep track of the endpoints of runs that we haven't yet read
from, then yes that would link my ideas with Algorithm F, so we just
have a single implementation. (F++ ?)

Probably easiest to store the endpoint tuples directly, with some sane
limits for when we have very large tuples.

You'll still need to do run-level forecasting as I had proposed to tell
whether you need to do any intermediate merging prior to the final
merge. So the two sets of ideas can't be brought together completely.

> I'm being somewhat vague here because I haven't taken the time to
> really understand it. If you think this idea has potential I will look
> into it in more detail.

Yes, F++ sound like it will use memory more effectively than we do
currently. That's likely to improve performance when the number of runs
approaches the limit for the size of work_mem. So this will improve
external sorts with too small memory allocations, but it won't do
anything about sorts with too large a memory allocation. That's probably
the order of importance for tackling sort performance, so thats good.

Probably best to test with
- 1M - 4M work_mem, so we see the full benefit of any improvements in
memory utilisation in a typical context
- number of runs is nearly at limit for memory
- total sort is very large, so we see real I/O issues starkly

You'll need to instrument things carefully so you can tell how many runs
are being merged at any one time and how that effects elapsed time/row.

--
Simon Riggs
2ndQuadrant http://www.2ndQuadrant.com