Re: Row pattern recognition

Hi hackers,

This follows the ten-patch increment on top of v53 that I posted for
row pattern recognition (RPR, SQL:2016 R020, CF 4460) in this thread
[1], and my 07-16 report [2], where I cross-checked the matcher
against Oracle 23ai and Trino 471. Patch 0003 of the increment fixes
another case of the empty-iteration rule that I described in item 1(b)
of that report. It changes query results for some patterns, and it
changes how a group is compiled, so this mail explains the reason for
the structure change for readers of execRPR.c. The other two fixes in
0003, a DEFINE memory leak and a missing interrupt check, are in its
commit message and not here.

The patch is the nocfbot-0003 file attached to [1]. The same commit
is in https://github.com/assam258-5892/postgres/tree/RPR-20260930, on
top of v53.

The rule

ISO/IEC 19075-5 7.2.8 says that once a quantifier's lower bound is
met and an iteration matches the empty string, the quantifier stops
looping. This is the Perl rule. Without it, a body that can match
empty, such as A? in (A? | B), could loop back without consuming a row
and derive the same position again.

How the matcher enforces it

The matcher is an NFA. Between two rows it follows the epsilon
transitions by depth-first search, and no row is consumed in one such
expansion, so arriving twice at the END of a nullable group means the
body matched empty in that iteration. The cycle guard marks a
nullable group's END when the search arrives there. A second arrival
finds the mark, and if the count has reached the lower bound the state
leaves the group instead of looping back.

What was missing

A group entered through its BEGIN has not been to its END yet, so its
first iteration had no mark to find. If that iteration matched empty
at a count between the lower bound and a finite upper bound, the empty
iteration went unrecognized, the state looped back, and the matcher
kept a derivation that the standard excludes. Take these rows, each
listing the variables it satisfies:

row 1: B row 2: A, C row 3: C

PATTERN ((A? | B){1,2} C)

Matching from row 1, the standard and Perl give rows 1-3: B, then A,
then C. The matcher gave rows 1-2. A? may match empty at row 1,
which is an empty first iteration at count 1, the lower bound, and the
standard stops the quantifier there. C does not match row 1, so that
derivation ends. The matcher did not stop: it looped back, took B in
a second iteration, and C matched row 2. Because A? comes first, that
derivation ranks above B, A, C, and it won.

A reluctant first branch shows the same defect. ((B?? | B*){0,2} C)
over {B}, {B}, {B, C}, {C} matched rows 1-4 instead of rows 1-3.

The fix

Mark the END at the entry as well, so the first iteration is guarded
like the later ones. That needs the BEGIN to find its END.
BEGIN.jump used to name the element after the group, the path taken
when the lower bound is 0, and the END cannot be found from there: for
a branch-terminal BEGIN, fillRPRPatternAlt() had redirected jump past
an enclosing alternation, so it need not be next to the END at all.

Now BEGIN.jump names the group's own END. nfa_mark_group_entered()
marks it on entry when the END can loop on an empty match. The skip
taken when the lower bound is 0 leaves through END.next, which already
points past an enclosing alternation, so the separate redirect in
fillRPRPatternAlt() is gone.

What changes

Query results change only for patterns whose group can match empty in
its first iteration with a lower bound of 0 or 1 and a finite upper
bound, as in the two examples. The compiled pattern
changes in one place, the meaning of BEGIN.jump, which the
RPRPatternElement comment in plannodes.h now says. EXPLAIN output,
error messages and deparse output are unchanged. The new tests in
rpr_nfa cover the empty first iteration with lower
bound 0 and 1, with greedy and reluctant first branches, and with both
skip modes.

[1]
https://postgr.es/m/CAAAe_zDsYugq506ou49PU+Ok+4Umn5n59Qs5wYofvKyfEpvZJQ@mail.gmail.com
[2] https://postgr.es/m/<Message-ID of the 07-16 report>

Best regards,
Henson