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>
 <CAAAe_zDephfiDA_A3FN0hCymJRogEr=Rt3QoCTf4qMYDLk+xNA@mail.gmail.com>
 <CACJufxGX17thWuEOq1tM5xbRHz2HXm1asooZC3GV25MYGmYqLQ@mail.gmail.com>
 <CAAAe_zAH0MvP0TBmW3PTLeHjEpiyBz0473zJRM9pwLpseefMNw@mail.gmail.com>
 <CACJufxEsaU8GQ4yeXTWhAO8VjbrZTh5CpvUqz=4a3T0Cwz44pA@mail.gmail.com>
In-Reply-To: 
 <CACJufxEsaU8GQ4yeXTWhAO8VjbrZTh5CpvUqz=4a3T0Cwz44pA@mail.gmail.com>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Sat, 30 May 2026 22:45:39 +0900
Message-ID: 
 <CAAAe_zBi1dOtWb2vnwSvGwuU0-bqAOm_7dOM4u-CmukA8xaV5Q@mail.gmail.com>
Subject: Re: Row pattern recognition
To: jian he <jian.universality@gmail.com>
Cc: Tatsuo Ishii <ishii@postgresql.org>, 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="000000000000f84b010653092df1"
Archived-At: 
 <https://www.postgresql.org/message-id/CAAAe_zBi1dOtWb2vnwSvGwuU0-bqAOm_7dOM4u-CmukA8xaV5Q%40mail.gmail.com>
Precedence: bulk

--000000000000f84b010653092df1
Content-Type: text/plain; charset="UTF-8"

[mailing-list reply draft -- pgsql-hackers, RPR thread.
 In-reply-to Jian's round-3 review, 2026-05-30 06:45
 (Message-ID CACJufxEsaU8GQ4yeXTWhAO8VjbrZTh5CpvUqz=
4a3T0Cwz44pA@mail.gmail.com).
 Covers R3-1..R3-4 (comments) and the three attached refactors R3-5a/b/c.
 All accepted; fold into the v48 refactor series.]

Subject: Re: Row pattern recognition

Hi Jian,

Thanks for the round-3 pass -- all seven are good catches. Going through
them inline below, with a summary of decisions at the end.

> Comments like "Tests line 251" should not appear in SQL, since the
> line number would change.
> So, we need to rephrase this comment. Please don't delete it, it may
> clarify the patch for future readers.

Agreed on both counts -- the intent (this case exercises the
child->max == RPR_QUANTITY_INF branch in mergeConsecutiveVars, where a
finite prev meets an infinite child) is worth keeping; only the "line 251"
anchor is fragile. I'll rephrase it to name the branch and the condition
it covers instead of the line, so it survives any later shuffle.

There's a parallel one a few tests down -- "Tests line 325 ... in
mergeConsecutiveGroups" -- with the same problem, so I'll fix both
together on the same principle.

> The "at the END" confuses me. It may also refers to RPR_VARID_END /
> RPRElemIsEnd.
> How about something like:
> "Add the state to the end of the ctx->states linked list, but only if
> a duplicate state is not already present."

Your wording is clearer than mine -- I'll take it almost verbatim. "at the
END" there meant the list tail, and capitalizing it was exactly the wrong
choice next to the END element kind.

> I think a bunch of these uppercase ENDs should just be lowercase "end",
> [...]
> Could we lowercase the list-end ones and keep uppercase only when actually
> referring to the END element kind?

Yes -- that's the right rule, and I'll go through them on it: lowercase
"end" for the linked-list tail, uppercase END only when it means the
element kind (RPRElemIsEnd / RPR_VARID_END). On the two you singled out:

  - nfa_match, "Non-VAR elements (ALT, END, FIN) ..." -- element kind,
    listed with the others, stays uppercase. Agreed.

  - "advance through END chain inline ..." -- this one is actually the
    element kind too: it walks the chain of group-END *elements* up to the
    absorption judgment point, not the state list. So it stays uppercase,
    but since it tripped you up I'll reword it to "chain of END elements"
    to make that unambiguous rather than leaning on the reader to infer it.

