MIME-Version: 1.0
References: <CAAAe_zA=BDm=e04aNFYe3Az0CzPipK+HHzu1KGHiLOg+r_z8XQ@mail.gmail.com>
 <20260205.102519.1298921431937419793.ishii@postgresql.org>
 <CAAAe_zDKsfzrLwvrMTwdHwzq9v38g3Tn1UC=excb0RFntqqh3w@mail.gmail.com> <20260207.133143.1951390390459539453.ishii@postgresql.org>
In-Reply-To: <20260207.133143.1951390390459539453.ishii@postgresql.org>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Sat, 7 Feb 2026 14:41:26 +0900
Message-ID: <CAAAe_zDoO47FzUBHQU-0CgYD63boZNi-BJSG5Q87Jr5w5bGcdw@mail.gmail.com>
Subject: Re: Row pattern recognition
To: Tatsuo Ishii <ishii@postgresql.org>
Cc: jacob.champion@enterprisedb.com, david.g.johnston@gmail.com, 
	vik@postgresfriends.org, er@xs4all.nl, peter@eisentraut.org, 
	pgsql-hackers@postgresql.org
Content-Type: multipart/alternative; boundary="00000000000038c24e064a355c84"
Archived-At: <https://www.postgresql.org/message-id/CAAAe_zDoO47FzUBHQU-0CgYD63boZNi-BJSG5Q87Jr5w5bGcdw%40mail.gmail.com>
Precedence: bulk

--00000000000038c24e064a355c84
Content-Type: text/plain; charset="UTF-8"

Hi Tatsuo,

+-- Filter function to normalize Storage memory values only (not NFA
> statistics)
> +-- Works for text, JSON, and XML formats
>
> What about add reasoning why only storage memory values are normalized
> something like:
>
> -- NFA statistics should not change between platforms.


Done. I've updated the comment to:

-- Filter function to normalize Storage memory values only (not NFA
statistics).
-- NFA statistics should not change between platforms; if they do, it could
-- indicate issues such as uninitialized memory access.
-- Works for text, JSON, and XML formats.

This round focused primarily on reviewing explain.c.  I believe we're
getting close to the final version now.  Only the nodeWindowAgg.c
code review remains on my side.

For the next submission, would it be helpful if I resend all the
incremental patches I've already sent since v42 together as separate
per-patch files?

I've also made some updates to the documentation (advanced.sgml and
ref/select.sgml).  Could you take a look and let me know if there are
any mistakes or if the changes look good to you?

I've sent several incremental patches on top of v42, and the attached
patch is the next one in that series.  Here are the changes:

Bugs fixed:

- Fix server crash in fillRPRPatternAlt() when an inner ALT is the
  last element of an outer ALT's branch.  Both alternations tried to
  set the 'next' pointer on the same endpoint element, triggering
  Assert(pat->elements[endPos].next == RPR_ELEMIDX_INVALID).  Fix by
  redirecting all elements in the branch that share the old target to
  point to the outer ALT's afterAlt instead.
  (Test: PATTERN (C (A | B) | D) -- inner ALT at end of outer branch)

- Add BEGIN element to fillRPRPatternGroup().  Previously only END was
  emitted for quantified groups, so groups with min=0 had no skip path
  to bypass the group content.  Change to BEGIN/END pairs where
  BEGIN.jump points past END (skip) and END.jump points to the first
  child (loop-back).  Add nfa_advance_begin() to the NFA executor for
  group entry and skip handling.
  (Test: PATTERN (A ((B | C) (D | E))* F?) -- * group matching 0 times)

- Fix deparse output producing wrong parenthesization for nested ALT
  patterns.  The flat-loop approach could not correctly suppress double
  parentheses for single-ALT groups or handle depth transitions around
  alternation separators.  Refactor into mutual recursion:
  deparse_rpr_elements, deparse_rpr_group, deparse_rpr_alt, and
  deparse_rpr_var.

- Fix deparse separator ordering for nested ALT: the ' | ' separator
  was emitted before closing inner parentheses, producing output like
  '(c (a | b | )d)' instead of '(c (a | b) | d)'.  Close parens to
  match separator depth before emitting ' | '.

- Fix missing ALT separator registration in deparse_rpr_alt() when an
  ALT is the first element of an outer ALT's branch.  The code only
  checked elem->next (always -1 for ALT markers) but not elem->jump,
  which carries the outer branch's separator position.

- Fix altEndPositions/altBranchStarts length mismatch caused by the
  'if (*idx > branchStart)' guard that skipped empty branches.  Remove
  the guard so both lists always have matching entries.

- Fix RPRPatternNode.reluctant initialization in gram.y.  ALT, SEQ,
  VAR, and GROUP primary productions used false (0) or left it
  uninitialized (defaulting to 0 from palloc0), but 0 is a valid
  ParseLoc meaning "location at offset 0".  Change all four creation
  sites to use -1 (no location), matching the convention used by
  ParseLoc throughout the parser.

- Fix reluctant quantifier display in both explain.c and ruleutils.c.
  A bare variable with reluctant ? (e.g. A?) was displayed as just 'a'
  since there was no quantifier to attach ? to.  Now emit '{1}?' to
  make the reluctant marker unambiguous.

New optimization:

- Add mergeConsecutiveAlts() to the SEQ optimization pipeline.  After
  GROUP{1,1} unwrap, bare alternations like (A | B) become ALT nodes
  in the SEQ.  This step detects consecutive identical ALT nodes and
  wraps them in a GROUP with the appropriate quantifier, e.g.
  (A | B) (A | B) (A | B) -> (A | B){3}.  Combined with the existing
  mergeGroupPrefixSuffix, patterns like (A | B) (A | B)+ (A | B)
  further reduce to (A | B){3,}.

- Extend tryMultiplyQuantifiers() to fold nested GROUP quantifiers
  (e.g. ((A B)+)* -> (A B)*) in addition to VAR quantifiers.

Other changes:

- Add RPR_VARID_BEGIN (252) to rpr.h for the new control element type.
  Reduce RPR_VARID_MAX from 252 to 251 accordingly and update the
  maximum-variables boundary tests.

- Add RPR_DEPTH_NONE (255) as sentinel for top-level elements that
  have no enclosing group.  Reduce RPR_DEPTH_MAX to 254 accordingly.

- Add BEGIN handling to computeAbsorbabilityRecursive() so that
  absorbability flags propagate correctly through group boundaries.

- Extract show_rpr_nfa_stats() from show_windowagg_info() for NFA
  statistics display.

- Replace defensive NULL check in collectPatternVariables() with
  Assert, since the caller guarantees a non-NULL pattern.

- Pair each EXPLAIN test query in rpr_explain.sql with a
  pg_get_viewdef() check via CREATE TEMP VIEW, verifying that both
  the ruleutils (parse tree) and explain (bytecode) deparse paths
  produce consistent PATTERN output.

- Add comment to rpr_explain_filter() explaining why only Storage
  memory values are normalized: NFA statistics should not change
  between platforms, and variation would indicate issues such as
  uninitialized memory access.

Also add EXPLAIN test cases for nested ALT patterns, consecutive ALT
merging, and ALT prefix/suffix merging.

On a side note, I feel that the automata characteristics of RPR --
state transitions, context management, absorbability, etc. -- tend to
require a much larger volume of test cases than typical RDBMS/SQL
features.  This seems unavoidable given the combinatorial nature of
NFA execution.

Best regards,
Henson

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

<div dir=3D"ltr"><div dir=3D"ltr">Hi Tatsuo,</div><div dir=3D"ltr"><br></di=
v><div class=3D"gmail_quote gmail_quote_container"><blockquote class=3D"gma=
il_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;border-le=
ft-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">
+-- Filter function to normalize Storage memory values only (not NFA statis=
tics)<br>
+-- Works for text, JSON, and XML formats<br>
<br>
What about add reasoning why only storage memory values are normalized<br>
something like:<br>
<br>
-- NFA statistics should not change between platforms.</blockquote><div><br=
></div>Done. I&#39;ve updated the comment to:<br><br>-- Filter function to =
normalize Storage memory values only (not NFA statistics).<br>-- NFA statis=
tics should not change between platforms; if they do, it could<br>-- indica=
te issues such as uninitialized memory access.<br>-- Works for text, JSON, =
and XML formats.<br><br>This round focused primarily on reviewing explain.c=
.=C2=A0 I believe we&#39;re<br>getting close to the final version now.=C2=
=A0 Only the nodeWindowAgg.c<br>code review remains on my side.<br><br>For =
the next submission, would it be helpful if I resend all the<br>incremental=
 patches I&#39;ve already sent since v42 together as separate<br>per-patch =
