Re: Use incremental sort paths for window functions

On Tue, 15 Sep 2020 at 20:12, Daniel Gustafsson <daniel(at)yesql(dot)se> wrote:
>
> 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.

It's a worthy cause, but unfortunately, I don't think there's any very
realistic thing that can be done about that. The problem is that
you're deciding the "most sorted" window clause and putting that first
in the parameters to the query_planner()'s callback function. If you
wanted to try some alternative orders then it means calling
query_planner() again with some other order for
qp_extra.activeWindows.

Perhaps there's some other way of doing it so that the planner does
some sort of preliminary investigation about the best order to
evaluate the windows in. Currently, standard_qp_callback just takes
the first window and has the planner perform the join order search
based on that. Performing the join order search multiple times is
just not realistic, so it could only be done by some sort of
pre-checks. e.g, is there an index that's likely to help me obtain
this specific order. Then we'd just have to hope that through the
join search that the planner actually managed to produce a more
optimal plan than it would have if we'd left the window evaluation
order alone. It sounds pretty tricky to make cheap and good enough at
the same time.

> No comments on this version, LGTM.

Cool. Many thanks for having a look.

David