MIME-Version: 1.0
References: <20260502.140304.670813149418899420.ishii@postgresql.org>
 <20260505.090124.365339750969814137.ishii@postgresql.org>
 <CACJufxEWL_ZnC-bs_yrg-Ys6ZUD3Ut_p1Ebj0bAcbzj67+HDAQ@mail.gmail.com>
 <20260517.190023.159085681032648582.ishii@postgresql.org>
 <CACJufxH-DZePhbdJM=8nNYceQiSbbXXLTw54iLhxiynQ+4hbBA@mail.gmail.com>
In-Reply-To: 
 <CACJufxH-DZePhbdJM=8nNYceQiSbbXXLTw54iLhxiynQ+4hbBA@mail.gmail.com>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Wed, 27 May 2026 14:49:44 +0900
Message-ID: 
 <CAAAe_zDephfiDA_A3FN0hCymJRogEr=Rt3QoCTf4qMYDLk+xNA@mail.gmail.com>
Subject: Re: Row pattern recognition
To: jian he <jian.universality@gmail.com>, Tatsuo Ishii <ishii@postgresql.org>
Cc: zsolt.parragi@percona.com, sjjang112233@gmail.com,
 vik@postgresfriends.org,
	er@xs4all.nl, jacob.champion@enterprisedb.com, david.g.johnston@gmail.com,
	peter@eisentraut.org, li.evan.chao@gmail.com, pgsql-hackers@postgresql.org
Content-Type: multipart/alternative; boundary="000000000000758c4c0652c62e2a"
Archived-At: 
 <https://www.postgresql.org/message-id/CAAAe_zDephfiDA_A3FN0hCymJRogEr%3DRt3QoCTf4qMYDLk%2BxNA%40mail.gmail.com>
Precedence: bulk

--000000000000758c4c0652c62e2a
Content-Type: text/plain; charset="UTF-8"

Hi jian, Tatsuo,

Thanks for the thorough first read of execRPR.c and the NFA. The
depth of understanding you reached on a fairly intricate body of
code in a short window is impressive -- and several of the open
questions in your review pointed straight at documentation and
comment debt on our side that needed exposing. First-reviewer
feedback of that kind is especially valuable, because the gaps it
surfaces are exactly the ones the next reader would otherwise have
to re-discover; closing them now puts everyone reading the code
afterwards on firmer ground. Would be glad to keep working together
on this area.


> Disclaimer: I had some private off-list discussions with Henson Choi
> regarding execRPR.c, and the NFA.
> The following are more formal comments regarding execRPR.c and the NFA
> algorithm, based on v47-0001 to v47-0009, I haven't applied the
> incremental diff yet.
> (Since the incremental diffs are scattered across several threads, a
> unified v48 would be better).
> (I'm still wrapping my head around the NFA in execRPR.c, so take the
> comments below with a grain of salt.)

Agreed on the unified v48 -- both the scattered incrementals and
the responses to your review will be part of that series. The
responses below will land alongside their corresponding change
(README, comment, test, or commit) in that series rather than as
a free-standing reply that defers the actual fixes.


> PATTERN (A B C D)
> We can short-circuit and exit early if any of the evaluations (A, B,
> or C) fail in nfa_match.
> This is necessary since the chance of a pattern element evaluation
> returning false is not rare, I think.

Agreed on the optimization intent. A slightly different shape worth
considering: rather than eager short-circuit in nfa_match, defer
DEFINE predicate evaluation to first use -- varMatched[i] computed
on demand and cached per row, so pruned paths never pay for
predicates they didn't reach. The code change is small; the part
needing care is whether "not evaluating" is safe for every predicate
(navigation state, slot setup, side effects). The current code or
the standard may already enforce constraints that make lazy
evaluation naturally safe, but I'd rather not act on that assumption
without concrete grounding in what the code actually enforces or in
test coverage that pins it down.

Would you be interested in driving the discussion in this thread?
You've been deep in execRPR.c recently, so the trade-offs sit
closest to you, and I think Tatsuo will land a good conclusion once
they're on the table. Happy to support the discussion in whatever
way is useful as it converges.


> For src/backend/executor/README.rpr:
> We should explicitly explain 'absorbable' and 'absorption' somewhere in
> README.rpr, as the text currently just assumes the reader knows what they
mean.
> Using some example illustrate "absorption" meaning, put it on
> README.rpr would be great.
> We can also mention that 'DFS' refers to Depth-First Search".

Acknowledged, and the request surfaced an underlying problem in the
README's terminology. "Absorption" is currently used for two
distinct things: an AST-level rewrite in Phase 1 that pulls
identical sequences around a group inside it, and the runtime
context-equivalence collapse that drives the O(n^2) -> O(n)
optimization. Sharing the word leaves a reader encountering
"absorbable" early on without an anchor.

Rather than disambiguate by qualifier ("prefix/suffix absorption"
vs "context absorption"), I'd lean toward renaming the AST-level
case so "absorption" stays reserved for the runtime concept. The
README then only needs to explain absorption in one place, in
detail, without the disambig preamble.

For the rename, "prefix/suffix merging" feels like the natural fit
-- the other AST-level optimizations in the same Phase 1 are already
named "consecutive variable / group / ALT merging", so it slots in
cleanly. "Prefix/suffix factoring" is another candidate if a more
descriptive verb is preferred.

