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

On Sun, Jul 14, 2019 at 10:16 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)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().

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

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

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

James Coleman