Todo: Teach planner to evaluate multiple windows in the optimal order

On Mon, 26 Dec 2022 at 02:04, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

Point #1

In the above query Oracle 10g performs 2 sorts, DB2 and Sybase perform 3
sorts. We also perform 3.

This shouldn't be too hard to do. See the code in
select_active_windows(). You'll likely want to pay attention to the
DISTINCT pathkeys if they exist and just use the ORDER BY pathkeys if
the query has no DISTINCT clause. DISTINCT is evaluated after Window
and before ORDER BY.

One idea to implement this would be to adjust the loop in
select_active_windows() so that we record any WindowClauses which have
the pathkeys contained in the ORDER BY / DISTINCT pathkeys then record
those separately and append those onto the end of the actives array
after the sort.

I do think you'll likely want to put any WindowClauses which have
pathkeys which are a true subset or true superset of the ORDER BY /
DISTINCT pathkeys last. If they're a superset then we won't need to
perform any additional ordering for the DISTINCT / ORDER BY clause.
If they're a subset then we might be able to perform an Incremental
Sort, which is likely much cheaper than a full sort. The existing
code should handle that part. You just need to make
select_active_windows() more intelligent.

You might also think that we could perform additional optimisations
and also adjust the ORDER BY clause of a WindowClause if it contains
the pathkeys of the DISTINCT / ORDER BY clause. For example:

SELECT *,row_number() over (order by a,b) from tab order by a,b,c;

However, if you were to adjust the WindowClauses ORDER BY to become
a,b,c then you could produce incorrect results for window functions
that change their result based on peer rows.

Note the difference in results from:

create table ab(a int, b int);
insert into ab select x,y from generate_series(1,5) x, generate_Series(1,5)y;

select a,b,count(*) over (order by a) from ab order by a,b;
select a,b,count(*) over (order by a,b) from ab order by a,b;

and Point #2

Teach planner to decide which window to evaluate first based on costs.
Currently the first window in the query is evaluated first, there may be no
index to help sort the first window, but perhaps there are for other windows
in the query. This may allow an index scan instead of a seqscan -> sort.

What Tom wrote about that in the first paragraph of [1]/messages/by-id/11535.1230501658@sss.pgh.pa.us still applies.
The problem is that if the query contains many joins that to properly
find the cheapest way of executing the query we'd have to perform the
join search once for each unique sort order of each WindowClause.
That's just not practical to do from a performance standpoint. The
join search can be very expensive. There may be something that could
be done to better determine the most likely candidate for the first
WindowClause using some heuristics, but I've no idea what those would
be. You should look into point #1 first. Point #2 is significantly
more difficult to solve in a way that would be acceptable to the
project.

David

[1]: /messages/by-id/11535.1230501658@sss.pgh.pa.us

On 03/01/23 08:21, David Rowley wrote:

On Mon, 26 Dec 2022 at 02:04, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

Point #1

In the above query Oracle 10g performs 2 sorts, DB2 and Sybase perform 3
sorts. We also perform 3.

This shouldn't be too hard to do. See the code in
select_active_windows(). You'll likely want to pay attention to the
DISTINCT pathkeys if they exist and just use the ORDER BY pathkeys if
the query has no DISTINCT clause. DISTINCT is evaluated after Window
and before ORDER BY.

One idea to implement this would be to adjust the loop in
select_active_windows() so that we record any WindowClauses which have
the pathkeys contained in the ORDER BY / DISTINCT pathkeys then record
those separately and append those onto the end of the actives array
after the sort.

I do think you'll likely want to put any WindowClauses which have
pathkeys which are a true subset or true superset of the ORDER BY /
DISTINCT pathkeys last. If they're a superset then we won't need to
perform any additional ordering for the DISTINCT / ORDER BY clause.
If they're a subset then we might be able to perform an Incremental
Sort, which is likely much cheaper than a full sort. The existing
code should handle that part. You just need to make
select_active_windows() more intelligent.

You might also think that we could perform additional optimisations
and also adjust the ORDER BY clause of a WindowClause if it contains
the pathkeys of the DISTINCT / ORDER BY clause. For example:

SELECT *,row_number() over (order by a,b) from tab order by a,b,c;

However, if you were to adjust the WindowClauses ORDER BY to become
a,b,c then you could produce incorrect results for window functions
that change their result based on peer rows.

Note the difference in results from:

create table ab(a int, b int);
insert into ab select x,y from generate_series(1,5) x, generate_Series(1,5)y;

select a,b,count(*) over (order by a) from ab order by a,b;
select a,b,count(*) over (order by a,b) from ab order by a,b;

Thanks, let me try this.

and Point #2

Teach planner to decide which window to evaluate first based on costs.
Currently the first window in the query is evaluated first, there may be no
index to help sort the first window, but perhaps there are for other windows
in the query. This may allow an index scan instead of a seqscan -> sort.