Tatsuo, curious what you think of this direction and naming. Happy
to take any name you prefer for the AST-level operation, or to keep
the original "absorption" wording with stronger forward-references
if you'd rather not rename.

For the absorption explanation itself in README.rpr, the diagnosis
I'd offer is that Chapter VIII already carries the necessary content
-- the issue is narrative order. VIII-1 leads with the O(n^2) problem
framing, so a reader meets the cost shape before meeting the
intuition for why absorption is possible, and has to carry the
problem until VIII-2's monotonicity argument finally lands. Beyond
that, VIII-2 stays abstract; there is no row-by-row trace showing
two states being judged equivalent.

Two small additions seem to close most of the gap:

  (A) A 4-5 line intuition summary at the top of Chapter VIII,
      before VIII-1, naming what absorption is (collapsing contexts
      that have converged on identical future behavior) and the
      monotonicity principle that makes it safe. This gives the
      reader an anchor before the problem framing.

  (B) A short worked example at the end of VIII-2: a PATTERN (A+)
      trace over a few rows showing each new context being absorbed
      by Context_1 once its (elemIdx, depth-0 count) is dominated.
      Concrete state/count comparisons make the abstract solution
      land.

Curious if this read of the gap matches what tripped you up, and
whether (A) + (B) feel sufficient. Happy to draft both as part of
the v48 README changes.

For DFS, will expand it to "Depth-First Search (DFS)" at the first
occurrence.


> ``````
>   (4) Call nfa_advance(initialAdvance=true)
> ``````
> In V47, the variable `initialAdvance` does not exist.

Leftover from an earlier patch version -- the boolean parameter was
refactored away and the README notation wasn't updated. I'll bring
it in line with the current signature.


> In nfa_advance_var, after the first Assert, we can add:
> Assert(elem->next <  pattern->numElements);

Agreed. Will add it right after Assert(canLoop || canExit) in
nfa_advance_var, with a >= 0 lower bound tacked on while there
(RPRElemIdx is signed int16, INVALID = -1):

  Assert(elem->next >= 0 && elem->next < pattern->numElements);


> ExecRPRFinalizeAllContexts seems unnecessary; I commented it out,
> rerun the regress tests
> (TESTS='test_setup rpr_base rpr_nfa rpr_explain rpr_integration rpr'
> meson test -C $BUILD3 --num-processes 20 --suite regress --verbose)
> Only two SQL tests in rpr_explain.sql failed.

Reproduced this. You're right on correctness and memory: data rows
are identical with the call removed, and release_partition's
MemoryContextReset reclaims memory anyway.

Finalize isn't really about handling matches. By the time the
partition ends, all genuine FIN reaches have already been recorded
in-flight. Its job is to kill any VAR states still pursuing when
rows run out, so cleanup sees a uniform ctx->states == NULL across
every context. Three shapes survive there:

  - Pure pursuit (no matchedState, e.g., A+ B mid-pattern).
  - Empty-match candidate + pursuit (matchedState set with
    matchEndRow < matchStartRow -- e.g., greedy A* with no
    successful matches yet, while VAR is still chasing a longer
    non-empty one).
  - Real match + pursuit (matchedState set with matchEndRow >=
    matchStartRow -- e.g., greedy A* with some matches recorded
    and still looping for a longer one).

The first two get reclassified as failures by cleanup; without
Finalize they linger without contributing to stats. The third is
stat-neutral -- cleanup skips it either way -- but goes through
the same uniform path so partition-end classification stays
centralized.

The classification surfaces today only via rpr_explain stats, but
becomes user-visible once we extend the R020 surface or move into
R010 -- MEASURES and eventual R010 hooks count matches based on
this classification. Worth locking in now, and an explicit
partition-end stage is structurally cleaner than scattering the
logic.

Plan: keep the call and reframe it as the partition-end
classification policy holder. Strategically, that gives the future
partition-end hooks a single anchor to extend, instead of growing
scattered end-of-partition paths.


> SELECT first_value(id) OVER w AS match_start FROM stock_ticks
> WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED
> FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN ((A B) {2}) DEFINE A
> AS price < 100, B AS price < 100);
>
> The query above invokes the following code. Since the PATTERN above is
> not greedy, is the comment below incorrect?
> ``````
>     else
>     {
>         /* Greedy: enter first, skip second */
>         ...
>     }
> ``````

The comment is misleading; the code is correct. Two pieces:

First, greedy vs reluctant: '?' plays two distinct roles in our
grammar. As a quantifier on its own (A?, (A B)?) it means "optional"
-- equivalent to {0,1}. As a suffix on another quantifier (A+?,
(A B)*?, {n}?, etc.) it makes that quantifier reluctant. So {n}
without a trailing '?' is greedy; the {n}? form is reluctant.
PATTERN ((A B){2}) is in fact greedy.

Second, why the branch is entered: nfa_advance_begin's else arm
handles two cases at once:

  (a) Greedy with optional group: skipState != NULL, not reluctant.
      "Enter the group; also create the skip path."
  (b) Non-nullable group (min > 0, regardless of greedy/reluctant):
      skipState stays NULL, the outer guard
      "if (skipState != NULL && RPRElemIsReluctant(elem))" falls
      through, and the inner "if (skipState != NULL)" prevents the
      skip-path action from running.

