Re: [PATCH] Incremental sort

On Sat, Sep 30, 2017 at 11:20 PM, Alexander Korotkov <
a.korotkov@postgrespro.ru> wrote:

> On Sat, Sep 16, 2017 at 2:46 AM, Alexander Korotkov <
> a.korotkov@postgrespro.ru> wrote:
>
>> On Thu, Sep 14, 2017 at 2:48 AM, Alexander Korotkov <
>> a.korotkov@postgrespro.ru> wrote:
>>
>>> Patch rebased to current master is attached.  I'm going to improve my
>>> testing script and post new results.
>>>
>>
>> New benchmarking script and results are attached.  There new dataset
>> parameter is introduced: skew factor.  Skew factor defines skew in
>> distribution of groups sizes.
>> My idea of generating is just usage of power function where power is from
>> 0 to 1.  Following formula is used to get group number for particular item
>> number i.
>> [((i / number_of_indexes) ^ power) * number_of_groups]
>> For example, power = 1/6 gives following distribution of groups sizes:
>> group number    group size
>> 0               2
>> 1               63
>> 2               665
>> 3               3367
>> 4               11529
>> 5               31031
>> 6               70993
>> 7               144495
>> 8               269297
>> 9               468558
>>
>> For convenience, instead of power itself, I use skew factor where power =
>> 1.0 / (1.0 + skew).  Therefore, with skew = 0.0, distribution of groups
>> sizes is uniform.  Larger skew gives more skewed distribution (and that
>> seems to be quite intuitive).  For, negative skew, group sizes are mirrored
>> as for corresponding positive skew.  For example, skew factor = -5.0 gives
>> following groups sizes distribution:
>> group number    group size
>> 0               468558
>> 1               269297
>> 2               144495
>> 3               70993
>> 4               31031
>> 5               11529
>> 6               3367
>> 7               665
>> 8               63
>> 9               2
>>
>> Results shows that between 2172 test cases, in 2113 incremental sort
>> gives speedup while in 59 it causes slowdown.  The following 4 test cases
>> show most significant slowdown (>10% of time).
>>
>> Table                   GroupedCols GroupCount Skew PreorderedFrac
>> FullSortMedian IncSortMedian TimeChangePercent
>> int4|int4|numeric       1                  100  -10              0
>> 1.5688240528  2.0607631207             31.36
>> text|int8|text|int4     1                    1    0              0
>> 1.7785198689 <(778)%20519-8689>  2.1816160679             22.66
>> int8|int8|int4          1                   10  -10              0
>>  1.136412859  1.3166360855             15.86
>> numeric|text|int4|int8  2                   10  -10              1
>> 0.4403841496  0.5070910454             15.15
>>
>> As you can see, 3 of this 4 test cases have skewed distribution while one
>> of them is related to costly location-aware comparison of text.  I've no
>> particular idea of how to cope these slowdowns.  Probably, it's OK to have
>> slowdown in some cases while have speedup in majority of cases (assuming
>> there is an option to turn off new behavior).  Probably, we should teach
>> optimizer more about skewed distributions of groups, but that doesn't seem
>> feasible for me.
>>
>> Any thoughts?
>>
>
> BTW, replacement selection sort was removed by 8b304b8b.  I think it worth
> to rerun benchmarks after that, because results might be changed.  Will do.
>

I've applied patch on top of c12d570f and rerun the same benchmarks.
CSV-file with results is attached.  There is no dramatical changes.  There
is still minority of performance regression cases while majority of cases
has improvement.

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company