Thread: Monotonic WindowFunc support for ntile(), percent_rank() and cume_dist()

9d9c02ccd [1] added infrastructure in the query planner and executor
so that the executor would know to stop processing a monotonic
WindowFunc when its value went beyond what some qual in the outer
query could possibly match in future evaluations due to the
WindowFunc's monotonic nature.

In that commit, support was added so that the optimisation would work
for row_number(), rank(), dense_rank() and forms of count(*).  On
further inspection, it looks like the same can be done for ntile(),
percent_rank() and cume_dist(). These WindowFuncs are always
monotonically increasing.

I've attached a trivial patch to add the required support request type
to the existing prosupport functions for these window functions.

David

[1] https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=9d9c02ccd

On Tue, Jan 24, 2023 at 11:01:08AM +1300, David Rowley wrote:
> 9d9c02ccd [1] added infrastructure in the query planner and executor
> so that the executor would know to stop processing a monotonic
> WindowFunc when its value went beyond what some qual in the outer
> query could possibly match in future evaluations due to the
> WindowFunc's monotonic nature.
> 
> In that commit, support was added so that the optimisation would work
> for row_number(), rank(), dense_rank() and forms of count(*).  On
> further inspection, it looks like the same can be done for ntile(),
> percent_rank() and cume_dist(). These WindowFuncs are always
> monotonically increasing.
> 

Silly question, but was there any reason these were omitted in the first
commit?