What Tom wrote about that in the first paragraph of [1] still applies.
The problem is that if the query contains many joins that to properly
find the cheapest way of executing the query we'd have to perform the
join search once for each unique sort order of each WindowClause.
That's just not practical to do from a performance standpoint. The
join search can be very expensive. There may be something that could
be done to better determine the most likely candidate for the first
WindowClause using some heuristics, but I've no idea what those would
be. You should look into point #1 first. Point #2 is significantly
more difficult to solve in a way that would be acceptable to the
project.

Okay, leaving this out for now.

--
Regards,
Ankit Kumar Pandey

Hi,

On 03/01/23 08:21, David Rowley wrote:

I do think you'll likely want to put any WindowClauses which have
pathkeys which are a true subset or true superset of the ORDER BY /
DISTINCT pathkeys last. If they're a superset then we won't need to
perform any additional ordering for the DISTINCT / ORDER BY clause.
If they're a subset then we might be able to perform an Incremental
Sort, which is likely much cheaper than a full sort. The existing
code should handle that part. You just need to make
select_active_windows() more intelligent.

I think current implementation does exactly this.

#1. If order by clause in the window function is subset of order by in query

create table abcd(a int, b int, c int, d int);
insert into abcd select x,y,z,c from generate_series(1,5) x, generate_Series(1,5)y, generate_Series(1,5) z, generate_Series(1,5) c;
explain analyze select a,row_number() over (order by b),count(*) over (order by a,b) from abcd order by a,b,c;

QUERY PLAN

--------------------------------------------------------------------------------------------------------------------------
--------
Incremental Sort (cost=80.32..114.56 rows=625 width=28) (actual time=1.440..3.311 rows=625 loops=1)
Sort Key: a, b, c
Presorted Key: a, b
Full-sort Groups: 13 Sort Method: quicksort Average Memory: 28kB Peak Memory: 28kB
-> WindowAgg (cost=79.24..91.74 rows=625 width=28) (actual time=1.272..2.567 rows=625 loops=1)
-> Sort (cost=79.24..80.80 rows=625 width=20) (actual time=1.233..1.296 rows=625 loops=1)
Sort Key: a, b
Sort Method: quicksort Memory: 64kB
-> WindowAgg (cost=39.27..50.21 rows=625 width=20) (actual time=0.304..0.786 rows=625 loops=1)
-> Sort (cost=39.27..40.84 rows=625 width=12) (actual time=0.300..0.354 rows=625 loops=1)
Sort Key: b
Sort Method: quicksort Memory: 54kB
-> Seq Scan on abcd (cost=0.00..10.25 rows=625 width=12) (actual time=0.021..0.161 rows=625 l
oops=1)
Planning Time: 0.068 ms
Execution Time: 3.509 ms
(15 rows)

Here, as window function (row count) has two cols a, b for order by,
incremental sort is performed for remaining col in query,

which makes sense.

#2. If order by clause in the Window function is superset of order by in
query

explain analyze select a,row_number() over (order by a,b,c),count(*) over (order by a,b) from abcd order by a;

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
WindowAgg (cost=39.27..64.27 rows=625 width=28) (actual time=1.089..3.020 rows=625 loops=1)
-> WindowAgg (cost=39.27..53.34 rows=625 width=20) (actual time=1.024..1.635 rows=625 loops=1)
-> Sort (cost=39.27..40.84 rows=625 width=12) (actual time=1.019..1.084 rows=625 loops=1)
Sort Key: a, b, c
Sort Method: quicksort Memory: 54kB
-> Seq Scan on abcd (cost=0.00..10.25 rows=625 width=12) (actual time=0.023..0.265 rows=625 loops=1)
Planning Time: 0.071 ms
Execution Time: 3.156 ms
(8 rows)

No, additional sort is needed to be performed in this case, as you referred.

On 03/01/23 08:21, David Rowley wrote:

If they're a superset then we won't need to perform any additional
ordering for the DISTINCT / ORDER BY clause.
If they're a subset then we might be able to perform an Incremental
Sort, which is likely much cheaper than a full sort.

So question is, how current implementation is different from desired one?

--
Regards,
Ankit Kumar Pandey

On Wed, 4 Jan 2023 at 03:11, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

#2. If order by clause in the Window function is superset of order by in query

explain analyze select a,row_number() over (order by a,b,c),count(*) over (order by a,b) from abcd order by a;

