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

From: Ankit Kumar Pandey <[email-masked]>
Date: Wed, 4 Jan 2023 21:00:50 +0530

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

---

From: Vik Fearing <[email-masked]>
Date: Thu, 5 Jan 2023 03:18:24 +0100

On 1/4/23 13:07, Ankit Kumar Pandey wrote:
> 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).

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

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

-- 
Vik Fearing

---

From: David Rowley <[email-masked]>
Date: Thu, 5 Jan 2023 15:30:59 +1300

On Thu, 5 Jan 2023 at 15:18, Vik Fearing <[email-masked]> wrote:
> This could give incorrect results.

Yeah, this seems to be what I warned against in [1].

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] https://www.postgresql.org/message-id/CAApHDvp=[email-masked]

---

From: Tom Lane <[email-masked]>
Date: Wed, 04 Jan 2023 21:48:05 -0500

> 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

---

From: Tom Lane <[email-masked]>
Date: Wed, 04 Jan 2023 22:12:04 -0500

> 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

---

From: David Rowley <[email-masked]>
Date: Thu, 5 Jan 2023 20:14:49 +1300

> 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

---

From: David Rowley <[email-masked]>
Date: Thu, 5 Jan 2023 20:23:40 +1300

> explain SELECT rank() OVER (ORDER BY a), count(*) OVER (ORDER BY a,b)

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