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

On Sat, Mar 28, 2020 at 2:54 PM Tomas Vondra
<tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
> ...
> >> >> >9. optimizer/path/allpaths.c get_useful_pathkeys_for_relation:
> >> >> >* Considering query_pathkeys is always worth it, because it might let us
> >> >> >* avoid a local sort.
> >> >> >
> >> >> >That originally was a copy from the fdw code, but since the two
> >> >> >functions have diverged (Is that concerning? I could be confusing, but
> >> >> >isn't a compilation problem) I didn't move the function.
> >> >> >
> >> >>
> >> >> I think it's OK the two functions diverged, it's simply because the FDW
> >> >> one needs to check other things too. But I might rework this once I look
> >> >> closer at truncate_useless_pathkeys.
> >> >
> >> >Agreed, for now at least. It's tempting to think they should always be
> >> >shared, but I'm not convinced (without a lot more digging) that this
> >> >represents structural rather than incidental duplication.
> >> >
> >>
> >> The more I look at pathkeys_useful_for_ordering() the more I think the
> >> get_useful_pathkeys_for_relation() function should look more like it
> >> than the postgres_fdw one ...
> >
> >If we go down that path (and indeed this is actually implied by
> >removing the volatile check too), doesn't that really just mean (at
> >least for now) that get_useful_pathkeys_for_relation goes away
> >entirely and we effectively use root->query_pathkeys directly?
>
> Yes, basically.
>
> >The only thing your lose them is the check that each eclass has a
> >member in the rel. But that check probably wasn't quite right anyway:
> >at least for incremental sort (maybe not regular sort), I think we
> >probably don't necessarily care that the entire list has members in the
> >rel, but rather that some prefix does, right?
>
> Probably, although I always forget how exactly this EC business works.
> My reasoning is more "If pathkeys_useful_for_ordering does not need
> that, why should we need it here?"

i think it effectively does, since it's called by
truncate_useless_pathkeys with the pathkeys list a path provides and
root-query_pathkeys and tries to find a prefix.

So if there wasn't a prefix of matching eclasses, we'd return 0 as the
number of matching prefix pathkeys, and thus a NIL list to the caller
of truncate_useless_pathkeys.

> >The idea there would be that we could create a gather merge here that
> >supplies a partial ordering (that prefix of query_pathkeys) and then
> >above it the planner might place another incremental sort (say above a
> >join), or perhaps even a join above that would actually be sufficient
> >(since many joins are capable of providing an ordering anyway).
> >
>
> Not sure. Isn't the idea that we do the Incremental Sort below the
> Gather Merge, because then it's actually done in parallel?

Yeah, I think as I was typing this my ideas got kinda mixed up a bit,
or at least was confusing. The incremental sort *would* need a path
that is ordered by a prefix of query_pathkeys and provide the sort on
the full query_pathkeys.

But the incremental sort at this point would still be on a path with a
given rel, and that path's rel would need to contain all of the
eclasses for the pathkeys we want as the final ordering to be able to
sort on them, right? For example, suppose:
select * from t join s order by t.a, s.b -- index on t.a

We'd have a presorted path on t.a that's has a prefix of the
query_pathkeys, but we couldn't have the incremental sort on path
whose rel only contained t, right? It'd have to a rel that was the
result of the join, otherwise we don't yet have access to s.b.

Given that, I think we have two options in this code. Suppose query
pathkeys (a, b, c):
1. Build an incremental sort path on (a, b, c) if we have a path
ordered by (a) or (a, b) but only when (c) is already available.
2. Additionally, (for the most possible paths generated): build an
incremental sort path on (a, b) if we have a path ordered by (a) but
(c) isn't yet available.

Either way I think we need the ability to know if all (or some subset)
of the query pathkeys are for eclasses we have access to in the
current rel.

> >I've attached (added prefix .txt to avoid the cfbot assuming this is a
> >full series) an idea in that direction to see if we're thinking along
> >the same route. You'll want to apply and view with `git diff -w`
> >probably.
> >
> >The attached also adds a few XXX comments. In particular, I wonder if
> >we should verify that some prefix of the root->query_pathkeys is
> >actually made up of eclass members for the current rel, because
> >otherwise I think we can skip the loop on the subpaths entirely.
> >
>
> Hmmm, that's an interesting possible optimization. I wonder if that
> actually saves anything, though, because the number of paths in the loop
> is likely fairly low.

If what I said above is correct (and please poke holes in it if
possible), then I think we have to know the matching eclass count
anyway, so we might as well include the optimization since it'd be a
simple int comparison.

> >> >> >I did notice though that find_em_expr_for_rel() is wholesale
> >> >> >copied (and unchanged) from the fdw code, so I moved it to
> >> >> >equivclass.c so both places can share it.
> >> >> >
> >> >>
> >> >> +1
> >> >>
> >>
> >> ... which would also get rid of find_em_expr_for_rel().
> >
> >... which, I think, would retain the need for find_em_expr_for_rel().
> >
> >Note: The attached applied to the previous series compiles and runs
> >make check...but I haven't really tested it; it's meant more for "is
> >this the direction we want to go".
> >
>
> Thanks, I'll take a look.

James