QUERY PLAN
----------------------------------------------------------------------------------------------------------------------
WindowAgg (cost=39.27..64.27 rows=625 width=28) (actual time=1.089..3.020 rows=625 loops=1)
-> WindowAgg (cost=39.27..53.34 rows=625 width=20) (actual time=1.024..1.635 rows=625 loops=1)
-> Sort (cost=39.27..40.84 rows=625 width=12) (actual time=1.019..1.084 rows=625 loops=1)
Sort Key: a, b, c
Sort Method: quicksort Memory: 54kB
-> Seq Scan on abcd (cost=0.00..10.25 rows=625 width=12) (actual time=0.023..0.265 rows=625 loops=1)
Planning Time: 0.071 ms
Execution Time: 3.156 ms
(8 rows)

No, additional sort is needed to be performed in this case, as you referred.

It looks like that works by accident. I see no mention of this either
in the comments or in [1]/messages/by-id/124A7F69-84CD-435B-BA0E-2695BE21E5C2@yesql.se. What seems to be going on is that
common_prefix_cmp() is coded in such a way that the WindowClauses end
up ordered by the highest tleSortGroupRef first, resulting in the
lowest order tleSortGroupRefs being the last WindowAgg to be
processed. We do transformSortClause() before
transformWindowDefinitions(), this is where the tleSortGroupRef
indexes are assigned, so the ORDER BY clause will have a lower
tleSortGroupRef than the WindowClauses.

If we don't have one already, then we should likely add a regression
test that ensures that this remains true. Since it does not seem to
be documented in the code anywhere, it seems like something that could
easily be overlooked if we were to ever refactor that code.

I just tried moving the calls to transformWindowDefinitions() so that
they come before transformSortClause() and our regression tests still
pass. That's not great.

With that change, the following query has an additional sort for the
ORDER BY clause which previously wasn't done.

explain select a,b,c,row_number() over (order by a) rn1, row_number()
over(partition by b) rn2, row_number() over (order by c) from abc
order by b;

David

[1]: /messages/by-id/124A7F69-84CD-435B-BA0E-2695BE21E5C2@yesql.se

On 04/01/23 09:32, David Rowley wrote:

It looks like that works by accident. I see no mention of this either
in the comments or in [1].

This kind of troubles me because function name
/select_active_windows///doesn't tell me if its only job is

to reorder window clauses for optimizing sort. From code, I don't see it
doing anything else either.

If we don't have one already, then we should likely add a regression
test that ensures that this remains true. Since it does not seem to
be documented in the code anywhere, it seems like something that could
easily be overlooked if we were to ever refactor that code.

I don't see any tests in windows specific to sorting operation (and in
what order). I will add those.

Also, one thing, consider the following query:

explain analyze select row_number() over (order by a,b),count(*) over
(order by a) from abcd order by a,b,c;

In this case, sorting is done on (a,b) followed by incremental sort on c
at final stage.

If we do just one sort: a,b,c at first stage then there won't be need to
do another sort (incremental one).

Now, I am not sure if which one would be faster: sorting (a,b,c) vs
sort(a,b) + incremental sort(c)

because even though datum sort is fast, there can be n number of combos
where we won't be doing that.

I might be looking at extreme corner cases though but still wanted to share.

--
Regards,
Ankit Kumar Pandey

Attaching test cases for this (+ small change in doc).

Tested this in one of WIP branch where I had modified
select_active_windows and it failed

as expected.

Please let me know if something can be improved in this.

Regards,
Ankit Kumar Pandey

On 05/01/23 07:48, Vik Fearing wrote:

On 1/4/23 13:07, Ankit Kumar Pandey wrote:

Also, one thing, consider the following query:

explain analyze select row_number() over (order by a,b),count(*) over
(order by a) from abcd order by a,b,c;

In this case, sorting is done on (a,b) followed by incremental sort
on c at final stage.

If we do just one sort: a,b,c at first stage then there won't be need
to do another sort (incremental one).

This could give incorrect results.  Consider the following query:

postgres=# select a, b, c, rank() over (order by a, b)
from (values (1, 2, 1), (1, 2, 2), (1, 2, 1)) as abcd (a, b, c)
order by a, b, c;

 a | b | c | rank
---+---+---+------
 1 | 2 | 1 |    1
 1 | 2 | 1 |    1
 1 | 2 | 2 |    1
(3 rows)

If you change the window's ordering like you suggest, you get this
different result:

postgres=# select a, b, c, rank() over (order by a, b, c)
from (values (1, 2, 1), (1, 2, 2), (1, 2, 1)) as abcd (a, b, c)
order by a, b, c;

 a | b | c | rank
---+---+---+------
 1 | 2 | 1 |    1
 1 | 2 | 1 |    1
 1 | 2 | 2 |    3
(3 rows)

We are already doing something like I mentioned.

Consider this example:

explain SELECT rank() OVER (ORDER BY a), count(*) OVER (ORDER BY a,b)
FROM abcd;
                                QUERY PLAN
