BUG #19911: Window aggregate over ROWS n FOLLOWING: "unexpected end of tuplestore" after spill

Started by PG Bug reporting form5 days ago5 messagesbugs
Jump to latest
#1PG Bug reporting form
noreply@postgresql.org

The following bug has been logged on the website:

Bug reference: 19911
Logged by: Robins Tharakan
Email address: tharakan@gmail.com
PostgreSQL version: Unsupported/Unknown
Operating system: Debian 13 (x86_64)
Description:

A window aggregate whose ROWS frame starts at an offset FOLLOWING fails
with an internal error when the rows before the frame's start don't fit
in work_mem:

ERROR: XX000: unexpected end of tuplestore
LOCATION: window_gettupleslot, nodeWindowAgg.c:3358

The query should return its rows: with work_mem large enough for the
partition (4MB for the first query below), it does. It fails the same
way for max(), sum() and count(*), with or without PARTITION BY or
ORDER BY. first_value() and nth_value(), RANGE and GROUPS frames, and
frames starting at an offset PRECEDING give the same rows at 64kB as at
64MB. A Valgrind run didn't report much else interesting.

SQL
===
SET work_mem = '64kB';
SELECT count(x), max(x)
FROM (SELECT max(g) OVER (ROWS BETWEEN 2000 FOLLOWING
AND UNBOUNDED FOLLOWING) AS x
FROM generate_series(1, 2002) g) s;

-- expected: 2 | 2002 (as with work_mem = '4MB')
-- got: ERROR: XX000: unexpected end of tuplestore

Commit
======
Reproduces on master (11591f273e6) and on every supported branch,
including v14 (853b35f35b1). A release build (no assertions, -O2)
raises the same error.

Error Log
=======
ERROR: unexpected end of tuplestore
STATEMENT: SELECT count(x), max(x)
FROM (SELECT max(g) OVER (ROWS BETWEEN 2000 FOLLOWING
AND UNBOUNDED FOLLOWING) AS x
FROM generate_series(1, 2002) g) s;

Backtrace
========
#0 window_gettupleslot (winobj=..., pos=2001, slot=...)
at nodeWindowAgg.c:3358
#1 eval_windowaggregates (winstate=...) at nodeWindowAgg.c:982
#2 ExecWindowAgg (pstate=...) at nodeWindowAgg.c:2431
#3 ExecProcNodeFirst (node=...) at execProcnode.c:469
#4 ExecProcNode (node=...) at executor.h:327
#5 fetch_input_tuple (aggstate=...) at nodeAgg.c:564
#6 agg_retrieve_direct (aggstate=...) at nodeAgg.c:2464
#7 ExecAgg (pstate=...) at nodeAgg.c:2279

At #0, for the first output row (currentpos 0, frameheadpos 2000): the
fetch of row 2000 has just returned g = 2002, and the read pointer is
at EOF with seekpos 2000.

Found using SQLsmith, SQLReduce, creduce and Claude.
-
Robins Tharakan
Databricks

#2Henson Choi
assam258@gmail.com
In reply to: PG Bug reporting form (#1)
Re: BUG #19911: Window aggregate over ROWS n FOLLOWING: "unexpected end of tuplestore" after spill

Subject: Re: BUG #19911: Window aggregate over ROWS n FOLLOWING:
"unexpected end of tuplestore" after spill

Hi Robins,

Thanks for the report. I can reproduce it on master, and the attached
patch fixes it. Below are the cause and fix, why this kind of bug
keeps turning up in WindowAgg, and two follow-up ideas for master.

1. Cause and fix

On the first row, WindowAgg reads rows up to the frame head, 2000 rows
ahead. The tuplestore spills to disk partway through, but the read
still stops there, so the frame head is the next row, not yet stored.
Moving the aggregate's mark to the frame head then leaves its read
pointer at the end of the stored rows, and still selected.

The next fetch first reads the rest of the partition, as it always
does once the store has spilled. A selected pointer at the end moves
along with the rows being written, so the pointer ends up two rows
further on, while the row WindowAgg remembers for it stays the same.
The next move is computed from that stale row and runs off the end.

The patch takes the pointer's row from the number of stored rows
whenever the pointer is at the end, before computing the move.

2. Why this keeps happening, and a mitigation

tuplestore has many users besides WindowAgg: Material, CTE scan,
recursive union and worktable scan, function and table function scans,
SRFs in materialize mode (SQL functions, PL/pgSQL RETURN NEXT, PL/Perl
and PL/Tcl return_next), portals and holdable cursors, trigger
transition tables, hash join and walreceiver queries, among others.
Its read pointers only move relative to where they are (forward or
back, skip, rewind); nothing fetches row N directly.

A window clause also needs random access: row N of the frame, a mark
that moves ahead. WindowAgg emulates it by remembering which row each
window function's and aggregate's pointer is on, while rows are added
to the store on demand from many places, both before reads and in
checks that only ask whether a row exists. Adding rows moves the
selected pointer sitting at the end, but neither side knows about the
other, which is what broke here. This makes the current approach
fragile to maintain.

As a mitigation, the code that manages these positions and limits
could move into a layer between the WindowAgg executor and tuplestore
that offers, in effect, seek by row number on top of the relative
moves: fetch a row, check whether row N or the end of the partition
exists, set a mark, make sure rows up to N are stored, and drop rows
no longer needed, plus pointer setup and partition reset. It would
sit on the existing tuplestore and is meant to behave the same. With
the bookkeeping in one place, including keeping positions right while
rows are added, this kind of defect should be easier to avoid.

3. Performance

Once the layer exists, the storage under it can change without
touching the executor. It could become a store dedicated to the
WindowAgg executor, in which each of several read pointers keeps its
own window of rows in memory and blocks are indexed by row number.

Today, after a spill every read pointer shares one temporary file with
a one-block buffer, and old rows are only dropped while the store is
in memory. Tuples are written to the file one after another with
varying lengths, and nothing maps a row number to a file offset, so
the only way to reach a row N rows away is to read every tuple in
between. When reads jump between distant positions, each row can mean
re-reading the file between them. Cases that do this:

- an aggregate over a long moving frame, whose read pointer walks back
to the frame head for every row
- a frame that starts at an offset FOLLOWING, as in this report
- lead() or lag() with a large offset
- first_value() or nth_value() over a long frame, whose pointer sits
at the frame head while the current row is read at the tail

With blocks indexed by row number, a jump becomes a direct read
instead of a walk, and with a window per pointer, alternating pointers
stop evicting each other's block. In memory, the store would keep
only those windows rather than everything from the oldest pointer to
the end.

The row pattern recognition patch under review adds navigation
operations in DEFINE that read rows near the row being tested (PREV,
NEXT, LAST) or near the match start (FIRST), which can sit far from
the row being tested. They add a read pointer whose fetches jump
between rows far apart, so they would gain from the same store.

The patch is for all supported branches. The ideas in sections 2 and
3 are master-only, and I would start a separate -hackers thread for
them if there is interest.

Regards,
Henson

Attachments:

t259286_2
v1-0001-Fix-stale-read-position-in-window_gettupleslot-af.patchapplication/x-patch; name=v1-0001-Fix-stale-read-position-in-window_gettupleslot-af.patchDownload+27-1
#3Tom Lane
tgl@sss.pgh.pa.us
In reply to: Henson Choi (#2)
Re: BUG #19911: Window aggregate over ROWS n FOLLOWING: "unexpected end of tuplestore" after spill

Henson Choi <assam258@gmail.com> writes:

Thanks for the report. I can reproduce it on master, and the attached
patch fixes it. Below are the cause and fix, why this kind of bug
keeps turning up in WindowAgg, and two follow-up ideas for master.

I've spent the last little while poking at this problem too.
I concur with your root-cause diagnosis: WindowAgg's dead reckoning
about where the tuplestore read pointers are positioned is getting
out of sync with their actual positions. I've got very little faith
in your proposed patch though. WindowAgg maintains a bunch of
read pointers and is less than consistent about which one is the
"active" one when it calls tuplestore_puttupleslot(), so I suspect
that there are more places than this one that would need resync logic
if we follow this fix approach.

I experimented with some alternative fix ideas, but couldn't come
up with anything very workable. I think what we need to do is
what you called a mitigation but seems to me to be a full fix:
get rid of WindowAgg's local tracking of tuplestore positions
in favor of extending the tuplestore API with some more-appropriate
operations. In particular, if tuplestore had an API call to the
effect of "set the read pointer to absolute tuple number N", we
could get rid of a lot of silliness in WindowAgg. Having a call
to read out the position as an absolute tuple number might help
too, but I'm not sure we'd even need it if we had the first one.

The reason that tuplestore hasn't got that already is long obsolete:
I think it's mainly that we wanted to support tuplestores with more
than 4G tuples on machines without int64 arithmetic, so dealing in
absolute rather than relative tuple numbers didn't work. There are
some fine points to be dealt with, like compensating for
"tuplestore_trim" operations, but I think it's not going to be too
complicated. And fortunately we never exposed the tuplestore state
structs in any header, so there's no ABI breakage risk to worry about
from adding or expanding fields.

I would not bother with the intermediate management layer that you
talked about; that seems like it's just adding bureaucracy.

regards, tom lane

#4Henson Choi
assam258@gmail.com
In reply to: Tom Lane (#3)
Re: BUG #19911: Window aggregate over ROWS n FOLLOWING: "unexpected end of tuplestore" after spill

Tom Lane <tgl@sss.pgh.pa.us> writes:

I've got very little faith in your proposed patch though. WindowAgg
maintains a bunch of read pointers and is less than consistent about
which one is the "active" one when it calls tuplestore_puttupleslot(),
so I suspect that there are more places than this one that would need
resync logic if we follow this fix approach.

Agreed, v1 depended on that. tuplestore does need improving, and
once row pattern recognition has settled, I'd like to rework it,
together with the performance side, so that several positions can be
read at once through multiple read buffers. For the problem at hand,
though, I'd like to propose a simpler fix that, unlike v1, does not
create the EOF state at all.

WinSetMarkPosition() skipped the aggregate's read pointer past the
end of the stored rows. A skip past the end leaves the pointer at
EOF. While it is at EOF and still the active pointer, it moves along
as the spool adds rows, but seekpos does not, so the two no longer
agree.

v2 limits the skip so that it cannot reach EOF: the read pointer
stops on the last stored row. Since the read pointer can never reach
EOF, seekpos and the pointer can no longer disagree.

An assertion in window_gettupleslot() checks that the pointer it uses
is not at EOF.

This does not depend on which pointer is active. On a write,
tuplestore moves a read pointer only if it is at EOF; a pointer
anywhere else stays where it is, active or not. The skip above is the
only way a WindowObject's read pointer reaches EOF. The frame head,
frame tail, group tail and current-row pointers keep no seekpos, and
reach EOF only at the real end of the partition, after which no more
rows are written.

To check this, I made spool_tuples() report any WindowObject read
pointer at EOF before it writes. On 2900 window queries and a set of
random ones at work_mem = 64kB, it found the active aggregate pointer
at EOF thousands of times with v1, and never with v2.

The regression test is the same as in v1. With assertions enabled,
it fails without the fix and passes with it on master and on REL_14
to REL_19.

I think what we need to do is what you called a mitigation but seems
to me to be a full fix: get rid of WindowAgg's local tracking of
tuplestore positions in favor of extending the tuplestore API with
some more-appropriate operations.

I agree that the tuplestore API is the right direction, and I'll
include it, without the extra layer, when I rework tuplestore as
mentioned above. As that is likely to take quite a while, would you
consider v2 first, as a small fix without side effects?

Regards,
Henson

Attachments:

t259286_4
v2-0001-Don-t-move-a-window-read-pointer-past-the-stored-.patchapplication/octet-stream; name=v2-0001-Don-t-move-a-window-read-pointer-past-the-stored-.patchDownload+40-5
#5Henson Choi
assam258@gmail.com
In reply to: Henson Choi (#4)
Re: BUG #19911: Window aggregate over ROWS n FOLLOWING: "unexpected end of tuplestore" after spill

Hi Tom,

In particular, if tuplestore had an API call to the
effect of "set the read pointer to absolute tuple number N", we
could get rid of a lot of silliness in WindowAgg. Having a call
to read out the position as an absolute tuple number might help
too, but I'm not sure we'd even need it if we had the first one.

v3 follows that direction. There are four patches.

0001 removes needless complexity unrelated to this bug: only the
heap tuple kind exists, so the tuple-kind callbacks become direct
calls. It can be dropped if you prefer.

0002 gives each read pointer an absolute row number, counted from 0
since creation or the last tuplestore_clear(). Assert-enabled builds
check it against the array position while the store is in memory.

0003 adds tuplestore_tell() and tuplestore_seek(). tell returns the
number of the row the next forward fetch would return, or the number
of rows stored at EOF. seek clears the EOF state, as fseek() does.
In memory it computes the array position; on disk it steps over the
records by their length words without reading the tuples, so the
cost is still proportional to the distance.

I also added tell. As the counterpart of seek it is likely to find
uses, and WinSetMarkPosition() already uses it to move the read
pointer only forward.

0004 removes seekpos from WindowAgg. window_gettupleslot() positions
the pointer with tell and seek, and WinSetMarkPosition() never seeks
past the stored rows, so a WindowObject's pointer never reaches EOF.
Asserts check that in both places. The regression test is the same
as in v1 and v2.

There are
some fine points to be dealt with, like compensating for
"tuplestore_trim" operations

The row numbers are not affected by trim. Trim does not change the
total row count tuplestore keeps, and the in-memory array position is
derived from that count. A seek to a trimmed row returns false.

v3 is for master. For the back branches, I'd like your view on
whether to use this series or v2. It applies to REL_19 as is; 14 to
18 need small context adjustments.

Best regards,
Henson

Attachments:

t259286_5
v3-0001-Remove-tuple-kind-callback-indirection-from-tuple.patchapplication/octet-stream; name=v3-0001-Remove-tuple-kind-callback-indirection-from-tuple.patchDownload+29-63
v3-0002-Track-absolute-row-numbers-in-tuplestore-read-poi.patchapplication/octet-stream; name=v3-0002-Track-absolute-row-numbers-in-tuplestore-read-poi.patchDownload+68-1
v3-0003-Add-tuplestore_tell-and-tuplestore_seek.patchapplication/octet-stream; name=v3-0003-Add-tuplestore_tell-and-tuplestore_seek.patchDownload+165-15
v3-0004-Use-absolute-tuplestore-positions-in-WindowAgg.patchapplication/octet-stream; name=v3-0004-Use-absolute-tuplestore-positions-in-WindowAgg.patchDownload+48-67