Horton

Re: [PATCH] Incremental sort

Alexander Korotkov <a.korotkov@postgrespro.ru>

View thread View on postgr.es
From: Alexander Korotkov <a.korotkov@postgrespro.ru>
To: Robert Haas <robertmhaas@gmail.com>
Cc: Heikki Linnakangas <hlinnaka@iki.fi>, Mithun Cy <mithun.cy@enterprisedb.com>, pgsql-hackers <pgsql-hackers@postgresql.org>
Date: 2017-09-13T23:48:42Z
Lists: pgsql-hackers

Attachments

On Mon, May 8, 2017 at 6:51 PM, Robert Haas <robertmhaas@gmail.com> wrote:

> On Fri, May 5, 2017 at 11:13 AM, Alexander Korotkov
> <a.korotkov@postgrespro.ru> wrote:
> > Incremental sort is faster in vast majority of cases.  It appears to be
> > slower only when whose dataset is one sort group.  In this case
> incremental
> > sort is useless, and it should be considered as misuse of incremental
> sort.
> > Slowdown is related to the fact that we anyway have to do extra
> comparisons,
> > unless we somehow push our comparison result into qsort itself and save
> some
> > cpu cycles (but that would be unreasonable break of encapsulation).
> Thus,
> > in such cases regression seems to be inevitable anyway.  I think we could
> > evade this regression during query planning.  If we see that there would
> be
> > only few groups, we should choose plain sort instead of incremental sort.
>
> I'm sorry that I don't have time to review this in detail right now,
> but it sounds like you are doing good work to file down cases where
> this might cause regressions, which is great.


Thank you for paying attention to this patch!


> Regarding the point in
> the paragraph above, I'd say that it's OK for the planner to be
> responsible for picking between Sort and Incremental Sort in some way.
> It is, after all, the planner's job to decide between different
> strategies for executing the same query and, of course, sometimes it
> will be wrong, but that's OK as long as it's not wrong too often (or
> by too much, hopefully).


Right, I agree.


> It may be a little difficult to get this
> right, though, because I'm not sure that the information you need
> actually exists (or is reliable).  For example, consider the case
> where we need to sort 100m rows and there are 2 groups.  If 1 group
> contains 1 row and the other group contains all of the rest, there is
> really no point in an incremental sort.  On the other hand, if each
> group contains 50m rows and we can get the data presorted by the
> grouping column, there might be a lot of point to an incremental sort,
> because two 50m-row sorts might be a lot cheaper than one 100m sort.
>
More generally, it's quite easy to imagine situations where the
> individual groups can be quicksorted but sorting all of the rows
> requires I/O, even when the number of groups isn't that big.  On the
> other hand, the real sweet spot for this is probably the case where
> the number of groups is very large, with many single-row groups or
> many groups with just a few rows each, so if we can at least get this
> to work in those cases that may be good enough.  On the third hand,
> when costing aggregation, I think we often underestimate the number of
> groups and there might well be similar problems here.


I agree with that.  I need to test this patch more carefully in the case
when groups have different sizes.  It's likely I need to add yet another
parameter to my testing script: groups count skew.

Patch rebased to current master is attached.  I'm going to improve my
testing script and post new results.

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