Re: Row pattern recognition

Hi Jian, Tatsuo,

In my mail of 2026-10-22 I wrote:

> So rather than add it with its duplication, how about taking enough
> time and replacing that part with this design?

Jian, your refactoring is what led here. Once it made ExecWindowAgg()
the only place where the match is resolved and left everything else to
read the result, it became clear that the readers need little beyond
the frame positions. The rest of this mail follows from that.

Today the reduced frame sits apart from the frame, so techniques core
uses on frames are switched off or worked around for an RPR window.
The results are right, but at a cost:

- Aggregates are restarted on every row, so under SKIP TO NEXT ROW
an aggregate such as sum() does a number of transitions quadratic
in the run length, even with an inverse transition function. The
reason given is that the reduced frame can change entirely from one
row to the next; as chapter 4 shows, it changes in only a few ways.
- With UNBOUNDED FOLLOWING the tail of the full frame is computed
first and then cut to the match, so last_value() spools the whole
partition into the tuplestore before returning its first row.
- Since the reduced frame is assumed to start at the current row, a
match that starts later, as SEEK will need, cannot be expressed.

All of these come down to one thing: the frame positions need a new
contract with the code that reads them.

To make this concrete, I have written down how the frame works without
RPR, the contract its readers assume today, and the new one RPR needs.

0. Overview

The idea in one sentence: RPR sets the frame positions, and everything
else keeps reading them as it does today.

- In the executor the frame clause is mostly the input to
update_frameheadpos() and update_frametailpos(). Window functions
and aggregates read the result, frameheadpos and frametailpos (H and
T below); the few places that still derive the end from frameOptions
are covered in chapter 3.
- So if RPR sets H and T from the match of the current row, most
readers see the reduced frame without knowing about RPR.
- What remains is moving the readers from what they assume about H and
T today to a new contract. Chapter 1 states both; chapters 2 to 7
go through the differences.
- One item, the order in which rows enter and leave an aggregate's
state, touches the contract of transition functions. That one would
be a separate proposal (chapters 5 and 6).
- The design is also faster, for a few reasons (chapters 4 and 8):
aggregates with an inverse transition function are carried forward
across overlapping frames instead of being restarted on every
row; the frame end comes from the match, so a tail fetch such as
last_value() does not spool the partition to find it; no frame
mark lags behind the current row, so frame readers never hold back
trimming; and empty frames share one precomputed result.

How the chapters fit together: chapter 2 is the base, and chapters
3 and 4 build on it. As a first step I have in mind these three,
the hook of chapter 7, which needs no code until MEASURES, and the
frame side of chapter 6, H moving backward. Chapter 5 is for its own
thread, and the match search of SEEK comes after.

1. The frame, end to end

Without RPR, ExecWindowAgg() handles one row like this:

frame clause frame positions readers
------------ --------------- -------
frameOptions ----> frameheadpos (H) ----> first_value
offsets frametailpos (T) last_value, nth_value
^ aggregates
| row_is_in_frame()
update_frame*pos(), lazily,
when a reader first asks

Below, frames are written as the rows they hold, first .. last. H is
the first row and T the row after the last, as in the code. The match
of the current row is the L rows M .. M+L-1.

With RPR the arrow into H and T comes from the match instead:

match of the current row, rows M .. M+L-1 --> H = M, T = M+L
no match / empty match / skipped --> H = T = current row
(SEEK: chapter 6)
(skipped: inside a previous match under SKIP PAST LAST ROW)

This is the last step of the subtractive definition I mentioned before
(ISO/IEC 19075-5, 6.10.1): of the full frame, only the rows mapped
by the match remain.

Core code relies on a few things about H and T. They are not written
down in one place, but this is the contract the readers assume today:

C1 H and T are computed from the frame clause, lazily, once per
row, by update_frame*pos().
C2 T follows from frameOptions, so a reader may work out the end
without reading T.
C3 T never decreases within a partition.
C4 Rows leave an aggregate's state only at H, earliest first;
that is what the inverse transition function receives.
C5 H never decreases, so frame readers never go back before H;
their marks sit at H or later, and trimming follows them.
C6 H and T say all there is to know about the frame (EXCLUDE
aside, which RPR forbids).

Empty frames (H >= T) are fine under all six. RPR moves the readers
to a new contract:

