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: Tomas Vondra <tomas.vondra@2ndquadrant.com>
Cc: Alexander Kuzmenkov <a.kuzmenkov@postgrespro.ru>, 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-05T23:43:18Z
Lists: pgsql-hackers

Attachments

Hi!

On Tue, Apr 3, 2018 at 2:10 PM, Tomas Vondra <tomas.vondra@2ndquadrant.com>
wrote:

> I think solving this may be fairly straight-forward. Essentially, until
> now we only had one way to do the sort, so it was OK to make the sort
> implicit by checking if the path is sorted
>
>     if (input not sorted)
>     {
>         ... add a Sort node ...
>     }
>
> But now we have multiple possible ways to do the sort, with different
> startup/total costs. So the places that create the sorts need to
> actually generate the Sort paths for each sort alternative, and store
> the information in the Sort node (instead of relying on pathkeys).
>
> Ultimately, this should simplify the createplan.c places making all the
> make_sort calls unnecessary (i.e. the input should be already sorted
> when needed). Otherwise it'd mean the decision needs to be done locally,
> but I don't think that should be needed.
>
> But it's surely a fairly invasive change to the patch ...
>

Right, there are situation when incremental sort has lower startup cost,
but higher total cost.  In order to find lower cost, we ideally should
generate
paths for both full sort and incremental sort.  However, that would increase
number of total pathes, and could slowdown planning time.  Another issue
that we don't always generate pathes for sort.  And yes, it would be rather
invasive.  So, that doesn't look feasible to get into 11.

Intead, I decided to cut usage of incremental sort.  Now, incremental sort
is generated only in create_sort_path().  Cheaper path selected between
incremental sort and full sort with taking limit_tuples into account.
That limits usage of incremental sort, however risk of regression by this
patch is also minimal.  In fact, incremental sort will be used only when
sort is explicitly specified and simultaneously LIMIT is specified or
dataset to be sorted is large and incremental sort saves disk IO.

Attached patch also incorporates following commits made by Alexander
Kuzmenkov:
* Rename fields of IncrementalSortState to snake_case for the sake of
consistency.
* Rename group test function to isCurrentGroup.
* Comments from Tomas Vondra about nodeIncrementalSort.c
* Add a test for incremental sort.
* Add a separate function to calculate costs of incremental sort.

------
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.