--------------------------------------------------------------------------
 WindowAgg  (cost=83.80..127.55 rows=1250 width=24)
   ->  WindowAgg  (cost=83.80..108.80 rows=1250 width=16)
         ->  Sort  (cost=83.80..86.92 rows=1250 width=8)
               Sort Key: a, b
               ->  Seq Scan on abcd  (cost=0.00..19.50 rows=1250 width=8)
(5 rows)

If it is okay to do extra sort for first window function (rank) here,
why would it be

any different in case which I mentioned?

My suggestion rest on assumption that for a window function, say

rank() OVER (ORDER BY a), ordering of columns (other than column 'a')
shouldn't matter.

--
Regards,
Ankit Kumar Pandey

On 1/4/23 13:07, Ankit Kumar Pandey wrote:

Also, one thing, consider the following query:

explain analyze select row_number() over (order by a,b),count(*) over
(order by a) from abcd order by a,b,c;

In this case, sorting is done on (a,b) followed by incremental sort on c
at final stage.

If we do just one sort: a,b,c at first stage then there won't be need to
do another sort (incremental one).

This could give incorrect results. Consider the following query:

postgres=# select a, b, c, rank() over (order by a, b)
from (values (1, 2, 1), (1, 2, 2), (1, 2, 1)) as abcd (a, b, c)
order by a, b, c;

a | b | c | rank
---+---+---+------
1 | 2 | 1 | 1
1 | 2 | 1 | 1
1 | 2 | 2 | 1
(3 rows)

If you change the window's ordering like you suggest, you get this
different result:

postgres=# select a, b, c, rank() over (order by a, b, c)
from (values (1, 2, 1), (1, 2, 2), (1, 2, 1)) as abcd (a, b, c)
order by a, b, c;

a | b | c | rank
---+---+---+------
1 | 2 | 1 | 1
1 | 2 | 1 | 1
1 | 2 | 2 | 3
(3 rows)

--
Vik Fearing

On Thu, 5 Jan 2023 at 15:18, Vik Fearing <vik@postgresfriends.org> wrote:

On 1/4/23 13:07, Ankit Kumar Pandey wrote:

Also, one thing, consider the following query:

explain analyze select row_number() over (order by a,b),count(*) over
(order by a) from abcd order by a,b,c;

In this case, sorting is done on (a,b) followed by incremental sort on c
at final stage.

If we do just one sort: a,b,c at first stage then there won't be need to
do another sort (incremental one).

This could give incorrect results.

Yeah, this seems to be what I warned against in [1]/messages/by-id/CAApHDvp=r1LnEKCmWCYaruMPL-jP4j_sdc8yeFYwaDT1ac5GsQ@mail.gmail.com.

If we wanted to make that work we'd need to do it without adjusting
the WindowClause's orderClause so that the peer row checks still
worked correctly in nodeWindowAgg.c.

Additionally, it's also not that clear to me that sorting by more
columns in the sort below the WindowAgg would always be a win over
doing the final sort for the ORDER BY. What if the WHERE clause (that
could not be pushed down before a join) filtered out the vast majority
of the rows before the ORDER BY. It might be cheaper to do the sort
then than to sort by the additional columns earlier.

David

[1]: /messages/by-id/CAApHDvp=r1LnEKCmWCYaruMPL-jP4j_sdc8yeFYwaDT1ac5GsQ@mail.gmail.com

Vik Fearing <vik@postgresfriends.org> writes:

On 1/4/23 13:07, Ankit Kumar Pandey wrote:

Also, one thing, consider the following query:
explain analyze select row_number() over (order by a,b),count(*) over
(order by a) from abcd order by a,b,c;
In this case, sorting is done on (a,b) followed by incremental sort on c
at final stage.
If we do just one sort: a,b,c at first stage then there won't be need to
do another sort (incremental one).

This could give incorrect results.

Mmmm ... your counterexample doesn't really prove that. Yes,
the "rank()" step must consider only two ORDER BY columns while
deciding which rows are peers, but I don't see why it wouldn't
be okay if the rows happened to already be sorted by "c" within
those peer groups.

I don't recall the implementation details well enough to be sure
how hard it would be to keep that straight.

regards, tom lane

David Rowley <dgrowleyml@gmail.com> writes:

Additionally, it's also not that clear to me that sorting by more
columns in the sort below the WindowAgg would always be a win over
doing the final sort for the ORDER BY. What if the WHERE clause (that
could not be pushed down before a join) filtered out the vast majority
of the rows before the ORDER BY. It might be cheaper to do the sort
then than to sort by the additional columns earlier.

That's certainly a legitimate question to ask, but I don't quite see
where you figure we'd be sorting more rows? WHERE filtering happens
before window functions, which never eliminate any rows. So it seems
like a sort just before the window functions must sort the same number
of rows as one just after them.

regards, tom lane

On Thu, 5 Jan 2023 at 16:12, Tom Lane <tgl@sss.pgh.pa.us> wrote:

David Rowley <dgrowleyml@gmail.com> writes:

Additionally, it's also not that clear to me that sorting by more
columns in the sort below the WindowAgg would always be a win over
doing the final sort for the ORDER BY. What if the WHERE clause (that
could not be pushed down before a join) filtered out the vast majority
of the rows before the ORDER BY. It might be cheaper to do the sort
then than to sort by the additional columns earlier.

That's certainly a legitimate question to ask, but I don't quite see
where you figure we'd be sorting more rows? WHERE filtering happens
before window functions, which never eliminate any rows. So it seems
like a sort just before the window functions must sort the same number
of rows as one just after them.

Yeah, I didn't think the WHERE clause thing out carefully enough. I
think it's only the WindowClause's runCondition that could possibly
filter any rows between the Sort below the WindowAgg and before the
ORDER BY is evaluated.

David

On Thu, 5 Jan 2023 at 19:14, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

We are already doing something like I mentioned.

Consider this example:

explain SELECT rank() OVER (ORDER BY a), count(*) OVER (ORDER BY a,b)
FROM abcd;
QUERY PLAN
--------------------------------------------------------------------------
WindowAgg (cost=83.80..127.55 rows=1250 width=24)
-> WindowAgg (cost=83.80..108.80 rows=1250 width=16)
-> Sort (cost=83.80..86.92 rows=1250 width=8)
Sort Key: a, b
-> Seq Scan on abcd (cost=0.00..19.50 rows=1250 width=8)
(5 rows)

If it is okay to do extra sort for first window function (rank) here,
why would it be

any different in case which I mentioned?

We *can* reuse Sorts where a more strict or equivalent sort order is
available. The question is how do we get the final WindowClause to do
something slightly more strict to save having to do anything for the
ORDER BY. One way you might think would be to adjust the
WindowClause's orderClause to add the additional clauses, but that
cannot be done because that would cause are_peers() in nodeWindowAgg.c
to not count some rows as peers when they maybe should be given a less
strict orderClause in the WindowClause.

It might be possible to adjust create_one_window_path() so that when
processing the final WindowClause that it looks at the DISTINCT or
ORDER BY clause to see if we can sort on a few extra columns to save
having to do any further sorting. We just *cannot* make any
adjustments to the WindowClause's orderClause.

David

On 05/01/23 12:53, David Rowley wrote:

We *can* reuse Sorts where a more strict or equivalent sort order is
available. The question is how do we get the final WindowClause to do
something slightly more strict to save having to do anything for the
ORDER BY. One way you might think would be to adjust the
WindowClause's orderClause to add the additional clauses, but that
cannot be done because that would cause are_peers() in nodeWindowAgg.c
to not count some rows as peers when they maybe should be given a less
strict orderClause in the WindowClause.

Okay, now I see issue in my approach.

It might be possible to adjust create_one_window_path() so that when
processing the final WindowClause that it looks at the DISTINCT or
ORDER BY clause to see if we can sort on a few extra columns to save
having to do any further sorting. We just *cannot* make any
adjustments to the WindowClause's orderClause.

This is much better solution. I will check

create_one_window_path for the same.

--
Regards,
Ankit Kumar Pandey

Sorry if multiple mails has been sent for this.

On 05/01/23 12:53, David Rowley wrote:

We *can* reuse Sorts where a more strict or equivalent sort order is
available.  The question is how do we get the final WindowClause to do
something slightly more strict to save having to do anything for the
ORDER BY.  One way you might think would be to adjust the
WindowClause's orderClause to add the additional clauses, but that
cannot be done because that would cause are_peers() in nodeWindowAgg.c
to not count some rows as peers when they maybe should be given a less
strict orderClause in the WindowClause.

I attempted this in attached patch.

#1. No op case

------------------------------------------In patched
version-----------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd order by a;
                QUERY PLAN
------------------------------------------
 WindowAgg
   ->  Sort
         Sort Key: a, b, c
         ->  WindowAgg
               ->  Sort
                     Sort Key: b
                     ->  Seq Scan on abcd
(7 rows)

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd;
                QUERY PLAN
------------------------------------------
 WindowAgg
   ->  Sort
         Sort Key: b
         ->  WindowAgg
               ->  Sort
                     Sort Key: a, b, c
                     ->  Seq Scan on abcd
(7 rows)

----------------------------------------------In
master--------------------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd order by a;
                QUERY PLAN
------------------------------------------
 WindowAgg
   ->  Sort
         Sort Key: a, b, c
         ->  WindowAgg
               ->  Sort
                     Sort Key: b
                     ->  Seq Scan on abcd
(7 rows)
explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a,b,c) FROM abcd;
                QUERY PLAN
