Re: first_value()/nth_value() with IGNORE NULLS loop forever (EXCLUDE GROUP/TIES, frame past partition end, no ORDER BY)

Hi Shihao, Tatsuo, Fujii-san, Andrey,

> Thanks for the patch. I had thought about a similar fix but still am
> not convinced it's worth the trouble.
>
> Let's continue the discussion on it after 19 GA is out.

That is fine with me, and the same goes for what follows: nothing here
needs to go in before 19 GA, and review and commit can wait until
after it. I am posting it now only so that it is on the list when the
discussion resumes. It is a series of eight patches on top of master,
starting with Shihao's v1 [2]. For the record, one case in it is a
query that worked before 69b20fdd20d [1] and fails on master and
REL_19_STABLE now (0003 and 0004 below).

The series has two parts. The first keeps the IGNORE NULLS scan
inside the frame. 0001 checks a ROWS frame end before reading the row
there. 0004 and 0005 handle what row_is_in_frame() cannot tell the
loop: it returns 0 both for a row that EXCLUDE removes and for a row
before the frame start, so the loop keeps stepping past such rows,
forward (0004) or backward (0005). The second part, 0006 and 0008,
makes sure that no frame access fetches a row before the frame start,
so that the mark can be moved there when no row is found. 0005 ties
the two together: it makes the frame start the explicit lower bound of
the backward walk, which 0008 then uses as the mark. 0002, 0003 and
0007 are comments and tests for these.

0001 is Shihao's v1, unchanged. I built current master and master
with v1: Fujii-san's query [3] returns NULL again with v1, and all of
Bhuvan's reproducers [4] return at once. Queries over a range of
frame modes, bounds, exclusions, and with and without ORDER BY and
PARTITION BY all finished, and their results matched array_agg(x)
FILTER (WHERE x IS NOT NULL).

0002 fixes the comment that started with "Likewise", which v1's
reordering moved away from the check it referred to, and says why
row_is_in_frame() is called first. Feel free to fold it into v1.

0003 adds tests for a case v1 does not cover: no ORDER BY in the
window, with EXCLUDE GROUP or EXCLUDE TIES.

WITH t AS MATERIALIZED (
SELECT NULLIF(i, 1) / (2 - i) AS v
FROM generate_series(1, 2) AS g(i)
)
SELECT first_value(v) IGNORE NULLS OVER (ROWS BETWEEN CURRENT ROW
AND 1 FOLLOWING EXCLUDE GROUP),
first_value(v) IGNORE NULLS OVER (ROWS BETWEEN UNBOUNDED
PRECEDING AND 1 FOLLOWING EXCLUDE TIES)
FROM t
LIMIT 1;

Before 69b20fdd20d this returned two NULLs; on master and with v1 it
fails with "ERROR: division by zero". Without ORDER BY every row is
a peer of the current row, so EXCLUDE GROUP leaves the frame empty and
EXCLUDE TIES leaves only the current row, and the second row is not
needed. But row_is_in_frame() returns 0 (excluded) for it, not -1,
and v1 leaves before spool_tuples() only on -1, so the row is still
read. 0003 records the current output (the error) as the expected
result. It also checks that EXCLUDE TIES does not take the value of
the current row when the current row is outside the frame.

0004 handles this case before the loop: without ORDER BY, EXCLUDE
GROUP returns "out of frame" at once, and EXCLUDE TIES looks at the
current row only. The query above returns NULL again. In this shape
the loop also stepped over the excluded rows one at a time for every
row, up to the frame end or the partition end with EXCLUDE GROUP,
which is O(N^2); with EXCLUDE GROUP it is the shape that looped
forever in the original report. Timings for first_value(x) IGNORE
NULLS OVER (ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING
...) over a 20000-row partition (cassert, -O0 build):

EXCLUDE GROUP EXCLUDE TIES
before the loop fix never ends 1.5 s
master 3.8 s 2.8 s
master + 0001 3.8 s 2.8 s
master + 0001-0004 8.6 ms 11.6 ms

