Re: Sort performance cliff with small work_mem

[Peter Geoghegan]

On Wed, May 2, 2018 at 11:06 AM, Tom Lane  wrote:
>> -1 from me. What about the case where only some tuples are massive?
>
> Well, what about it?  If there are just a few wide tuples, then the peak
> memory consumption will depend on how many of those happen to be in memory
> at the same time ... but we have zero control over that in the merge
> phase, so why sweat about it here?  I think Heikki's got a good idea about
> setting a lower bound on the number of tuples we'll hold in memory during
> run creation.

We don't have control over it, but I'm not excited about specifically
going out of our way to always use more memory in dumptuples() because
it's no worse than the worst case for merging. I am supportive of the
idea of making sure that the amount of memory left over for tuples is
reasonably in line with memtupsize at the point that the sort starts,
though.

-- 
Peter Geoghegan

Re: Sort performance cliff with small work_mem

[Peter Geoghegan]

On Wed, May 2, 2018 at 10:43 AM, Heikki Linnakangas  wrote:
> I'm not sure what you could derive that from, to make it less arbitrary. At
> the moment, I'm thinking of just doing something like this:
>
> /*
>  * Minimum amount of memory reserved to hold the sorted tuples in
>  * TSS_BUILDRUNS phase.  This specifies a minimum size for the merge runs,
>  * when work_mem is very small.
>  */
> #define MIN_TUPLE_MEMORY(32 * 1024)

If you end up doing something like this, I suggest that you also
change this code to simply assign 1024 (or maybe a new preprocessor
constant):

state->memtupsize = Max(1024, ALLOCSET_SEPARATE_THRESHOLD /
sizeof(SortTuple) + 1);

The ALLOCSET_SEPARATE_THRESHOLD part can become a static assertion.

-- 
Peter Geoghegan

Re: Sort performance cliff with small work_mem

[Peter Geoghegan]

On Wed, May 2, 2018 at 10:43 AM, Heikki Linnakangas  wrote:
> Independently of this, perhaps we should put in special case in
> dumptuples(), so that it would never create a run with fewer than maxTapes
> tuples. The rationale is that you'll need to hold that many tuples in memory
> during the merge phase anyway, so it seems silly to bail out before that
> while building the initial runs. You're going to exceed work_mem by the
> roughly same amount anyway, just in a different phase. That's not the case
> in this example, but it might happen when sorting extremely wide tuples.

-1 from me. What about the case where only some tuples are massive?

-- 
Peter Geoghegan

Re: Sort performance cliff with small work_mem

[Heikki Linnakangas]

On 02/05/18 19:41, Tom Lane wrote:

Robert Haas  writes:

On Wed, May 2, 2018 at 11:38 AM, Heikki Linnakangas  wrote:

To fix, I propose that we change the above so that we always subtract
tapeSpace, but if there is less than e.g. 32 kB of memory left after that
(including, if it went below 0), then we bump availMem back up to 32 kB. So
we'd always reserve 32 kB to hold the tuples, even if that means that we
exceed 'work_mem' slightly.



Sounds very reasonable.


Agreed.  I think that was my code to start with, and the issue certainly
didn't occur to me at the time.

I don't like the idea of using hardwired "32kB" though; some multiple
of TAPE_BUFFER_OVERHEAD seems more plausible.  Perhaps MINORDER times
TAPE_BUFFER_OVERHEAD would be good?


I don't think the amount that we reserve to hold the tuples should 
depend on those things. The function is "allocating" memory for the tape 
buffers, yes, but now we're talking about keeping some memory for the 
tuples, while quicksorting the initial runs. That seems independent from 
the number of tapes or the tape buffer size.


I'm not sure what you could derive that from, to make it less arbitrary. 
At the moment, I'm thinking of just doing something like this:


/*
 * Minimum amount of memory reserved to hold the sorted tuples in
 * TSS_BUILDRUNS phase.  This specifies a minimum size for the merge runs,
 * when work_mem is very small.
 */
#define MIN_TUPLE_MEMORY(32 * 1024)

Independently of this, perhaps we should put in special case in 
dumptuples(), so that it would never create a run with fewer than 
maxTapes tuples. The rationale is that you'll need to hold that many 
tuples in memory during the merge phase anyway, so it seems silly to 
bail out before that while building the initial runs. You're going to 
exceed work_mem by the roughly same amount anyway, just in a different 
phase. That's not the case in this example, but it might happen when 
sorting extremely wide tuples.


- Heikki

Re: Sort performance cliff with small work_mem

[Peter Geoghegan]

On Wed, May 2, 2018 at 8:38 AM, Heikki Linnakangas  wrote:
> With a small work_mem values, maxTapes is always 6, so tapeSpace is 48 kB.
> With a small enough work_mem, 84 kB or below in this test case, there is not
> enough memory left at this point, so we don't subtract tapeSpace. However,
> with a suitably evil test case, you can get arbitrary close to the edge, so
> that we will subtract away almost all the remaining memory above, leaving
> only a few bytes for the tuples. In this example case, with work_mem='85
> kB', each quicksorted run consists of only 15 tuples on average.

This is an extreme example of the memtuples array and memory for
tuples becoming unbalanced. You'll have 1024 memtuples (24KiB), which
is rather a lot more than the 15 tuples that you can fit in this
example case.

I don't feel strongly about it, but arguably the minimum additional
amount of memory should be big enough that you have some chance of
using all 1024 SortTuples (the whole memtuples array).

-- 
Peter Geoghegan

Re: Sort performance cliff with small work_mem

[Peter Geoghegan]

On Wed, May 2, 2018 at 8:46 AM, Robert Haas  wrote:
> On Wed, May 2, 2018 at 11:38 AM, Heikki Linnakangas  wrote:
>> To fix, I propose that we change the above so that we always subtract
>> tapeSpace, but if there is less than e.g. 32 kB of memory left after that
>> (including, if it went below 0), then we bump availMem back up to 32 kB. So
>> we'd always reserve 32 kB to hold the tuples, even if that means that we
>> exceed 'work_mem' slightly.
>
> Sounds very reasonable.

+1

-- 
Peter Geoghegan

Re: Sort performance cliff with small work_mem

[Robert Haas]

On Wed, May 2, 2018 at 11:38 AM, Heikki Linnakangas  wrote:
> To fix, I propose that we change the above so that we always subtract
> tapeSpace, but if there is less than e.g. 32 kB of memory left after that
> (including, if it went below 0), then we bump availMem back up to 32 kB. So
> we'd always reserve 32 kB to hold the tuples, even if that means that we
> exceed 'work_mem' slightly.

Sounds very reasonable.

-- 
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company