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

On Sun, Jul 14, 2019 at 02:38:40PM -0400, James Coleman wrote:
>On Tue, Jul 9, 2019 at 10:54 AM Tomas Vondra
><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>>
>> On Tue, Jul 09, 2019 at 09:28:42AM -0400, James Coleman wrote:
>> >On Mon, Jul 8, 2019 at 9:37 PM Tomas Vondra
>> ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>> >>
>> >> On Mon, Jul 08, 2019 at 12:07:06PM -0400, James Coleman wrote:
>> >> > ...
>> >> >
>> >> >I guess I'm still not following. If (2) is responsible (currently) for
>> >> >adding an explicit sort, why wouldn't adding an incremental sort be an
>> >> >example of that responsibility? The subpath that either a Sort or
>> >> >IncrementalSort is being added on top of (to then feed into the
>> >> >GatherMerge) is the same in both cases right?
>> >> >
>> >> >Unless you're saying that the difference is that since we have a
>> >> >partial ordering already for incremental sort then incremental sort
>> >> >falls into the category of "maintaining" existing ordering of the
>> >> >subpath?
>> >> >
>> >>
>> >> Oh, I think I understand what you're saying. Essentially, we should not
>> >> be making generate_gather_paths responsible for adding the incremental
>> >> sort. Instead, we should be looking at places than are adding explicit
>> >> sort (using create_sort_path) and also consider adding incremental sort.
>> >>
>> >> I definitely agree with the second half - we should look at all places
>> >> that create explicit sorts and make them also consider incremental
>> >> sorts. That makes sense.
>> >
>> >Yep, exactly.
>> >
>>
>> If I remember correctly, one of the previous patch versions (in the early
>> 2018 commitfests) actually modified many of those places, but it did that
>> in a somewhat "naive" way. It simply used incremental sort whenever the
>> path was partially sorted, or something like that. So it did not use
>> costing properly. There was an attempt to fix that in the last commitfest
>> but the costing model was deemed to be a bit too rough and unreliable
>> (especially the ndistinct estimates can be quite weak), so the agreement
>> was to try salvaging the patch for PG11 by only considering incremental
>> sort in "safest" places with greatest gains.
>>
>> We've significantly improved the costing model since then, and the
>> implementation likely handles the corner cases much better. But that does
>> not mean we have to introduce the incremental sort to all those places at
>> once - it might be wise to split that into separate patches.
>
>Yes, although we haven't added the MCV checking yet; that's on my
>mental checklist, but another new area of the codebase for me to
>understand, so I've been prioritizing other parts of the patch.
>

Sure, no problem.

>> It's not just about picking the right plan - we've kinda what impact these
>> extra paths might have on planner performance, so maybe we should look at
>> that too. And the impact might be different for each of those places.
>>
>> I'll leave that up to you, but I certainly won't insist on doing it all in
>> one huge patch.
>
>I'm not opposed to handling some of them separately, but I would like
>to at least hit the places where it's most likely (for example, with
>LIMIT) to improve things. I supposed I'll have to look at all of the
>usages of create_sort_path() and try to rank them in terms of
>perceived likely value.
>

Yep, makes sense.

