Re: Row pattern recognition

Hi hackers,

This is another increment on top of v49, following the 07-19 posting. It
carries Tatsuo's 07-21 review and the three changes he asked for, a lazy
DEFINE evaluation rework, and the navigation-offset and DEFINE-volatility
work from Jian's side. The attachments are named nocfbot-XXXX-*.txt so
that cfbot does not pick them up.

The bands are the same as last time:

0XXX build fixes on top of the base (rebase, platform)
1XXX reviewed by Tatsuo
2XXX awaiting review from Tatsuo
3XXX Henson, in progress
4XXX Jian, in progress
8XXX restore pre-existing code (paired with 9XXX)
9XXX separately committable (paired with 8XXX)

Within 1XXX and 2XXX the last three digits belong to the patch and do not
change; only the leading digit moves as the status does. The other bands
are numbered on their own, from 001. The numbers follow the apply order.

This posting's fixed branch, which I will not rewrite, is:

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

An HTML companion carries the per-item tables -- the pre-commit triage
list, what the audits found this range introduced, the scope boundary,
and the provenance of each patch carried from Jian:

https://assam258-5892.github.io/postgresql/rpr/artifacts/2026-07-26-rpr-increment-map.en.html

Everything needed to review is in this mail. Where this mail gives a
count, the companion has the items behind it.

What moved since 07-19:

- Tatsuo finished reviewing 2015-2026 on 07-21, so those twelve move
from 2XXX to 1XXX as 1015..1026. The 2XXX band is now empty and the
review line stands at 1026 (was 2026).

- The three points that review raised are handled. 1016 keeps the
explicit arguments rather than the WindowClause, so the function
stays callable from an R010 / MATCH_RECOGNIZE node later. 8002 /
9002 are dropped -- they had nothing to do with RPR, as you said --
and 1019 no longer carries the patch that went with them. The
pg_attribute_unused() on function arguments is removed.

- 3XXX gained one patch, 3006, for lazy DEFINE evaluation.

- 4XXX is renumbered: old 4001..4006 folded into new 4001..4002, and
4003 onward are new. The new 4001 also carries three changes that
were never posted, so the band had to be renumbered to stay
consecutive. Old 4006, "Introduce execution struct RprNavState", is
part of the new 4001 and is renamed RPRNavState there.

- 0003 is new: it fixes the gram.y comments that name PATTERN as a
keyword.

- Nine of the eighteen are otherwise unchanged from 07-19, and 34 of
the 47 attachments are identical to what was posted then.

How the work is divided

Since 07-13 this has run on two tracks, and the band numbers follow that
split. 3XXX is the matcher and the pattern tree, execRPR.c and rpr.c.
4XXX is everything the matcher meets at its edges: navigation offset
resolution in the executor, DEFINE volatility across the planner's
preprocessing, junk targetlist entries, subquery pull-up interaction,
grammar diagnostics, deparse. The matcher's open questions are about how
the standard's preferment rules have to be read; the questions around it
are about PostgreSQL's own planner and executor invariants, so splitting
them let both move at once.

Coordination is continuous rather than per-posting: patches,
counter-patches and review notes go back and forth offlist, with
day-to-day discussion on Discord. Several patches below started as
something Jian sent offlist and were revised in that exchange. All eight
patches in band 4XXX are authored by Jian He.

Received offlist since 07-11, and where each one is now:

07-11 v51-0001 Fix the regression failure -> 4001
07-11 v51-0002 Stop evaluating navigation arguments -> 4002
pub v51-0003 Introduce execution struct RprNavState -> 4001
07-20 Remove validate_rpr_define_volatility (wip) -> 4003
07-21 mergeConsecutiveVars1 is equivalent (wip) -> 4004
07-21 Further enhance DEFINE volatility check -> 4008
07-23 code simplification -> 4006
07-24 Fix wrong results from mergeConsecutiveVars -> 4004
07-20 remove_ensure_reduced_frame.diff -> declined

Each was checked against the tree rather than the commit message:
RPRNavState at 11 sites and the old name at none,
validate_rpr_define_volatility at none, mergeConsecutiveVars1 at none,
hasRPR at 7, and the initial field gone.

The declined one is remove_ensure_reduced_frame, and the reason is a
decision this list already took. ensure_reduced_frame() is not there for
readability: it removes the (void) row_is_in_reduced_frame() call Tatsuo
flagged, and the RF_NOT_DETERMINED guard that call wrapped is
load-bearing -- without it a row already determined, RF_SKIPPED say,
overwrites the shared rpr_match_* record and is silently reclassified as
UNMATCHED. Where to put that guard went to the list as two options,
inline or in a shared helper, and Tatsuo picked the helper. Raised again
on 07-20; the answer is unchanged.

The third strand