> The comment under nfa_advance_var is confusing (for me).
> /* After a successful match, count >= 1, so at least one must be true */
> nfa_advance_var doesn't actually know anything about match status (i
> think), it can be reached with count == 0.
> [...] and it does fire, so the comment's premise isn't quite right.

You're right, and thanks for confirming it with the elog. nfa_advance_var
is part of the advance phase, which generates every reachable next state
regardless of what matched -- so it's routinely entered with count == 0,
for a VAR just reached through an ALT branch or a group that hasn't been
evaluated yet. The comment carries match-phase reasoning into a phase that
has no notion of matching. The Assert above still holds, but on the
structure of a VAR's bounds, not on any prior match, so I'll reword the
comment to say that instead.

> please check the attached minor refactoring.
> 1.  Refactor struct WindowAggState: Remove the nfaStateSize and
>     nfaVisitedNWords fields because they are constant, and we can easily
>     compute it, [...] not necessary to stay in WindowAggState.
> 2. Rename nfa_context_alloc() to nfa_context_make(), nfa_state_alloc()
>    to nfa_state_make(), nfa_state_create() to nfa_state_clone().
>    Rationale: We have makeNode [...]. In tablecmd.c, we have
>    CloneForeignKeyConstraints, which is based on existing information,
>    creating a new node, here we are doing the same in nfa_state_create.
> 3. Refactor functions: nfa_advance_alt, nfa_advance_begin,
>    nfa_advance_end, and nfa_advance_var. Because the
>    (RPRPatternElement *elem) parameter is unnecessary.

Looked at all three. 0002 and 0003 I'll take; 0001 I'd split.

  1. The two fields differ. nfaVisitedNWords -- yes: in the current tree
     it's read only once, at init, to size the visited bitmap, since the
     per-row reset clears just the high-water [min,max] range. Demoting it
     to a local is clean. (Heads up: the patch is on v47, before that
     high-water-mark change, so its nfa_advance hunk no longer applies and
     drops out on rebase.)

     nfaStateSize I'd keep. The patch recomputes it inside the allocator,
     i.e. on every state allocation -- the hottest path in the engine; a
     pathological (V1|...|Vk)* can allocate hundreds of millions of states.
     It's a loop-invariant fixed at init, so I'd rather keep it precomputed
     than rebuild offsetof + maxDepth*4 each alloc -- the same reasoning I
     gave for keeping the frame offsets out of the per-row loop.

  2. make/clone: agreed, and there's a closer precedent than I'd have
     reached for -- our own regex NFA engine already clones states
     (clonesuccessorstates / cloneouts in regcomp.c), so clone is the right
     word for duplicating an NFA state, not just the CloneForeignKey sense.
     The pair reads well too: make for the blank allocation, clone for
     building a state from an existing one's counts. (create was itself an
     earlier rename of mine from clone "for clarity," so this just lands us
     back on clone, which I now agree is better.) When I apply it I'll also
     tidy two comments the rename left behind -- the nfa_state_make header
     now reads "a new RPRNFAState state," and nfa_state_clone's body comment
     still says "Create."

  3. elem parameter: here I'd keep it, on the same grounds as nfaStateSize.
     The four functions have a single caller, nfa_advance_state, which
     already computes elem = &elements[state->elemIdx] for its own
     mark-visited check and switch, and hands it down. Dropping the
     parameter makes each function rebuild that same address on the
     per-dispatch advance path -- discarding a value the caller already
     holds. And with one trusted caller, the mismatch the change guards
     against can't really arise. The cost either way is tiny; I'd just
     rather keep the value flowing from where it's already computed than
     recompute it, which is the same call I made on nfaStateSize.

Summary of decisions, in the order above:

  "Tests line N" test comments     Rephrase -- name the branch, not the
line (both)
  "at the END" wording             Accept -- your wording, near-verbatim
  uppercase END cleanup            Accept -- lowercase the list-end ones,
keep the kind
  nfa_advance_var count comment    Reword -- wrong premise; state the
structural reason
  0001 nfaVisitedNWords            Accept -- demote to a local
  0001 nfaStateSize                Keep -- hottest path; leave it
precomputed
  0002 make / clone rename         Accept -- plus tidy two stray comments
  0003 drop the elem parameter     Keep -- single caller already holds it

So the next revision carries the four comment fixes, 0002, and the
nfaVisitedNWords half of 0001; nfaStateSize and the elem parameter I'd keep
as they are. Happy to be talked round on either if you see a cost I'm
missing.

Thanks again,
Henson

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

<div dir=3D"ltr">[mailing-list reply draft -- pgsql-hackers, RPR thread.<br=
>=C2=A0In-reply-to Jian&#39;s round-3 review, 2026-05-30 06:45<br>=C2=A0(Me=
ssage-ID CACJufxEsaU8GQ4yeXTWhAO8VjbrZTh5CpvUqz=3D<a href=3D"mailto:4a3T0Cw=
z44pA@mail.gmail.com">4a3T0Cwz44pA@mail.gmail.com</a>).<br>=C2=A0Covers R3-=
1..R3-4 (comments) and the three attached refactors R3-5a/b/c.<br>=C2=A0All=
 accepted; fold into the v48 refactor series.]<br><br>Subject: Re: Row patt=
ern recognition<br><br>Hi Jian,<br><br>Thanks for the round-3 pass -- all s=
even are good catches. Going through<br>them inline below, with a summary o=
f decisions at the end.<br><br>&gt; Comments like &quot;Tests line 251&quot=
; should not appear in SQL, since the<br>&gt; line number would change.<br>=
&gt; So, we need to rephrase this comment. Please don&#39;t delete it, it m=
ay<br>&gt; clarify the patch for future readers.<br><br>Agreed on both coun=
ts -- the intent (this case exercises the<br>child-&gt;max =3D=3D RPR_QUANT=
ITY_INF branch in mergeConsecutiveVars, where a<br>finite prev meets an inf=
inite child) is worth keeping; only the &quot;line 251&quot;<br>anchor is f=
ragile. I&#39;ll rephrase it to name the branch and the condition<br>it cov=
ers instead of the line, so it survives any later shuffle.<br><br>There&#39=
;s a parallel one a few tests down -- &quot;Tests line 325 ... in<br>mergeC=
onsecutiveGroups&quot; -- with the same problem, so I&#39;ll fix both<br>to=
gether on the same principle.<br><br>&gt; The &quot;at the END&quot; confus=
es me. It may also refers to RPR_VARID_END /<br>&gt; RPRElemIsEnd.<br>&gt; =
How about something like:<br>&gt; &quot;Add the state to the end of the ctx=
-&gt;states linked list, but only if<br>&gt; a duplicate state is not alrea=
dy present.&quot;<br><br>Your wording is clearer than mine -- I&#39;ll take=
 it almost verbatim. &quot;at the<br>END&quot; there meant the list tail, a=
nd capitalizing it was exactly the wrong<br>choice next to the END element =
kind.<br><br>&gt; I think a bunch of these uppercase ENDs should just be lo=
wercase &quot;end&quot;,<br>&gt; [...]<br>&gt; Could we lowercase the list-=
end ones and keep uppercase only when actually<br>&gt; referring to the END=
 element kind?<br><br>Yes -- that&#39;s the right rule, and I&#39;ll go thr=
ough them on it: lowercase<br>&quot;end&quot; for the linked-list tail, upp=
ercase END only when it means the<br>element kind (RPRElemIsEnd / RPR_VARID=
_END). On the two you singled out:<br><br>=C2=A0 - nfa_match, &quot;Non-VAR=
 elements (ALT, END, FIN) ...&quot; -- element kind,<br>=C2=A0 =C2=A0 liste=
d with the others, stays uppercase. Agreed.<br><br>=C2=A0 - &quot;advance t=
hrough END chain inline ...&quot; -- this one is actually the<br>=C2=A0 =C2=
=A0 element kind too: it walks the chain of group-END *elements* up to the<=
br>=C2=A0 =C2=A0 absorption judgment point, not the state list. So it stays=
 uppercase,<br>=C2=A0 =C2=A0 but since it tripped you up I&#39;ll reword it=
 to &quot;chain of END elements&quot;<br>=C2=A0 =C2=A0 to make that unambig=