C1 H and T are assigned once per row, when the match is ch. 2
resolved.
C2 Readers read T and never work it out from frameOptions; ch. 3
only the match search uses the full frame.
C3 T may decrease from one row to the next. ch. 4
C4 Rows leave an aggregate's state at H; when a non-empty ch. 4
frame ends before the last row already aggregated, or
starts before the first (ch. 6), the state starts over.
Avoiding that: ch. 5.
C5 H may decrease under SEEK with a finite frame, so marks ch. 6
follow the current row there.
C6 H and T say all a window function needs about the ch. 7
frame; the match status and inputs that depend on the
match sit beside them.

The shapes RPR forbids (RANGE, GROUPS, EXCLUDE, a start other than
CURRENT ROW, an end other than FOLLOWING) are rejected at parse
analysis, and the planner leaves an RPR window's frame alone. The
branches that only serve those shapes never run for an RPR window,
so they need no change.

2. Setting H and T: assign, do not update

Core computes H and T lazily and incrementally. Lazily, because a
tail such as UNBOUNDED FOLLOWING requires reading ahead, up to the
whole partition, so it is put off until a reader asks. Incrementally,
because under RANGE and GROUPS the bounds advance from where the
previous row left them.

Neither applies to a reduced frame. H and T are known the moment the
match is resolved, and the NFA has read the rows it needs by then.
Nor can they be derived from the previous row:

row r r .................. E
row r+1 r+1 ........ ? not necessarily "r+1 .. E"

Under SKIP TO NEXT ROW the match for r+1 runs the pattern from
scratch, so it may end before E, after E, or not exist. The NFA has
to run it. (Under SKIP PAST LAST ROW, r+1 is skipped when r's match
covers it, and its frame is empty.)

So they are best assigned where the match is resolved. In outline:

ExecWindowAgg NFA H/T functions, aggs
| | | |
| advance row | | |
|--drive match-->| | |
|<--M .. M+L-1---| | |
|--set H, T, valid------------->| |
|--evaluate------------------------------------->|
| | |<---read H/T----|

if (rpr_is_defined(winstate))
{
ensure_reduced_frame(winstate); /* drive the match */
set_reduced_framepos(winstate); /* H, T, *_valid = true */
}
/* else: core's lazy update_frame*pos() as today */

update_frameheadpos() and update_frametailpos() stay as they are on
master; with the valid flags already set they return immediately,
and for an RPR window they assert so. H and T can then never be
read for a row whose match is not yet resolved, since they are set
only right after it is.

3. Ends inferred from frameOptions

Four places work out the frame end, or act before checking it,
without reading T:

row_is_in_frame() END CURRENT ROW and ROWS offsets are computed
on the spot; UNBOUNDED FOLLOWING has no end
check at all.
reuse shortcut reuses the previous result when the head has
not moved, the end is UNBOUNDED FOLLOWING or
CURRENT ROW, and the current row lies in the
previous frame.
update_frametailpos() UNBOUNDED FOLLOWING spools the partition.
WinGetFuncArgInFrame() a HEAD fetch reads the row first and
asks row_is_in_frame() afterwards, so
nth_value(x, k) with a large k spools up to
row H+k-1 or the end of the partition. v54
compares k with the match length first.

row_is_in_frame() matters most, because aggregates find their
end through it:

aggregatedupto --> fetch row, row_is_in_frame()?
1: add it 0: skip it -1: stop

They never look at T. So for RPR, row_is_in_frame() must return
-1 based on T, or aggregates would run past the match. The reuse
shortcut assumes the end follows from frameOptions; in v54 it never
fires for RPR only because H moves on every row, so it gets an
explicit guard. The tail spooling goes away with chapter 2. The
HEAD fetch keeps the check v54 already has, now against T: for RPR, a
HEAD fetch at or past T is out of frame before any row is read.

4. T moving backward

Empty frames are nothing new. Core has plenty of them:

ROWS BETWEEN 7 PRECEDING AND 8 PRECEDING H = T (the docs say
it never selects rows)
ROWS BETWEEN 3 PRECEDING AND 5 PRECEDING H > T
ROWS BETWEEN 1 FOLLOWING AND 3 FOLLOWING H = T at the last row
RANGE offsets with no value in range H >= T

