Re: Row pattern recognition

Hi hackers,

This is the increment on top of v50: the work that came out of the
fortnight Jian spent in Korea in July -- the 18th to the end of the
month -- plus what has been fixed since. It is 38 patches. The
attachments are named nocfbot-XXXX-*.txt so that cfbot does not try
them on master, where they cannot apply without v50 underneath.

The fixed branch for this posting, which I will not rewrite, is:

https://github.com/assam258-5892/postgres/tree/RPR-20260825

They apply on top of v50, in numeric order and with nothing else in
between. The base I cut them against is the cfbot branch's commit for
it, "[CF 4460] v50 - Implement row pattern recognition feature", which
is the posted v50 series applied to master of 2026-08-01
(7a0299a1348). That is the rule I mean to keep for anything I post
from here on: cut against the latest version on the cfbot branch,
never against our own branch, so that what arrives applies for whoever
picks it up.

Each entry below says what v50 does wrong and what the patch does
about it, and the tag in brackets says what kind of problem it is. Of
the 38, ten produce a wrong answer or a spurious error on v50 today;
the rest are cleanup, plan shape, diagnostics, comments and tests,
what v50 changed outside its own scope, a latent out-of-bounds read, a
combination refused as not implemented, and a change to what EXPLAIN
prints.

What follows keeps each patch to a short paragraph, and each of the
known issues at the end to the same. Whichever of them needs more --
a fix whose reasoning will not fit in a paragraph, an issue that has
to be worked out before it can be fixed -- will get a posting of its
own; those come after this one.

One note on authorship before the list. 20 of these 38 carry Jian as
the author -- he wrote them, I rebased them onto the series, verified
them and wrote the messages. A batch this size makes an individual
contribution hard to see from outside, which is the other reason each
patch below gets its own paragraph rather than a line in a table. His
are 2007-2013, 2017, 2023, 2025, 2026 and the whole 4XXX band. Where
one of them gets a posting of its own, I will say in it what review
changed, as far as I remember it.

The bands have been renumbered since v50 went out. Anything written
before today uses the old numbers:

0XXX put back what v50 changed outside its own scope
2XXX the series proper -- cleaned up, not yet reviewed upstream
3XXX deparse work that closes a reported round-trip failure
4XXX carries known open items, or came in from Jian's inbox
9XXX reproduces without RPR at all -- submitted separately

Two bands from the July postings are gone. 1XXX was what had already
been reviewed upstream, and v50 absorbed all of it, so nothing is left
to carry that number. 8XXX was where these reverts sat; they moved to
0XXX because they apply before the series and 8XXX sorted them after
it.

Apply order is the numeric order.

0XXX -- put back what v50 changed outside its own scope

0001 Revert window_gettupleslot() mark-position elog to its original
message [pre-existing code]
v50 rewrote an error message in pre-existing window code that
has nothing to do with row pattern recognition.

0002 Remove EXCLUDE TIES window tests unrelated to row pattern
recognition [pre-existing code]
Likewise for the EXCLUDE TIES tests v50 added to the existing
window suite. The coverage is worth having, so it comes back
as a separate submission (see the end of this mail).

2XXX -- the series

2001 Bound the END search in row pattern absorption analysis
[latent]
The search for the END that closes a group leaves only on a
shallower element, and at the outermost depth nothing is
shallower -- not even the terminal element. So the walk runs
past the end of the element array and carries on through
whatever it finds there: it hangs, looping on that memory until
the read faults, since no value it meets out there can end the
walk either. Only a pattern tree the optimization pass never
produced can get that far, so it is unreachable today; the
bound keeps it that way.

2002 Fix row pattern recognition alternation branch-walk overload
[wrong result]
Alternation branch links and a group's skip past its own END
share one field, so a branch that begins with a quantified
group breaks both ways. In the last branch the walk reads that
skip as one more branch: PATTERN (A | (B C)+ (D E)+) behaves
like A | (B C)+ (D E)+ | (D E)+ and matches D E D E. Nesting
depth cannot tell the two apart. Every branch now ends with a
SEP element of its own, and the branch links move onto that
chain.

