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

Note: As I was writing this, I saw a new email come in from Tomas with
a new patch series, and some similar observations. I'll look at that
patch series more, but I think it's likely far more complete, so will
end up going with that. I wanted to send this email anyway to at least
capture the debugging process for reference.

On Mon, Jul 8, 2019 at 12:07 PM James Coleman <jtc331(at)gmail(dot)com> wrote:
>
> On Mon, Jul 8, 2019 at 10:58 AM Tomas Vondra
> <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> >
> > On Mon, Jul 08, 2019 at 10:32:18AM -0400, James Coleman wrote:
> > >On Mon, Jul 8, 2019 at 9:59 AM Tomas Vondra
> > ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> > >>
> > >> On Mon, Jul 08, 2019 at 09:22:39AM -0400, James Coleman wrote:
> > >> >On Sun, Jul 7, 2019 at 5:02 PM Tomas Vondra
> > >> ><tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> > >> >> We're running query like this:
> > >> >>
> > >> >> SELECT a, sum(b), count(*) FROM pagg_tab_ml GROUP BY a HAVING avg(b) < 3 ORDER BY 1, 2, 3
> > >> >>
> > >> >> but we're trying to add the incremental sort *before* the aggregation,
> > >> >> because the optimizer also considers group aggregate with a sorted
> > >> >> input. And (a) is a prefix of (a,sum(b),count(b)) so we think we
> > >> >> actually can do this, but clearly that's nonsense, because we can't
> > >> >> possibly know the aggregates yet. Hence the error.
> > >> >>
> > >> >> If this is the actual issue, we need to ensure we actually can evaluate
> > >> >> all the pathkeys. I don't know how to do that yet. I thought that maybe
> > >> >> we should modify pathkeys_common_contained_in() to set presorted_keys to
> > >> >> 0 in this case.
> > >> >>
> > >> >> But then I started wondering why we don't see this issue even for
> > >> >> regular (non-incremental-sort) paths built in create_ordered_paths().
> > >> >> How come we don't see these failures there? I've modified costing to
> > >> >> make all incremental sort paths very cheap, and still nothing.
> > >> >
> > >> >I assume you mean you modified costing to make regular sort paths very cheap?
> > >> >
> > >>
> > >> No, I mean costing of incremental sort paths, so that they end up being
> > >> the cheapest ones. If some other path is cheaper, we won't see the error
> > >> because it only happens when building plan from the cheapest path.
> > >
> > >Ah, I misunderstood as you trying to figure out a way to try to cause
> > >the same problem with a regular sort.
> > >
> > >> >> So presumably there's a check elsewhere (either implicit or explicit),
> > >> >> because create_ordered_paths() uses pathkeys_common_contained_in() and
> > >> >> does not have the same issue.
> > >> >
> > >> >Given this comment in create_ordered_paths():
> > >> >
> > >> > generate_gather_paths() will have already generated a simple Gather
> > >> > path for the best parallel path, if any, and the loop above will have
> > >> > considered sorting it. Similarly, generate_gather_paths() will also
> > >> > have generated order-preserving Gather Merge plans which can be used
> > >> > without sorting if they happen to match the sort_pathkeys, and the loop
> > >> > above will have handled those as well. However, there's one more
> > >> > possibility: it may make sense to sort the cheapest partial path
> > >> > according to the required output order and then use Gather Merge.
> > >> >
> > >> >my understanding is that generate_gather_paths() only considers paths
> > >> >that already happen to be sorted (not explicit sorts), so I'm
> > >> >wondering if it would make more sense for the incremental sort path
> > >> >creation for this case to live alongside the explicit ordered path
> > >> >creation in create_ordered_paths() rather than in
> > >> >generate_gather_paths().
> > >> >
> > >>
> > >> How would that solve the issue? Also, we're building a gather path, so
> > >> I think generate_gather_paths() is the right place where to do it. And
> > >> we're not changing the semantics of generate_gather_paths() - the result
> > >> path should be sorted "correctly" with respect to sort_pathkeys.
> > >
> > >Does that imply what the explicit sort in create_ordered_paths() is in
> > >the wrong spot?
> > >
> >
> > I think those are essentially the right places where to do this sort of
> > stuff. Maybe there's a better place, but I don't think those places are
> > somehow wrong.
> >
> > >Or, to put it another way, do you think that both kinds of sorts
> > >should be added in the same place? It seems confusing to me that
> > >they'd be split between the two methods (unless I'm completely
> > >misunderstanding how the two work).
> > >
> >
> > The paths built in those two places were very different in one aspect:
> >
> > 1) generate_gather_paths only ever looked at pathkeys for the subpath, it
> > never even looked at ordering expected by paths above it (or the query as
> > a whole). Plain Gather ignores pathkeys entirely, Gather Merge only aims
> > to maintain ordering of the different subpaths.
> >
> > 2) create_oredered_paths is meant to enforce ordering needed by upper
> > parts of the plan - either by using a properly sorted path, or adding an
> > explicit sort.
> >
> >
> > We want to extend (1) to also look at ordering expected by the upper parts
> > of the plan, and consider incremental sort if applicable. (2) already does
> > that, and it already has the correct pathkeys to enforce.
>
> 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?

To try to understand this better I looked through all usages of
generate_gather_paths(). The usage in gather_grouping_paths() also
treats explicit sorting as its responsibility rather than the
responsibility of generate_gather_paths(). Since I consider
incremental sort to be just another form of explicit sorting, I think
it's reasonable to make it the responsibility of callers, given that
currently generate_gather_paths() currently seems to be explicitly
only about fully presorted paths.

Of course that might not be ideal the more callers that have to handle
it specially. So maybe it's worth shifting responsibility.

> > But looking at root->sort_pathkeys in (1) seems to be the wrong thing :-(
> >
> > The thing is, we don't have just sort_pathkeys, there's distinct_pathkeys
> > and group_pathkeys too, so maybe we should be looking at those too?
>
> I don't know enough yet to answer, but I'd like to look at (in the
> debugger) the subpaths considered in each function to try to get a
> better understanding of why we don't try to explicitly sort the aggs
> (which we know we can't sort yet) but do for incremental sort. I
> assume that means a subpath has to be present in one but not the other
> since they both use the same pathkey checking function.

I stepped through one of the failing test cases and found that in
create_ordered_paths() the if expression fails because
input_rel->partial_pathlist == NIL. So apparently that is the guard
against incorrectly adding as-yet unsortable paths below the
aggregate. So if I move the create_incremental_sort_path() call inside
this block the error goes away.

Attached is patch revision with that changes that.

James Coleman