Horton

Re: [PATCH] Incremental sort (was: PoC: Partial sort)

Tomas Vondra <tomas.vondra@2ndquadrant.com>

View thread View on postgr.es
From: Tomas Vondra <tomas.vondra@2ndquadrant.com>
To: James Coleman <jtc331@gmail.com>
Cc: Simon Riggs <simon@2ndquadrant.com>, Rafia Sabih <rafia.pghackers@gmail.com>, Shaun Thomas <shaun.thomas@2ndquadrant.com>, Dmitry Dolgov <9erthalion6@gmail.com>, Alexander Korotkov <a.korotkov@postgrespro.ru>, Tom Lane <tgl@sss.pgh.pa.us>, PostgreSQL Developers <pgsql-hackers@lists.postgresql.org>
Date: 2019-06-24T20:16:01Z
Lists: pgsql-hackers 
On Mon, Jun 24, 2019 at 01:00:50PM -0400, James Coleman wrote:
>On Mon, Jun 24, 2019 at 12:56 PM Simon Riggs <simon@2ndquadrant.com> wrote:
>>
>> On Mon, 24 Jun 2019 at 16:10, James Coleman <jtc331@gmail.com> wrote:
>>>
>>> On Thu, Jun 13, 2019 at 11:38:12PM -0400, James Coleman wrote:
>>> >I think the first thing to do is get some concrete numbers on performance if we:
>>> >
>>> >1. Only sort one group at a time.
>>> >2. Update the costing to prefer traditional sort unless we have very
>>> >high confidence we'll win with incremental sort.
>>> >
>>> >It'd be nice not to have to add additional complexity if at all possible.
>>>
>>> I've been focusing my efforts so far on seeing how much we can
>>> eliminate performance penalties (relative to traditional sort). It
>>> seems that if we can improve things enough there that we'd limit the
>>> amount of adjustment needed to costing -- we'd still need to consider
>>> cases where the lower startup cost results in picking significantly
>>> different plans in a broad sense (presumably due to lower startup cost
>>> and the ability to short circuit on a limit). But I'm hopeful then we
>>> might be able to avoid having to consult MCV lists (and we wouldn't
>>> have that available in all cases anyway)
>>>
>>> As I see it the two most significant concerning cases right now are:
>>> 1. Very large batches (in particular where the batch is effectively
>>> all of the matching rows such that we're really just doing a standard
>>> sort).
>>> 2. Many very small batches.
>>
>>
>> What is the specific use case for this? This sounds quite general case.
>
>They are both general cases in some sense, but the concerns lie mostly
>with what happens when they're unexpectedly encountered. For example,
>if the expected row count or group size is off by a good bit and we
>effectively have to perform a sort of all (or most) possible rows.
>
>If we can get the performance to a point where that misestimated row
>count or group size doesn't much matter, then ISTM including the patch
>becomes a much more obvious total win.
>

Yes, that seems like a reasonable approach. Essentially, we're trying to
construct plausible worst case examples, and then minimize the overhead
compared to regular sort. If we get sufficiently close, then it's fine
to rely on somewhat shaky stats - like group size estimates.


>> Do we know something about the nearly-sorted rows that could help us?
>> Or could we introduce some information elsewhere that would help with
>> the sort?
>>
>> Could we for-example, pre-sort the rows block by block, or filter out
>> the rows that are clearly out of order, so we can re-merge them
>> later?
>
>I'm not sure what you mean by "block by block"?
>

I'm not sure what "block by block" means either.


regards

-- 
Tomas Vondra                  http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

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.