------------------------------------------
 WindowAgg
   ->  Sort
         Sort Key: b
         ->  WindowAgg
               ->  Sort
                     Sort Key: a, b, c
                     ->  Seq Scan on abcd
(7 rows)

No change between patched version and master.

2. In case where optimization can happen

----------------------------In patched
version-------------------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a) FROM abcd order by a,b;
                QUERY PLAN
------------------------------------------
 WindowAgg
   ->  Sort
         Sort Key: a, b
         ->  WindowAgg
               ->  Sort
                     Sort Key: b
                     ->  Seq Scan on abcd
(7 rows)

explain (costs off)  SELECT rank() OVER (ORDER BY a), count(*) OVER
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order
by a,b,c,d;
                   QUERY PLAN
------------------------------------------------
 WindowAgg
   ->  WindowAgg
         ->  Sort
               Sort Key: a, b, c, d
               ->  WindowAgg
                     ->  Sort
                           Sort Key: b
                           ->  Seq Scan on abcd
(8 rows)

-------------------------------------------In
master--------------------------------------------------------

explain (costs off) SELECT rank() OVER (ORDER BY b), count(*) OVER
(ORDER BY a) FROM abcd order by a,b;
                   QUERY PLAN
------------------------------------------------
 Incremental Sort
   Sort Key: a, b
   Presorted Key: a
   ->  WindowAgg
         ->  Sort
               Sort Key: a
               ->  WindowAgg
                     ->  Sort
                           Sort Key: b
                           ->  Seq Scan on abcd
(10 rows)

explain (costs off)  SELECT rank() OVER (ORDER BY a), count(*) OVER
(ORDER BY b), count(*) OVER (PARTITION BY a ORDER BY b) FROM abcd order
by a,b,c,d;
                      QUERY PLAN
------------------------------------------------------
 Incremental Sort
   Sort Key: a, b, c, d
   Presorted Key: a, b
   ->  WindowAgg
         ->  WindowAgg
               ->  Sort
                     Sort Key: a, b
                     ->  WindowAgg
                           ->  Sort
                                 Sort Key: b
                                 ->  Seq Scan on abcd
(11 rows)

Patched version removes few sorts.

Regression tests all passed so it is not breaking anything existing.

We don't have any tests for verifying sorting plan in window functions
(which would have failed, if present).

Please let me know any feedbacks (I have added some my own concerns in
the comments)

Thanks

--
Regards,
Ankit Kumar Pandey

On Thu, 5 Jan 2023 at 04:11, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

Attaching test cases for this (+ small change in doc).

Tested this in one of WIP branch where I had modified
select_active_windows and it failed

as expected.

Please let me know if something can be improved in this.

Thanks for writing that.

I had a look over the patch and ended up making some adjustments to
the tests. Looking back at 728202b63, I think any tests we add here
should be kept alongside the tests added by that commit rather than
tacked on to the end of the test file. It also makes sense to me just
to use the same table as the original tests. I also thought the
comment in select_active_windows should be in the sort comparator
function instead. I think that's a more likely place to capture the
attention of anyone making modifications.

I've now pushed the adjusted patch.

David

On Sat, 7 Jan 2023 at 02:11, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

On 05/01/23 12:53, David Rowley wrote:

We *can* reuse Sorts where a more strict or equivalent sort order is
available. The question is how do we get the final WindowClause to do
something slightly more strict to save having to do anything for the
ORDER BY. One way you might think would be to adjust the
WindowClause's orderClause to add the additional clauses, but that
cannot be done because that would cause are_peers() in nodeWindowAgg.c
to not count some rows as peers when they maybe should be given a less
strict orderClause in the WindowClause.

I attempted this in attached patch.

I had a quick look at this and it's going to need some additional code
to ensure there are no WindowFuncs in the ORDER BY clause. We can't
sort on those before we evaluate them.

Right now you get:

postgres=# explain select *,row_number() over (order by oid) rn1 from
pg_class order by oid,rn1;
ERROR: could not find pathkey item to sort

I also don't think there's any point in adding the additional pathkeys
when the input path is already presorted. Have a look at:

postgres=# set enable_seqscan=0;
SET
postgres=# explain select *,row_number() over (order by oid) rn1 from
pg_class order by oid,relname;
QUERY PLAN
----------------------------------------------------------------------------------------------------
WindowAgg (cost=0.43..85.44 rows=412 width=281)
-> Incremental Sort (cost=0.43..79.26 rows=412 width=273)
Sort Key: oid, relname
Presorted Key: oid
-> Index Scan using pg_class_oid_index on pg_class
(cost=0.27..60.72 rows=412 width=273)
(5 rows)

It would be better to leave this case alone and just do the
incremental sort afterwards.

You also don't seem to be considering the fact that the query might
have a DISTINCT clause. That's evaluated between window functions and
the order by. It would be fairly useless to do a more strict sort when
the sort order is going to be obliterated by a Hash Aggregate. Perhaps
we can just not do this when the query has a DISTINCT clause.