(A B){2} has min = max = 2, so it lands in (b) -- the action that
actually runs is "enter the group", no skip path. The current label
only describes (a), which is why it reads wrong for your test query.
Plan is to rewrite the comment along the lines of
"Greedy-or-non-nullable: route to the first child; for optional
groups (skipState != NULL), additionally create the skip path."


> nfa_advance_var
> ```
>     else if (canExit)
>     {
>         ...
>     }
> ```
> The above ELSE IF overrides all RPRNFAState field values except
> RPRNFAState->next.
> Should we set RPRNFAState->next to NULL?
> (If I add ``state->next = NULL;`` in the above ELSE IF branch, all the
> regress tests still pass)

Good catch on the asymmetry. Tracing it through, state->next is
actually already NULL at every branch you flagged: nfa_advance
resets it just before crossing into nfa_advance_state, and the
intermediate branches don't disturb it. Your experiment passing
with an added "state->next = NULL" is consistent with that -- the
assignment is redundant rather than load-bearing.

The contract that keeps state->next sane lives at two concentrated
points (nfa_advance entry, nfa_add_state_unique linking), and the
branches in between are pass-through. Sprinkling the same reset at
every branch would be defensive noise rather than a real safety
net, so I'd leave the branches alone.

Happy to add a short comment near nfa_advance's reset marking it
as the boundary contract, so the next reader doesn't trip on the
same question.


> For function nfa_advance_var, I don't understand the meaning of the
> variable "count", after the first Assert I have added below:
> ...
> Rerunning the regress tests shows that count >= 3 occurs very
infrequently.
> ...
> Can we add more complex queries (more count >= 3) to check if the
> "count" variable is working correctly?

The "count" semantics will read more cleanly once the absorption
README work above lands (counts[d] = iteration count at nesting
depth d). For coverage I'll add a nested reluctant quantifier to
rpr_nfa (e.g., PATTERN ((A B){3,5}? C)) to drive count through the
3..5 band repeatedly. (rpr_nfa is the suite that already targets
Quantifier Runtime Behavior and Absorption Optimization.)


> In function nfa_add_state_unique:
>     /* Mark VAR in visited before duplicate check to prevent DFS loops */
>     ...
> I honestly don't understand the purpose of the code block above. But it
doesn't
> seem to influence the subsequent FOR LOOP;
> ...
> Could we add some comments explaining which external functions rely on
> this code and why it belongs in nfa_add_state_unique?

The code is correct, but the contract is split across two functions
and currently only one side points to the other. The visited marking
scheme is asymmetric on purpose:

  - Non-VAR elements (END/ALT/BEGIN/FIN) are marked on entry to
    nfa_advance_state because epsilon cycles must be prevented
    immediately.
  - VAR elements are marked later, in nfa_add_state_unique, only
    when added to the state list. That delay is intentional: it
    keeps legitimate quantifier loop-back to the same VAR across
    iterations possible.

The paired cycle check sits in nfa_advance_state, and the
asymmetric-marking rationale is documented there. What's missing is
the back-reference from nfa_add_state_unique. I'll add a single line
at the marking site pointing back to nfa_advance_state.


> nfa_states_equal
> compareDepth = elem->depth + 1; /* depth 0 needs 1 count, etc. */
> The comment above isn't helpful, IMHO, and I don't understand it.
> We should focus on why compareDepth should be ```elem->depth + 1```.

Agree the trailing comment is too terse. Two pieces are missing:

  (a) The +1 arithmetic: to compare counts up to depth N, we need
      slots counts[0..N], which is N+1 entries.
  (b) Why deeper slots are excluded: counts[d > elem->depth] are
      scratch state from deeper groups and get reset on re-entry,
      so they must not participate in equivalence judgment.

Two states sharing elemIdx are equivalent iff all
enclosing-or-current depth counts match. I'll replace the trailing
comment with a small block covering both pieces.


> function nfa_add_state_unique return value is not being used?
> Do we need to do something with the return value, or is this expected?
> (I don't have an opinion on it, I guess it would be better to raise this
issue)

Leftover from an earlier design -- the duplicate case is fully
handled inside the function (the state is freed and nfaStatesMerged
is incremented), so callers have nothing to branch on, and indeed
none of them do. Will change the signature from bool to void and
drop the return statements.


