Horton

Re: [HACKERS] [PATCH] Incremental sort

Alexander Korotkov <a.korotkov@postgrespro.ru>

View thread View on postgr.es
From: Alexander Korotkov <a.korotkov@postgrespro.ru>
To: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>
Cc: Tomas Vondra <tomas.vondra@2ndquadrant.com>, Andres Freund <andres@anarazel.de>, Teodor Sigaev <teodor@sigaev.ru>, Darafei Komяpa Praliaskouski <me@komzpa.net>, Antonin Houska <ah@cybertec.at>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2018-04-07T13:56:07Z
Lists: pgsql-hackers

Attachments

On Fri, Apr 6, 2018 at 11:40 PM, Alexander Kuzmenkov <
a.kuzmenkov@postgrespro.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.

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

Commits

  1. Further adjustments to Hashagg EXPLAIN ANALYZE output

  2. Rework EXPLAIN format for incremental sort

  3. Fix typos and improve incremental sort comments

  4. Stabilize incremental_sort tests

  5. Minor improvements in Incremental Sort explain

  6. Consider Incremental Sort paths at additional places

  7. Fix representation of SORT_TYPE_STILL_IN_PROGRESS.

  8. Fix failures in incremental_sort due to number of workers

  9. Fix show_incremental_sort_info with force_parallel_mode

  10. Implement Incremental Sort

  11. Fix handling of "Subplans Removed" field in EXPLAIN output.

  12. Fix EXPLAIN (SETTINGS) to follow policy about when to print empty fields.

  13. Ensure plpgsql result tuples have the right composite type marking.

  14. Propagate sort instrumentation from workers back to leader.

  15. Make new regression test case parallel-safe, and improve its output.

  16. Push limit through subqueries to underlying sort, where possible.

  17. Fix inappropriate printing of never-measured times in EXPLAIN.

  18. Fix some infelicities in EXPLAIN output for parallel query plans.