files?<br><br>I&#39;ve also made some updates to the documentation (advance=
d.sgml and<br>ref/select.sgml).=C2=A0 Could you take a look and let me know=
 if there are<br>any mistakes or if the changes look good to you?<br><br>I&=
#39;ve sent several incremental patches on top of v42, and the attached<br>=
patch is the next one in that series.=C2=A0 Here are the changes:<br><br>Bu=
gs fixed:<br><br>- Fix server crash in fillRPRPatternAlt() when an inner AL=
T is the<br>=C2=A0 last element of an outer ALT&#39;s branch.=C2=A0 Both al=
ternations tried to<br>=C2=A0 set the &#39;next&#39; pointer on the same en=
dpoint element, triggering<br>=C2=A0 Assert(pat-&gt;elements[endPos].next =
=3D=3D RPR_ELEMIDX_INVALID).=C2=A0 Fix by<br>=C2=A0 redirecting all element=
s in the branch that share the old target to<br>=C2=A0 point to the outer A=
LT&#39;s afterAlt instead.<br>=C2=A0 (Test: PATTERN (C (A | B) | D) -- inne=
r ALT at end of outer branch)<br><br>- Add BEGIN element to fillRPRPatternG=
roup().=C2=A0 Previously only END was<br>=C2=A0 emitted for quantified grou=
ps, so groups with min=3D0 had no skip path<br>=C2=A0 to bypass the group c=
ontent.=C2=A0 Change to BEGIN/END pairs where<br>=C2=A0 BEGIN.jump points p=
ast END (skip) and END.jump points to the first<br>=C2=A0 child (loop-back)=
.=C2=A0 Add nfa_advance_begin() to the NFA executor for<br>=C2=A0 group ent=
ry and skip handling.<br>=C2=A0 (Test: PATTERN (A ((B | C) (D | E))* F?) --=
 * group matching 0 times)<br><br>- Fix deparse output producing wrong pare=
nthesization for nested ALT<br>=C2=A0 patterns.=C2=A0 The flat-loop approac=
h could not correctly suppress double<br>=C2=A0 parentheses for single-ALT =
groups or handle depth transitions around<br>=C2=A0 alternation separators.=
=C2=A0 Refactor into mutual recursion:<br>=C2=A0 deparse_rpr_elements, depa=
rse_rpr_group, deparse_rpr_alt, and<br>=C2=A0 deparse_rpr_var.<br><br>- Fix=
 deparse separator ordering for nested ALT: the &#39; | &#39; separator<br>=
=C2=A0 was emitted before closing inner parentheses, producing output like<=
br>=C2=A0 &#39;(c (a | b | )d)&#39; instead of &#39;(c (a | b) | d)&#39;.=
=C2=A0 Close parens to<br>=C2=A0 match separator depth before emitting &#39=
; | &#39;.<br><br>- Fix missing ALT separator registration in deparse_rpr_a=
lt() when an<br>=C2=A0 ALT is the first element of an outer ALT&#39;s branc=
h.=C2=A0 The code only<br>=C2=A0 checked elem-&gt;next (always -1 for ALT m=
arkers) but not elem-&gt;jump,<br>=C2=A0 which carries the outer branch&#39=
;s separator position.<br><br>- Fix altEndPositions/altBranchStarts length =
mismatch caused by the<br>=C2=A0 &#39;if (*idx &gt; branchStart)&#39; guard=
 that skipped empty branches.=C2=A0 Remove<br>=C2=A0 the guard so both list=
s always have matching entries.<br><br>- Fix RPRPatternNode.reluctant initi=
alization in gram.y.=C2=A0 ALT, SEQ,<br>=C2=A0 VAR, and GROUP primary produ=
ctions used false (0) or left it<br>=C2=A0 uninitialized (defaulting to 0 f=
rom palloc0), but 0 is a valid<br>=C2=A0 ParseLoc meaning &quot;location at=
 offset 0&quot;.=C2=A0 Change all four creation<br>=C2=A0 sites to use -1 (=
no location), matching the convention used by<br>=C2=A0 ParseLoc throughout=
 the parser.<br><br>- Fix reluctant quantifier display in both explain.c an=
d ruleutils.c.<br>=C2=A0 A bare variable with reluctant ? (e.g. A?) was dis=
played as just &#39;a&#39;<br>=C2=A0 since there was no quantifier to attac=
h ? to.=C2=A0 Now emit &#39;{1}?&#39; to<br>=C2=A0 make the reluctant marke=
r unambiguous.<br><br>New optimization:<br><br>- Add mergeConsecutiveAlts()=
 to the SEQ optimization pipeline.=C2=A0 After<br>=C2=A0 GROUP{1,1} unwrap,=
 bare alternations like (A | B) become ALT nodes<br>=C2=A0 in the SEQ.=C2=
=A0 This step detects consecutive identical ALT nodes and<br>=C2=A0 wraps t=
hem in a GROUP with the appropriate quantifier, e.g.<br>=C2=A0 (A | B) (A |=
 B) (A | B) -&gt; (A | B){3}.=C2=A0 Combined with the existing<br>=C2=A0 me=
rgeGroupPrefixSuffix, patterns like (A | B) (A | B)+ (A | B)<br>=C2=A0 furt=
her reduce to (A | B){3,}.<br><br>- Extend tryMultiplyQuantifiers() to fold=
 nested GROUP quantifiers<br>=C2=A0 (e.g. ((A B)+)* -&gt; (A B)*) in additi=
on to VAR quantifiers.<br><br>Other changes:<br><br>- Add RPR_VARID_BEGIN (=
252) to rpr.h for the new control element type.<br>=C2=A0 Reduce RPR_VARID_=
MAX from 252 to 251 accordingly and update the<br>=C2=A0 maximum-variables =
boundary tests.<br><br>- Add RPR_DEPTH_NONE (255) as sentinel for top-level=
 elements that<br>=C2=A0 have no enclosing group.=C2=A0 Reduce RPR_DEPTH_MA=
X to 254 accordingly.<br><br>- Add BEGIN handling to computeAbsorbabilityRe=
cursive() so that<br>=C2=A0 absorbability flags propagate correctly through=
 group boundaries.<br><br>- Extract show_rpr_nfa_stats() from show_windowag=
g_info() for NFA<br>=C2=A0 statistics display.<br><br>- Replace defensive N=
ULL check in collectPatternVariables() with<br>=C2=A0 Assert, since the cal=
ler guarantees a non-NULL pattern.<br><br>- Pair each EXPLAIN test query in=
 rpr_explain.sql with a<br>=C2=A0 pg_get_viewdef() check via CREATE TEMP VI=
EW, verifying that both<br>=C2=A0 the ruleutils (parse tree) and explain (b=
ytecode) deparse paths<br>=C2=A0 produce consistent PATTERN output.<br><br>=
</div><div class=3D"gmail_quote gmail_quote_container">- Add comment to rpr=
_explain_filter() explaining why only Storage<br>=C2=A0 memory values are n=
ormalized: NFA statistics should not change<br>=C2=A0 between platforms, an=
d variation would indicate issues such as<br>=C2=A0 uninitialized memory ac=
cess.<br><br>Also add EXPLAIN test cases for nested ALT patterns, consecuti=
ve ALT<br>merging, and ALT prefix/suffix merging.<br><br><div>On a side not=
e, I feel that the automata characteristics of RPR --<br>state transitions,=
 context management, absorbability, etc. -- tend to<br>require a much large=
r volume of test cases than typical RDBMS/SQL<br>features.=C2=A0 This seems=
 unavoidable given the combinatorial nature of<br>NFA execution.<br></div><=
div><br></div>Best regards,<br><div>Henson=C2=A0</div></div></div>

--00000000000038c24e064a355c84--