RESPECT NULLS with the same frames takes about 8 ms and 11 ms on every
build. The appendix has the queries and the build used for all the
numbers in this mail. The partition-end check stays as a safety
net. 0004 also updates the expected output from 0003, so the diff
shows what changes.

0005 stops the backward walk of last_value() IGNORE NULLS at the frame
start. When the frame holds no non-null value, the walk does not stop
there today: row_is_in_frame() returns 0 (excluded), not -1, for a row
before the frame start, so the walk steps over every row back to the
partition start. It reads none of those rows, so the result is the
same, but it costs O(N^2). Timings for last_value(nullif(i, i))
IGNORE NULLS OVER (ORDER BY i ROWS BETWEEN CURRENT ROW AND 2
FOLLOWING) (cassert, -O0 build):

20000 rows 40000 rows
master + 0001-0004 2.4 s 9.3 s
master + 0001-0005 19 ms 38 ms

RESPECT NULLS with the same frame takes 19 ms and 37 ms.

Since no output changes, the regression tests cannot show this fix
itself. The test added in 0005 has the same output before and after;
it only checks that the walk neither returns the value just before the
frame start nor misses the one at it.

0006 is Andrey's v4 from CF 7412 [5] (bug #19732 [6]), unchanged. It
fixes first_value(), nth_value() and last_value() with EXCLUDE TIES
when the frame starts or ends on a peer of the current row. 0008
depends on it: without it, the WINDOW_SEEK_HEAD branch fetches the
current row even when the current row is before the frame start. That
fetch already fails with "cannot fetch row before WindowObject's mark
position" on master when the frame starts two or more rows after the
current row, and once 0008 also moves the mark when no row is found,
it fails in more cases. If 7412 goes in first, 0006 can be dropped.

0007 adds tests for frame accessors that find no row. With work_mem
set to 64kB, EXPLAIN ANALYZE shows the window storage for five
queries: first_value() over a one-row frame emptied by EXCLUDE CURRENT
ROW, nth_value() beyond the frame length, last_value() IGNORE NULLS,
which marks the partition start, and with IGNORE NULLS an empty frame
and a frame with no non-null value. All five show Disk today. It
also adds result tests that pass before and after 0008: a scan that
finds nothing in one frame and something in the next, and frames that
start after their end.

0008, with 0005, is the core-side patch I mentioned in the RPR thread
[7]. When the frame is empty or the requested row is outside it,
WinGetFuncArgInFrame() and ignorenulls_getfuncarginframe() return
without moving the mark, even if the caller asked them to set it, so
the tuplestore keeps every row since the last successful call. 0008
moves the mark to the frame start in that case, and makes last_value()
IGNORE NULLS mark the frame start instead of the partition start. The
window storage shown by EXPLAIN ANALYZE over a 20000-row table with
the default work_mem:

before 0008 with 0008
first_value, empty frame Disk, 4336kB Memory, 17kB
nth_value(pad, 5) Disk, 4336kB Memory, 18kB
last_value IGNORE NULLS Memory, 1142kB Memory, 17kB

count(*) over the same empty frame, nth_value(pad, 2), and
last_value() without IGNORE NULLS use Memory, 17kB on
both. 2d7b247cb41 [8] adjusted the IGNORE NULLS mark in
WinGetFuncArgInPartition() to avoid a fetch error; 0008 deals with the
mark of the frame accessors. With 0008 all five tests in 0007 show
Memory. This changes what set_mark means for a call that finds no
row. A window function that passed set_mark and then read rows before
the frame start after such a call would now fail; the built-in ones do
not, and a call that finds a row already moves the mark at least that
far.

