Re: Window Function "Run Conditions" - Mailing list pgsql-hackers

On Wed, 23 Mar 2022 at 16:30, David Rowley <dgrowleyml@gmail.com> wrote:
>
> On Wed, 23 Mar 2022 at 11:24, David Rowley <dgrowleyml@gmail.com> wrote:
> > I think it's safer to just disable the optimisation when there are
> > multiple window clauses.  Multiple matching clauses are merged
> > already, so it's perfectly valid to have multiple window functions,
> > it's just they must share the same window clause.  I don't think
> > that's terrible as with the major use case that I have in mind for
> > this, the window function is only added to limit the number of rows.
> > In most cases I can imagine, there'd be no reason to have an
> > additional window function with different frame options.
>
> I've not looked into the feasibility of it, but I had a thought that
> we could just accumulate all the run-conditions in a new field in the
> PlannerInfo then just tag them onto the top-level WindowAgg when
> building the plan.
>
> I'm just not sure it would be any more useful than what the v3 patch
> is currently doing as intermediate WindowAggs would still need to
> process all rows.  I think it would only save the window function
> evaluation of the top-level WindowAgg for rows that don't match the
> run-condition.  All the supported window functions are quite cheap, so
> it's not a huge saving. I'd bet there would be example cases where it
> would be measurable though.

Another way of doing this that seems better is to make it so only the
top-level WindowAgg will stop processing when the run condition
becomes false.  Any intermediate WindowAggs must continue processing
tuples, but may skip evaluation of their WindowFuncs.

Doing things this way also allows us to handle cases where there is a
PARTITION BY clause, however, in this case, the top-level WindowAgg
must not stop processing and return NULL, instead, it can just act as
if it were an intermediate WindowAgg and just stop evaluating
WindowFuncs.  The top-level WindowAgg must continue processing the
tuples so that the other partitions are also processed.

I made the v4 patch do things this way and tested the performance of
it vs current master.  Test 1 and 2 have PARTITION BY clauses. There's
a small performance increase from not evaluating the row_number()
function once rn <= 2 is no longer true.

Test 3 shows the same speedup as the original patch where we just stop
processing any further tuples when the run condition is no longer true
and there is no PARTITION BY clause.

Setup:
create table xy (x int, y int);
insert into xy select x,y from generate_series(1,1000)x,
generate_Series(1,1000)y;
create index on xy(x,y);
vacuum analyze xy;

Test 1:

explain analyze select * from (select x,y,row_number() over (partition
by x order by y) rn from xy) as xy where rn <= 2;

Master:

Execution Time: 359.553 ms
Execution Time: 354.235 ms
Execution Time: 357.646 ms

v4 patch:

Execution Time: 346.641 ms
Execution Time: 337.131 ms
Execution Time: 336.531 ms

(5% faster)

Test 2:

explain analyze select * from (select x,y,row_number() over (partition
by x order by y) rn from xy) as xy where rn = 1;

Master:

Execution Time: 359.046 ms
Execution Time: 357.601 ms
Execution Time: 357.977 ms

v4 patch:

Execution Time: 336.540 ms
Execution Time: 337.024 ms
Execution Time: 342.706 ms

(5.7% faster)

Test 3:

explain analyze select * from (select x,y,row_number() over (order by
x,y) rn from xy) as xy where rn <= 2;

Master:

Execution Time: 362.322 ms
Execution Time: 348.812 ms
Execution Time: 349.471 ms

v4 patch:

Execution Time: 0.060 ms
Execution Time: 0.037 ms
Execution Time: 0.037 ms

(~8000x faster)

One thing which I'm not sure about with the patch is how I'm handling
the evaluation of the runcondition in nodeWindowAgg.c.  Instead of
having ExecQual() evaluate an OpExpr such as "row_number() over (...)
<= 10", I'm replacing the WindowFunc with the Var in the targetlist
that corresponds to the given WindowFunc.  This saves having to double
evaluate the WindowFunc. Instead, the value of the Var can be taken
directly from the slot.  I don't know of anywhere else we do things
quite like that.  The runcondition is slightly similar to HAVING
clauses, but HAVING clauses don't work this way.  Maybe they would
have if slots had existed back then. Or maybe it's a bad idea to set a
precedent that the targetlist Vars must be evaluated already.  Does
anyone have any thoughts on this part?

v4 patch attached.

David