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

Поиск
Список
Период
Сортировка
Искать

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

От:
BHUVAN CHILUKUTI <c.bhuvan@iitg.ac.in>
Дата:
Вложения:
Hello,
A window function call with IGNORE NULLS never terminates, and the backend
does not respond to query cancellation, when all of the following hold:
    • the function scans the frame forward: first_value() or nth_value();
    • the window has no ORDER BY;
    • the frame end is UNBOUNDED FOLLOWING, or a ROWS offset past the end of
      the partition (e.g. 1000000000000 FOLLOWING);
    • the exclusion is EXCLUDE GROUP, or EXCLUDE TIES when the current row
      does not supply the requested non-null value.
The backend spins at 100% CPU and never reaches a CHECK_FOR_INTERRUPTS(), so
statement_timeout, pg_cancel_backend(), pg_terminate_backend() and
"pg_ctl stop -m fast" do not stop it; recovery needs SIGKILL, which restarts
all sessions. The wedged backend also does not absorb a ProcSignalBarrier, so
an unrelated "ALTER DATABASE <other_db> SET TABLESPACE" (normally ~0.2 s)
blocks for as long as the query runs. Any role that can run a SELECT can
trigger it; no table and no special privilege are required.

PostgreSQL version
------------------
Reproduced on REL_19_STABLE (tip 015f4c9fc3, and also fc189eb750) and on
master (20devel, 126976a8ff). No commit touches
src/backend/executor/nodeWindowAgg.c between these revisions. PostgreSQL 18
and earlier are not affected (IGNORE NULLS is new in 19).
Platform: x86_64 Linux (Ubuntu 24.04, gcc 13.3.0), build configured with
--enable-cassert --enable-debug. The defect is in executor control flow and
is not expected to depend on the platform.

Minimal reproduction
---------------------
No tables or settings are needed. Run on a DISPOSABLE cluster: the statement
does not return and cannot be cancelled; stop it with SIGKILL on the backend.
SELECT first_value(x) IGNORE NULLS OVER (
ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING EXCLUDE GROUP
) FROM (VALUES (1)) v(x);
Expected: one row containing NULL. With no ORDER BY every row is a peer of the
current row (ref/select.sgml: "all rows are peers if there is no ORDER BY"),
EXCLUDE GROUP removes the current row and its peers, so the frame is empty,
and first_value() over an empty frame is NULL. The same query with RESPECT
NULLS returns NULL immediately, as does the aggregate-path equivalent
(array_agg(x) FILTER (WHERE x IS NOT NULL) OVER w)[1].
Actual: the statement never completes. In a debugger on this one-row query,
the loop position advances by ~1.8e8 per second (backend in state R), where
any valid position is 0 -- i.e. an unbounded loop, not slow execution.
Other shapes that hang the same way (each in its own session):
-- EXCLUDE TIES, current row NULL (expected: NULL)
SELECT first_value(x) IGNORE NULLS OVER (ROWS BETWEEN UNBOUNDED PRECEDING
AND UNBOUNDED FOLLOWING EXCLUDE TIES) FROM (VALUES (NULL::int)) v(x);
-- nth_value, second non-null never exists (expected: NULL)
SELECT nth_value(x,2) IGNORE NULLS OVER (ROWS BETWEEN CURRENT ROW
AND UNBOUNDED FOLLOWING EXCLUDE TIES)
FROM (VALUES (1),(2)) v(x) WHERE x = 1;
-- huge finite ROWS offset past the partition (expected: NULL)
SELECT first_value(x) IGNORE NULLS OVER (ROWS BETWEEN UNBOUNDED PRECEDING
AND 1000000000000 FOLLOWING EXCLUDE GROUP) FROM (VALUES (1)) v(x);
-- RANGE mode, same conditions (expected: NULL)
SELECT first_value(x) IGNORE NULLS OVER (RANGE BETWEEN UNBOUNDED PRECEDING
AND UNBOUNDED FOLLOWING EXCLUDE GROUP) FROM (VALUES (1)) v(x);
These related forms terminate correctly: the same queries with an ORDER BY in
the window; a frame ending at CURRENT ROW or a small finite offset;
last_value() (which scans backward); and RESPECT NULLS.