0001-0004 deal with what changed in 69b20fdd20d, so I think they
belong in REL_19_STABLE as well as master. For 0005-0008 it is a
policy call. 0005 and the IGNORE NULLS part of 0008 fix
inefficiencies in code that is new in 19, while the
WinGetFuncArgInFrame() part of 0008 predates IGNORE NULLS. 0005, 0007
and 0008 change no result, and 0006 is here only because 0008 depends
on it. I left 0005, 0007 and 0008 without a Backpatch-through line,
and I can split 0008 if only its IGNORE NULLS part should go to 19. I
put them in this thread because they work on the same functions and
the same out_of_frame paths, and 0008 applies on top of 0005, but if
you would rather keep this thread to the regression, I will move
0005-0008 to a separate thread on pgsql-hackers.

Appendix: how the numbers were measured

Each build: --enable-cassert --enable-debug, CFLAGS=-O0, default
settings, macOS on Apple Silicon. Times are the best of three runs in
psql with \timing.

CREATE TABLE t20k AS
SELECT i AS x FROM generate_series(1, 20000) i;
CREATE TABLE u016_t AS
SELECT g AS id, repeat('x', 200) AS pad,
CASE WHEN g % 3 = 0 THEN NULL ELSE g END AS v
FROM generate_series(1, 20000) g;
ANALYZE t20k, u016_t;

0004 (EXCLUDE TIES for the second column; without IGNORE NULLS for
RESPECT NULLS):

SELECT count(f) FROM (
SELECT first_value(x) IGNORE NULLS
OVER (ROWS BETWEEN UNBOUNDED PRECEDING
AND UNBOUNDED FOLLOWING EXCLUDE GROUP) AS f
FROM t20k) s;

0005 (40000 for the second column; without IGNORE NULLS for RESPECT
NULLS):

SELECT count(v) FROM (
SELECT last_value(nullif(i, i)) IGNORE NULLS
OVER (ORDER BY i ROWS BETWEEN CURRENT ROW
AND 2 FOLLOWING) AS v
FROM generate_series(1, 20000) i) s;

0008, each under EXPLAIN (ANALYZE, COSTS OFF, TIMING OFF, SUMMARY OFF,
BUFFERS OFF), reading the Storage line of the WindowAgg node:

SELECT first_value(pad) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW
AND CURRENT ROW EXCLUDE CURRENT ROW) FROM u016_t;
SELECT count(*) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW
AND CURRENT ROW EXCLUDE CURRENT ROW) FROM u016_t;
SELECT nth_value(pad, 5) OVER (ORDER BY id ROWS BETWEEN
CURRENT ROW AND 2 FOLLOWING) FROM u016_t;
SELECT nth_value(pad, 2) OVER (ORDER BY id ROWS BETWEEN
CURRENT ROW AND 2 FOLLOWING) FROM u016_t;
SELECT last_value(v) IGNORE NULLS OVER (ORDER BY id ROWS BETWEEN
CURRENT ROW AND 2 FOLLOWING) FROM u016_t;
SELECT last_value(v) OVER (ORDER BY id ROWS BETWEEN CURRENT ROW
AND 2 FOLLOWING) FROM u016_t;

[1]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=69b20fdd20de68b0f0eaa855669a6657c65c8533
[2]
https://postgr.es/m/CAGRkXqQEwe4aP-1eo3b8qJ_A2cxPQGd=n1U4-36z5CZx_niFxA@mail.gmail.com
[3]
https://postgr.es/m/CAHGQGwFTmdD5T+7z8kZekrjVkA=Z2yNhq43ff3AuoxPVxDXP1A@mail.gmail.com
[4]
https://postgr.es/m/PN0P287MB09038F3BD9921EBACF5646F6A7632@PN0P287MB0903.INDP287.PROD.OUTLOOK.COM
[5] https://commitfest.postgresql.org/patch/7412/
[6] https://postgr.es/m/19732-d4eed889e3021ef8@postgresql.org
[7]
https://postgr.es/m/CAAAe_zDM87k_d_UnkYVeG-XP+z_aBHWQFoe8osTN7DYcb_32cA@mail.gmail.com
[8]
https://git.postgresql.org/gitweb/?p=postgresql.git;a=commitdiff;h=2d7b247cb414ccbc052c485fd82a841477a7e1ff

Best regards,
Henson