MIME-Version: 1.0
References: 
 <CAAAe_zCvHz=tHkggP37OoQH8R0ux4j_CJdBTiPUg-L=6cVMyWg@mail.gmail.com>
 <20260309.120802.1845076903520202301.ishii@postgresql.org>
 <CAAAe_zAn2nFgM_gfsEDYu+MXCArRFoP6s9bRz2bP4X5HNmnYww@mail.gmail.com>
 <20260309.142202.1739855502263731478.ishii@postgresql.org>
 <CAE+cgNgVWChqF-f-s4zT18V+oK1y9UOvORq9JX7jFKj4=r_taw@mail.gmail.com>
In-Reply-To: 
 <CAE+cgNgVWChqF-f-s4zT18V+oK1y9UOvORq9JX7jFKj4=r_taw@mail.gmail.com>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Wed, 11 Mar 2026 19:32:15 +0900
Message-ID: 
 <CAAAe_zBY+Eqk_DQpS0cy1Eb67H9v92tyaf+U+SKKuLGUs_z+EA@mail.gmail.com>
Subject: Re: Row pattern recognition
To: SungJun Jang <sjjang112233@gmail.com>
Cc: Tatsuo Ishii <ishii@postgresql.org>, vik@postgresfriends.org,
 er@xs4all.nl,
	jacob.champion@enterprisedb.com, david.g.johnston@gmail.com,
	peter@eisentraut.org, pgsql-hackers@postgresql.org
Content-Type: multipart/alternative; boundary="000000000000039e2a064cbd27eb"
Archived-At: 
 <https://www.postgresql.org/message-id/CAAAe_zBY%2BEqk_DQpS0cy1Eb67H9v92tyaf%2BU%2BSKKuLGUs_z%2BEA%40mail.gmail.com>
Precedence: bulk

--000000000000039e2a064cbd27eb
Content-Type: text/plain; charset="UTF-8"

Hi SungJun,

Thanks for the cross-validation report.

This appears to be due to its NFA implementation combined with Context
> Absorption,
>
which discards redundant matching contexts when they reach the same NFA
> state
>
but start later in the input.
>
> Example:
>
> Ctx1 start=0 length=2
> Ctx2 start=1 length=1
>
> Ctx1 subsumes Ctx2, so Ctx2 is discarded.
>
> This keeps the number of active contexts small and prevents quadratic
> growth.
>

Your description is accurate. An earlier-started context subsumes
all matches of a later-started context (monotonicity principle),
so the newer one can be safely removed.

However, Context Absorption is not universally applicable. It
requires careful analysis of several factors, and we continue to
refine the conditions under which absorption can be safely applied.

The current scope of absorption is determined by three factors:

1. Pattern structure:
   Currently supported:
   - Simple unbounded quantifiers: A+, (A B)+
   - Leading unbounded quantifier in group: (A+ B)+
   - First iteration of nested unbounded alternation (e.g., ((A+)|(B+))+)
   Planned improvements:
   - Patterns with a prefix before the repeating group (e.g., A (B+) C)
   - Fixed-length iteration groups (e.g., (A B{2})+ where each
     iteration consumes exactly 3 rows)

2. Frame specification:
   - AFTER MATCH SKIP TO NEXT ROW is not eligible (only
     SKIP PAST LAST ROW)
   - Frame end must be UNBOUNDED FOLLOWING

3. DEFINE clause evaluation:
   - Absorption relies on the monotonicity assumption that DEFINE
     conditions produce the same result regardless of starting
     position. Currently DEFINE uses simple boolean conditions
     where this holds. However, future additions such as
     CLASSIFIER() or running aggregates (e.g., RUNNING SUM())
     may introduce context-dependent evaluation that breaks
     this invariance, requiring absorption to be disabled for
     those cases.

