Обсуждение: Remove WindowClause PARTITION BY items belonging to redundant pathkeys

Recently Markus Winand pointed out to me that the PG15 changes made in
[1] to teach the query planner about monotonic window functions
improved the situation for PostgreSQL on his feature/optimization
timeline for PostgreSQL.  These can be seen in [2].

Unfortunately, if you look at the timeline in [2], we're not quite on
green just yet per Markus's "Not with partition by clause (see below)"
caveat.  This is because nodeWindowAgg.c's use_pass_through code must
be enabled when the WindowClause has a PARTITION BY clause.

The reason for this is that we can't just stop spitting out rows from
the WindowAgg when one partition is done as we still need to deal with
rows from any subsequent partitions and we can only get to those by
continuing to read rows until we find rows belonging to the next
partition.

There is however a missed optimisation here when there is a PARTITION
BY clause, but also some qual exists for the column(s) mentioned in
the partition by clause that makes it so only one partition can exist.
A simple example of that is in the following:

EXPLAIN
SELECT *
FROM
  (SELECT
      relkind,
      pg_relation_size(oid) size,
      rank() OVER (PARTITION BY relkind ORDER BY pg_relation_size(oid) DESC
      ) rank
    FROM pg_class)
WHERE relkind = 'r' AND rank <= 10;

(the subquery may be better imagined as a view)

Here, because of the relkind='r' qual being pushed down into the
subquery, effectively that renders the PARTITION BY relkind clause
redundant.

What the attached patch does is process each WindowClause and removes
any items from the PARTITION BY clause that are columns or expressions
relating to redundant PathKeys.

Effectively, this allows the nodeWindowAgg.c code which stops
processing WindowAgg rows when the run condition is met to work as the
PARTITION BY clause is completely removed in the case of the above
query.  Removing the redundant PARTITION BY items also has the added
benefit of not having to needlessly check if the next row belongs to
the same partition as the last row. For the above, that check is a
waste of time as all rows have relkind = 'r'

I passed the patch along to Markus and he kindly confirmed that we're
now green for this particular optimisation.

I'll add this patch to the July commitfest.

David

[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=9d9c02ccd
[2] https://use-the-index-luke.com/sql/partial-results/window-functions

Thank you for having a look at this.

On Thu, 8 Jun 2023 at 21:11, Richard Guo <guofenglinux@gmail.com> wrote:
>
> On Thu, Jun 8, 2023 at 7:37 AM David Rowley <dgrowleyml@gmail.com> wrote:
>>
>> What the attached patch does is process each WindowClause and removes
>> any items from the PARTITION BY clause that are columns or expressions
>> relating to redundant PathKeys.

> Also I'm wondering if we can do the same optimization to
> wc->orderClause.  I tested it with the query below and saw performance
> gains.

After looking again at nodeWindowAgg.c, I think it might be possible
to do a bit more work and apply this to ORDER BY items too.  Without
an ORDER BY clause, all rows in the partition are peers of each other,
and if the ORDER BY column is redundant due to belonging to a
redundant pathkey, then those rows must also be peers too since the
redundant pathkey must mean all rows have an equal value in the
redundant column.

However, there is a case where we must be much more careful.  The
comment you highlighted in create_windowagg_plan() does mention this.
It reads "we must *not* remove the ordering column for RANGE OFFSET
cases".

The following query can't work when the WindowClause has no ORDER BY column.

postgres=# select relname,sum(pg_relation_size(oid)) over (range
between 10 preceding and current row) from pg_Class;
ERROR:  RANGE with offset PRECEDING/FOLLOWING requires exactly one
ORDER BY column
LINE 1: select relname,sum(pg_relation_size(oid)) over (range between...

It might be possible to make adjustments in nodeWindowAgg.c to have
the equality checks come out as true when there is no ORDER BY.
update_frameheadpos() is one location that would need to be adjusted.
It would need further study to ensure we don't accidentally break
anything. I've not done that study, so won't be adjusting the patch
for now.

I've attached an updated patch which updates the outdated comment
which you highlighted.  I ended up moving the mention of removing
redundant columns into make_pathkeys_for_window() as it seemed a much
more relevant location to mention this optimisation.

David

On Fri, 9 Jun 2023 at 20:57, Richard Guo <guofenglinux@gmail.com> wrote:
>
> On Fri, Jun 9, 2023 at 8:13 AM David Rowley <dgrowleyml@gmail.com> wrote:
>> It might be possible to make adjustments in nodeWindowAgg.c to have
>> the equality checks come out as true when there is no ORDER BY.
>> update_frameheadpos() is one location that would need to be adjusted.
>> It would need further study to ensure we don't accidentally break
>> anything. I've not done that study, so won't be adjusting the patch
>> for now.
>
>
> I'm also not sure if doing that is safe in all cases.  Hmm, do you think
> we can instead check wc->frameOptions to see if it is the RANGE OFFSET
> case in make_pathkeys_for_window(), and decide to not remove or remove
> redundant ORDER BY items according to whether it is or not RANGE OFFSET?

I think ideally, we'd not have to add special cases to the planner to
disable the optimisation for certain cases. I'd much rather see
adjustments in the executor to handle cases where we've removed ORDER
BY columns (e.g adjust update_frameheadpos() to assume rows are equal
when there are no order by columns.)  That of course would require
that there are no cases where removing ORDER BY columns would change
the actual query results.  I can't currently think of any reason why
the results would change, but I'm not overly familiar with the RANGE
option, so I'd need to spend a bit longer looking at it than I have
done so far to feel confident in making the patch process ORDER BY
columns too.

I'm ok with just doing the PARTITION BY stuff as step one.  The ORDER
BY stuff is more complex and risky which seems like a good reason to
tackle separately.

David

On Mon, 12 Jun 2023 at 20:20, Richard Guo <guofenglinux@gmail.com> wrote:
>  So now the v2 patch looks good to me.

Thank you for reviewing this. I've just pushed the patch.

David