Analysis
--------
ignorenulls_getfuncarginframe() (nodeWindowAgg.c) walks the frame forward,
calling row_is_in_frame(winobj, abs_pos, slot, true) for each position and
skipping to the next on a 0 result without fetching the row. But
row_is_in_frame()'s header states the caller must have already determined the
row is in the partition. For a frame ending at UNBOUNDED FOLLOWING it has no
frame-end test, and its exclusion branch returns 0 ("excluded") for every
position other than the current row when ordNumCols == 0 (EXCLUDE GROUP, and
EXCLUDE TIES for pos != currentpos). So once abs_pos passes the last row,
every call returns 0; window_gettupleslot() -- the only place that detects
pos >= spooled_rows -- is never called, and abs_pos (an int64) just keeps
growing. No CHECK_FOR_INTERRUPTS() runs on this path.
With an ORDER BY, positions past the partition are not peers, row_is_in_frame()
returns 1, window_gettupleslot() fails, and the loop ends -- which is why only
the no-ORDER-BY case hangs. (This is distinct from the separately reported
abs() overflow in the same function: that needs a large negative offset to
overflow an int, whereas here the offset is 0 and the counter is int64.)

Fix

The attached patch makes ignorenulls_getfuncarginframe() establish partition
membership before calling row_is_in_frame(), using the same test
window_gettupleslot() uses (spool_tuples() + spooled_rows), and adds a
CHECK_FOR_INTERRUPTS() to the loop (which can skip many excluded or
known-NULL rows without fetching any tuple). It also adds regression queries
to window.sql. A lower-level alternative would be to make row_is_in_frame()
itself report positions past the partition end, but that would change its
documented precondition and affect every caller, so the caller-side fix seems
preferable; I'm happy to redo it that way if you disagree.
With the patch: the frame-scan queries above return at once with the expected
values; the core regression suite passes (239/239), isolation passes
(134/134), and the relevant TAP suites pass (psql including the query-cancel
test, plus pg_ctl and test_misc). The new window.sql expected output was
cross-checked against the aggregate-path results on an unpatched server, and a
24,000-query randomized comparison of IGNORE NULLS against that oracle found
no differences. The patch applies to both current master and REL_19_STABLE.

Thanks,
Bhuvan Chilukuti

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
> Hello,
> A window function call with IGNORE NULLS never terminates, and the backend
> does not respond to query cancellation, when all of the following hold:
> 
>      *
> the function scans the frame forward: first_value() or nth_value();
>      *
> the window has no ORDER BY;
>      *
> the frame end is UNBOUNDED FOLLOWING, or a ROWS offset past the end of
> the partition (e.g. 1000000000000 FOLLOWING);
>      *
> the exclusion is EXCLUDE GROUP, or EXCLUDE TIES when the current row
> does not supply the requested non-null value.
> 
> The backend spins at 100% CPU and never reaches a CHECK_FOR_INTERRUPTS(), so
> statement_timeout, pg_cancel_backend(), pg_terminate_backend() and
> "pg_ctl stop -m fast" do not stop it; recovery needs SIGKILL, which restarts
> all sessions. The wedged backend also does not absorb a ProcSignalBarrier, so
> an unrelated "ALTER DATABASE  SET TABLESPACE" (normally ~0.2 s)
> blocks for as long as the query runs. Any role that can run a SELECT can
> trigger it; no table and no special privilege are required.
> 
> PostgreSQL version
> ------------------
> Reproduced on REL_19_STABLE (tip 015f4c9fc3, and also fc189eb750) and on
> master (20devel, 126976a8ff). No commit touches
> src/backend/executor/nodeWindowAgg.c between these revisions. PostgreSQL 18
> and earlier are not affected (IGNORE NULLS is new in 19).
> Platform: x86_64 Linux (Ubuntu 24.04, gcc 13.3.0), build configured with
> --enable-cassert --enable-debug. The defect is in executor control flow and
> is not expected to depend on the platform.
> 
> Minimal reproduction
> ---------------------
> No tables or settings are needed. Run on a DISPOSABLE cluster: the statement
> does not return and cannot be cancelled; stop it with SIGKILL on the backend.
> SELECT first_value(x) IGNORE NULLS OVER (
> ROWS BETWEEN UNBOUNDED PRECEDING AND UNBOUNDED FOLLOWING EXCLUDE GROUP
> ) FROM (VALUES (1)) v(x);
> Expected: one row containing NULL. With no ORDER BY every row is a peer of the
> current row (ref/select.sgml: "all rows are peers if there is no ORDER BY"),
> EXCLUDE GROUP removes the current row and its peers, so the frame is empty,
> and first_value() over an empty frame is NULL. The same query with RESPECT
> NULLS returns NULL immediately, as does the aggregate-path equivalent
> (array_agg(x) FILTER (WHERE x IS NOT NULL) OVER w)[1].
> Actual: the statement never completes. In a debugger on this one-row query,
> the loop position advances by ~1.8e8 per second (backend in state R), where
> any valid position is 0 -- i.e. an unbounded loop, not slow execution.
> Other shapes that hang the same way (each in its own session):
> -- EXCLUDE TIES, current row NULL (expected: NULL)
> SELECT first_value(x) IGNORE NULLS OVER (ROWS BETWEEN UNBOUNDED PRECEDING
> AND UNBOUNDED FOLLOWING EXCLUDE TIES) FROM (VALUES (NULL::int)) v(x);
> -- nth_value, second non-null never exists (expected: NULL)
> SELECT nth_value(x,2) IGNORE NULLS OVER (ROWS BETWEEN CURRENT ROW
> AND UNBOUNDED FOLLOWING EXCLUDE TIES)
> FROM (VALUES (1),(2)) v(x) WHERE x = 1;
> -- huge finite ROWS offset past the partition (expected: NULL)
> SELECT first_value(x) IGNORE NULLS OVER (ROWS BETWEEN UNBOUNDED PRECEDING
> AND 1000000000000 FOLLOWING EXCLUDE GROUP) FROM (VALUES (1)) v(x);
> -- RANGE mode, same conditions (expected: NULL)
> SELECT first_value(x) IGNORE NULLS OVER (RANGE BETWEEN UNBOUNDED PRECEDING
> AND UNBOUNDED FOLLOWING EXCLUDE GROUP) FROM (VALUES (1)) v(x);
> These related forms terminate correctly: the same queries with an ORDER BY in
> the window; a frame ending at CURRENT ROW or a small finite offset;
> last_value() (which scans backward); and RESPECT NULLS.
> 
> Analysis
> --------
> ignorenulls_getfuncarginframe() (nodeWindowAgg.c) walks the frame forward,
> calling row_is_in_frame(winobj, abs_pos, slot, true) for each position and
> skipping to the next on a 0 result without fetching the row. But
> row_is_in_frame()'s header states the caller must have already determined the
> row is in the partition. For a frame ending at UNBOUNDED FOLLOWING it has no
> frame-end test, and its exclusion branch returns 0 ("excluded") for every
> position other than the current row when ordNumCols == 0 (EXCLUDE GROUP, and
> EXCLUDE TIES for pos != currentpos). So once abs_pos passes the last row,
> every call returns 0; window_gettupleslot() -- the only place that detects
> pos >= spooled_rows -- is never called, and abs_pos (an int64) just keeps
> growing. No CHECK_FOR_INTERRUPTS() runs on this path.
> With an ORDER BY, positions past the partition are not peers, row_is_in_frame()
> returns 1, window_gettupleslot() fails, and the loop ends -- which is why only
> the no-ORDER-BY case hangs. (This is distinct from the separately reported
> abs() overflow in the same function: that needs a large negative offset to
> overflow an int, whereas here the offset is 0 and the counter is int64.)
> 
> Fix
> ________________________________
> The attached patch makes ignorenulls_getfuncarginframe() establish partition
> membership before calling row_is_in_frame(), using the same test
> window_gettupleslot() uses (spool_tuples() + spooled_rows), and adds a
> CHECK_FOR_INTERRUPTS() to the loop (which can skip many excluded or
> known-NULL rows without fetching any tuple). It also adds regression queries
> to window.sql. A lower-level alternative would be to make row_is_in_frame()
> itself report positions past the partition end, but that would change its
> documented precondition and affect every caller, so the caller-side fix seems
> preferable; I'm happy to redo it that way if you disagree.
> With the patch: the frame-scan queries above return at once with the expected
> values; the core regression suite passes (239/239), isolation passes
> (134/134), and the relevant TAP suites pass (psql including the query-cancel
> test, plus pg_ctl and test_misc). The new window.sql expected output was
> cross-checked against the aggregate-path results on an unpatched server, and a
> 24,000-query randomized comparison of IGNORE NULLS against that oracle found
> no differences. The patch applies to both current master and REL_19_STABLE.
> 
> Thanks,
> Bhuvan Chilukuti