On the other hand, there are also a few reasons why we shouldn't do
this. I mentioned the WindowClause runConditions earlier here.

The patched version produces:

postgres=# explain (analyze, costs off) select * from (select
oid,relname,row_number() over (order by oid) rn1 from pg_class order
by oid,relname) where rn1 < 10;
QUERY PLAN
------------------------------------------------------------------------------
WindowAgg (actual time=0.488..0.497 rows=9 loops=1)
Run Condition: (row_number() OVER (?) < 10)
-> Sort (actual time=0.466..0.468 rows=10 loops=1)
Sort Key: pg_class.oid, pg_class.relname
Sort Method: quicksort Memory: 67kB
-> Seq Scan on pg_class (actual time=0.028..0.170 rows=420 loops=1)
Planning Time: 0.214 ms
Execution Time: 0.581 ms
(8 rows)

Whereas master produces:

postgres=# explain (analyze, costs off) select * from (select
oid,relname,row_number() over (order by oid) rn1 from pg_class order
by oid,relname) where rn1 < 10;
QUERY PLAN
----------------------------------------------------------------------------------------
Incremental Sort (actual time=0.506..0.508 rows=9 loops=1)
Sort Key: pg_class.oid, pg_class.relname
Presorted Key: pg_class.oid
Full-sort Groups: 1 Sort Method: quicksort Average Memory: 26kB
Peak Memory: 26kB
-> WindowAgg (actual time=0.475..0.483 rows=9 loops=1)
Run Condition: (row_number() OVER (?) < 10)
-> Sort (actual time=0.461..0.461 rows=10 loops=1)
Sort Key: pg_class.oid
Sort Method: quicksort Memory: 67kB
-> Seq Scan on pg_class (actual time=0.022..0.178
rows=420 loops=1)
Planning Time: 0.245 ms
Execution Time: 0.594 ms
(12 rows)

(slightly bad example since oid is unique but...)

It's not too clear to me that the patched version is a better plan.
The bottom level sort, which sorts 420 rows has a more complex
comparison to do. Imagine the 2nd column is a long text string. That
would make the sort much more expensive. The top-level sort has far
fewer rows to sort due to the runCondition filtering out anything that
does not match rn1 < 10. The same can be said for a query with a LIMIT
clause.

I think the patch should also be using pathkeys_contained_in() and
Lists of pathkeys rather than concatenating lists of SortGroupClauses
together. That should allow things to work correctly when a given
pathkey has become redundant due to either duplication or a Const in
the Eclass.

Also, since I seem to be only be able to think of these cases properly
by actually trying them, I ended up with the attached patch. I opted
to not do the optimisation when there are runConditions or a LIMIT
clause. Doing it when there are runConditions really should be a
cost-based decision, but we've about no hope of having any idea about
how many rows will match the runCondition. For the LIMIT case, it's
also difficult as it would be hard to get an idea of how many times
the additional sort columns would need their comparison function
called. That's only required in a tie-break when the leading columns
are all equal.

The attached patch has no tests added. It's going to need some of
those. These tests should go directly after the tests added in
a14a58329 and likely use the same table for consistency.

David

Thanks for looking into this.

On 07/01/23 09:58, David Rowley wrote:

On Sat, 7 Jan 2023 at 02:11, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

On 05/01/23 12:53, David Rowley wrote:

We *can* reuse Sorts where a more strict or equivalent sort order is
available. The question is how do we get the final WindowClause to do
something slightly more strict to save having to do anything for the
ORDER BY. One way you might think would be to adjust the
WindowClause's orderClause to add the additional clauses, but that
cannot be done because that would cause are_peers() in nodeWindowAgg.c
to not count some rows as peers when they maybe should be given a less
strict orderClause in the WindowClause.

I attempted this in attached patch.

I had a quick look at this and it's going to need some additional code
to ensure there are no WindowFuncs in the ORDER BY clause. We can't
sort on those before we evaluate them.

Okay I will add this check.

I also don't think there's any point in adding the additional pathkeys
when the input path is already presorted.

It would be better to leave this case alone and just do the
incremental sort afterwards.

So this will be no operation case well.

You also don't seem to be considering the fact that the query might
have a DISTINCT clause.

Major reason for this was that I am not exactly aware of what distinct
clause means (especially in

context of window functions) and how it is different from other
sortClauses (partition, order by, group).

Comments in parsenodes.h didn't help.

That's evaluated between window functions and
the order by. It would be fairly useless to do a more strict sort when
the sort order is going to be obliterated by a Hash Aggregate. Perhaps
we can just not do this when the query has a DISTINCT clause.

On the other hand, there are also a few reasons why we shouldn't do
this. I mentioned the WindowClause runConditions earlier here.

