Re: Row pattern recognition

Hi hackers,

Over the last few weeks I put the RPR matcher through a systematic
cross-check against Oracle 23ai and Trino 471. This message reports
what that surfaced: a few correctness defects in the matcher and in
context absorption, and a list of feature gaps that are directions
rather than bugs.

== How the cross-check was done ==

I took the roughly 1,000 PATTERN statements in the regression suite.
At the point each query runs I dumped the source rows and asked each
engine the same three things per row -- the length of the match that
starts at this row, and that match's first and last row. On PG that
is count(*) / first_value / last_value over the RPR window. Trino has
the same window form of row pattern recognition, so I ran it there in
the same shape. Oracle has only MATCH_RECOGNIZE, so there I reduced

MATCH_RECOGNIZE ... ALL ROWS PER MATCH WITH UNMATCHED ROWS

to the same shape (keeping only the match's first row, empty matches
being the ones with a NULL classifier).

Where Oracle runs a query I judged against Oracle; where Oracle
rejects it (a quantified subpattern that can match empty -- ORA-62513)
I used Trino; where the two engines split I used the ISO/IEC TR
19075-5 text.

On the queries both engines run, zero rows differ. But the cross-
check surfaced defects in areas the suite did not cover.

== Correctness defects ==

--- 1. Preferment in the matcher ---

There are three roots.

(a) The cycle guard identifies a matcher state by its position in the
pattern alone. A state is really (position, repetition count);
looping back to the same variable with a different count is a new
state, not a cycle. The guard kills it and the whole match
disappears.

PATTERN (A+ | B){2} on A, A, A
now: no match expected: 3 rows

(b) An empty iteration does not stop the quantifier (TR 19075-5
7.2.8: once the lower bound is met and the body matches empty, the
quantifier stops looping -- the Perl rule). Discarding the empty-
iteration state demotes "stop here" below a less-preferred branch,
which then consumes rows first.

PATTERN (A? | B)* on A, B
now: 2 rows expected: 1 row

(c) The fast-forward order is decided by the group's own greed. When
min == max the group's greed says nothing, yet the body may still
prefer to consume.

PATTERN ((A?){2}?) on A, A
now: 1 row expected: 2 rows

Engine cross-check:

case PG now exp Oracle Trino std
(A+|B){2} AAA 0 3 3 3 -
(A?|B)* AB 2 1 rej 2 1 (7.2.8)
((A?){2}?) AA 1 2 rej 2 -
((A??){2}) AA 2 empty rej empty -

One point to note. On the (A?|B)* row, current PG and Trino give the
same value, 2 rows -- and 2 is wrong. Had Trino been the sole
reference this defect would have passed; two engines agreeing is not
by itself proof. I come back to this case, with Perl, in the last
section.

Direction: apply the cycle guard only to states that are not a pattern
variable (a variable consumes a row, so it cannot form an epsilon
cycle, and duplicates are already screened by the existing uniqueness
check, which compares the counts). When an empty iteration reaches a
repetition's exit with the lower bound already met, do not discard it
-- enumerate the stop at that preference rank. And decide the fast-
forward order from the body's preference, not the group's.

--- 2. Context absorption ---

The absorption optimization (dropping an inferior context once
dominance holds at a comparison point) produced two wrong answers and
one potential hang.

First, absorption drops a match that a non-absorbable branch has
already recorded.

PATTERN (A{5,} | C)
-- at id=2, C matches [2,2] but cnt=0 (expected 1)
-- EXPLAIN ANALYZE: "0 matched, 2 absorbed"

The dominance argument covers only a context's future (in-progress)
matches; a match already recorded on a non-absorbable branch is
outside it. (I reported this on the thread on 2026-07-07.)

Second, a wrong result in the alternation branch walk.

PATTERN (A | (B C)+ (D E)+) input: D E D E
-- now: match [1,4] expected: no match

The walk follows a link that is overloaded -- it means "next branch"
at a branch head but "skip this group" at a group head -- so when
the last branch starts with a group, the trailing group leaks out as
an extra branch. The pattern behaves as A | (B C)+ | (D E)+ and
matches a bare (D E)+. It is a common-mode wrong answer: the same
with absorption on and off, so an on/off differential does not catch
it. (Reported on 2026-07-08.)

Third, a potential hang in the absorption analysis. To find a group's
end it walks forward through the pattern; with a {1,1} group in a
non-leading position of a sequence, the walk never leaves the group
and spins. It is at plan time (EXPLAIN alone triggers it) and the
loop has no interrupt check, so statement_timeout does not fire
either. A normalization that unwraps a {1,1} group removes this shape
before the matcher is built, so it does not reach users today -- but
one slip there turns it into a plan-time hang. Bounding that forward
walk would guard it.

== R020 subset vs R010 -- scope, not bugs ==

There are 11 queries PG rejects at parse time that Oracle implements.
None give a wrong answer -- the suite pins each as a negative test.
The root is one thing: PG implements a subset of R020 (the WINDOW
clause) while Oracle implements R010 (MATCH_RECOGNIZE). Going through
them, each already has a documented rationale -- none is an
unexplained gap. Six kinds:

feature n PG error
aggregate in DEFINE 3 aggregate functions are not allowed
in DEFINE
variable qualifier in 2 pattern variable qualified
DEFINE (A.val) expression ... is not supported in
DEFINE
pattern anchor ^, $ 2 syntax error at or near "^" / "$"
nav argument with no 2 argument of row pattern navigation
column, PREV(1) operation must include at least one
column
scalar subquery in DEFINE 1 cannot use subquery in DEFINE
expression
non-integer nav offset 1 offset argument of PREV must be type
PREV(val, 1.5) bigint, not type numeric

Grouped by why PG rejects:

Documented as not implemented (the v49 patch message lists both):

- Aggregate in DEFINE. It needs the per-match RUNNING/FINAL machinery
that MEASURES relies on (Oracle evaluates it as a running aggregate
that decides the match length), and this RPR does not implement
MEASURES.

- Variable qualifier in DEFINE (A.val). Also listed as not
implemented; it needs no machinery on the scale of MEASURES, so it
ranks differently.

Rejected because the standard says so in R020, so PG is right:

- Anchors ^ and $ (and the empty pattern PATTERN ()) are not permitted
in R020; the v49 message notes this. Oracle accepts them under
R010.
- The column-less navigation argument, PREV(1). ISO/IEC TR 19075-5
5.6.2 requires the first argument of PREV/NEXT to hold at least one
column reference or CLASSIFIER function, so PG's rejection follows
the standard, and was a deliberate call on the thread.

Intentional over-rejection, left as future work:

- A scalar subquery in DEFINE. 19075-5 6.17.4 permits one if it does
no pattern recognition itself and does not reference an outer
pattern variable. PG rejects all subqueries for now by design -- a
source comment marks it as future work, the blanket rejection
subsuming both conditions. This is the one I would call an actual
direction for later.

Type strictness, correct as is:

- DEFINE must be boolean, and a nav offset must be an integer.
SQL:2016 requires a boolean DEFINE condition; PG checks at parse
time while Oracle coerces with type-dependent rules (a text column
can die at runtime on the first non-boolean value). A fractional
row offset like PREV(val, 1.5) has no meaning, so the bigint
requirement holds too.

I record these so a migrating user knows what to expect and they are
not later read as bugs. The only forward item is relaxing the DEFINE
subquery rejection, which the source already marks as future work.

== On Trino as a reference ==

Trino implements the empty-match quantifier region Oracle rejects, so
it was a useful tie-breaker there. But it is only a partial
reference. The clearest case is the (A? | B)* row above, on rows
A, B:

PG now, Trino 2 rows <- both wrong
standard 1 row (7.2.8)

Trino keeps looping the * after the body has matched empty, so it lets
the second branch B consume row 2. 7.2.8 says the opposite: once the
lower bound is met and the body matches empty, the quantifier stops.

Perl settles it -- 7.2.8 states its stopping rule is modeled on Perl.
The equivalent pattern matches one character, not two:

"AB" =~ /^(?:A?|B)*/ -> "A"

At iteration 2 the preferred branch A? matches empty, the quantifier
stops there, and B is never reached. Perl and the standard agree on
one row; Trino's two is the outlier -- exactly what PG does now,
which is why PG matching Trino is not by itself proof. Forms with an
unbounded quantifier over a nullable-body alternation ((A*)*,
(A* B*)*, (A??)* B) cannot be trusted without deriving them from the
standard again.

== Pattern-tree optimizations ==

These rewrites are PG-internal, so the cross-check does not diff them
directly; it sees them only when a rewrite changes the final answer.
Three did. Each kept the set of matchable lengths but changed which
match is preferred [1]. The rewrite reorders a repetition's exit
decision relative to a choice point in the body, so a plain query
returns a different match with the optimization than without.

- One flattens a nested bounded quantifier, (A{2,3}){1,2} -> A{2,6}.
The nested form settles the first iteration's count before deciding
to iterate again: on four A rows it takes three and stops, while
A{2,6} takes all four.

- Another folds a copy of the body into an adjacent group's
quantifier, (A | B B)+ (A | B B)+ -> (A | B B){2,}. The merged form
defers the group's stop past a choice the separate copy made first:
it prefers a two-row match where the pattern as written prefers
four. A third folds a trailing copy of a group's body the same way,
with the same effect.

The common cause is reordering the exit decision against a body
choice. The safe gates: flatten only when the child cannot fall short
of its lower bound (min <= 1 or max unbounded); merge only when the
body consumes a fixed number of rows (equal-length alternatives
count). A mandatory leading copy of a group's body reorders nothing
and needs no gate.

[1] "Preferred" is the standard's preference ordering over the
possible matches (TR 19075-5 7.2): leftmost alternative first, and
greedy vs. reluctant on each quantifier. The set of matches does
not change; only this ordering moves.

That is everything the cross-check surfaced. The fix directions for
the matcher preferment and absorption defects are above; the R020
rejections each already have a documented rationale, with the DEFINE
subquery relaxation the one forward item.

Best regards,
Henson