That said, many practically useful patterns fall within these
conditions. Here are examples from our regression tests using
synthetic stock data:

  V-shape recovery (decline then rise):
    PATTERN (DECLINE{4,} RISE{4,})
    DEFINE
      DECLINE AS price < PREV(price),
      RISE AS price > PREV(price)

  W-bottom (decline, bounce, re-decline, recovery):
    PATTERN (DECLINE{3,} BOUNCE{3,} DIP{3,} RECOVER{3,})
    DEFINE
      DECLINE AS price < PREV(price),
      BOUNCE AS price > PREV(price),
      DIP AS price < PREV(price),
      RECOVER AS price > PREV(price)

  Consolidation then breakout:
    PATTERN (FLAT{5,} BREAKOUT)
    DEFINE
      FLAT AS price BETWEEN PREV(price) * 0.98 AND PREV(price) * 1.02,
      BREAKOUT AS price > PREV(price) * 1.05

  Price-volume divergence (bearish signal):
    PATTERN (INIT DIVERGE{3,})
    DEFINE
      DIVERGE AS price > PREV(price) AND volume < PREV(volume)

  Volume climax reversal:
    PATTERN (RALLY{3,} CLIMAX SELLOFF{2,})
    DEFINE
      RALLY AS price > PREV(price),
      CLIMAX AS volume > PREV(volume) * 1.5,
      SELLOFF AS price < PREV(price)

All of these use unbounded quantifiers with position-invariant
DEFINE conditions -- exactly the cases where Context Absorption
guarantees O(n) scaling. So despite the constraints, it remains
a powerful optimization for the workloads where RPR is most
commonly applied.

Best regards,
Henson

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

<div dir=3D"ltr"><div dir=3D"ltr">Hi SungJun,<br><br>Thanks for the cross-v=
alidation report.<br></div><br><div class=3D"gmail_quote gmail_quote_contai=
ner"><blockquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;bo=
rder-left-width:1px;border-left-style:solid;border-left-color:rgb(204,204,2=
04);padding-left:1ex"><div dir=3D"ltr">This appears to be due to its NFA im=
plementation combined with Context Absorption,=C2=A0</div></blockquote><blo=
ckquote class=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left=
-width:1px;border-left-style:solid;border-left-color:rgb(204,204,204);paddi=
ng-left:1ex"><div dir=3D"ltr"> which discards redundant matching contexts w=
hen they reach the same NFA state=C2=A0</div></blockquote><blockquote class=
=3D"gmail_quote" style=3D"margin:0px 0px 0px 0.8ex;border-left-width:1px;bo=
rder-left-style:solid;border-left-color:rgb(204,204,204);padding-left:1ex">=
<div dir=3D"ltr">but start later in the input.<br><br>Example:<br><br>Ctx1 =
start=3D0 length=3D2<br>Ctx2 start=3D1 length=3D1<br><br>Ctx1 subsumes Ctx2=
, so Ctx2 is discarded.<br><br>This keeps the number of active contexts sma=
ll and prevents quadratic growth.</div></blockquote><div><br></div>Your des=
cription is accurate. An earlier-started context subsumes<br>all matches of=
 a later-started context (monotonicity principle),<br>so the newer one can =
be safely removed.<br><br>However, Context Absorption is not universally ap=
plicable. It<br>requires careful analysis of several factors, and we contin=
ue to<br>refine the conditions under which absorption can be safely applied=
.<br><br>The current scope of absorption is determined by three factors:<br=
><br>1. Pattern structure:<br>=C2=A0 =C2=A0Currently supported:<br>=C2=A0 =
=C2=A0- Simple unbounded quantifiers: A+, (A B)+<br>=C2=A0 =C2=A0- Leading =
unbounded quantifier in group: (A+ B)+<br>=C2=A0 =C2=A0- First iteration of=
 nested unbounded alternation (e.g., ((A+)|(B+))+)<br>=C2=A0 =C2=A0Planned =
