Re: [PATCH] Incremental sort (was: PoC: Partial sort) - Mailing list pgsql-hackers

On Mon, Jul 15, 2019 at 09:25:32AM -0400, James Coleman wrote:
>On Sun, Jul 14, 2019 at 10:16 PM Tomas Vondra
><tomas.vondra@2ndquadrant.com> wrote:
>> >> >> Attached is a slightly modified patch series:
>> >> >>
>> >> >> 1) 0001 considers incremental sort paths in various places (adds the new
>> >> >> generate_useful_gather_paths and modifies places calling create_sort_path)
>> >> >
>> >> >I need to spend some decent time digesting this patch, but the concept
>> >> >sounds very useful.
>> >> >
>> >>
>> >> OK.
>> >
>> >I've been reading this several times + stepping through with the
>> >debugger to understand when this is useful, but I have a few
>> >questions.
>> >
>> >The first case considered in get_useful_pathkeys_for_relation (which
>> >considers root->query_pathkeys) makes a lot of sense -- obviously if
>> >we want sorted results then it's useful to consider both full and
>> >incremental sort.
>> >
>> >But I'm not sure I see yet a way to trigger the second case (which
>> >uses get_useful_ecs_for_relation to build pathkeys potentially useful
>> >for merge joins). In the FDW case we need to consider it since we want
>> >to avoid local sort and so want to see if the foreign server might be
>> >able to provide us useful presorted data, but in the local case I
>> >don't think that's useful. From what I can tell merge join path
>> >costing internally considers possible sorts of both the inner and
>> >outer input paths, and merge join plan node creation is responsible
>> >for building explicit sort nodes as necessary (i.e., there are no
>> >explicit sort paths created for merge join paths.) That means that,
>> >for example, a query like:
>> >
>> >select * from
>> >(select * from j2 order by j2.t, j2.a) j2
>> >join (select * from j1 order by j1.t) j1
>> >    on j1.t = j2.t and j1.a = j2.a;
>> >
>> >don't consider incremental sort for the merge join path (I disabled
>> >hash joins, nested loops, and full sorts testing that on an empty
>> >table just to easily force a merge join plan). And unfortunately I
>> >don't think there's an easy way to remedy that: from what I can tell
>> >it'd be a pretty invasive patch requiring refactoring merge join
>> >costing to consider both kinds of sorting (in the most simple
>> >implementation that would mean considering up to 4x as many merge join
>> >paths -- inner/outer sorted by: full/full, full/incremental,
>> >incremental/full, and incremental/incremental). Given that's a
>> >significant undertaking on its own, I think I'm going to avoid
>> >addressing it as part of this patch.
>> >
>> >If it's true that the get_useful_ecs_for_relation part of that logic
>> >isn't actually exercisable currently, that that would cut down
>> >significantly on the amount of code that needs to be added for
>> >consideration of valid gather merge paths. But if you can think of a
>> >counterexample, please let me know.
>> >
>>
>> It's quite possible parts of the code are not needed - I've pretty much
>> just copied the code and did minimal changes to get it working.
>>
>> That being said, it's not clear to me why plans like this would not be
>> useful (or why would it require changes to merge join costing):
>>
>>     Merge Join
>>       -> Gather Merge
>>           -> Incremental Sort
>>       -> Gather Merge
>>           -> Incremental Sort
>>
>> But I have not checked the code, so maybe it would, in which case I
>> think it's OK to skip it in this patch (or at least in v1 of it).
>
>Someone could correct me if I'm wrong, but I've noticed some comments
>that seem to imply we avoid plans with multiple parallel gather
>[merge]s; i.e., we try to put a single parallel node as high as
>possible in the plan. I assume that's to avoid multiplying out the
>number of workers we might consume. And in the sample query above that
>kind of plan never got considered because there were no partial paths
>to loop through (I'm not sure I fully understand why) when the new
>code is called from under apply_scanjoin_target_to_paths().
>

I think you're probably right in this case it'd be more efficient to just
do one Gather Merge on top of the merge join. And yes - we try to put the
Gather node as high as possible, to parallelize as large part of a query
as possible. Keeping the number of necessary workers low is one reason,
but it's also about the serial part in Amdahl's law.

>Of course, we should consider non-parallel incremental sort inputs to
>merge joins...but as I noted that's a lot of extra work...
>

OK, understood. I agree such plans would be useful, but if you think it'd
be a lot of extra work, then we can leave it out for now.

Although, looking at the mergejoin path construction code, it does not
seem very complex. Essentially, generate_mergejoin_paths() would need to
consider adding incremental sort on inner/outer path. It would need some
refactoring, but it's not clear to me why would this need changes to
costing? Essentially, we'd produce multiple mergejoin paths that would be
costed by the current code.

That being said, I'm perfectly fine with ignoring this for now. There are
more fundamental bits that we need to tackle first.

>> >> FWIW I'm not sure it's a good idea to look at both enable_incremental_sort
>> >> and enable_sort in cost_incremental_sort(). Not only end up with
>> >> disable_cost twice when both GUCs are set to 'off' at the moment, but it
>> >> might be useful to be able to disable those two sort types independently.
>> >> For example you might set just enable_sort=off and we'd still generate
>> >> incremental sort paths.
>> >
>> >That would cover the usage case I was getting at. Having enable_sort
>> >disable incremental sort also came in without much explanation [1]:
>> >
>> >On Fri, Apr 6, 2018 at 11:40 PM, Alexander Kuzmenkov <
>> >a(dot)kuzmenkov(at)postgrespro(dot)ru> wrote:
>> >> Also some other changes from me:
>> >> ...
>> >> enable_sort should act as a cost-based soft disable for both incremental
>> >> and normal sort.
>> >
>> >I wasn't sure that fully made sense to me, but was assuming the idea
>> >was to effectively not introduce a regression for anyone already
>> >disabling sort to force a specific plan shape. That being said, any
>> >new execution node/planning feature can cause a regression in such
>> >"hinted" queries, so I'm not sure that's a good reason on its own. In
>> >any case, incremental sort is different enough in performance
>> >qualities that I think you'd want to re-evaluate possible plans in
>> >queries where enable_sort=off is useful, so I'm going make incremental
>> >sort independent of enable_sort unless there's a strong objection
>> >here.
>> >
>>
>> OK
>>
>> >Tangentially: I'd almost expect enable_incremental_sort to act as a
>> >hard disable (and not even generate the paths) rather than a soft
>> >cost-based disable, since while standard sort is the most basic
>> >operation that needs to always be available as a last resort the same
>> >is not true for incremental sort...
>> >
>>
>> Good point. It's somewhat similar to options like enable_parallel_hash
>> which also are "hard" switches (i.e. not cost-based penalties).
>
>I assume the proper approach here then is to check the GUC before
>building and adding the path?
>

Yeah. The simplest way to do that might be setting the number of presorted
keys to 0 in pathkeys_common_contained_in(). That effectively says it
makes no sense to do incremental sort. It's a bit too deep, though - not
sure it does not affect any other plans, though.

Or you might reference the GUC in every place that considers incremental
sort, but that's going to be a lot of places.

>> >If we end up wanting to limit the number of places we consider
>> >incremental sort (whether for planning time or merely for size of the
>> >initial patch, do you have any thoughts on what general areas we
>> >should consider most valuable? Besides the obvious LIMIT case aother
>> >area that might benefit was min/max, though I'm not sure yet at the
>> >moment if that would really end up meaning considering it all over the
>> >place.
>> >
>>
>> OK, sounds like a plan!
>
>Did you have any thoughts on the question about where this is likely
>to be most valuable?
>

Good question. I can certainly list some generic cases where I'd expect
incremental sort to be most beneficial:

1) (ORDER BY + LIMIT) - in this case the main advantage is low startup
cost (compared to explicit sort, which has to fetch/sort everything)

2) ORDER BY with on-disk sort - in this case the main advantage is ability
to sort data in small chunks that fit in memory, instead of flushing large
amounts of data into temporary files

Of course, (2) helps with any operation that can leverage the ordering,
i.e. aggregation/...

But the question is how to map this to places in the source code. I don't
have a very good answer to that :-(

IMO the best thing we can do is get some realistic queries, and address
them first. And then eventually add incremental sort to some other places. 


regards

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