2003 Preserve row pattern preferment in three PATTERN optimizations
[wrong result]
Three pattern rewrites move the decision to stop repeating past
a choice point inside the body. Search order is what decides
which match wins, so the same query returned different rows
depending on whether the rewrite fired. All three are gated
now on the body consuming a fixed number of rows, which is when
the two search orders agree. Flattening a nested repetition
needs one condition more, because the nested form settles each
round's count before starting another and stops early when the
rest cannot reach the inner minimum: (A{2,3}){1,2} prefers
three rows where the flattened A{2,6} takes four.

2004 Fix row pattern preferment and cycle handling in the NFA matcher
[wrong result]
Three fixes, worst first. The cycle guard identified a state
by its position in the pattern alone, so re-entering a body at
a higher repeat count counted as a cycle and (A+|B){2} lost the
match entirely on an all-A partition. The guard that keeps a
less-preferred match from replacing a preferred one asked
whether its own call had recorded a match, not whether there
was a match at all; rewriting it as a per-context flag exposed
four places v50 did not guard at all. And below the lower
bound, preferment order came from the group's own greed instead
of its body's.

2005 Follow local conventions in row pattern recognition additions
[cleanup]
Include order, case order, a typedef entry, and one generated
function that can never be called -- conventions the files
declare for themselves. No functional change.

2006 Evaluate an RPR DEFINE only where the NFA maps its variable
[wrong result]
A DEFINE should be evaluated only where the NFA actually maps
its variable. v50 evaluated every one of them on every row
before advancing the state, so the predicate of a variable no
row is being mapped to still ran, and a query died on an error
that had nothing to do with its answer: PATTERN (A B) DEFINE A
AS v < 0, B AS 1 / (v - v) > 0 raises division by zero although
A is false everywhere and B is never reached. Each DEFINE is
now evaluated at the point it is first consumed, and cached per
row.

2007 Correct resno and dedup handling of RPR DEFINE targetlist
entries [wrong result]
Two fixes in the same loop. The junk targetlist entry a
DEFINE-only column needs drew its number from the list length
instead of the parser's counter, which then fell behind and let
a later window's key reuse a number already taken. And the
duplicate check ignored query level, so a column one level up
that the check could not tell from the one it wanted -- an
outer reference in a lateral subquery -- made it skip the entry
the DEFINE needs.

2008 Register DEFINE-only correlated parameters in the WindowAgg's
extParam [wrong result]
A parameter only the DEFINE references was never registered
among the ones the window node depends on, so a change to it
never reached the subtree and the hash aggregate a DISTINCT put
above it handed back the first row's table.

2009 Return null from a row pattern navigation to a nonexistent row
[wrong result]
When the target row does not exist v50 evaluated the argument
on a dummy all-NULL row, so PREV(val IS NOT NULL) at the start
of a partition was false instead of null. The standard has the
navigation itself return null with the argument not evaluated
at all, and the compiled expression now jumps over it.

2010 Resolve RPR navigation offsets in the executor, not the plan tree
[plan shape]
An offset is a run-time constant, not a plan-time one: it can
come from an inlined function, from a LATERAL, or from a bind
parameter under a generic plan. v50 walked for offsets on both
sides -- once in the planner, which wrote the resulting trim
bounds into the window node, and again in the executor. Two
changes follow. The walk runs only in the executor now, so the
planner writes no trim bounds and five fields leave the plan
node. And the values are settled on the first call of a scan,
which is where frame offsets have always been settled.

2011 Centralize the RPR field initialization in ExecInitWindowAgg
[cleanup]
The RPR fields were initialized wherever the surrounding code
happened to need them; they move into one block at the end, in
struct declaration order. The navigation offsets go first,
because what fills them has to run before the DEFINE
expressions are initialized. No behaviour change.

2012 Check RPR DEFINE volatility after expression preprocessing
[diagnostics]
Checking volatility after the planner has run is the practice
here already -- the FOR PORTION OF check beside this one works
that way, and so does the post-flattening check. What it buys
is that the check sees what the executor would run, and what
the planner never plans is not its business. v50's own walker
ran before preprocessing and broke that in both directions: it
rejected volatility that folds away and never executes, and
missed the volatility that folding splices in. The check runs
on the folded clause now, in line with the rest, and the tests
put four shapes the planner never reaches beside the planned
ones they resemble.

2013 Report a sibling navigation as not being a direct argument
[diagnostics]
PREV(FIRST(v) + LAST(v)) was rejected as nesting navigation
more than two levels deep, which is not what is wrong with it:
the nesting is two levels, and the inner navigation simply is
not the outer one's immediate argument. The two checks swap
order; both keep their text.