uous rather than leaning on the reader to infer it.<br><br>&gt; The comment=
 under nfa_advance_var is confusing (for me).<br>&gt; /* After a successful=
 match, count &gt;=3D 1, so at least one must be true */<br>&gt; nfa_advanc=
e_var doesn&#39;t actually know anything about match status (i<br>&gt; thin=
k), it can be reached with count =3D=3D 0.<br>&gt; [...] and it does fire, =
so the comment&#39;s premise isn&#39;t quite right.<br><br>You&#39;re right=
, and thanks for confirming it with the elog. nfa_advance_var<br>is part of=
 the advance phase, which generates every reachable next state<br>regardles=
s of what matched -- so it&#39;s routinely entered with count =3D=3D 0,<br>=
for a VAR just reached through an ALT branch or a group that hasn&#39;t bee=
n<br>evaluated yet. The comment carries match-phase reasoning into a phase =
that<br>has no notion of matching. The Assert above still holds, but on the=
<br>structure of a VAR&#39;s bounds, not on any prior match, so I&#39;ll re=
word the<br>comment to say that instead.<br><br>&gt; please check the attac=
hed minor refactoring.<br>&gt; 1.=C2=A0 Refactor struct WindowAggState: Rem=
ove the nfaStateSize and<br>&gt; =C2=A0 =C2=A0 nfaVisitedNWords fields beca=
use they are constant, and we can easily<br>&gt; =C2=A0 =C2=A0 compute it, =
[...] not necessary to stay in WindowAggState.<br>&gt; 2. Rename nfa_contex=
t_alloc() to nfa_context_make(), nfa_state_alloc()<br>&gt; =C2=A0 =C2=A0to =
nfa_state_make(), nfa_state_create() to nfa_state_clone().<br>&gt; =C2=A0 =
=C2=A0Rationale: We have makeNode [...]. In tablecmd.c, we have<br>&gt; =C2=
=A0 =C2=A0CloneForeignKeyConstraints, which is based on existing informatio=
n,<br>&gt; =C2=A0 =C2=A0creating a new node, here we are doing the same in =
nfa_state_create.<br>&gt; 3. Refactor functions: nfa_advance_alt, nfa_advan=
ce_begin,<br>&gt; =C2=A0 =C2=A0nfa_advance_end, and nfa_advance_var. Becaus=
e the<br>&gt; =C2=A0 =C2=A0(RPRPatternElement *elem) parameter is unnecessa=
ry.<br><br>Looked at all three. 0002 and 0003 I&#39;ll take; 0001 I&#39;d s=
plit.<br><br>=C2=A0 1. The two fields differ. nfaVisitedNWords -- yes: in t=
he current tree<br>=C2=A0 =C2=A0 =C2=A0it&#39;s read only once, at init, to=
 size the visited bitmap, since the<br>=C2=A0 =C2=A0 =C2=A0per-row reset cl=
ears just the high-water [min,max] range. Demoting it<br>=C2=A0 =C2=A0 =C2=
=A0to a local is clean. (Heads up: the patch is on v47, before that<br>=C2=
=A0 =C2=A0 =C2=A0high-water-mark change, so its nfa_advance hunk no longer =
applies and<br>=C2=A0 =C2=A0 =C2=A0drops out on rebase.)<br><br>=C2=A0 =C2=
=A0 =C2=A0nfaStateSize I&#39;d keep. The patch recomputes it inside the all=
ocator,<br>=C2=A0 =C2=A0 =C2=A0i.e. on every state allocation -- the hottes=
t path in the engine; a<br>=C2=A0 =C2=A0 =C2=A0pathological (V1|...|Vk)* ca=
n allocate hundreds of millions of states.<br>=C2=A0 =C2=A0 =C2=A0It&#39;s =
a loop-invariant fixed at init, so I&#39;d rather keep it precomputed<br>=
=C2=A0 =C2=A0 =C2=A0than rebuild offsetof + maxDepth*4 each alloc -- the sa=
me reasoning I<br>=C2=A0 =C2=A0 =C2=A0gave for keeping the frame offsets ou=
t of the per-row loop.<br><br>=C2=A0 2. make/clone: agreed, and there&#39;s=
 a closer precedent than I&#39;d have<br>=C2=A0 =C2=A0 =C2=A0reached for --=
 our own regex NFA engine already clones states<br>=C2=A0 =C2=A0 =C2=A0(clo=
nesuccessorstates / cloneouts in regcomp.c), so clone is the right<br>=C2=
=A0 =C2=A0 =C2=A0word for duplicating an NFA state, not just the CloneForei=
gnKey sense.<br>=C2=A0 =C2=A0 =C2=A0The pair reads well too: make for the b=
lank allocation, clone for<br>=C2=A0 =C2=A0 =C2=A0building a state from an =
existing one&#39;s counts. (create was itself an<br>=C2=A0 =C2=A0 =C2=A0ear=
lier rename of mine from clone &quot;for clarity,&quot; so this just lands =
us<br>=C2=A0 =C2=A0 =C2=A0back on clone, which I now agree is better.) When=
 I apply it I&#39;ll also<br>=C2=A0 =C2=A0 =C2=A0tidy two comments the rena=
me left behind -- the nfa_state_make header<br>=C2=A0 =C2=A0 =C2=A0now read=
s &quot;a new RPRNFAState state,&quot; and nfa_state_clone&#39;s body comme=
nt<br>=C2=A0 =C2=A0 =C2=A0still says &quot;Create.&quot;<br><br>=C2=A0 3. e=
lem parameter: here I&#39;d keep it, on the same grounds as nfaStateSize.<b=
r>=C2=A0 =C2=A0 =C2=A0The four functions have a single caller, nfa_advance_=
state, which<br>=C2=A0 =C2=A0 =C2=A0already computes elem =3D &amp;elements=
[state-&gt;elemIdx] for its own<br>=C2=A0 =C2=A0 =C2=A0mark-visited check a=
nd switch, and hands it down. Dropping the<br>=C2=A0 =C2=A0 =C2=A0parameter=
 makes each function rebuild that same address on the<br>=C2=A0 =C2=A0 =C2=
=A0per-dispatch advance path -- discarding a value the caller already<br>=
=C2=A0 =C2=A0 =C2=A0holds. And with one trusted caller, the mismatch the ch=
ange guards<br>=C2=A0 =C2=A0 =C2=A0against can&#39;t really arise. The cost=
 either way is tiny; I&#39;d just<br>=C2=A0 =C2=A0 =C2=A0rather keep the va=
lue flowing from where it&#39;s already computed than<br>=C2=A0 =C2=A0 =C2=
=A0recompute it, which is the same call I made on nfaStateSize.<br><br>Summ=
ary of decisions, in the order above:<br><br><font face=3D"monospace">=C2=
=A0 &quot;Tests line N&quot; test comments =C2=A0 =C2=A0 Rephrase -- name t=
he branch, not the line (both)<br>=C2=A0 &quot;at the END&quot; wording =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 Accept -- your wording, near-verbati=
m<br>=C2=A0 uppercase END cleanup =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
Accept -- lowercase the list-end ones, keep the kind<br>=C2=A0 nfa_advance_=
var count comment =C2=A0 =C2=A0Reword -- wrong premise; state the structura=
l reason<br>=C2=A0 0001 nfaVisitedNWords =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 =C2=A0Accept -- demote to a local<br>=C2=A0 0001 nfaStateSize =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=A0Keep -- hottest path; leave it=
 precomputed<br>=C2=A0 0002 make / clone rename =C2=A0 =C2=A0 =C2=A0 =C2=A0=
 Accept -- plus tidy two stray comments<br>=C2=A0 0003 drop the elem parame=
ter =C2=A0 =C2=A0 Keep -- single caller already holds it</font><br><br>So t=
he next revision carries the four comment fixes, 0002, and the<br>nfaVisite=
dNWords half of 0001; nfaStateSize and the elem parameter I&#39;d keep<br>a=
s they are. Happy to be talked round on either if you see a cost I&#39;m<br=
>missing.<br><br>Thanks again,<br>Henson<br></div>

--000000000000f84b010653092df1--