Re: Use incremental sort paths for window functions

> On 15 Sep 2020, at 01:17, David Rowley <dgrowleyml(at)gmail(dot)com> wrote:
>
> 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

Thanks!

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

Right, the combination of these two optimizations will however work well
together for quite a few cases.

On that note, assume we have the below scenario:

wfunc .. (order by a), .. (order by a,b), .. (order by a,b,c)

Currently the windows will be ordered such that a,b,c is sorted first, with a,b
and a not having to sort. I wonder if there is a good heuristic to find cases
where sorting a, then a,b incrementally and finally a,b,c incrementally is
cheaper than a big sort of a,b,c? If a,b,c would spill but subsequent
incremental sorts won't then perhaps that could be a case? Not sure if it's
worth the planner time, just thinking out loud.

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

No comments on this version, LGTM.

cheers ./daniel