Thank you for the report and the fix. Unfortunately I have no time to
take care this for now (till November 3rd). I will work on this after
November 4th unless someone beats me.

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


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

От:
shihao zhong <zhong950419@gmail.com>
Дата:
Hi Bhuvan,

Thanks for the report and the patch. I can reproduce all five queries
on master and on 19rc1. 

This came in with 25a30bbd423. I think it belongs on the 19 open items.

https://wiki.postgresql.org/wiki/PostgreSQL_19_Open_Items

With your patch all five return at once and the regression tests
pass. I also compared the three functions against array_agg(x) FILTER
(WHERE x IS NOT NULL) over about 11k frame combinations. That included
spill to disk and volatile arguments. No differences.

One suggestion for the test. Could you add last_value IGNORE NULLS
with EXCLUDE TIES and no ORDER BY? It scans backward, so it would
catch a later fix in row_is_in_frame that returns -1 for every
position after the current row.

Thanks,
Shihao

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

От:
BHUVAN CHILUKUTI <c.bhuvan@iitg.ac.in>
Дата:
Вложения:
Hi Shihao,
Thanks for reproducing the issue and for the helpful suggestion.
I've added the last_value(x) IGNORE NULLS regression case with EXCLUDE TIES and no ORDER BY. This covers the backward-scan path you mentioned: with no window ORDER BY, all rows are peers, so EXCLUDE TIES leaves only the current row in the frame, and the expected results are 1, 2, and 3.
The updated patch passes make check on both master and REL_19_STABLE (239/239 on each), and it applies cleanly to both branches. The production C fix is unchanged.
I've attached the updated patch for your review.
Best regards,
Bhuvan Chilukuti

From: shihao zhong <zhong950419@gmail.com>
Sent: Sunday, October 25, 2026 9:34 PM
To: Tatsuo Ishii <ishii@postgresql.org>
Cc: BHUVAN CHILUKUTI <c.bhuvan@iitg.ac.in>; pgsql-bugs@lists.postgresql.org <pgsql-bugs@lists.postgresql.org>
Subject: Re: first_value()/nth_value() with IGNORE NULLS loop forever (EXCLUDE GROUP/TIES, frame past partition end, no ORDER BY)
 
You don't often get email from zhong950419@gmail.com. Learn why this is important
Hi Bhuvan,

Thanks for the report and the patch. I can reproduce all five queries
on master and on 19rc1. 

This came in with 25a30bbd423. I think it belongs on the 19 open items.

https://wiki.postgresql.org/wiki/PostgreSQL_19_Open_Items

With your patch all five return at once and the regression tests
pass. I also compared the three functions against array_agg(x) FILTER
(WHERE x IS NOT NULL) over about 11k frame combinations. That included
spill to disk and volatile arguments. No differences.

One suggestion for the test. Could you add last_value IGNORE NULLS
with EXCLUDE TIES and no ORDER BY? It scans backward, so it would
catch a later fix in row_is_in_frame that returns -1 for every
position after the current row.

Thanks,
Shihao

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

От:
shihao zhong <zhong950419@gmail.com>
Дата:
Hi Bhuvan,

Thanks, v2 looks good tp me.

Tatsuo said he can look after Nov 3, so I think we just wait.

Thanks,
Shihao

 

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
Hi Shihao,

> Hi Bhuvan,
> 
> Thanks for the report and the patch. I can reproduce all five queries
> on master and on 19rc1.
> 
> This came in with 25a30bbd423. I think it belongs on the 19 open items.
> 
> https://wiki.postgresql.org/wiki/PostgreSQL_19_Open_Items

Yeah, I have just added this to the 19 open items.

> With your patch all five return at once and the regression tests
> pass. I also compared the three functions against array_agg(x) FILTER
> (WHERE x IS NOT NULL) over about 11k frame combinations. That included
> spill to disk and volatile arguments. No differences.
> 
> One suggestion for the test. Could you add last_value IGNORE NULLS
> with EXCLUDE TIES and no ORDER BY? It scans backward, so it would
> catch a later fix in row_is_in_frame that returns -1 for every
> position after the current row.

I have just started to read the discussion and patches. Just to
clarify, is the test for feature improvement of row_is_in_frame?

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


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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
Hi Shihao,

Fixing typo in the previous message...

>> Hi Bhuvan,
>> 
>> Thanks for the report and the patch. I can reproduce all five queries
>> on master and on 19rc1.
>> 
>> This came in with 25a30bbd423. I think it belongs on the 19 open items.
>> 
>> https://wiki.postgresql.org/wiki/PostgreSQL_19_Open_Items
> 
> Yeah, I have just added this to the 19 open items.
> 
>> With your patch all five return at once and the regression tests
>> pass. I also compared the three functions against array_agg(x) FILTER
>> (WHERE x IS NOT NULL) over about 11k frame combinations. That included
>> spill to disk and volatile arguments. No differences.
>> 
>> One suggestion for the test. Could you add last_value IGNORE NULLS
>> with EXCLUDE TIES and no ORDER BY? It scans backward, so it would
>> catch a later fix in row_is_in_frame that returns -1 for every
>> position after the current row.
> 
> I have just started to read the discussion and patches. Just to
> clarify, is the test for feature improvement of row_is_in_frame?
                           ~~~~~~~future
			   
Regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp


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

От:
shihao zhong <zhong950419@gmail.com>
Дата:
Yes, the last_value test passes with or without the fix and only
guards against a later change to row_is_in_frame that returns -1 for
rows after the current row.

Thanks,
Shihao

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
> Yes, the last_value test passes with or without the fix and only
> guards against a later change to row_is_in_frame that returns -1 for
> rows after the current row.

The change to row_is_in_frame has not been decided in the community
yet. Why we need to install a test for it now?

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


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

От:
shihao zhong <zhong950419@gmail.com>
Дата:

Hi Tatsuo,

I think you are right here, sorry for my previous email confused you.

I misread Bhuvan's first mail. I thought row_is_in_frame also needed a fix, so that it would return -1 for rows after the current row when there is no ORDER BY.

I rechecked the code and the fix already covered all the cases, I dont think we need to adjust the test anymore.


Thanks,

Shihao

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
Вложения:
Hi Shihao,

> Hi Tatsuo,
> 
> I think you are right here, sorry for my previous email confused you.

No problem at all.

> I misread Bhuvan's first mail. I thought row_is_in_frame also needed a fix,
> so that it would return -1 for rows after the current row when there is no
> ORDER BY.
> 
> I rechecked the code and the fix already covered all the cases, I dont
> think we need to adjust the test anymore.

Ok.

