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

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.

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

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

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

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

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

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

James Coleman

[1]: https://www.postgresql.org/message-id/CAPpHfdtKHETXhf062CPvkjpG1wnjQ7rv4uLhZgYQ6VZjwqDYpg%40mail.gmail.com