> In nfa_advance_alt, during the main WHILE loop, I think altElem->depth
> must be larger than elem->depth.
> Therefore we can do
> ``````
>         if (altElem->depth == elem->depth)
>             elog(ERROR, "nfa_advance_alt altElem->depth should not be
> the same as elem->depth reached");
>         if (altElem->depth < elem->depth)
>             break;
> ``````

I had to push back on this one. Tracing the depth bookkeeping:

  - For an ALT at depth D, branches sit at depth D+1, and each
    branch's first element has .jump pointing to the next branch's
    first (set in fillRPRPatternAlt). So the walk normally
    terminates when the last branch's .jump = INVALID -- the depth
    check doesn't fire at all.
  - But when the last branch is a quantified group, its first
    element is a BEGIN whose .jump = past-END (set by
    fillRPRPatternGroup and not overridden for the last branch).
    The walk then steps to a post-ALT element, and the depth check
    is what stops it from creating a stray state out there.

That post-ALT element has depth <= D:

  * D-1 if the ALT is inside an enclosing group with a non-trivial
    quantifier, e.g., PATTERN ((A | (B C)+){2}) -- post-ALT lands
    on the outer END at depth 0, ALT at depth 1. (A {1,1} outer
    wrap gets removed by single-child unwrap, so it has to be a
    real quantifier.)
  * D if the ALT has a sibling at the same level, e.g.,
    PATTERN (A | (B C)+) at top level -- post-ALT is FIN at depth 0,
    matching the ALT's depth 0.

So "altElem->depth == elem->depth" is a legitimate end-of-walk
signal for the quantified-group-last-branch case, not an invariant
violation. Treating it as an error would misfire on patterns like
A | (B C)+. The current "if (altElem->depth <= elem->depth) break;"
in nfa_advance_alt is intentionally <= and not <, and the looser
comparison is correct. Happy to add a brief comment there noting
the trigger condition, if it would help future readers.


Summary of decisions, in the order above:

  Short-circuit optimization       Separate series -- invite you to drive
  Absorption README narrative      Accept -- Chapter VIII summary + example
  AST-level "absorption" rename    Pending Tatsuo's call -- prefix/suffix
merging?
  DFS expansion                    Accept
  initialAdvance README mismatch   Accept -- align with current signature
  Defensive Assert in advance_var  Accept -- also add lower bound
  Finalize unnecessary?            Keep -- partition-end policy holder
  Greedy comment label             Accept -- rewrite to cover both cases
  state->next reset                Decline -- boundary contract covers it
  count >= 3 test coverage         Accept -- add to rpr_nfa
  visited marking purpose          Accept -- add back-reference comment
  compareDepth comment             Accept -- rewrite with intent
  Unused bool return               Accept -- change to void
  ALT depth invariant Assert       Decline -- end-of-walk signal, not
invariant

That's the full pass. The actual patches (nocfbot-0016 onward) will
follow shortly as a separate submission, for another review round.


Thanks,
Henson

--000000000000758c4c0652c62e2a
Content-Type: text/html; charset="UTF-8"
Content-Transfer-Encoding: quoted-printable

<div dir=3D"ltr">Hi jian, Tatsuo,<br><br>Thanks for the thorough first read=
 of execRPR.c and the NFA. The<br>depth of understanding you reached on a f=
airly intricate body of<br>code in a short window is impressive -- and seve=
ral of the open<br>questions in your review pointed straight at documentati=
on and<br>comment debt on our side that needed exposing. First-reviewer<br>=
feedback of that kind is especially valuable, because the gaps it<br>surfac=
es are exactly the ones the next reader would otherwise have<br>to re-disco=
ver; closing them now puts everyone reading the code<br>afterwards on firme=
r ground. Would be glad to keep working together<br>on this area.<br><br><b=
r>&gt; Disclaimer: I had some private off-list discussions with Henson Choi=
<br>&gt; regarding execRPR.c, and the NFA.<br>&gt; The following are more f=
ormal comments regarding execRPR.c and the NFA<br>&gt; algorithm, based on =
v47-0001 to v47-0009, I haven&#39;t applied the<br>&gt; incremental diff ye=
t.<br>&gt; (Since the incremental diffs are scattered across several thread=
s, a<br>&gt; unified v48 would be better).<br>&gt; (I&#39;m still wrapping =
my head around the NFA in execRPR.c, so take the<br>&gt; comments below wit=
h a grain of salt.)<br><br>Agreed on the unified v48 -- both the scattered =
incrementals and<br>the responses to your review will be part of that serie=
s. The<br>responses below will land alongside their corresponding change<br=
>(README, comment, test, or commit) in that series rather than as<br>a free=
-standing reply that defers the actual fixes.<br><br><br>&gt; PATTERN (A B =
C D)<br>&gt; We can short-circuit and exit early if any of the evaluations =
(A, B,<br>&gt; or C) fail in nfa_match.<br>&gt; This is necessary since the=
 chance of a pattern element evaluation<br>&gt; returning false is not rare=
, I think.<br><br>Agreed on the optimization intent. A slightly different s=
hape worth<br>considering: rather than eager short-circuit in nfa_match, de=
fer<br>DEFINE predicate evaluation to first use -- varMatched[i] computed<b=
r>on demand and cached per row, so pruned paths never pay for<br>predicates=
 they didn&#39;t reach. The code change is small; the part<br>needing care =
is whether &quot;not evaluating&quot; is safe for every predicate<br>(navig=
ation state, slot setup, side effects). The current code or<br>the standard=
 may already enforce constraints that make lazy<br>evaluation naturally saf=
e, but I&#39;d rather not act on that assumption<br>without concrete ground=
ing in what the code actually enforces or in<br>test coverage that pins it =
down.<br><br>Would you be interested in driving the discussion in this thre=
ad?<br>You&#39;ve been deep in execRPR.c recently, so the trade-offs sit<br=
>closest to you, and I think Tatsuo will land a good conclusion once<br>the=
y&#39;re on the table. Happy to support the discussion in whatever<br>way i=
s useful as it converges.<br><br><br>&gt; For src/backend/executor/README.r=
pr:<br>&gt; We should explicitly explain &#39;absorbable&#39; and &#39;abso=
rption&#39; somewhere in<br>&gt; README.rpr, as the text currently just ass=
umes the reader knows what they mean.<br>&gt; Using some example illustrate=
 &quot;absorption&quot; meaning, put it on<br>&gt; README.rpr would be grea=
t.<br>&gt; We can also mention that &#39;DFS&#39; refers to Depth-First Sea=
rch&quot;.<br><br>Acknowledged, and the request surfaced an underlying prob=
lem in the<br>README&#39;s terminology. &quot;Absorption&quot; is currently=
 used for two<br>distinct things: an AST-level rewrite in Phase 1 that pull=
s<br>identical sequences around a group inside it, and the runtime<br>conte=
xt-equivalence collapse that drives the O(n^2) -&gt; O(n)<br>optimization. =
Sharing the word leaves a reader encountering<br>&quot;absorbable&quot; ear=
ly on without an anchor.<br><br>Rather than disambiguate by qualifier (&quo=
t;prefix/suffix absorption&quot;<br>vs &quot;context absorption&quot;), I&#=
39;d lean toward renaming the AST-level<br>case so &quot;absorption&quot; s=
tays reserved for the runtime concept. The<br>README then only needs to exp=
lain absorption in one place, in<br>detail, without the disambig preamble.<=
br><br>For the rename, &quot;prefix/suffix merging&quot; feels like the nat=
ural fit<br>-- the other AST-level optimizations in the same Phase 1 are al=
ready<br>named &quot;consecutive variable / group / ALT merging&quot;, so i=
t slots in<br>cleanly. &quot;Prefix/suffix factoring&quot; is another candi=
date if a more<br>descriptive verb is preferred.<br><br>Tatsuo, curious wha=
t you think of this direction and naming. Happy<br>to take any name you pre=
fer for the AST-level operation, or to keep<br>the original &quot;absorptio=
n&quot; wording with stronger forward-references<br>if you&#39;d rather not=
 rename.<br><br>For the absorption explanation itself in README.rpr, the di=
agnosis<br>I&#39;d offer is that Chapter VIII already carries the necessary=
 content<br>-- the issue is narrative order. VIII-1 leads with the O(n^2) p=
roblem<br>framing, so a reader meets the cost shape before meeting the<br>i=
ntuition for why absorption is possible, and has to carry the<br>problem un=
til VIII-2&#39;s monotonicity argument finally lands. Beyond<br>that, VIII-=
2 stays abstract; there is no row-by-row trace showing<br>two states being =
judged equivalent.<br><br>Two small additions seem to close most of the gap=
:<br><br>=C2=A0 (A) A 4-5 line intuition summary at the top of Chapter VIII=
,<br>=C2=A0 =C2=A0 =C2=A0 before VIII-1, naming what absorption is (collaps=
ing contexts<br>=C2=A0 =C2=A0 =C2=A0 that have converged on identical futur=
e behavior) and the<br>=C2=A0 =C2=A0 =C2=A0 monotonicity principle that mak=
es it safe. This gives the<br>=C2=A0 =C2=A0 =C2=A0 reader an anchor before =
the problem framing.<br><br>=C2=A0 (B) A short worked example at the end of=
 VIII-2: a PATTERN (A+)<br>=C2=A0 =C2=A0 =C2=A0 trace over a few rows showi=
ng each new context being absorbed<br>=C2=A0 =C2=A0 =C2=A0 by Context_1 onc=
e its (elemIdx, depth-0 count) is dominated.<br>=C2=A0 =C2=A0 =C2=A0 Concre=
te state/count comparisons make the abstract solution<br>=C2=A0 =C2=A0 =C2=
=A0 land.<br><br>Curious if this read of the gap matches what tripped you u=
p, and<br>whether (A) + (B) feel sufficient. Happy to draft both as part of=
<br>the v48 README changes.<br><br>For DFS, will expand it to &quot;Depth-F=
irst Search (DFS)&quot; at the first<br>occurrence.<br><br><br>&gt; ``````<=
br>&gt; =C2=A0 (4) Call nfa_advance(initialAdvance=3Dtrue)<br>&gt; ``````<b=
r>&gt; In V47, the variable `initialAdvance` does not exist.<br><br>Leftove=
r from an earlier patch version -- the boolean parameter was<br>refactored =
away and the README notation wasn&#39;t updated. I&#39;ll bring<br>it in li=
ne with the current signature.<br><br><br>&gt; In nfa_advance_var, after th=
e first Assert, we can add:<br>&gt; Assert(elem-&gt;next &lt; =C2=A0pattern=
-&gt;numElements);<br><br>Agreed. Will add it right after Assert(canLoop ||=
 canExit) in<br>nfa_advance_var, with a &gt;=3D 0 lower bound tacked on whi=
le there<br>(RPRElemIdx is signed int16, INVALID =3D -1):<br><br>=C2=A0 Ass=
ert(elem-&gt;next &gt;=3D 0 &amp;&amp; elem-&gt;next &lt; pattern-&gt;numEl=
ements);<br><br><br>&gt; ExecRPRFinalizeAllContexts seems unnecessary; I co=
mmented it out,<br>&gt; rerun the regress tests<br>&gt; (TESTS=3D&#39;test_=
setup rpr_base rpr_nfa rpr_explain rpr_integration rpr&#39;<br>&gt; meson t=
est -C $BUILD3 --num-processes 20 --suite regress --verbose)<br>&gt; Only t=
wo SQL tests in rpr_explain.sql failed.<br><br>Reproduced this. You&#39;re =
right on correctness and memory: data rows<br>are identical with the call r=
emoved, and release_partition&#39;s<br>MemoryContextReset reclaims memory a=
nyway.<br><br>Finalize isn&#39;t really about handling matches. By the time=
 the<br>partition ends, all genuine FIN reaches have already been recorded<=
br>in-flight. Its job is to kill any VAR states still pursuing when<br>rows=
 run out, so cleanup sees a uniform ctx-&gt;states =3D=3D NULL across<br>ev=
ery context. Three shapes survive there:<br><br>=C2=A0 - Pure pursuit (no m=
atchedState, e.g., A+ B mid-pattern).<br>=C2=A0 - Empty-match candidate + p=
ursuit (matchedState set with<br>=C2=A0 =C2=A0 matchEndRow &lt; matchStartR=
ow -- e.g., greedy A* with no<br>=C2=A0 =C2=A0 successful matches yet, whil=
e VAR is still chasing a longer<br>=C2=A0 =C2=A0 non-empty one).<br>=C2=A0 =
- Real match + pursuit (matchedState set with matchEndRow &gt;=3D<br>=C2=A0=
 =C2=A0 matchStartRow -- e.g., greedy A* with some matches recorded<br>=C2=
=A0 =C2=A0 and still looping for a longer one).<br><br>The first two get re=
classified as failures by cleanup; without<br>Finalize they linger without =
contributing to stats. The third is<br>stat-neutral -- cleanup skips it eit=
her way -- but goes through<br>the same uniform path so partition-end class=
ification stays<br>centralized.<br><br>The classification surfaces today on=
ly via rpr_explain stats, but<br>becomes user-visible once we extend the R0=
20 surface or move into<br>R010 -- MEASURES and eventual R010 hooks count m=
atches based on<br>this classification. Worth locking in now, and an explic=
it<br>partition-end stage is structurally cleaner than scattering the<br>lo=
gic.<br><br>Plan: keep the call and reframe it as the partition-end<br>clas=
sification policy holder. Strategically, that gives the future<br>partition=
-end hooks a single anchor to extend, instead of growing<br>scattered end-o=
f-partition paths.<br><br><br>&gt; SELECT first_value(id) OVER w AS match_s=
tart FROM stock_ticks<br>&gt; WINDOW w AS ( ORDER BY id ROWS BETWEEN CURREN=
T ROW AND UNBOUNDED<br>&gt; FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTER=
N ((A B) {2}) DEFINE A<br>&gt; AS price &lt; 100, B AS price &lt; 100);<br>=
&gt;<br>&gt; The query above invokes the following code. Since the PATTERN =
above is<br>&gt; not greedy, is the comment below incorrect?<br>&gt; ``````=
<br>&gt; =C2=A0 =C2=A0 else<br>&gt; =C2=A0 =C2=A0 {<br>&gt; =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 /* Greedy: enter first, skip second */<br>&gt; =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 ...<br>&gt; =C2=A0 =C2=A0 }<br>&gt; ``````<br><br>The comment=
 is misleading; the code is correct. Two pieces:<br><br>First, greedy vs re=
luctant: &#39;?&#39; plays two distinct roles in our<br>grammar. As a quant=
ifier on its own (A?, (A B)?) it means &quot;optional&quot;<br>-- equivalen=
t to {0,1}. As a suffix on another quantifier (A+?,<br>(A B)*?, {n}?, etc.)=
 it makes that quantifier reluctant. So {n}<br>without a trailing &#39;?=
9; is greedy; the {n}? form is reluctant.<br>PATTERN ((A B){2}) is in fact =
greedy.<br><br>Second, why the branch is entered: nfa_advance_begin&#39;s e=
lse arm<br>handles two cases at once:<br><br>=C2=A0 (a) Greedy with optiona=
l group: skipState !=3D NULL, not reluctant.<br>=C2=A0 =C2=A0 =C2=A0 &quot;=
Enter the group; also create the skip path.&quot;<br>=C2=A0 (b) Non-nullabl=
e group (min &gt; 0, regardless of greedy/reluctant):<br>=C2=A0 =C2=A0 =C2=
=A0 skipState stays NULL, the outer guard<br>=C2=A0 =C2=A0 =C2=A0 &quot;if =
(skipState !=3D NULL &amp;&amp; RPRElemIsReluctant(elem))&quot; falls<br>=
=C2=A0 =C2=A0 =C2=A0 through, and the inner &quot;if (skipState !=3D NULL)&=
quot; prevents the<br>=C2=A0 =C2=A0 =C2=A0 skip-path action from running.<b=
r><br>(A B){2} has min =3D max =3D 2, so it lands in (b) -- the action that=
<br>actually runs is &quot;enter the group&quot;, no skip path. The current=
 label<br>only describes (a), which is why it reads wrong for your test que=
ry.<br>Plan is to rewrite the comment along the lines of<br>&quot;Greedy-or=
-non-nullable: route to the first child; for optional<br>groups (skipState =
!=3D NULL), additionally create the skip path.&quot;<br><br><br>&gt; nfa_ad=
vance_var<br>&gt; ```<br>&gt; =C2=A0 =C2=A0 else if (canExit)<br>&gt; =C2=
=A0 =C2=A0 {<br>&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 ...<br>&gt; =C2=A0 =C2=A0 =
}<br>&gt; ```<br>&gt; The above ELSE IF overrides all RPRNFAState field val=
ues except<br>&gt; RPRNFAState-&gt;next.<br>&gt; Should we set RPRNFAState-=
&gt;next to NULL?<br>&gt; (If I add ``state-&gt;next =3D NULL;`` in the abo=
ve ELSE IF branch, all the<br>&gt; regress tests still pass)<br><br>Good ca=
tch on the asymmetry. Tracing it through, state-&gt;next is<br>actually alr=
eady NULL at every branch you flagged: nfa_advance<br>resets it just before=
 crossing into nfa_advance_state, and the<br>intermediate branches don&#39;=
t disturb it. Your experiment passing<br>with an added &quot;state-&gt;next=
 =3D NULL&quot; is consistent with that -- the<br>assignment is redundant r=
ather than load-bearing.<br><br>The contract that keeps state-&gt;next sane=
 lives at two concentrated<br>points (nfa_advance entry, nfa_add_state_uniq=
ue linking), and the<br>branches in between are pass-through. Sprinkling th=
e same reset at<br>every branch would be defensive noise rather than a real=
 safety<br>net, so I&#39;d leave the branches alone.<br><br>Happy to add a =
short comment near nfa_advance&#39;s reset marking it<br>as the boundary co=
ntract, so the next reader doesn&#39;t trip on the<br>same question.<br><br=
><br>&gt; For function nfa_advance_var, I don&#39;t understand the meaning =
of the<br>&gt; variable &quot;count&quot;, after the first Assert I have ad=
ded below:<br>&gt; ...<br>&gt; Rerunning the regress tests shows that count=
 &gt;=3D 3 occurs very infrequently.<br>&gt; ...<br>&gt; Can we add more co=
mplex queries (more count &gt;=3D 3) to check if the<br>&gt; &quot;count&qu=
ot; variable is working correctly?<br><br>The &quot;count&quot; semantics w=
ill read more cleanly once the absorption<br>README work above lands (count=
s[d] =3D iteration count at nesting<br>depth d). For coverage I&#39;ll add =
a nested reluctant quantifier to<br>rpr_nfa (e.g., PATTERN ((A B){3,5}? C))=
 to drive count through the<br>3..5 band repeatedly. (rpr_nfa is the suite =
that already targets<br>Quantifier Runtime Behavior and Absorption Optimiza=
tion.)<br><br><br>&gt; In function nfa_add_state_unique:<br>&gt; =C2=A0 =C2=
=A0 /* Mark VAR in visited before duplicate check to prevent DFS loops */<b=
r>&gt; =C2=A0 =C2=A0 ...<br>&gt; I honestly don&#39;t understand the purpos=
e of the code block above. But it doesn&#39;t<br>&gt; seem to influence the=
 subsequent FOR LOOP;<br>&gt; ...<br>&gt; Could we add some comments explai=
ning which external functions rely on<br>&gt; this code and why it belongs =
in nfa_add_state_unique?<br><br>The code is correct, but the contract is sp=
lit across two functions<br>and currently only one side points to the other=
. The visited marking<br>scheme is asymmetric on purpose:<br><br>=C2=A0 - N=
on-VAR elements (END/ALT/BEGIN/FIN) are marked on entry to<br>=C2=A0 =C2=A0=
 nfa_advance_state because epsilon cycles must be prevented<br>=C2=A0 =C2=
=A0 immediately.<br>=C2=A0 - VAR elements are marked later, in nfa_add_stat=
e_unique, only<br>=C2=A0 =C2=A0 when added to the state list. That delay is=
 intentional: it<br>=C2=A0 =C2=A0 keeps legitimate quantifier loop-back to =
the same VAR across<br>=C2=A0 =C2=A0 iterations possible.<br><br>The paired=
 cycle check sits in nfa_advance_state, and the<br>asymmetric-marking ratio=
nale is documented there. What&#39;s missing is<br>the back-reference from =
nfa_add_state_unique. I&#39;ll add a single line<br>at the marking site poi=
nting back to nfa_advance_state.<br><br><br>&gt; nfa_states_equal<br>&gt; c=
ompareDepth =3D elem-&gt;depth + 1; /* depth 0 needs 1 count, etc. */<br>&g=
t; The comment above isn&#39;t helpful, IMHO, and I don&#39;t understand it=
.<br>&gt; We should focus on why compareDepth should be ```elem-&gt;depth +=
 1```.<br><br>Agree the trailing comment is too terse. Two pieces are missi=
ng:<br><br>=C2=A0 (a) The +1 arithmetic: to compare counts up to depth N, w=
e need<br>=C2=A0 =C2=A0 =C2=A0 slots counts[0..N], which is N+1 entries.<br=
>=C2=A0 (b) Why deeper slots are excluded: counts[d &gt; elem-&gt;depth] ar=
e<br>=C2=A0 =C2=A0 =C2=A0 scratch state from deeper groups and get reset on=
 re-entry,<br>=C2=A0 =C2=A0 =C2=A0 so they must not participate in equivale=
nce judgment.<br><br>Two states sharing elemIdx are equivalent iff all<br>e=
nclosing-or-current depth counts match. I&#39;ll replace the trailing<br>co=
mment with a small block covering both pieces.<br><br><br>&gt; function nfa=
_add_state_unique return value is not being used?<br>&gt; Do we need to do =
something with the return value, or is this expected?<br>&gt; (I don&#39;t =
have an opinion on it, I guess it would be better to raise this issue)<br><=
br>Leftover from an earlier design -- the duplicate case is fully<br>handle=
d inside the function (the state is freed and nfaStatesMerged<br>is increme=
nted), so callers have nothing to branch on, and indeed<br>none of them do.=
 Will change the signature from bool to void and<br>drop the return stateme=
nts.<br><br><br>&gt; In nfa_advance_alt, during the main WHILE loop, I thin=
k altElem-&gt;depth<br>&gt; must be larger than elem-&gt;depth.<br>&gt; The=
refore we can do<br>&gt; ``````<br>&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 if (alt=
Elem-&gt;depth =3D=3D elem-&gt;depth)<br>&gt; =C2=A0 =C2=A0 =C2=A0 =C2=A0 =
=C2=A0 =C2=A0 elog(ERROR, &quot;nfa_advance_alt altElem-&gt;depth should no=
t be<br>&gt; the same as elem-&gt;depth reached&quot;);<br>&gt; =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 if (altElem-&gt;depth &lt; elem-&gt;depth)<br>&gt; =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 break;<br>&gt; ``````<br><br>I had to p=
ush back on this one. Tracing the depth bookkeeping:<br><br>=C2=A0 - For an=
 ALT at depth D, branches sit at depth D+1, and each<br>=C2=A0 =C2=A0 branc=
h&#39;s first element has .jump pointing to the next branch&#39;s<br>=C2=A0=
 =C2=A0 first (set in fillRPRPatternAlt). So the walk normally<br>=C2=A0 =
=C2=A0 terminates when the last branch&#39;s .jump =3D INVALID -- the depth=
<br>=C2=A0 =C2=A0 check doesn&#39;t fire at all.<br>=C2=A0 - But when the l=
ast branch is a quantified group, its first<br>=C2=A0 =C2=A0 element is a B=
EGIN whose .jump =3D past-END (set by<br>=C2=A0 =C2=A0 fillRPRPatternGroup =
and not overridden for the last branch).<br>=C2=A0 =C2=A0 The walk then ste=
ps to a post-ALT element, and the depth check<br>=C2=A0 =C2=A0 is what stop=
s it from creating a stray state out there.<br><br>That post-ALT element ha=
s depth &lt;=3D D:<br><br>=C2=A0 * D-1 if the ALT is inside an enclosing gr=
oup with a non-trivial<br>=C2=A0 =C2=A0 quantifier, e.g., PATTERN ((A | (B =
C)+){2}) -- post-ALT lands<br>=C2=A0 =C2=A0 on the outer END at depth 0, AL=
T at depth 1. (A {1,1} outer<br>=C2=A0 =C2=A0 wrap gets removed by single-c=
hild unwrap, so it has to be a<br>=C2=A0 =C2=A0 real quantifier.)<br>=C2=A0=
 * D if the ALT has a sibling at the same level, e.g.,<br>=C2=A0 =C2=A0 PAT=
TERN (A | (B C)+) at top level -- post-ALT is FIN at depth 0,<br>=C2=A0 =C2=
=A0 matching the ALT&#39;s depth 0.<br><br>So &quot;altElem-&gt;depth =3D=
=3D elem-&gt;depth&quot; is a legitimate end-of-walk<br>signal for the quan=
tified-group-last-branch case, not an invariant<br>violation. Treating it a=
s an error would misfire on patterns like<br>A | (B C)+. The current &quot;=
if (altElem-&gt;depth &lt;=3D elem-&gt;depth) break;&quot;<br>in nfa_advanc=
e_alt is intentionally &lt;=3D and not &lt;, and the looser<br>comparison i=
s correct. Happy to add a brief comment there noting<br>the trigger conditi=
on, if it would help future readers.<br><br><br>Summary of decisions, in th=
e order above:<br><br>=C2=A0 Short-circuit optimization =C2=A0 =C2=A0 =C2=
=A0 Separate series -- invite you to drive<br>=C2=A0 Absorption README narr=
ative =C2=A0 =C2=A0 =C2=A0Accept -- Chapter VIII summary + example<br>=C2=
=A0 AST-level &quot;absorption&quot; rename =C2=A0 =C2=A0Pending Tatsuo&#39=
;s call -- prefix/suffix merging?<br>=C2=A0 DFS expansion =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Accept<br>=C2=A0 initia=
lAdvance README mismatch =C2=A0 Accept -- align with current signature<br>=
=C2=A0 Defensive Assert in advance_var =C2=A0Accept -- also add lower bound=
<br>=C2=A0 Finalize unnecessary? =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0K=
eep -- partition-end policy holder<br>=C2=A0 Greedy comment label =C2=A0 =
=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Accept -- rewrite to cover both cases<br=
>=C2=A0 state-&gt;next reset =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0Decline -- boundary contract covers it<br>=C2=A0 count &gt;=3D 3 =
test coverage =C2=A0 =C2=A0 =C2=A0 =C2=A0 Accept -- add to rpr_nfa<br>=C2=
=A0 visited marking purpose =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Accept -- add=
 back-reference comment<br>=C2=A0 compareDepth comment =C2=A0 =C2=A0 =C2=A0=
 =C2=A0 =C2=A0 =C2=A0 Accept -- rewrite with intent<br>=C2=A0 Unused bool r=
eturn =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Accept -- change to =
void<br>=C2=A0 ALT depth invariant Assert =C2=A0 =C2=A0 =C2=A0 Decline -- e=
nd-of-walk signal, not invariant<br><br>That&#39;s the full pass. The actua=
l patches (nocfbot-0016 onward) will<br>follow shortly as a separate submis=
sion, for another review round.<br><br><br>Thanks,<br>Henson<br></div>

--000000000000758c4c0652c62e2a--