2014 Point the RPR quantifier diagnostics at the offending token
[diagnostics]
A quantifier error concatenated two tokens and quoted a
spelling nobody typed ("*??", "??||"). Name the second token
and put the cursor on it.

2015 Stop RPR absorption at a reluctant group's BEGIN [plan shape]
Absorption cannot apply under a reluctant quantifier, and the
code says as much -- but the test looked only at the quantifier
handed to it, so the greedy A+ in PATTERN ((A+ B)+? C) still
became a comparison point. Stop at the group instead.

2016 Clear the RPR reluctant flag when min equals max [plan shape]
With min == max the quantifier repeats a fixed number of times
either way, so reluctant means nothing there and the flag is
cleared. The matcher never reads it in that state, but the
planner does, and (A{2}? | A{2}) failed to dedup because of
it.

2017 Rewrite RPR pattern list optimizations to compact lists in place
[plan shape]
The five optimizations that only ever drop elements edit the
list they were handed instead of building a second one. The
group merge also runs a second time, because folding a copy
between two groups leaves those groups adjacent and nothing
used to produce that combination. Quantifier arithmetic goes
through the standard overflow helpers now, in place of the
ad-hoc widened product and the subtraction-form guards it had,
and both checks earn their place: without the product one,
((A{46341,}){46341,}) would wrap to a negative minimum and walk
past the infinity gate. An overflow declines the rewrite
rather than raising an error no query can reach.

2018 Use # and ~ for the absorption markers and document EXPLAIN's RPR
output [output shape]
The absorption markers were " and ', and " is what identifier
quoting already uses: a pattern variable named "select" with a
greedy unbounded quantifier printed as "select"+", the trailing
marker reading as the start of another quoted name. # and ~
cannot appear in an unquoted name, so the marker always lands
outside the quotes. It has to come before 2019, which adds one
more name to the ones the printers already quote. The plan
chapter's account of these markers was wrong twice over -- it
read them as opportunities the planner might still take rather
than an analysis already made, and tied the second one to
alternation, which it has nothing to do with -- and it said
nothing about the navigation lines or the counters ANALYZE
adds; all of that is filled in here.

2019 Reject PERMUTE and keep a pattern variable of that name quoted
[diagnostics]
v50 has no PERMUTE keyword, so the standard spelling parsed as
a pattern variable of that name followed by a group, and an
undefined variable defaults to TRUE -- PATTERN (PERMUTE(A)) was
accepted with a meaning the standard does not give it. The
keyword makes that name ambiguous in one position, so a pattern
variable called permute is printed quoted there -- by the
rewriter and by EXPLAIN alike, so the two spellings of a
pattern agree -- while a DEFINE entry, always followed by AS,
stays bare.

2020 Raise the RPR nesting depth limit to the last representable depth
[cleanup]
Nesting depth is stored in an unsigned byte, so 255 is the last
value it holds, and the ceiling was set one below it -- which
cost a depth: 253 was accepted where 254 fits. At 254 the
depth plus one lands exactly on 255 and the type is spent.

2021 Refresh stale RPR comments and drop three duplicated blocks
[comments]
No code changes. A design overview in the executor source that
repeated the README and the struct headers goes away, along
with an appendix that listed functions by name.

2022 Correct stale RPR test comments and fill gaps in the RPR
documentation [tests, docs]
No code. The only SQL statement that changes is one that is
deleted -- a GROUP BY + RPR case whose recorded output is a
syntax error, so no change to RPR could ever have made it fail.

2023 Jumble RPR DEFINE variable names [wrong result]
A DEFINE variable name lives only in a field the query jumble
ignores, so DEFINE A AS p > 50, B AS p < 50 and the same two
swapped collapsed onto one query id.

2024 Section the trailing RPR integration tests and gather the planner
guards [tests]
A refactor of the test cases. What had piled up at the end of
the integration file gets the numbered headers the rest of it
uses, and the planner properties two other files were asserting
as well move here, beside the assertions that already cover
them. One case stays for a reason of its own: it is the only
view in the tree that serializes an RPR window with a non-RPR
one, so it is what pg_dump and pg_upgrade need to exercise that
round trip, and it is left undropped on purpose.

2025 Remove stray spaces and column qualifiers from deparsed RPR
clauses [wrong result]
Two defects in how a row pattern window is printed. AFTER
MATCH, INITIAL, PATTERN and DEFINE came out as four independent
blocks, each opening a newline of its own, so the separator
space meant to sit between them landed at the end of the
preceding line, and DEFINE left one more before the closing
parenthesis. The four only ever appear together, so they fold
into a single branch. And a DEFINE's columns were printed with
whatever qualification the variable carried, though that
qualifier slot belongs to pattern variables and the parser
rejects every qualified spelling -- so the deparsed text of a
view over more than one relation could not be restored. That
is the failure Tatsuo reported on 08-14 and fixed himself on
08-21; rule-fix.txt and this patch fix the same thing, and I
kept this one because the series is built on it.

2026 Drop the always-true RPR initial flag [cleanup]
The field is always true and the deparser stopped reading it in
2025. Nothing marks it as ignored by the query jumble, so
removing it moves the query id of every window clause, harmless
while the field is unreleased.

3XXX -- deparse

3001 Pin the column names a DEFINE clause references when deparsing
[wrong result]
A draft -- expect this one to change. It closes the round-trip
failure reported on the list on 08-12: a view is created, a
later ALTER TABLE ADD COLUMN on the join partner makes the
DEFINE's unqualified name ambiguous, and the view can no longer
be restored. Rather than restoring the qualification, which
the parser rejects, the name a DEFINE references is reserved
the way a column merged by USING is: the intruder is pushed
aside to name_1 and its relation gets a column alias list.

4XXX -- carries an open item, or came in from Jian's inbox

These are here because they are ready, not because they are
finished. 4001..4004 each still carry something I know about,
listed with the patch. I would rather post them with the open items
named than hold the whole band back.

4001 Reject row pattern recognition combined with GROUP BY
[not implemented]
The combination does not survive today: more than one grouping
set trips an internal consistency error, and none of the path
it takes is tested, so it is refused for now and left to be
widened later.
Open: the gate reads the GROUP BY spelling only. A query with
HAVING and no GROUP BY, or a bare aggregate, produces grouped
output just the same and still runs. Behind the blanket
rejection there is also a mis-rejection of DEFINE x+y with
GROUP BY x+y, which reappears the moment the gate is narrowed.

4002 Retain DEFINE columns only for a window some window function uses
[plan shape]
A window nothing reads still kept its DEFINE's columns alive in
the subquery below it, so those values were carried up the plan
for a match that never runs. Only a window some window
function actually references keeps them now.
Open: it is still all-or-nothing per window clause, and the
neighbouring guard that 4003 removes answers the same question
the other way, so the two have to be judged together.

4003 Let an unreferenced RPR window function be removed [plan shape]
A window function whose clause carried a DEFINE was never
replaced with NULL, on the grounds that the pattern match has
to run regardless. It does not: the match has no side effect,
and its only observable output is that function's own result,
so if nothing reads it the whole window can go. The guard goes
with it.
Open: the test shape that overlaps a non-junk DEFINE column
with a fully unreferenced window was removed here and needs to
come back.

4004 Reject whole-row references in a DEFINE clause [diagnostics]
Closes the ROW(alias.*) path that bypassed both DEFINE gates.
Open: a three- or four-part column name with a typo takes the
same fallback and is now reported as a whole-row reference, so
the "Perhaps you meant" hint that still appears outside DEFINE
is lost inside it. The 53 lines of coverage this deleted have
not been restored.

4005 Drop the dead NULL varMatched path from the RPR executor
[cleanup]
The per-row cache was allocated only when the DEFINE list was
non-empty, and the reset carried a matching NULL test. Neither
can fire: DEFINE is mandatory for a row pattern window, and the
allocation is reached only for one. Assert it where the array
is allocated and reset unconditionally.

4006 Simplify the RPR pattern grammar actions with castNode [cleanup]
Two grammar actions tested the node's tag before reading it and
wrapped the value when the test failed. Every value reaching
them is already that node type, so the fallback arms were
unreachable. castNode() asserts the tag instead of branching
on it, which is what the neighbouring action already does.

4007 Drop a redundant assertion and a redundant copy from the RPR
planner [cleanup]
An assertion that both arguments are non-NULL, one line before
they are dereferenced and with nothing able to violate it: the
requirement moves to the header comment, where a caller reads
it. And a copy of each DEFINE variable name into an array that
outlives nothing.

4008 Assert the two RPR absorption invariants where each is relied on
[cleanup]
Both places that settle a state's absorbability were deciding
what they could have asserted. The invariant is load-bearing
-- state merging keeps one state of a merged pair, so a failure
would let a context be freed while it still holds the match --
and both were measured never to fire across the whole test
corpus before being written as Asserts.

4009 Take the failed match in nfa_match as an early exit [cleanup]
The matched case, some seventy lines with the deepest block in
the file inside it, sat in an if whose else only unlinked the
state and moved on. Inverting the test makes that an early
continue and takes a level of nesting off the rest. The
statement sequence is otherwise unchanged.

9XXX -- reproduces without RPR at all, submitted separately

These three touch pre-existing window code, deparse code, or the
port layer, so none of them belongs in the same commit as this
feature. They are not attached here; each goes out on its own.

9002 Add EXCLUDE TIES window frame test coverage [coverage]
The coverage 0002 removes, put back by itself.

9003 Keep column names of RTEs outside the FROM clause unchanged when
deparsing [upstream defect]
Column names are uniquified for RTEs the FROM clause never
prints, a rule's NEW and OLD among them, and such an RTE has
nowhere to carry a column alias list. An unnamed FULL JOIN
USING makes those names unique query-wide, so new.x deparses as
new.x_1, and pg_dump output built that way drops the rule on
restore with only "column new.x_1 does not exist" to show for
it. It surfaced while writing 3001, but an unnamed FULL JOIN
USING reaches it without any of this; 3001 only widens the
path.

9004 Retry open() when it fails with EINTR [upstream defect]
Three of my per-commit sweeps stopped here, all of them on
macOS with the vnode table pegged at its limit. The existing
retry covers only the out-of-descriptor errors, so EINTR became
a plain error -- and when that lands during abort processing,
abort re-enters itself and trips an assertion the backend
cannot survive, whereupon the postmaster takes shared memory
for corrupt and restarts the cluster.

Known issues

The per-patch open items sit with their patches; in number order
they come to this.

3001 closes the round-trip failure reported on 08-12. It is a
draft, and its approach may still change.
4001 refuses row pattern recognition together with GROUP BY. The
gate reads that spelling alone, so a query that groups without
it still runs.
4002 keeps a DEFINE's columns only for a window something reads.
It is all-or-nothing per window clause, and 4003 answers the
same question the other way, so the two have to be judged
together.
4003 lets a window nothing reads be removed. It deleted the one
test that overlapped a non-junk DEFINE column with a fully
unreferenced window.
4004 closes the whole-row path through a DEFINE. A mistyped three-
or four-part name now takes that path too, and loses the hint
it used to get.

What follows is the rest: what no patch here carries, which stands
after this series and has to be settled before the feature is
committed, whoever settles it.

A navigation answers with the current row when its argument folds to
a constant. Constant folding does not know the navigation node, so
it descends into the argument, and where a column there is replaced
by a constant -- over a VALUES list or an inlined CTE -- nothing is
left to read from the target row. What comes back is a wrong answer
rather than an error: the current row's value, where the absent
target row should have given null. Where the folded argument raises
instead, it raises during planning. 2009 leaves this out because
the fix belongs in constant folding, which neither v50 nor this
series opens.

Whether a DEFINE is accepted turns on the plan shape: volatility
that folds away is accepted, volatility that folding splices in is
rejected. The FOR PORTION OF check and the one over HAVING decide
the same way, and I take the convention to be that such a check sees
what the executor would run, and that what the planner never plans
is not its business. That reading took a good deal of confusion to
arrive at, which is reason enough to want it confirmed rather than
assumed.

The pattern node's hand-written serialization does not honour its
contract in three places: a field one path keeps and another drops,
a writer and a reader that are not a pair, and a signedness
mismatch. None misbehaves today, each held safe by something
outside the serialization code rather than by design. Each is a
line or a character, and they will go out as a patch of their own
for review.

The two defects that reproduce without row pattern recognition
should go out as their own submissions, each with its own commitfest
entry. Neither belongs in this feature's judgement, and neither
should wait on it.

Best regards,
Henson