MIME-Version: 1.0
References: 
 <CAAAe_zBMvzn6ZwmTPhsi0mP6FPVv3hZ2cb1Xe3KD8brT5EPTFg@mail.gmail.com>
 <20260704.162841.39857602849942465.ishii@postgresql.org>
 <CAAAe_zAZCeXAP73q01zdXXc2tTG7=iNM1tX4XgtbTWb02ef1-Q@mail.gmail.com>
 <20260706.150221.1117486145015185971.ishii@postgresql.org>
 <CAAAe_zBtXQPqcRq3vDoOX+1zJ6bYEpJbp4ohFn2AkVC-UoxCKw@mail.gmail.com>
 <CAAAe_zC6iN79qEOgD2TzLHxA8i4T9R3pYtn_5dsQV8FXn3cEcA@mail.gmail.com>
In-Reply-To: 
 <CAAAe_zC6iN79qEOgD2TzLHxA8i4T9R3pYtn_5dsQV8FXn3cEcA@mail.gmail.com>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Tue, 7 Jul 2026 16:07:29 +0900
Message-ID: 
 <CAAAe_zCVyVZVyKwOEpHOCKSHODCYn_vnbFqGo7rUAX+btmxxqQ@mail.gmail.com>
Subject: Re: Row pattern recognition
To: jian.universality@gmail.com, Tatsuo Ishii <ishii@postgresql.org>
Cc: pgsql-hackers@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
Content-Type: multipart/alternative; boundary="000000000000018fc60656000cea"
Archived-At: 
 <https://www.postgresql.org/message-id/CAAAe_zCVyVZVyKwOEpHOCKSHODCYn_vnbFqGo7rUAX%2BbtmxxqQ%40mail.gmail.com>
Precedence: bulk

--000000000000018fc60656000cea
Content-Type: text/plain; charset="UTF-8"

Hi Tatsuo, Jian,

I found a wrong result that comes from the context-absorption
optimization, and wanted to run it by you both.

  WITH d(id, a, c) AS (
    VALUES (1, true,  false),
           (2, true,  true),
           (3, true,  false),
           (4, false, false))
  SELECT id, count(*) OVER w AS cnt
  FROM d
  WINDOW w AS (
    ORDER BY id
    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
    AFTER MATCH SKIP PAST LAST ROW
    PATTERN (A{5,} | C)
    DEFINE A AS a, C AS c);

   id | cnt
  ----+-----
    1 |   0
    2 |   0
    3 |   0
    4 |   0

id = 2 returns cnt = 0, but C matches [2,2] there, so it should be
1. EXPLAIN ANALYZE on the query reports "0 matched" and "2 absorbed".

The cause: whether a context can be absorbed is decided from its
in-progress states. Once the id=2 context records the C match [2,2],
that match moves to matchedState and its C state leaves the
in-progress set, so only the A run remains and the context is judged
fully absorbable. The id=1 context's longer A run then dominates it
and frees the whole context -- including the recorded [2,2] match.
The dominance argument only covers a context's future matches; it
does not account for a match already recorded on the non-absorbable
branch.

The fix: bring matchedState into the absorption comparison as well --
a context should be absorbed only when the absorbing context also
covers the recorded match, not just the in-progress states, so a
match the absorber cannot reproduce is never dropped.

Best regards,
Henson

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

<div dir=3D"ltr"><div dir=3D"ltr"><font face=3D"monospace">Hi Tatsuo, Jian,=
<br><br>I found a wrong result that comes from the context-absorption<br>op=
timization, and wanted to run it by you both.<br><br>=C2=A0 WITH d(id, a, c=
) AS (<br>=C2=A0 =C2=A0 VALUES (1, true, =C2=A0false),<br>=C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0 =C2=A0(2, true, =C2=A0true),<br>=C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0 =C2=A0(3, true, =C2=A0false),<br>=C2=A0 =C2=A0 =C2=A0 =C2=A0 =C2=
=A0 =C2=A0(4, false, false))<br>=C2=A0 SELECT id, count(*) OVER w AS cnt<br=
>=C2=A0 FROM d<br>=C2=A0 WINDOW w AS (<br>=C2=A0 =C2=A0 ORDER BY id<br>=C2=
=A0 =C2=A0 ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING<br>=C2=A0 =C2=
=A0 AFTER MATCH SKIP PAST LAST ROW<br>=C2=A0 =C2=A0 PATTERN (A{5,} | C)<br>=
=C2=A0 =C2=A0 DEFINE A AS a, C AS c);<br><br>=C2=A0 =C2=A0id | cnt<br>=C2=
=A0 ----+-----<br>=C2=A0 =C2=A0 1 | =C2=A0 0<br>=C2=A0 =C2=A0 2 | =C2=A0 0<=
br>=C2=A0 =C2=A0 3 | =C2=A0 0<br>=C2=A0 =C2=A0 4 | =C2=A0 0<br><br>id =3D 2=
 returns cnt =3D 0, but C matches [2,2] there, so it should be<br>1. EXPLAI=
N ANALYZE on the query reports &quot;0 matched&quot; and &quot;2 absorbed&q=
uot;.<br><br>The cause: whether a context can be absorbed is decided from i=
ts<br>in-progress states. Once the id=3D2 context records the C match [2,2]=
,<br>that match moves to matchedState and its C state leaves the<br>in-prog=
ress set, so only the A run remains and the context is judged<br>fully abso=
rbable. The id=3D1 context&#39;s longer A run then dominates it<br>and free=
s the whole context -- including the recorded [2,2] match.<br>The dominance=
 argument only covers a context&#39;s future matches; it<br>does not accoun=
t for a match already recorded on the non-absorbable<br>branch.<br><br>The =
fix: bring matchedState into the absorption comparison as well --<br>a cont=
ext should be absorbed only when the absorbing context also<br>covers the r=
ecorded match, not just the in-progress states, so a<br>match the absorber =
cannot reproduce is never dropped.<br><br>Best regards,<br>Henson</font><br=
></div>
</div>

--000000000000018fc60656000cea--