Re: Add RESPECT/IGNORE NULLS and FROM FIRST/LAST options

> Here is the v12 patch to implement the optimization on top of Oliver's
> v11 patch. Only src/backend/executor/nodeWindowAgg.c was modified
> (especially ignorenulls_getfuncarginframe). In the patch I created
> 2-bit not null information array, representing following status for
> each row:
> 
> UNKNOWN: the row is not determined whether it's NULL or NOT yet.
>      This is the initial value.
> NULL: the row has been determined to be NULL.
> NOT NULL: the row has been determined to be NOT NULL.
> 
> In ignorenulls_getfuncarginframe:
> 
> For the first time window function visits a row in a frame, the row is
> fetched using window_gettupleslot() and it is checked whether it is in
> the frame using row_is_in_frame(). If it's in the frame and the
> information in the array is UNKNOWN, ExecEvalExpr() is executed to
> find out if the expression on the function argument is NULL or
> not. And the result (NULL or NOT NULL) is stored in the array.
> 
> If the information in the array is not UNKNOWN, we can skip calling
> ExecEvalExpr() because the information is already in the array.
> 
> Note that I do not skip calling window_gettupleslot() and
> row_is_in_frame(), skip only calling ExecEvalExpr(), because whether a
> row is in a frame or not could be changing as the current row position
> moves while processing window functions.
> 
> With this technique I observed around 40% speed up in my environment
> using the script attached, comparing with Oliver's v11 patch.
> 
> v11:
> rows    duration (msec)
> 1000    41.019 
> 2000    148.957 
> 3000    248.291 
> 4000    442.478 
> 5000    687.395
> 
> v12:
> rows    duration (msec)
> 1000    27.515 
> 2000    78.913 
> 3000    174.737 
> 4000    311.412 
> 5000    482.156 
> 
> The patch is now generated using the standard git format-patch.  Also
> I have slightly adjusted the coding style so that it aligns with the
> one used in nodeWindowAgg.c, and ran pgindent.
> 
> Note that I have not modified ignorenulls_getfuncarginpartition yet. I
> think we could optimize it using the not null info infrastructure as
> well. Will come up with it.

Attached is the v13 patch to address this: i.e. optimize window
functions (lead/lag) working in a partition. In summary I get 40x
speed up comparing with v12 patch. Here is the test script.

EXPLAIN ANALYZE
SELECT lead(x, 5000) IGNORE NULLS OVER ()
              FROM generate_series(1,10000) g(x);

This looks for the 5k th row in a partition including 10k rows.
The average duration of 3 trials are:

v12: 2563.665 ms
v13: 126.259 ms

So I got 40x speed up with the v13 patch. In v12, we needed to scan
10k row partition over and over again. In v13 I used the same NULL/NOT
NULL cache infrastructure created in v12, and we need to scan the
partition only once. This is the reason for the speed up.

Also I removed ignorenulls_getfuncarginpartition(), which was the work
horse for null treatment for window functions working for partitions
in v12 patch. Basically it was a copy and modified version of
WinGetFuncArgInPartition(), thus had quite a few code duplication. In
v13, instead I modified WinGetFuncArgInPartition() so that it can
handle directly null treatment procedures.

BTW I am still not satisfied by the performance improvement for window
functions for frames, that was only 40%. I will study the code to look
for more optimization.

Best regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp