Re: Row pattern recognition

Hi hackers,

This is the increment on top of v51. It is 27 patches, named
nocfbot-XXXX-*.txt as before.

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

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

They apply on top of v51, in numeric order and with nothing else in
between. The base is the cfbot branch's commit for it, ac0ac5c599e
"[CF 4460] v51 - Implement row pattern recognition feature", which
is the posted v51 series on master of 2026-09-02.

Each entry says what v51 does wrong and what the patch does about
it, and the tag in brackets says what kind of problem it is. Four
of the 22 in the series proper give a wrong answer or a spurious
error on v51 today; with those in, no wrong answer we know of is
left standing, and what remains open is quality, set out under
"Known issues" at the end.

The four are:

- 2001 a view over a join stops re-parsing once the other side
acquires a column the DEFINE names
- 2008 a DEFINE clause reads ungrouped columns under GROUP BY
- 2010 a DEFINE clause takes a qualifier the pattern variable owns
- 2012 a navigation argument reads a constant, not the target row

Numbering

Numbers are reissued whenever the base version changes. These are
cut against v51; they do not continue the ones that went out on
08-26 against v50, where the same number names a different commit.

The bands are the ones the last posting set out:

0XXX put back what the series changed outside its own scope,
or bring it level with a base that has moved
1XXX reviewed upstream, not yet absorbed into a version
(empty -- v50 took all of it)
2XXX the series proper -- cleaned up, not yet reviewed upstream
3XXX my own lane, in progress (empty)
4XXX Jian's lane, in progress (empty -- it held what still had
an open question or had just come in from his inbox, and
everything that stood there has been settled and sits in
2XXX now)
9XXX reproduces without RPR at all -- submitted separately

The empty bands stay reserved.

Apply order is the numeric order.

One note on authorship before the list. Twelve of the 27 carry Jian
as the author -- he wrote them, I rebased them onto the series,
verified them and wrote the messages. His are 2008 through 2019.

0XXX -- bring the series level with the base

0001 Place pg_nodiscard ahead of the storage class in the RPR
optimizer [build]
Seven forward declarations wrote "static pg_nodiscard
List *". The attribute has to come first, and cfbot's
Windows MinGW job rejected them. Move it in front of
static, as the rest of the tree writes it. I have no
Windows environment here, so I expect cfbot to confirm it.

2XXX -- the series

2001 Pin the column names a DEFINE clause references when
deparsing [wrong result]
The standard gives the qualifier slot in a DEFINE clause to
the pattern variable, so a column there is written bare and
cannot be qualified with its table -- which is how the
deparser resolves an ambiguous column everywhere else. A
view over a join whose DEFINE names a column of one side
therefore stops re-parsing once the other side acquires a
column of that name, and pg_dump output fails to restore.
Pin the names a DEFINE clause reads instead: the newcomer is
renamed to name_1 and declared in a column alias list, so
the DEFINE reference goes on meaning what it meant. This
went out as wip-0001 on 08-31.

2002 Evaluate an RPR DEFINE clause in the context reserved for it
[leak]
A context was built for the DEFINE predicate, but the
evaluation never used it, so the predicate's scratch went to
one that lives as long as the query. That was an omission
in writing the patch; my apologies. Peak resident size over
300k rows falls from 94MB to 18MB for a DEFINE that
allocates. No test: this shows up in resident size, which
the regression suite does not observe.

2003 Report the frame row pattern recognition needs, not the
broken option [diagnostics]
Each guard named the option it caught, so a window with no
frame clause was told about an option the query never wrote,
and a frame that broke more than one rule was told about
them one at a time. Naming what is wrong without saying
what is allowed leaves the user to guess. The report now
lists the frames row pattern recognition accepts, so the
query can be corrected from it. The set of accepted frames
does not change.

2004 Report a non-constant row pattern navigation offset as a
syntax error [diagnostics]
Two guards enforce one rule -- a navigation offset must be a
constant -- but reported it in two classes, one as a syntax
error and the other as not implemented. It is a restriction
on what the offset may be, not a gap in what was built, so
both report it as a syntax error now. Only the class
changes.

2005 Blame the alternation when a glued quantifier token is
followed by an Op [diagnostics]
A quantifier written against an operator with no space
between them arrives as one token, handled by a trick rather
than taken apart. Nothing is known to go wrong in what the
grammar accepts; the diagnostics are where it shows. The
report named a pair that is not a quantifier at all; it
blames the alternation now. Other spellings leave the same
kind of ambiguity, and pulling this out as its own patch,
done properly, may be the better answer later.

2006 Settle one contract for the RPRPattern copy, out and read
functions [latent]
The pattern node needs its copy, out and read written by
hand, and the three disagreed with each other and with the
header in three places. For the values actually in use they
agree, so nothing goes wrong today. This makes them agree
over the whole range the fields can represent, and states
the contract in the header.

2007 Correct two errors in the row pattern recognition
documentation [docs]
One clause was described in the wrong synopsis, and a note
said that exceeding one limit raises an error where the
limit named beside it raises one too and does not say so.
Both are corrected. The documentation, the comments and
README.rpr may want a review round of their own once the
code is settled; this posting does not attempt that.

2008 Let a row pattern DEFINE clause take part in grouping
[wrong result]
GROUP BY restricts which columns a query may name, and
makes a grouped expression readable only through its
result. The DEFINE clause was left out of that
substitution, so it went on reading the ungrouped columns.
Cases needing no substitution happened to work; a grouping
set that can null a column failed outright. ISO/IEC
19075-5 6.4 puts the row pattern input table after GROUP BY,
so this is a shape the feature owes. The substitution is
carried through DEFINE now, the deparser included, so a view
over grouped input still re-parses. More usage patterns are
worth testing than the ones covered here.

2009 Let an unreferenced RPR window and its DEFINE columns be
removed [plan shape]
A window whose function nothing reads is dropped when the
subquery is planned. Row pattern recognition had been made
an exception, and should not have been. What changes:

- a window is no longer kept alive merely because it
carries a DEFINE clause; that premise was false
- which windows survive is decided in this same pass, so
the window functions are settled first and the set is
read from what they leave
- a dropped window's DEFINE clause is withdrawn with it,
being the one place a window clause owns an expression
tree

The window clause itself stays in the list, so indexes into
it do not move.

2010 Reject whole-row references and qualified names in a DEFINE
clause [wrong result]
ISO/IEC 19075-5 6.5 gives the qualifier slot in a DEFINE
clause to the pattern variable, so nothing else may occupy
it. Two gaps let something else through:

- a bare relation name was accepted and produced a
whole-row reference, which has nothing to resolve
against there
- ROW(t.*) was expanded before either check saw it, and a
view written that way cannot be restored

Both are rejected now, and the rule widens to every
qualified name. Nothing becomes unreachable -- unqualified,
each of them still resolves -- and a name resolved by a hook
that answers before the parser never reaches this rule at
all. The checks also moved to where the reference has
resolved, so a mistyped column keeps the hint it gets
everywhere else.

2011 Simplify the RPR pattern grammar actions with castNode
[cleanup]
Two grammar actions tested the node type before reading it
and wrapped the value when the test failed. The test cannot
fail. Take the cast instead. No grammar rule or precedence
changes.

2012 Do not substitute a row-independent value into a navigation
argument [wrong result]
Subquery pull-up substitutes the constant a one-row
subquery's column stands for. Inside a navigation argument
it must not: PREV and its kin read the argument at another
row, where the column is not the constant this row gave.
That substitution is the defect, and it is what this
corrects. Constant folding only surfaced it -- with the
column gone nothing stopped the fold, so PREV(v / 0) over a
one-row VALUES read 10 / 0 and raised while planning, where
execution, finding no target row, never divides. The
folding pass is not at fault and is unchanged.

2013 Have the RPR executor read its own state instead of being
handed it [cleanup]
A bundle of small refactorings:

- values the executor already holds were computed by the
caller and passed down; they are read where they are
- a helper took one context and left the guard and the walk
to each of its callers; it does both itself now
- a function with no caller left, and a free path that
cleared three fields where it should clear all
- a classification whose cascade order carried the meaning;
it tests the recorded row first instead
- an early exit for the case that was wrapping the other
- assertions that re-derived what had just been enforced

2014 Name the RPR NFA helpers for what they do and assert what
they assume [cleanup]
- two helpers named neither their subject nor their
effect; renamed
- one of them did a second job that belonged to its
caller; moved out
- three assumptions carried in comments become assertions,
and two unreachable NULL branches go

2015 Name the RPR quantifier tests instead of spelling them out
[cleanup]
- two functions made the same quantifier decisions, one
through local booleans and the other written out by
hand; the tests get names in the header, so both ask the
same question
- two of those differ only in < versus <=, which is the
reason to name them rather than merge them

2016 Pass elements, not indexes, through the absorbability walk
[cleanup]
- three functions took an element index, and one a scope
depth with it, which every caller had to keep
consistent; they take the element now
- that exposed an assumption one of them rested on, which
holds by test rather than by luck now

2017 Drop the redundant origin and collation marking of a DEFINE
clause [cleanup]
Two calls at the end of DEFINE parse analysis do nothing
the clause needs, and both go:

- one fills in fields only a SELECT targetlist or a
RETURNING list uses
- the other repeats work a later pass does anyway

2018 Report an EXCLUDE clause on its own, not as a frame shape
[diagnostics]
- EXCLUDE was listed among the frames 2003 reports as
accepted, but it modifies a frame rather than being one;
it gets a report of its own
- that report is raised after the shape has been settled,
so a query breaking both is told about the shape first,
which has to be rewritten either way
- the remaining message carries its frames as parameters,
so a translator is not asked to reproduce SQL syntax

2019 Reset the DEFINE evaluation context where the predicate runs
[cleanup]
- the context was reset in two places away from the
predicate it belongs to, correct only because nothing
allocated across those boundaries; it is reset
immediately before the predicate now
- one function is renamed to the verb it actually performs

2020 Bring README.rpr level with the code it describes
[comments]
Read from the code back to the document, the README was
wrong in eighteen places and silent about more:

