Re: [HACKERS] [PATCH] Incremental sort

On Sat, Apr 7, 2018 at 4:56 PM, Alexander Korotkov <
a(dot)korotkov(at)postgrespro(dot)ru> wrote:

> On Fri, Apr 6, 2018 at 11:40 PM, Alexander Kuzmenkov <
> a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
>
>> On 06.04.2018 20:26, Tomas Vondra wrote:
>>
>>> I personally am OK with reducing the scope of the patch like this. It's
>>> still beneficial for the common ORDER BY + LIMIT case, which is good. I
>>> don't think it may negatively affect other cases (at least I can't think
>>> of any).
>>>
>>
>> I think we can reduce it even further. Just try incremental sort along
>> with full sort over the cheapest path in create_ordered_paths, and don't
>> touch anything else. This is a very minimal and a probably safe start, and
>> then we can continue working on other, more complex cases. In the attached
>> patch I tried to do this. We probably should also remove changes in
>> make_sort() and create a separate function make_incremental_sort() for it,
>> but I'm done for today.
>
>
> I've done further unwedding of sort and incremental sort providing them
> separate function for plan createion.
>
> 2) Likewise, I've suggested that the claim about abbreviated keys in
>>>
>> nodeIncrementalsort.c is dubious. No response, and the XXX comment was
>>> instead merged into the patch:
>>>
>>> * XXX The claim about abbreviated keys seems rather dubious, IMHO.
>>>
>>
>> Not sure about that, maybe just use abbreviated keys for the first
>> version? Later we can research this more closely and maybe start deciding
>> whether to use abbrev on planning stage.
>
>
> That comes from time when we're trying to make incremental sort to be
> always
> not worse than full sort. Now, we have separate paths for full and
> incremental sorts,
> and some costing penalty for incremental sort. So, incremental sort
> should be
> selected only when it's expected to give big win. Thus, we can give up
> with this
> optimization at least in the initial version.
>
> So, removed.
>
> 4) It's not clear to me why INITIAL_MEMTUPSIZE is defined the way it is.
>>> There needs to be a comment - the intent seems to be making it large
>>> enough to exceed ALLOCSET_SEPARATE_THRESHOLD, but it's not quite clear
>>> why that's a good idea.
>>>
>>
>> Not sure myself, let's ask the other Alexander.
>
>
> I've added comment to INITIAL_MEMTUPSIZE. However, to be fair it's not
> invention of this patch. Initial size of memtuples array was so
> previously.
> What this patch did is just move it to the macro.
>
> Also, this note hadn't been adressed yet.
>
> On Sat, Mar 31, 2018 at 11:43 PM, Tomas Vondra <tomas.vondra@
> 2ndquadrant.com> wrote:
>
>> I'm wondering if a static MIN_GROUP_SIZE is good idea. For example, what
>> if the subplan is expected to return only very few tuples (say, 33), but
>> the query includes LIMIT 1. Now, let's assume the startup/total cost of
>> the subplan is 1 and 1000000. With MIN_GROUP_SIZE 32 we're bound to
>> execute it pretty much till the end, while we could terminate after the
>> first tuple (if the prefix changes).
>>
>> So I think we should use a Min(limit,MIN_GROUP_SIZE) here, and perhaps
>> this should depend on average group size too.
>>
>
> I agree with that. For bounded sort, attached patch now selects minimal
> group
> size as Min(DEFAULT_MIN_GROUP_SIZE, bound). That should improve
> "LIMIT small_number" case.
>

I've just noticed that incremental sort now is not used in
contrib/postgres_fdw.
It's even better assuming that we're going to limit use-cases of incremental
sort. I've rolled back all the changes made in tests of
contirb/postgres_fdw
by this patch. Revised version is attached.

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