One strand carries no band number: cross-review and verification. Each
track reviews the other's patches, and the whole range is audited before
posting.

The 07-11 triage list catalogued 53 candidate defects, one entry per
distinct failure; each patch below says how many it closes, and the
increment closes 30. Two later audits looked for what the work itself
introduced -- 07-24 over the preceding eight commits, 07-26 over the whole
4XXX band against the last 3XXX commit. Alongside those, the suite was
compared row by row against Oracle 23ai and Trino 471 with no query
differing in result, and the rebase carried a clean build, the regression
suites and pgindent at every patch.

3XXX -- Henson, the matcher and the pattern tree

3001 through 3005 are unchanged from 07-19 and are described in that
mail. Between them 3003 and 3004 close ten triage items: the four PATTERN
rewrites that changed which match is preferred, and the six ways the
matcher violated the preferment rules or mishandled a zero-consumption
cycle. One patch is new.

3006 Simplify RPR DEFINE evaluation and match-result tracking
[behavior change -- valid queries no longer error]
DEFINE predicates were evaluated for every variable on every row,
including variables the NFA never goes on to test, so a predicate
that errors on a row the match would never have reached killed an
otherwise valid query. Evaluation is now lazy through a tri-state
RPRVarMatch cache consulted at the point of use; each predicate is
still evaluated at most once per row. rpr_evaluate_row() becomes
rpr_prepare_row(). Follows Jian's 07-20 review. Closes one triage
item.

3002, 3003 and 3004 remain one clause of the standard failing at three
layers, which is why they stay together.

4XXX -- Jian, the planner and executor around the matcher

Authorship is Jian's throughout. This is the least settled band and it
closes the most, so each entry notes what it fixes.

4001 Resolve RPR navigation offsets in the executor, not the plan tree
[behavior change -- wrong results / internal errors]
(Replaces old 4001..4004 and 4006.) Offsets were resolved during
executor init and written back into the RPRNavExpr of what may be a
cached, shared plan tree, so a non-constant offset -- a parameter,
an inlined SQL function, a volatile DEFAULT -- was frozen at what
the first execution saw, or was unavailable. This collects offset
resolution into one place in the executor, keeps the result in
executor state, and distinguishes constant, runtime and overflow
through RPRNavOffsetKind. It does not divide: split apart, the
intermediate states either give wrong answers or write into a
shared plan tree. The three unposted changes it carries are the
offset-kind enum, the nav-state lifetime rework, and finalize_plan
handling for DEFINE-only PARAM_EXEC.
Closes seven triage items, all in the offset-freezing family: a
PARAM_EXEC offset frozen at init, EXPLAIN (GENERIC_PLAN) failing on
one, compound outer-offset validation skipped, a DEFINE-only
PARAM_EXEC missing from extParam, offsets written into a cached
plan, and two comment contracts.

4002 Stop evaluating navigation arguments in case rows not exists
[behavior change -- wrong results]
(Was 4005.) Unchanged from 07-19. Closes one triage item: an
out-of-range navigation evaluated its argument over an all-NULL row
instead of returning an operation-level NULL, so the DEFINE truth
value flipped for a non-strict argument.

4003 Check RPR DEFINE volatility after expression preprocessing
[behavior change -- non-deterministic matches rejected]
The check ran before preprocessing, so anything constant folding or
function inlining introduced afterwards escaped it -- a volatile
default argument, or a volatile implicit cast planted into a JOIN
USING merged column. The result was a DEFINE that matched
differently on each execution, with no error. The bespoke walker
becomes one contain_volatile_functions() call on the folded
defineClause in subquery_planner().
Closes four triage items: those two injection paths, a misdirected
error cursor in the post-fold recheck, and -- with 4001 -- an
init-time frozen trim that disagreed with per-row re-evaluation.

4004 Rewrite RPR pattern list optimizations to edit lists in place
[behavior change -- wrong results]
The three list rewrites now edit in place, which also fixes two
ordering bugs: flattened children are spliced in at their original
position rather than appended, and the GROUP wrapping a run of
identical alternatives replaces the run in place rather than moving
to the head. Both orderings are semantically significant.
It carries its own guard: mergeConsecutiveVars must not merge a
greedy quantifier with a following reluctant one over the same
variable, since the pair settles the first count before the second
decides and leftmost-choice-first makes that observable. That was
the one wrong-results regression the 07-24 audit found, and the
guard is here rather than in a later patch because this is the
patch that gives mergeConsecutiveVars its current shape. Three
regression tests come with it, covering greedy-then-reluctant and
the cascade case; the committed tests only covered reluctant-first,
which is why the suite stayed green.

4005 Fix RPR junk targetlist entries and DEFINE diagnostics
[defect -- assertion failure / valid query rejected]
A junk TargetEntry took its resno from the targetlist length
instead of p_next_resno, so a second RPR window collided with the
first and tripped an assertion; and the dedup scan compared only
varno and varattno, so a LATERAL outer reference collided with a
local Var and made a valid query fail.
The diff does not read in the order the message does, so a map:
strands 1 and 2 are those defects, 29 lines in parse_rpr.c; 3 and 4
are diagnostics in gram.y and the DEFINE walker; 5 refreshes four
stale comments; 6 initializes a nav markpos to -1 for consistency,
changing no behaviour; 7 gives the rpr_integration tests numbered
sections, 358 of the 467 added lines. Reviewing 1 and 2 first, then
3 to 5, then 7, matches the risk.
Closes eight triage items: the two defects, a nav-depth
misdiagnosis, a quantifier error naming the wrong token, and four
comment contracts.

4006 Remove the always-true RPR initial flag and simplify window
deparse
No functional change. The initial flag in parsenodes.h was true at
every site that read it. Must follow 4005 because it removes the
field.

4007 Generate the RPR pattern-depth boundary tests with repeat() and
\gexec
Tests only. Generating the boundary cases keeps the file readable
and makes the boundary explicit; the generated queries and their
output are unchanged.

4008 Keep RPR subqueries un-flattened so DEFINE volatility is checked
[behavior change -- non-deterministic matches rejected]
4003 moved the check to the right place, but three paths still
reach a plan without passing it: pull_up_simple_subquery,
simplify_EXISTS_query, and UNION ALL leaf pull-up. A hasRPR gate
keeps those subqueries un-flattened. Two of the three are closed;
the third, constant-false pruning, is not, so that triage item
stays partly open.

8XXX / 9XXX -- restorations and separately committable patches

Unchanged from 07-13 except that 8002 / 9002 are dropped per the 07-21
review. They restore pre-existing code RPR had no reason to touch (8XXX),
then put back only the parts RPR needs (9XXX), and apply in the order
8001, 8003, 9001, 9003.

Where that leaves the two lists

Of the 53 triage items this increment closes 30, and the 07-21 review
closed one more in 1026. Of the rest:

11 open, nine of them in the planner and deparse axes, which this
increment does not touch
3 partly closed
2 waiting on a design decision that gates them
6 re-judged as not defects, or decisions now taken

The two audits found 15 items the work itself introduced or left behind.
Two are closed, one is an accepted trade-off, and twelve are open:

1 undefined behaviour, reachable from a plain EXPLAIN
3 behaviour changes that I think are right but that no commit
message records and no test pins
1 a plan-shape cost from a gate wider than it needs to be
3 test-suite items -- two latent flakes and one test that cannot
distinguish the fix it documents
4 diagnostics and hygiene

None of the twelve affects a query result: the 07-26 audit found no
path across the eight patches by which an answer differs from the last
3XXX commit.

Both counts are a working classification. Verdicts can move as each item
is worked through in detail.

The first is worth naming here rather than leaving to the table. In 4001,
resolve_one_nav() reaches signed int64 overflow on two subtraction sites,
because the negative-offset clamps that sat in extract_const_offset() and
eval_nav_offset_helper() were removed while the init pass still runs with
validate = false. A plain EXPLAIN reaches it; the sibling arms use
pg_add_s64_overflow() and only the subtractions are unguarded. Restoring
the clamp on the non-validating path is the fix, and it makes the
"both >= 0, cannot underflow int64" comment true again -- that comment was
resting on the deleted clamp. It belongs in 4001, and since the branch
above is fixed as posted, it goes in with the next revision.

Also carried to the next revision: createplan.c keeps an #include
"common/int.h" whose last use 4001 removed, and the removal of
nav_null_slot is the one item from the v51 review not yet carried.

And one I owe an answer on. Jian's 06-24 message raising four cleanups
in ParseRPRNavCall -- the decoration comment block, coerce_to_target_type
over coerce_to_common_type, dropping the offtype test, and the extra
parentheses around ereport() -- never got a reply from me. It came in
from his other address and I missed it. parse_func.c has not changed
since, so all four still stand as written. I will review them and
reply.

One resource question outside this series

One tuplestore read pointer is shared by the navigation target and the
frontier, so once the tuplestore spills a match costs Theta(length^2)
physical re-reads -- PREV 1.7 ms against FIRST 5358 ms at n=4000.
Results are correct; the cost is I/O. Splitting the read pointer fixes
it without touching absorption, and it is post-commit work.

One question

Tatsuo -- a view on the CF 7056 direction would unblock the whole deparse
axis. The window-name quoting defect it fixes is the same defect RPR has
for pattern/after/initial/seek, and the two other deparse items touch the
same function, so they cannot be sequenced until that one is settled.

As before, please let me know if any of the slicing or grouping looks
off.

Best regards,
Henson