- the wrong ones had mostly outlived the code they
described
- what the feature asks of the planner had never been
written down, nor anything about the two printers that
display a pattern; those are two new chapters, appended
so no existing number moves
- eight more sections fill gaps inside the existing ones

2021 Record which WindowClause field answers "is this a row
pattern window" [comments]
Three fields are set together at parse analysis, so any of
them looks like the marker for a row pattern window. The
planner does not keep them so: 2009 empties defineClause
alone. The header now says to test rpPattern, and what an
emptied defineClause beside it means -- the clause will not
run. Comment only.

2022 Mark two costs the RPR engine carries on purpose
[comments]
Two limitations the series carries knowingly met nothing
at the code, and README.rpr said the opposite at both:

- states are compared exactly where nothing above the
lower bound is read, so two with the same future stay
apart and a branching unbounded pattern piles them up:
(A{2,} B)+ C with C never true takes 30 ms over 80 rows,
37 s over 320, and does not finish over 640
- the frontier row and the navigation target share one
read pointer, so once the tuplestore spills each drags
the other back: PATTERN (S A+) DEFINE A AS v >= FIRST(v)
over 8000 rows takes 2.6 ms in memory and 24.3 s at
work_mem 64kB

The answers do not change and no code does.

9XXX -- reproduces without row pattern recognition

These four are here because they sit on the branch, not because
they belong to this feature. Each should go out as its own
submission with its own commitfest entry, and none should wait on
this one.

9001 Add EXCLUDE TIES window frame test coverage [coverage]
Working on the row pattern code turned up window frame
cases the existing tests do not reach: nth_value() has no
EXCLUDE TIES coverage at all, and last_value() has it only
over frames that contain the current row. One query for
each. Coverage of this kind belongs with the window tests
rather than the RPR ones, and I am collecting whatever else
turns up to propose as a patch of its own.

9002 Keep column names of relation RTEs outside the FROM clause
unchanged [wrong result]
An unnamed FULL JOIN USING makes the USING name unique
across the whole query, and that was applied to relations
the deparser never prints -- a rule's NEW and OLD, and the
target of an UPDATE or DELETE -- which have nowhere to
declare a renamed column:

CREATE TABLE t1 (x int, y int);
CREATE TABLE t2 (x int, z int);
CREATE TABLE t3 (x int, w int);
CREATE TABLE log (x int);

CREATE RULE r AS ON UPDATE TO t1 DO ALSO
INSERT INTO log
SELECT g.y FROM t1 g, t2 FULL JOIN t3 USING (x)
WHERE g.x <> new.x;

g is in the FROM clause and can take an alias list, so it
deparses as g(x_1, y). new cannot, and deparsed as new.x_1
all the same, so pg_dump output dropped the rule on
restore, reporting only

ERROR: column new.x_1 does not exist

This reproduces without row pattern recognition and goes
out as its own patch. It came out of writing 2001, which
only widens the way in.

9003 Retry open() when it fails with EINTR [wrong result]
POSIX allows open() to fail with EINTR and macOS returns
it, but only under heavy file I/O -- ordinary use never
sees it, and every occurrence here followed a macOS 26.6.1
update. We did not retry, so the failure surfaced far from
its cause: a file initdb should have created was missing,
or a parallel query crashed while starting its workers.
Add pg_open(), which retries, and use it in place of open()
through the backend, frontend and port layers.

9004 Put two typedefs.list entries back in sorted order
[cleanup]
typedefs.list is otherwise in byte order.
JsonTablePlanJoinType went in after JsonTablePlanState, and
PgStatShared_Index ahead of PgStatShared_IO, which reads as
alphabetical only under a case-insensitive comparison the
rest of the file does not use. The file then agrees with
LC_ALL=C sort throughout.

Known issues

What remains is quality, not correctness. Nothing below gives a
wrong answer, and as far as we have been able to find that class
is now empty: what stands is performance, an optimization not
applied, and one legitimate query refused.

One patch leaves an item of its own. 2010 refuses every
qualified name in a DEFINE clause, including a function
parameter written as f1.thr, which v51 accepts and which still
works unqualified. Where such a name collides with a pattern
variable, the hook's reading wins. The detail goes in a posting
of its own.

What no patch here carries, and what has to be settled before the
feature is committed, comes to this. None of it gives a wrong
answer, and each is worth a patch of its own rather than a line
here:

- to keep preferment from returning wrong answers the cycle
detection was narrowed to where it hardly fires, and a
repetition over a nullable body explodes. A bound on the
states held is the first answer; refusing such a pattern, as
Oracle does with ORA-62513, is the alternative
- the frontier row and the navigation target sit far apart in
the partition and share one read pointer, so once it spills
each access walks between them. A pointer each removes the
walk, but one buffer still serves them all, so every switch
re-reads a block. Keeping the last n blocks read, with n
taken from the pattern and the data, would close it
- the run condition is off wherever a DEFINE is present, even
for window functions that do not depend on the frame
- a DEFINE expression refuses every subquery, where the
standard allows one that neither does row pattern
recognition itself nor reads an outer pattern variable

Best regards,
Henson