What is new is that T can go down from one row to the next. In core
neither H nor T ever goes down within a partition. Under RPR, with
SKIP TO NEXT ROW:

PATTERN (A+), rows r to E are A
r r .............. E
r+1 r+1 .......... E H +1, T stays: one inverse transition

PATTERN (A B C | B), rows r, r+1, r+2 are A, B, C
r r ......... r+2
r+1 r+1 .. r+1 shorter match: T r+3 -> r+2, backward
r+2 (empty) no match starts at C: H = T = r+2

Two places assume that T never goes down:

- aggregates: the restart test, an assertion that the end never
moves backward, and skipping rows already aggregated;
- the mark of a TAIL fetch (last_value) is set at T-1, so a later
row with a smaller T would fetch before the mark and fail. v54
already puts it at H for RPR, and that stays.

Not about T, but in the same code: IGNORE NULLS from the tail marks
row 0 and, when the frame has too few non-null values, walks past H
toward row 0. Rows before H are outside the frame, so it can stop
at H and mark H. This is an inefficiency in core, with or without
RPR, and so is leaving the mark behind when an access finds the frame
empty; I will send a separate patch for the core side.

For aggregates the cheap fix is to restart when T moves back. A
better one keeps the state across empty frames:

PATTERN ((A B)+), ROWS BETWEEN CURRENT ROW AND 5 FOLLOWING,
SKIP TO NEXT ROW, rows alternate A B A B ...

row frame restart each time keep the state
0 0 .. 5 add 0..5 add 0..5
1 (empty) state dropped keep, empty result
2 2 .. 7 add 2..7 inverse 0, 1; add 6, 7
3 (empty) state dropped keep, empty result
4 4 .. 9 add 4..9 inverse 2, 3; add 8, 9
5 (empty) state dropped keep, empty result
6 6 .. 11 add 6..11 inverse 4, 5; add 10, 11
per A row 6 forward 2 forward, 2 inverse

A rows start a match that fills the frame and B rows start none, so
frames alternate with empty ones and T falls back on every B row.
When the state is kept, each A row slides the frame by two rows.
With a frame of F rows, restarting costs about F transitions per
A row and keeping the state costs 4, so keeping wins for all but
the smallest frames.

The empty result (the final value of the initial state) is computed
once per aggregate and partition, or for every empty frame when the
final function is volatile. Beyond the restarts core already makes,
a restart is then needed only when a non-empty frame ends before the
last row already aggregated, as at row r+1 of (A B C | B). When
DEFINE looks only at a row and its neighbours, this is rare within a
run of a greedy quantifier, since matches that start later mostly end
at the same row or later; it happens with alternatives of different
lengths, or when DEFINE refers to the match start through FIRST().

Where a restart is not forced, it may still be cheaper. The previous
state and the new frame are both known before the aggregates run:
keeping costs the rows that leave plus the rows that arrive, and
restarting costs the rows that stay plus the rows that arrive. So
keep when fewer rows leave than stay, and restart otherwise. Core
frames move a little at a time, so keeping almost always wins there;
RPR frames can jump.

Under SKIP PAST LAST ROW none of this arises: the next match starts
after the current one, so frames never overlap and there is nothing to
carry forward. So moving aggregation is turned off there, and the
aggregates use their plain transition functions; v54 picks the moving
ones and restarts them on every row.

5. Removing rows at the end: inverse transition functions

To keep the state when a non-empty frame ends before the last row
already aggregated, we would have to remove rows from the end of the
state. The contract in xaggr.sgml does not allow it: the inverse
function receives "the earliest row included in the current state".
It is a FIFO contract, and the executor trusts it without checking.

For the built-ins, the contract is stricter than needed. Forty
built-in aggregates have an inverse function (count, sum, avg, the
var and stddev family, bool_and, bool_or, every), and all of them keep
only counts and sums, so none of them cares which row goes out:

int4_avg_accum_inv: count--; sum -= newval;
bool_accum_inv: aggcount--; if (newval) aggtrue--;

numeric's display-scale tracking may refuse a removal (the inverse
returns NULL), but the same way from either end. A user-defined
aggregate, on the other hand, may rely on FIFO order, say a queue
whose inverse pops the front without looking at its argument. Nothing
in the catalog tells the two apart.

