Re: Use incremental sort paths for window functions

On Tue, 15 Sep 2020 at 00:02, Daniel Gustafsson <daniel(at)yesql(dot)se> wrote:
>
> > On 8 Jul 2020, at 06:57, David Rowley <dgrowleyml(at)gmail(dot)com> 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.)
>
> The [1] reference wasn't qualified, do you remember which thread it was?

That was sloppy of me. It's
https://www.postgresql.org/message-id/CADd42iFZWwYNsXjEM_3HWK3QnfiCrMNmpOkZqyBQCabnVxOPtw%40mail.gmail.com

> > 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.
>
> Commit 728202b63cdcd7f counteracts this optimization in part since it orders
> the windows such that the longest common prefix is executed first to allow
> subsequent windows to skip sorting entirely.

This would have been clearer if I'd remembered to include the link to
the thread. The thread talks about sorting requirements like c1, c3
then c1, c4. So it can make use of the common prefix and do
incremental sorts.

It sounds like you're talking about cases like: wfunc() over (order by
a), wfunc2() over (order by a,b). Where we can just sort on a,b and
have that order work for the first wfunc(). That's a good optimisation
but does not work for the above case.

> That being said, it's only in part and when the stars don't align with sub-
> sequently shorter common prefixes then incremental sort can help. A synthetic
> unscientific test with three windows over 10M rows, where no common prefix
> exists, shows consistent speedups (for worst cases) well past what can be
> attributed to background noise.
>
> > 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.
>
> A few comments on the patch: there is no check for enable_incremental_sort, and
> it lacks tests (as already mentioned) for the resulting plan.

Yeah, it should be making sure enable_incremental_sort is on for sure.
I've attached another version with a few tests added too.

David