improvements:<br>=C2=A0 =C2=A0- Patterns with a prefix before the repeating=
 group (e.g., A (B+) C)<br>=C2=A0 =C2=A0- Fixed-length iteration groups (e.=
g., (A B{2})+ where each<br>=C2=A0 =C2=A0 =C2=A0iteration consumes exactly =
3 rows)<br><br>2. Frame specification:<br>=C2=A0 =C2=A0- AFTER MATCH SKIP T=
O NEXT ROW is not eligible (only<br>=C2=A0 =C2=A0 =C2=A0SKIP PAST LAST ROW)=
<br>=C2=A0 =C2=A0- Frame end must be UNBOUNDED FOLLOWING<br><br>3. DEFINE c=
lause evaluation:<br>=C2=A0 =C2=A0- Absorption relies on the monotonicity a=
ssumption that DEFINE<br>=C2=A0 =C2=A0 =C2=A0conditions produce the same re=
sult regardless of starting<br>=C2=A0 =C2=A0 =C2=A0position. Currently DEFI=
NE uses simple boolean conditions<br>=C2=A0 =C2=A0 =C2=A0where this holds. =
However, future additions such as<br>=C2=A0 =C2=A0 =C2=A0CLASSIFIER() or ru=
nning aggregates (e.g., RUNNING SUM())<br>=C2=A0 =C2=A0 =C2=A0may introduce=
 context-dependent evaluation that breaks<br>=C2=A0 =C2=A0 =C2=A0this invar=
iance, requiring absorption to be disabled for<br>=C2=A0 =C2=A0 =C2=A0those=
 cases.<br><br>That said, many practically useful patterns fall within thes=
e<br>conditions. Here are examples from our regression tests using<br>synth=
etic stock data:<br><br>=C2=A0 V-shape recovery (decline then rise):<br>=C2=
=A0 =C2=A0 PATTERN (DECLINE{4,} RISE{4,})<br>=C2=A0 =C2=A0 DEFINE<br>=C2=A0=
 =C2=A0 =C2=A0 DECLINE AS price &lt; PREV(price),<br>=C2=A0 =C2=A0 =C2=A0 R=
ISE AS price &gt; PREV(price)<br><br>=C2=A0 W-bottom (decline, bounce, re-d=
ecline, recovery):<br>=C2=A0 =C2=A0 PATTERN (DECLINE{3,} BOUNCE{3,} DIP{3,}=
 RECOVER{3,})<br>=C2=A0 =C2=A0 DEFINE<br>=C2=A0 =C2=A0 =C2=A0 DECLINE AS pr=
ice &lt; PREV(price),<br>=C2=A0 =C2=A0 =C2=A0 BOUNCE AS price &gt; PREV(pri=
ce),<br>=C2=A0 =C2=A0 =C2=A0 DIP AS price &lt; PREV(price),<br>=C2=A0 =C2=
=A0 =C2=A0 RECOVER AS price &gt; PREV(price)<br><br>=C2=A0 Consolidation th=
en breakout:<br>=C2=A0 =C2=A0 PATTERN (FLAT{5,} BREAKOUT)<br>=C2=A0 =C2=A0 =
DEFINE<br>=C2=A0 =C2=A0 =C2=A0 FLAT AS price BETWEEN PREV(price) * 0.98 AND=
 PREV(price) * 1.02,<br>=C2=A0 =C2=A0 =C2=A0 BREAKOUT AS price &gt; PREV(pr=
ice) * 1.05<br><br>=C2=A0 Price-volume divergence (bearish signal):<br>=C2=
=A0 =C2=A0 PATTERN (INIT DIVERGE{3,})<br>=C2=A0 =C2=A0 DEFINE<br>=C2=A0 =C2=
=A0 =C2=A0 DIVERGE AS price &gt; PREV(price) AND volume &lt; PREV(volume)<b=
r><br>=C2=A0 Volume climax reversal:<br>=C2=A0 =C2=A0 PATTERN (RALLY{3,} CL=
IMAX SELLOFF{2,})<br>=C2=A0 =C2=A0 DEFINE<br>=C2=A0 =C2=A0 =C2=A0 RALLY AS =
price &gt; PREV(price),<br>=C2=A0 =C2=A0 =C2=A0 CLIMAX AS volume &gt; PREV(=
volume) * 1.5,<br>=C2=A0 =C2=A0 =C2=A0 SELLOFF AS price &lt; PREV(price)<br=
><br>All of these use unbounded quantifiers with position-invariant<br>DEFI=
NE conditions -- exactly the cases where Context Absorption<br>guarantees O=
(n) scaling. So despite the constraints, it remains<br>a powerful optimizat=
ion for the workloads where RPR is most<br>commonly applied.<br><br>Best re=
gards,<br>Henson=C2=A0</div></div>

--000000000000039e2a064cbd27eb--