RPR is not the only feature that would benefit. Core recomputes
the aggregate for every row under EXCLUDE CURRENT ROW, GROUP or TIES
("we punt and recalculate for every row", eval_windowaggregates()),
because the row to take out is in the middle and the row to put back
comes out of order:

EXCLUDE CURRENT ROW
row r h .. r-1, r+1 .. t
row r+1 h .. r, r+2 .. t add r back, take r+1 out

The options I can see:

A. Change the contract: any row may be removed. Silently wrong for
FIFO aggregates that exist today. No.
B. A per-aggregate declaration, like FINALFUNC_MODIFY (4de2d4fba38),
that the state depends only on the set of rows, not on their
order. FIFO stays the default; the 40 built-ins are marked.
Covers EXCLUDE (middle rows, any order) and RPR (removing from
the end, adding at the front).
C. A second inverse function for the end. Lets order-dependent
aggregates with a deque state remove from both ends, but it
cannot help EXCLUDE, and only RPR would use it.
D. One inverse function with a position argument. Breaks existing
signatures; under a new name it is C.

B looks right to me, stored as an enum column so that C can be added
later if anyone needs it. It belongs in its own thread with EXCLUDE
as the motivation, not in this patch. Until then RPR restarts
in that rare case.

6. H moving backward: SEEK with a finite frame

SEEK is not in v54. Under SEEK the match of row R is the first one
that starts at or after R. The frame side of this chapter, H moving
backward, would go in the first step, so that SEEK later only has
to supply the match; the match search itself comes with SEEK.

Under SEEK an empty frame cannot simply sit at the current row: the
previous row's H may already be past it. It sits at the later of the
two, so H does not go down on that account.

INITIAL keeps H from going down, and as far as I can see so does SEEK
with UNBOUNDED FOLLOWING. SEEK with n FOLLOWING and SKIP TO NEXT ROW
does not, because the scan end is tied to the output row R (it is
R+n), not to the start of a match:

n = 2, PATTERN (A B C | B), rows 4, 5, 6 are A, B, C,
row 3 is neither

row 3 4 5 6
R = 3 [3 4 5] start 4 (ABC) is cut before 6,
B start 5 matches B: H = 5
R = 4 [4 5 6] start 4 completes,
A B C earlier start wins: H = 4

This reads SKIP TO NEXT ROW as resuming at R+1, which is also what
Trino does. Taken literally, the standard resumes "at the row after
the first row of the current match" (4.13), and under SEEK that row
is M+1, not R+1: rows R+1 .. M would be skipped (6.11) and H would
never go back. The wording assumes a match that starts at the
current row, and I think it needs revising for SEEK. This chapter
follows the R+1 reading.

So marks go at R, which only grows and never passes the H of
any later row.

H moving back pairs with T moving back in chapter 4, and the cheap
answer for aggregates is the same: when H moves before the first row
already aggregated, which core treats as an error, drop the
moving-aggregate state and restart. In
the example, R = 4 aggregates 4 .. 6 from scratch.

The better answer is to add the earlier rows to the state. In the
example, the state 5 .. 5 takes 4 at the front and 6 at the end. This
is the same contract question as chapter 5: a transition function
sees rows in order, so feeding it a row that comes before rows
already aggregated is wrong for an aggregate that relies on order.
Option B of chapter 5, the declaration that the state depends only on
the set of rows, covers this case too; for such an aggregate, adding
a row at the front is an ordinary transition. Until then aggregates
restart, and chapter 4's comparison of the cost of keeping against
restarting applies as is.

7. What H and T cannot say

Nothing to code for this now; it is where MEASURES will plug in.

MEASURES is written like DEFINE, with the same notation and the same
pattern variables in view, but it is evaluated where window functions
are. The standard calls a measure with OVER and computes it
positioned on the last row of the match (19075-5, 6.9). So as far as
the frame goes, a measure is a window function: it is evaluated after
H and T are assigned, over H .. T-1. What H and T cannot say is
about the match, and two things sit beside them for that:

- The match status. An empty match and no match both give an empty
frame, yet COUNT(*) as a measure is 0 for one and null for the
other (6.16). So the per-row match status is kept.
- The variable each row maps to. Under CLASSIFIER() or B.price the
same row gives different values in different matches: with
PATTERN (A B+) and SKIP TO NEXT ROW it can be B in the match
starting at r and A in the one starting at r+1. So the path the
NFA chose is handed over. Overlapping frames then give a row
different inputs, so moving aggregation cannot apply; a check
beside the one initialize_peragg() makes for volatile arguments
turns it off.

Aggregates inside DEFINE are a separate matter. v54 rejects them for
now, but they are to come later, and under the standard they are
evaluated while the match is being searched, over the rows mapped so
far (running semantics). So once supported they live inside the NFA
and have nothing to do with the frame.

8. Cost, and what it buys

In v54, nodeWindowAgg.c grows by about 1300 lines. About 150 of them
lay the reduced frame over the frame (row_is_in_reduced_frame() and
the RPR branches in the accessors, IGNORE NULLS and aggregation).
This design replaces them with the assignment of chapter 2, the
checks of chapters 3 and 4, and the empty-frame handling of chapter
4. Navigation and the NFA itself are untouched. The gain is in
shape and in speed.

In shape, the following go away or become exact:

- The clipping to the reduced frame, which today has a different shape
in each of the two accessors (the plain path and IGNORE NULLS), is
replaced by the one assignment of chapter 2. The IGNORE NULLS path
needs no knowledge of RPR: the T check of chapter 3 sets its end.
The mark issue of chapter 4 is a core inefficiency unrelated to
RPR; it only shows up more often under RPR, where empty frames are
common.
- The workaround that gets past that assertion when T moves back
goes away. Empty frames take the precomputed result and never
reach the aggregation loop, so the assertion holds unless the
aggregates restart.
- The path that drives the NFA from inside the aggregation loop goes
away. It is already unreachable, since ExecWindowAgg() resolves
the match first, and Jian's v55-0001 removes it as well.
- H and T of a row whose match is not yet resolved cannot be read; an
attempt fails an Assert.
- The comment saying the inverse transition optimization is
inapplicable, and the matching text in README.rpr, are rewritten
along the lines of chapter 4.

The speed comes from mechanisms already in core:

- Aggregates move instead of restarting. An RPR window restarts
every aggregate on every row today. With H and T in place,
the overlapping frames of SKIP TO NEXT ROW take the ordinary
moving-aggregate path, for aggregates that have an inverse
transition function. For a run of L rows under PATTERN (A+) and
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING, where the frames
are r .. E, r+1 .. E, ...:

forward transitions inverse transitions
v54 (restart per row) L + (L-1) + ... + 1 0
this design L L - 1

Quadratic per run becomes linear. Where the frame jumps, so that
more rows leave than stay, keeping the state costs more than
restarting; the choice of chapter 4 restarts there, so no row costs
more transitions than it does in v54. Under SKIP PAST LAST ROW
matches never overlap, so moving aggregation is turned off there and
the plain transition functions run instead.

- Nothing reads past the match. Today the tail of the full frame
is still computed before it is cut down to the match, and for
UNBOUNDED FOLLOWING that spools the whole partition, for example
for last_value(). T from the match is known from rows the NFA has
already read, so the tuplestore holds only what the matches need and
can stay in memory instead of spilling to disk.

- Frame marks never lag behind the current row. Every frame access
sets its mark at H (at the current row under SEEK, chapter 6),
including the IGNORE NULLS fetch from the tail, which today pins
row 0 and keeps the whole partition. Only DEFINE navigation, as
today, and an aggregate state kept across an empty frame hold rows
before the current row.

I would like to settle this design as the end goal, and adjust in
steps what goes in when. The first step in chapter 0 is only a
proposal too; whether to go this way at all is what I would like to
hear first. The aggregate contract of chapters 5 and 6 and the SEEK
match search come after it. Question 1 is about the goal; 2 and 3
are about the steps.

Questions:

1. Can we take this direction, chapter 2's assignment in place of a
separate RPR accessor (WinGetFuncArgInReducedFrame()), as the end
goal?
2. Is it fine to leave the aggregate contract (removing from the end,
chapter 5; adding at the front, chapter 6) out of the first step
and raise it in its own thread later? Until then RPR restarts in
those cases.
3. For SEEK, is it fine to handle only the frame side in the first
step (H moving backward, chapter 6) and leave the match search
for later?

Best regards,
Henson