Sort performance cliff with small work_mem - Mailing list pgsql-hackers

Hi,

I spent some time performance testing sorting, and spotted a funny 
phenomenon with very small work_mem settings. This example demonstrates 
it well:

I sorted about 1 GB worth of pre-sorted integers, with different 
settings of work_mem, between 64 kB (the minimum), and 100 kB. I also 
added some logging to print out the number of "runs" performed:


work_mem   elapsed time      runs
--------   ------------      ----
    64 kB       20167 ms   35301
    65 kB       19769 ms   34454
    66 kB       19844 ms   33646
    67 kB       20318 ms   32840
    68 kB       20022 ms   32105
    69 kB       19455 ms   31403
    70 kB       19509 ms   30700
    71 kB       19200 ms   30057
    72 kB       19248 ms   29441
    73 kB       19809 ms   29071
    74 kB       19840 ms   28657
    75 kB       19864 ms   28281
    76 kB       19634 ms   27914
    77 kB       19599 ms   27557
    78 kB       19429 ms   27184
    79 kB       19425 ms   26845
    80 kB       20196 ms   26515
    81 kB       21781 ms   26192
    82 kB       18883 ms   25877
    83 kB       20460 ms   25548
    84 kB       18910 ms   25249
    85 kB       29245 ms   2009692
    86 kB       26532 ms   1039496
    87 kB       25126 ms   701056
    88 kB       25241 ms   528867
    89 kB       24235 ms   418686
    90 kB       24038 ms   350528
    91 kB       24803 ms   301454
    92 kB       23192 ms   264434
    93 kB       23111 ms   233686
    94 kB       23295 ms   210807
    95 kB       26602 ms   192009
    96 kB       22990 ms   176289
    97 kB       22700 ms   162948
    98 kB       22370 ms   150727
    99 kB       22686 ms   140867
   100 kB       22413 ms   132217

Huh, something funny happened going from 84 kB to 85 kB. I traced it to 
this piece of code in inittapes().

>     /*
>      * Decrease availMem to reflect the space needed for tape buffers; but
>      * don't decrease it to the point that we have no room for tuples. (That
>      * case is only likely to occur if sorting pass-by-value Datums; in all
>      * other scenarios the memtuples[] array is unlikely to occupy more than
>      * half of allowedMem.  In the pass-by-value case it's not important to
>      * account for tuple space, so we don't care if LACKMEM becomes
>      * inaccurate.)
>      */
>     tapeSpace = (int64) maxTapes * TAPE_BUFFER_OVERHEAD;
> 
>     if (tapeSpace + GetMemoryChunkSpace(state->memtuples) < state->allowedMem)
>         USEMEM(state, tapeSpace);

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.

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.

Memory accounting isn't very accurate in general. Even as the code 
stands, we will exceed the requested work_mem if it's small enough, and 
we don't account for every small allocation and overhead anyway. So I 
think that would be acceptable, even though it's kind of cheating.

Of course, sorting large sets with tiny work_mem settings isn't a very 
good idea to begin with. But I'd nevertheless like to avoid 
non-intuitive performance cliffs like this. It threw me off while 
performance testing another patch.

- Heikki