> diff --git a/src/backend/utils/adt/windowfuncs.c b/src/backend/utils/adt/windowfuncs.c
> index af13b8e53d..b87a624fb2 100644
> --- a/src/backend/utils/adt/windowfuncs.c
> +++ b/src/backend/utils/adt/windowfuncs.c
> @@ -288,6 +288,15 @@ window_percent_rank_support(PG_FUNCTION_ARGS)
>  {
>      Node       *rawreq = (Node *) PG_GETARG_POINTER(0);
>  
> +    if (IsA(rawreq, SupportRequestWFuncMonotonic))
> +    {
> +        SupportRequestWFuncMonotonic *req = (SupportRequestWFuncMonotonic *) rawreq;
> +
> +        /* percent_rank() is monotonically increasing */
> +        req->monotonic = MONOTONICFUNC_INCREASING;
> +        PG_RETURN_POINTER(req);
> +    }
> +
>      if (IsA(rawreq, SupportRequestOptimizeWindowClause))
>      {
>          SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
> @@ -362,6 +371,15 @@ window_cume_dist_support(PG_FUNCTION_ARGS)
>  {
>      Node       *rawreq = (Node *) PG_GETARG_POINTER(0);
>  
> +    if (IsA(rawreq, SupportRequestWFuncMonotonic))
> +    {
> +        SupportRequestWFuncMonotonic *req = (SupportRequestWFuncMonotonic *) rawreq;
> +
> +        /* cume_dist() is monotonically increasing */
> +        req->monotonic = MONOTONICFUNC_INCREASING;
> +        PG_RETURN_POINTER(req);
> +    }
> +
>      if (IsA(rawreq, SupportRequestOptimizeWindowClause))
>      {
>          SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;
> @@ -465,6 +483,18 @@ window_ntile_support(PG_FUNCTION_ARGS)
>  {
>      Node       *rawreq = (Node *) PG_GETARG_POINTER(0);
>  
> +    if (IsA(rawreq, SupportRequestWFuncMonotonic))
> +    {
> +        SupportRequestWFuncMonotonic *req = (SupportRequestWFuncMonotonic *) rawreq;
> +
> +        /*
> +         * ntile() is monotonically increasing as the number of buckets cannot
> +         * change after the first call
> +         */
> +        req->monotonic = MONOTONICFUNC_INCREASING;
> +        PG_RETURN_POINTER(req);
> +    }
> +
>      if (IsA(rawreq, SupportRequestOptimizeWindowClause))
>      {
>          SupportRequestOptimizeWindowClause *req = (SupportRequestOptimizeWindowClause *) rawreq;

Since all three cases are exactly the same code, maybe you could
macro-ize it and add a single comment?

- Melanie

Thanks for having a look at this.

On Tue, 24 Jan 2023 at 13:26, Melanie Plageman
<melanieplageman@gmail.com> wrote:
> Silly question, but was there any reason these were omitted in the first
> commit?

Good question, it's just that I didn't think of it at the time and
nobody else did or if they did, they didn't mention it.

> Since all three cases are exactly the same code, maybe you could
> macro-ize it and add a single comment?

Hmm, I kinda like that it's being spelt out explicitly. To me, it
seems clean and easy to read. I know we could have fewer lines of code
with something else, but for me, being able to quickly see what the
properties of the WindowFunc are without having to look at some other
function is more important than saving some space in windowfuncs.c

I'd likely feel differently if the code in question didn't all fit on
my screen at once, but it does and I can see at a quick glance that
the function is unconditionally monotonically increasing. Functions
such as COUNT(*) are conditionally monotonically
increasing/decreasing, depending on the frame options.

If you feel strongly about that, then feel free to show me what you
have in mind in more detail so I can think harder about it.

David

On Tue, Jan 24, 2023 at 02:00:33PM +1300, David Rowley wrote:
> Thanks for having a look at this.
> 
> On Tue, 24 Jan 2023 at 13:26, Melanie Plageman
> <melanieplageman@gmail.com> wrote:
> 
> > Since all three cases are exactly the same code, maybe you could
> > macro-ize it and add a single comment?
> 
> Hmm, I kinda like that it's being spelt out explicitly. To me, it
> seems clean and easy to read. I know we could have fewer lines of code
> with something else, but for me, being able to quickly see what the
> properties of the WindowFunc are without having to look at some other
> function is more important than saving some space in windowfuncs.c
> 
> I'd likely feel differently if the code in question didn't all fit on
> my screen at once, but it does and I can see at a quick glance that
> the function is unconditionally monotonically increasing. Functions
> such as COUNT(*) are conditionally monotonically
> increasing/decreasing, depending on the frame options.
> 
> If you feel strongly about that, then feel free to show me what you
> have in mind in more detail so I can think harder about it.

Nah, I don't feel strongly. I think it was because looking at the patch
in isolation, the repetition stands out but in the context of the rest
of the code it doesn't.

- Melanie

On Wed, 25 Jan 2023 at 02:39, Melanie Plageman
<melanieplageman@gmail.com> wrote:
>
> On Tue, Jan 24, 2023 at 02:00:33PM +1300, David Rowley wrote:
> > If you feel strongly about that, then feel free to show me what you
> > have in mind in more detail so I can think harder about it.
>
> Nah, I don't feel strongly. I think it was because looking at the patch
> in isolation, the repetition stands out but in the context of the rest
> of the code it doesn't.

I played around with this patch again and the performance gains for
the best case are not quite as good as we got for row_number(), rank()
and dense_rank() in the original commit.  The reasons for this is that
ntile() and co all require getting a count of the total rows in the
partition so it can calculate the result. ntile() needs to know how
large the tiles are, for example. That obviously requires pulling all
tuples into the tuplestore.

Despite this, the performance with the patch is still much better than
without.  Here's master:

explain (analyze, timing off, costs off) select * from (select
a,ntile(10) over (order by a) nt from a) where nt < 1;

 Subquery Scan on unnamed_subquery (actual rows=0 loops=1)
   Filter: (unnamed_subquery.nt < 1)
   Rows Removed by Filter: 1000000
   ->  WindowAgg  (actual rows=1000000 loops=1)
         ->  Index Only Scan using a_a_idx on a  (actual rows=1000000 loops=1)
               Heap Fetches: 0
 Planning Time: 0.073 ms
 Execution Time: 254.118 ms
(8 rows)

and with the patch:

 WindowAgg  (actual rows=0 loops=1)
   Run Condition: (ntile(10) OVER (?) < 1)
   ->  Index Only Scan using a_a_idx on a (actual rows=1000000 loops=1)
         Heap Fetches: 0
 Planning Time: 0.072 ms
 Execution Time: 140.023 ms
(6 rows)

Here's with row_number() for reference:

explain (analyze, timing off, costs off) select * from (select
a,row_number() over (order by a) rn from a) where rn < 1;

 WindowAgg (actual rows=0 loops=1)
   Run Condition: (row_number() OVER (?) < 1)
   ->  Index Only Scan using a_a_idx on a (actual rows=1 loops=1)
         Heap Fetches: 0
 Planning Time: 0.089 ms
 Execution Time: 0.054 ms
(6 rows)

you can clearly see the difference with the number of rows pulled out
of the index only scan.

This is just a 1 million row table with a single INT column and an
index on that column.

Anyway, all seems like clear wins and low controversy so I've now pushed it.

David