>> >> But I'm not sure it'll address all cases - the problem is that those
>> >> places add the explicit sort because they need sorted input. Gather
>> >> Merge does not do that, it only preserves existing ordering of paths.
>> >>
>> >> So it's possible the path does not have an explicit sort on to, and
>> >> gather merge will not know to add it. And once we have the gather merge
>> >> in place, we can't push place "under" it.
>> >
>> >That's the explanation I was missing; and it makes sense (to restate:
>> >sometimes sorting is useful even when not required for correctness of
>> >the user returned data).
>> >
>>
>> Yes, although even when the sorting is required for correctness (because
>> the user specified ORDER BY) you can do it at different points in the
>> plan. We'd still produce correct results, but the sort might be done at
>> the very end without these changes.
>>
>> For example we might end up with plans
>>
>> Incremental Sort (presorted: a, path keys: a,b)
>> -> Gather Merge (path keys: a)
>> -> Index Scan (path keys: a)
>>
>> but with those changes we might push the incremental sort down into the
>> parallel part:
>>
>> Gather Merge (path keys: a,b)
>> -> Incremental Sort (presorted: a, path keys: a,b)
>> -> Index Scan (path keys: a)
>>
>> which is likely better. Perhaps that's what you meant, though.
>
>I was thinking of ordering being useful for grouping/aggregation or
>merge joins; I didn't realize the above plan wasn't possible yet, so
>that explanation is helpful.
>
>> >> And I think I know why is that - while gather_grouping_paths() tries to
>> >> add explicit sort below the gather merge, there are other places that
>> >> call generate_gather_paths() that don't do that. In this case it's
>> >> probably apply_scanjoin_target_to_paths() which simply builds
>> >>
>> >> parallel (seq|index) scan + gather merge
>> >>
>> >> and that's it. The problem is likely the same - the code does not know
>> >> which pathkeys are "interesting" at that point. We probably need to
>> >> teach planner to do this.
>> >
>> >I had also noticed that that was an obvious place where
>> >generate_gather_paths() was used but an explicit sort wasn't also
>> >added separately, which makes me think the division of labor is
>> >probably currently wrong regardless of the incremental sort patch.
>> >
>> >Do you agree? Should we try to fix that (likely with your new
>> >"interesting paths" version of generate_gather_paths()) first as a
>> >prefix patch to adding incremental sort?
>> >
>>
>> I'm not sure what the generate_useful_gather_paths() should do but does
>> not? Or is it just the division of labor that you think is wrong? In any
>> case, feel free to whack it until you're happy with it.
>
>Oh, I didn't mean to imply generate_useful_gather_paths() was
>deficient in some way; I was noting that I'd noticed that
>apply_scanjoin_target_to_paths() didn't consider explicit sort +
>gather merge on master, and that maybe that was an unintentional miss
>and something that should be remedied.
>
>And if it is a miss, then that would demonstrate in my mind that the
>addition of generate_useful_gather_paths() would be a helpful refactor
>as a standalone patch even without incremental sort. So "currently
>wrong" above meant "on master" not "in the current version of the
>patch."
>

Ah, OK. I don't know if it's a miss or intentional omission - it might
be a mix of both, actually. I wouldn't be surprised if doing that was
considered and considered not worth it, but if we can come up with a
plan where adding an explicit sort here helps ...

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

>> >> 2) 0002 and 0003 are fixes I mentioned before
>
>I'm incorporating those with a bit of additional cleanup.
>
>> >> 3) 0004 adds a new GUC force_incremental_sort that (when set to 'on')
>> >> tries to nudge the optimizer into using incremental sort by essentially
>> >> making it free (i.e. using startup/total costs of the subpath). I've found
>> >> this useful when trying to force incremental sorts into plans where it may
>> >> not be the best strategy.
>> >
>> >That will be super helpful. I do wonder if we need to expose (in the
>> >production patch) a GUC of some kind to adjust incremental sort
>> >costing so that users can try to tweak when it is preferred over
>> >regular sort.
>> >
>>
>> This GUC is really meant primarily for development, to force choice of
>> incremental sort during regression tests (so as to use incremental sort in
>> as many plans as possible). I'd remove it from the final patch. I think
>> the general consensus on pgsql-hackers is that we should not introduce
>> GUCs unless absolutely necessary. But for development GUCs - sure.
>>
>> 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).

>> Another thing we should have is a collection of tests with data sets that
>> "break" the costing model in some way (skew, correlated columns,
>> non-uniform group sizes, ...). That's something not meant for commit,
>> because it'll probably require significant amounts of data, but we need it
>> to asses the quality of the planner/costing part. I know there are various
>> ad-hoc test cases in the thread history, it'd be good to consolidate that
>> into once place.
>
>Agreed.
>
>I'm continuing to work on the planning side of this with the goal of
>not needing to modify too many places to consider an incremental sort
>path + considering which ones are most likely to be useful, but I
>wanted to get my questions about get_useful_ecs_for_relation sent out
>while I work on that.
>
>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!

regards

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