The patched version produces:

postgres=# explain (analyze, costs off) select * from (select
oid,relname,row_number() over (order by oid) rn1 from pg_class order
by oid,relname) where rn1 < 10;
QUERY PLAN
------------------------------------------------------------------------------
WindowAgg (actual time=0.488..0.497 rows=9 loops=1)
Run Condition: (row_number() OVER (?) < 10)
-> Sort (actual time=0.466..0.468 rows=10 loops=1)
Sort Key: pg_class.oid, pg_class.relname
Sort Method: quicksort Memory: 67kB
-> Seq Scan on pg_class (actual time=0.028..0.170 rows=420 loops=1)
Planning Time: 0.214 ms
Execution Time: 0.581 ms
(8 rows)

Whereas master produces:

postgres=# explain (analyze, costs off) select * from (select
oid,relname,row_number() over (order by oid) rn1 from pg_class order
by oid,relname) where rn1 < 10;
QUERY PLAN
----------------------------------------------------------------------------------------
Incremental Sort (actual time=0.506..0.508 rows=9 loops=1)
Sort Key: pg_class.oid, pg_class.relname
Presorted Key: pg_class.oid
Full-sort Groups: 1 Sort Method: quicksort Average Memory: 26kB
Peak Memory: 26kB
-> WindowAgg (actual time=0.475..0.483 rows=9 loops=1)
Run Condition: (row_number() OVER (?) < 10)
-> Sort (actual time=0.461..0.461 rows=10 loops=1)
Sort Key: pg_class.oid
Sort Method: quicksort Memory: 67kB
-> Seq Scan on pg_class (actual time=0.022..0.178
rows=420 loops=1)
Planning Time: 0.245 ms
Execution Time: 0.594 ms
(12 rows)

(slightly bad example since oid is unique but...)

It's not too clear to me that the patched version is a better plan.
The bottom level sort, which sorts 420 rows has a more complex
comparison to do. Imagine the 2nd column is a long text string. That
would make the sort much more expensive. The top-level sort has far
fewer rows to sort due to the runCondition filtering out anything that
does not match rn1 < 10. The same can be said for a query with a LIMIT
clause.

Yes, this is a fair point. Multiple sort is actually beneficial in cases

like this, perhaps limits clause and runCondition should be no op too?

I think the patch should also be using pathkeys_contained_in() and
Lists of pathkeys rather than concatenating lists of SortGroupClauses
together. That should allow things to work correctly when a given
pathkey has become redundant due to either duplication or a Const in
the Eclass.

Make sense, I actually duplicated that logic from

make_pathkeys_for_window. We should make this changes there as well because

if we have SELECT rank() OVER (PARTITION BY a ORDER BY a)

(weird example but you get the idea), it leads to duplicates in
window_sortclauses.

Also, since I seem to be only be able to think of these cases properly
by actually trying them, I ended up with the attached patch. I opted
to not do the optimisation when there are runConditions or a LIMIT
clause. Doing it when there are runConditions really should be a
cost-based decision, but we've about no hope of having any idea about
how many rows will match the runCondition. For the LIMIT case, it's
also difficult as it would be hard to get an idea of how many times
the additional sort columns would need their comparison function
called. That's only required in a tie-break when the leading columns
are all equal.

Agree with runConditions part but for limit clause, row reduction happens

at the last, so whether we use patched version or master version,

none of sorts would benefit/degrade from that, right?

The attached patch has no tests added. It's going to need some of
those. These tests should go directly after the tests added in
a14a58329 and likely use the same table for consistency.

Thanks for the patch. It looks much neater now. I will add cases for this

(after a14a58329). I do have a very general question though. Is it okay

to add comments in test cases? I don't see it much on existing cases

so kind of reluctant to add but it makes intentions much more clear.

--
Regards,
Ankit Kumar Pandey

On 07/01/23 07:59, David Rowley wrote:

On Thu, 5 Jan 2023 at 04:11, Ankit Kumar Pandey <itsankitkp@gmail.com> wrote:

Attaching test cases for this (+ small change in doc).

Tested this in one of WIP branch where I had modified
select_active_windows and it failed

as expected.

Please let me know if something can be improved in this.

Thanks for writing that.

I had a look over the patch and ended up making some adjustments to
the tests. Looking back at 728202b63, I think any tests we add here
should be kept alongside the tests added by that commit rather than
tacked on to the end of the test file. It also makes sense to me just
to use the same table as the original tests. I also thought the
comment in select_active_windows should be in the sort comparator
function instead. I think that's a more likely place to capture the
attention of anyone making modifications.

Thanks, I will look it through.

I've now pushed the adjusted patch.

I can't seem to find updated patch in the attachment, can you please

forward the patch again.

Thanks.

--
Regards,
Ankit Kumar Pandey