Re: Use incremental sort paths for window functions

On Tue, 15 Sep 2020 at 05:19, Tomas Vondra <tomas(dot)vondra(at)2ndquadrant(dot)com> wrote:
>
> On Wed, Jul 08, 2020 at 04:57:21PM +1200, David Rowley wrote:
> >Over on [1] someone was asking about chained window paths making use
> >of already partially sorted input. (The thread is on -general, so I
> >guessed they're not using PG13.)
> >
> >However, On checking PG13 to see if incremental sort would help their
> >case, I saw it didn't. Looking at the code I saw that
> >create_window_paths() and create_one_window_path() don't make any use
> >of incremental sort paths.
> >
> >I quickly put together the attached. It's only about 15 mins of work,
> >but it seems worth looking at a bit more for some future commitfest.
> >Yeah, I'll need to add some tests as I see nothing failed by changing
> >this.
> >
>
> Yeah, I'm sure there are a couple other places that might benefit from
> incremental sort but were not included in the PG13 commit. The patch
> seems correct - did it help in the reported thread? How much?

Looks like I didn't mention the idea on the thread. I must have felt
it was just too many steps away from being very useful to mention it
in the -general thread.

I suppose it'll help similar to any use case for incremental sort;
lots in some and less so in others. It'll mostly depend on how big
each incremental sort is. e.g order by a,b when there's only an index
on (a) will be pretty good if a is unique. Each sort will be over
quite fast. If there are a million rows for each value of a then
incremental sort would be less favourable

> I suppose this might benefit from an optimization similar to the GROUP
> BY reordering discussed in [1]. For example, with
>
> max(a) over (partition by b,c)
>
> I think we could use index on (c) and consider incremental sort by c,b,
> i.e. with the inverted pathkeys. But that's a completely independent
> topic, I believe.

I've only vaguely followed that. Sounds like interesting work, but I
agree that it's not related to this.

Thanks for having a look at this.

David