Attached is the v1 patch, based on Bhuvan's second patch, minus the
last_value test case. The commit message is almost copied from his
patch, except comments about the test cases, which I feel too verbose
for a commit message. IMO attached patch is ready for commit, but
comments are welcome. If there's no objection, I will push it to
master and 19 branches soon.

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

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
> Attached is the v1 patch, based on Bhuvan's second patch, minus the
> last_value test case. The commit message is almost copied from his
> patch, except comments about the test cases, which I feel too verbose
> for a commit message. IMO attached patch is ready for commit, but
> comments are welcome. If there's no objection, I will push it to
> master and 19 branches soon.

Pushed. Thank you!

https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=69b20fdd20de68b0f0eaa855669a6657c65c8533
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp


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

От:
Fujii Masao <masao.fujii@gmail.com>
Дата:
On Fri, Nov 6, 2026 at 9:26 AM Tatsuo Ishii  wrote:
> Pushed. Thank you!
>
> https://git.postgresql.org/gitweb/?p=postgresql.git;a=commit;h=69b20fdd20de68b0f0eaa855669a6657c65c8533

Thanks for working on this!

The following query succeeded before this fix but fails afterward.
Is this intentional?

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 CURRENT ROW)
FROM t
LIMIT 1;

Regards,

-- 
Fujii Masao


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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
> The following query succeeded before this fix but fails afterward.
> Is this intentional?
> 
> 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 CURRENT ROW)
> FROM t
> LIMIT 1;

Not intentional. I think it just happened to work by chance.  The
outer node (WITH t AS MATERIALIZED ... FROM generate_series(1, 2)...)
raises an error (division by zero) as soon as the second row is
fetched.

When the window aggregate node (SELECT first_value(v) IGNORE NULLS
OVER (ROWS CURRENT ROW) FROM t) is executed, the outer node provides
the first row with v = NULL. So the window agg node tries to fetch the
second row to find out a non NULL row.

Previously we called row_is_in_frame() to determine if the second row
is in the frame without fetching the row in this
case. row_is_in_frame() determined that the second row is out of frame
because the framing option is "ROWS CURRENT ROW", meaning only the
current row (in this case the first row) is within a frame. Thus it
gave up searching further rows and return NULL without an error.

After the fix, before calling row_is_in_frame(), we call
spool_tuples() which tries to read rows from outer node to check
whether we hit the partition end. In the case above, we want to read
up to the second row. Unfortunately it raises the error in the outer
node.

I think this kind of behavior (reading beyond frame end) is not
specific to window functions with IGNORE NULLLS. Consider following
query:

WITH t AS MATERIALIZED (
  SELECT NULLIF(i, 1) / (2 - i) AS v
  FROM generate_series(1, 2) AS g(i)
)
SELECT nth_value(v,2) RESPECT NULLS OVER (ROWS CURRENT ROW)
FROM t
LIMIT 1;

This throws an error:
ERROR:  division by zero

The window agg node tries to fetch the second row to evaluate
nth_value(v,2) and fails. One may ask why it fetches the second row
even if it is out of frame. In my understanding to determine whether a
row is in frame, we need to fetch the row first. We need to check the
tuple content in some frame options.

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


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

От:
shihao zhong <zhong950419@gmail.com>
Дата:
Вложения:
> In my understanding to determine whether a
> row is in frame, we need to fetch the row first. We need to check the
> tuple content in some frame options.

I agree about nth_value() with RESPECT NULLS. It has always worked
this way.

But for ROWS frames row_is_in_frame() can tell from the position
alone that the row is out of frame. The attached patch moves that call
back in front of the partition end check. Fujii-san's query returns
NULL again, and the loop from the original report still ends.

Thanks,
Shihao

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

От:
Tatsuo Ishii <ishii@postgresql.org>
Дата:
> I agree about nth_value() with RESPECT NULLS. It has always worked
> this way.
> 
> But for ROWS frames row_is_in_frame() can tell from the position
> alone that the row is out of frame. The attached patch moves that call
> back in front of the partition end check. Fujii-san's query returns
> NULL again, and the loop from the original report still ends.

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.

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


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

От:
Henson Choi <assam258@gmail.com>
Дата:
Вложения:
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
FAQ