MIME-Version: 1.0
References: <20260701.211805.2273383346456030984.ishii@postgresql.org>
 <20260703.211309.1130370315247638762.ishii@postgresql.org>
 <CAAAe_zBMvzn6ZwmTPhsi0mP6FPVv3hZ2cb1Xe3KD8brT5EPTFg@mail.gmail.com>
 <20260704.162841.39857602849942465.ishii@postgresql.org>
 <CAAAe_zAZCeXAP73q01zdXXc2tTG7=iNM1tX4XgtbTWb02ef1-Q@mail.gmail.com>
In-Reply-To: 
 <CAAAe_zAZCeXAP73q01zdXXc2tTG7=iNM1tX4XgtbTWb02ef1-Q@mail.gmail.com>
Reply-To: assam258@gmail.com
From: Henson Choi <assam258@gmail.com>
Date: Sun, 5 Jul 2026 01:39:43 +0900
Message-ID: 
 <CAAAe_zBMyW7=ZEgZ2=rgka328FKyBS6sw=xpWztv4AD8wskffw@mail.gmail.com>
Subject: Re: Row pattern recognition
To: Tatsuo Ishii <ishii@postgresql.org>, jian.universality@gmail.com
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="0000000000000549050655cbb13f"
Archived-At: 
 <https://www.postgresql.org/message-id/CAAAe_zBMyW7%3DZEgZ2%3Drgka328FKyBS6sw%3DxpWztv4AD8wskffw%40mail.gmail.com>
Precedence: bulk

--0000000000000549050655cbb13f
Content-Type: text/plain; charset="UTF-8"

Hi hackers,

This is a design note on the core data structures for CLASSIFIER and
row pattern variables, aimed at the next round of window-clause row
pattern recognition (RPR, R020) rather than the current patch. I'd
like to share it and open it up for discussion.

It opens with a reflection, because the reflection is the point. For
about six months I took it for granted that we must keep the full
per-row match history during matching. That premise was wrong. Once I
dropped it, the data-structure problem dissolved into a handful of
small, bounded pieces -- which is what the rest of the note works out:
what to store per case, how much, and how to encode it.

I believe the storage/representation side is settled. What I have
deliberately left open is the part that lives in the matching engine
-- the aggregate accumulator lifecycle (clone on branch, discard on
failure) and the winning-match replay. I'd welcome thoughts there,
particularly from Tatsuo and Jian, given their work on the current
patch.

Best regards,
Henson

----------------------------------------------------------------------

RPR CLASSIFIER / row pattern variable storage (window clause)

I. Reflection -- the "full match history" premise was wrong

Since January this year -- six months into starting RPR work in
earnest -- I kept reasoning under one premise:

    To implement CLASSIFIER and row pattern variables, we must keep
    the per-row sequence of variable labels (the match history) that
    the match consumes, throughout matching.

For that half year I set the data-structure problem on top of it --
"where and how do we hold that whole sequence cheaply?" -- and kept
piling up storage / sharing / compression / lookup structures.

Yet no usable lookup structure ever came out. Worse: matchStates
branch and most of them vanish on match failure, so the cost of
building a lookup structure for each of those countless
(soon-discarded) states was exceeding the lookup efficiency it bought
-- paying up front, for the many that die, on behalf of the few that
survive.

The premise was wrong. RPR does not need to keep the full match
history during matching. The one place a full per-row sequence is
genuinely materialized is the universal-scope MEASURE aggregate (case
8, ARRAY_AGG(CLASSIFIER())). So that entire storage / sharing /
compression / lookup apparatus was solving a problem that did not need
solving.

II. The corrected picture -- what to store, per case

Here is how the storage requirement splits, case by case:

1. DEFINE navigation -- the reference range is bounded by the
   navigation offset. The offset is a run-time constant, so the upper
   bound to keep during execution is fixed and can be computed
   directly, without any lookup. A nav with no row pattern variable
   just derives the position from the offset and reads it from the
   tuplestore. (How much to retain, per nav function, is detailed in
   section III.)

2. bare row pattern variable reference (A.col) -- equivalent to
   LAST(A.col, 0). The structure is a pos list for A -- since
   everything in it is A, membership is implicit and no varId is
   needed. As a bare reference this is the special case with length =
   1 (only the last pos); the full list is needed only for an A
   aggregate or a larger FIRST/LAST offset (section III).

3. SUBSET (union) variable -- for SUBSET U=(A,B), CLASSIFIER(U) and
   U.col are merely derived from the primary classification (which row
   is A/B); they are not new information. Because A and B are
   interleaved in the list and we must tell them apart, the structure
   is a list of (pos, varId) pairs.

4. bare CLASSIFIER() (current row) -- unless it is inside an aggregate
   (ARRAY_AGG etc.), only the current row is needed (no list). The
   classifier comes straight from the variable (its name) that the
   pattern element currently being consumed by the matchState
   designates.

5. aggregate in DEFINE -- it drives matching, so it is evaluated live
   during matching under RUNNING semantics (no post-processing
   possible). The aggregate inputs (which row is which variable, its
   column, its classifier) are all already obtained from 1-4, so no
   new structure is needed -- only one running accumulator folding
   them on top. That is as far as the match-history view goes (no full
   history needed). Separately, there are two costs: (a) computing
   live for the many matchStates that mostly fail, and (b) cloning the
   in-progress accumulator into children on a branch. But this is
   aggregate accumulator management cost, not match history.

6-8 (MEASURE aggregates): since the match is already complete, it is
better to avoid paying for a live accumulator per failing candidate
(the cost in 5) and instead process only the winning match by post
replay. What each case must store/replay is below.

6. aggregate in MEASURE -- variable/SUBSET scope -- e.g. sum(A.price),
   sum(U.price), ARRAY_AGG(CLASSIFIER(U)). Only membership is needed
   (values in the tuplestore), compressed as a bitmap / run length
   (alternating m A's and n non-A's; sequential, no lookup). But the
   granularity differs: sum(A.price) / sum(U.price) need only is-A /
   is-U, whereas ARRAY_AGG(CLASSIFIER(U)) must distinguish which
   sub-variable, so it needs per-sub-variable membership (A and B
   each). Those per-sub memberships are precisely the per-row member
   label, and when several aggregates use the same sub-variable, these
   memberships fuse into that single label. (For bare scalar
   CLASSIFIER(U), see 3 -- just the last varId in the U list.)

7. aggregate in MEASURE -- CLASSIFIER(variable) inside an aggregate
   (special case: optimized to the first-occurrence position) -- in
   ARRAY_AGG(CLASSIFIER(A)), CLASSIFIER(A) is a running LAST, so its
   value is null before the first A and the constant 'A' afterwards.
   So instead of the full membership of 6, it optimizes to a single
   first-occurrence position for A (the null->A boundary) -- a
   single-variable special case. (For SUBSET CLASSIFIER(U) the member
   varies, so this optimization does not apply; handle it in 6.) bare
   scalar CLASSIFIER(A) is derived from 2 -- just whether A's list is
   empty.

8. aggregate in MEASURE -- universal scope -- every match row is in
   scope. For a column (e.g. sum(price)) it is all rows, so not even
   membership is needed (values in the tuplestore). For
   ARRAY_AGG(CLASSIFIER()), each row's value is the row pattern
   variable name (the label), and the storage is a run-length encoding
   of varId (a run of the same variable as (varId, run)) -- since all
   rows are in order, no pos is needed; just pile up varId runs (order
   implies pos). (For bare scalar CLASSIFIER(), see 4 -- just the last
   row's varId.)

III. Retained length per nav function -- offset fixes the bound

If 1-2 above say what to hold, this pins down how much of it to hold
during matching, per nav function. The key: the offset is a run-time
constant (a literal, embedded variable, and the like -- not a column
or subquery), so the size of the retained window is fixed at plan
time. So you can pre-allocate a ring buffer of that size per variable,
and there is no lookup during matching.

Physical nav and logical nav split apart:

- physical nav (PREV/NEXT) -- the offset is a physical position in the
  partition, so it does not grow the variable's history at all. The
  anchor is just "that variable's running last row", and offset n
  merely indexes the tuplestore from there. Even when NEXT looks
  ahead, that row is already in the tuplestore (only its
  classification is pending). So: retain = 1 anchor, extra +0.

- logical nav (FIRST/LAST) -- the offset is a position within the rows
  mapped to that variable. Their retention costs are asymmetric.
  FIRST(X.col, n) is the (n+1)-th from the front, and the front never
  changes once passed, so you count X rows and latch only the single
  row where the count reaches n+1 -- a counter + 1 holder, O(1)
  regardless of n (later X rows are ignored). LAST(X.col, n) is the
  (n+1)-th from the back, but since it is running the end keeps
  moving, so you must hold X's last n+1 rows in a sliding window --
  retain = n+1. bare X.col = LAST(X.col, 0) = 1.

- nested PREV/NEXT(FIRST/LAST(X.col, k), m) -- retention follows the
  rule above for the inner (logical) part only: counter+holder for
  FIRST, k+1 sliding for LAST. The physical part m just reads the
  tuplestore from that row, so +0.

Boundary -- this bound applies to navigation references only. An
aggregate reference (sum(A.price) etc.) folds the entire prefix, so it
is absorbed into a running accumulator (5), not a window -- an O(1)
accumulated value, not a length. Do not mix the two into one
structure.

IV. Compressed storage -- one run-length spine

2-3 (during matching) and 6-8 (MEASURE replay) use the same
information under different access patterns, so their encodings
diverge:

- live / sparse (2-3) -- during matching you append only the rows
  mapped to X, as they come. It is a subsequence of all rows, so to
  know which row is which you must carry the pos too (2's pos list,
  3's pos+varId).

- replay / dense (6-8) -- you walk the winning match from the start
  over every match row, so no pos is needed -- order is the pos. This
  is where compression pays off.

The replay-side structures are all one run-length spine, specialized
only by granularity:

- universal classifier (8) -- per-row varId as (varId, run) runs. No
  pos; the cumulative run lengths give the position.

- per-variable membership (6) -- is-X as alternating runs: just a
  repetition of (present length, absent length) pairs (alternative: a
  1-bit-per-row bitmap). The case where is-A alone suffices, as in
  sum(A.price).

- per-sub-member (6) -- (varId, run) within the union, when you must
  tell A/B apart as in ARRAY_AGG(CLASSIFIER(U)). Rows outside U
  (non-A/non-B) must be carried as runs of a "none" sentinel varId so
  that order = pos is preserved.

- single-variable boundary (7) -- ARRAY_AGG(CLASSIFIER(A)) has only
  the null->A boundary, so the run degenerates to essentially a single
  item.

single varId RLE vs several per-variable memberships -- for the
per-sub-member case the two encodings trade off. (i) single varId RLE
(the bullet above): the per-row label comes out directly, but every
aggregate scans the whole span. (ii) several per-variable memberships:
is-A and is-B each as alternating runs (no sentinel needed) -- an
aggregate can pick just the sub-variable streams it uses, but a
CLASSIFIER(U) label must be read by merging several streams.

bitmap vs RLE -- a match is inherently runs (the greedy A^m B^n
shape). So RLE is natural, and since consumption is a sequential scan
no index is needed. A 1-bit-per-row bitmap (as long as the match) wins
only when the runs fragment finely or random access is needed.

Values are not stored -- the spine carries only
membership/label(varId); the actual column values live in the
tuplestore, and the replay scan fetches them by pos as it goes. This
is the principle behind 6-8 repeatedly noting that values stay in the
tuplestore.

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

<div dir=3D"ltr"><font face=3D"monospace">Hi hackers,<br><br>This is a desi=
gn note on the core data structures for CLASSIFIER and<br>row pattern varia=
bles, aimed at the next round of window-clause row<br>pattern recognition (=
RPR, R020) rather than the current patch. I&#39;d<br>like to share it and o=
pen it up for discussion.<br><br>It opens with a reflection, because the re=
flection is the point. For<br>about six months I took it for granted that w=
e must keep the full<br>per-row match history during matching. That premise=
 was wrong. Once I<br>dropped it, the data-structure problem dissolved into=
 a handful of<br>small, bounded pieces -- which is what the rest of the not=
e works out:<br>what to store per case, how much, and how to encode it.<br>=
<br>I believe the storage/representation side is settled. What I have<br>de=
liberately left open is the part that lives in the matching engine<br>-- th=
e aggregate accumulator lifecycle (clone on branch, discard on<br>failure) =
and the winning-match replay. I&#39;d welcome thoughts there,<br>particular=
ly from Tatsuo and Jian, given their work on the current<br>patch.<br><br>B=
est regards,<br>Henson<br><br>---------------------------------------------=
-------------------------<br><br>RPR CLASSIFIER / row pattern variable stor=
age (window clause)<br><br>I. Reflection -- the &quot;full match history&qu=
ot; premise was wrong<br><br>Since January this year -- six months into sta=
rting RPR work in<br>earnest -- I kept reasoning under one premise:<br><br>=
=C2=A0 =C2=A0 To implement CLASSIFIER and row pattern variables, we must ke=
ep<br>=C2=A0 =C2=A0 the per-row sequence of variable labels (the match hist=
ory) that<br>=C2=A0 =C2=A0 the match consumes, throughout matching.<br><br>=
For that half year I set the data-structure problem on top of it --<br>&quo=
t;where and how do we hold that whole sequence cheaply?&quot; -- and kept<b=
r>piling up storage / sharing / compression / lookup structures.<br><br>Yet=
 no usable lookup structure ever came out. Worse: matchStates<br>branch and=
 most of them vanish on match failure, so the cost of<br>building a lookup =
structure for each of those countless<br>(soon-discarded) states was exceed=
ing the lookup efficiency it bought<br>-- paying up front, for the many tha=
t die, on behalf of the few that<br>survive.<br><br>The premise was wrong. =
RPR does not need to keep the full match<br>history during matching. The on=
e place a full per-row sequence is<br>genuinely materialized is the univers=
al-scope MEASURE aggregate (case<br>8, ARRAY_AGG(CLASSIFIER())). So that en=
tire storage / sharing /<br>compression / lookup apparatus was solving a pr=
oblem that did not need<br>solving.<br><br>II. The corrected picture -- wha=
t to store, per case<br><br>Here is how the storage requirement splits, cas=
e by case:<br><br>1. DEFINE navigation -- the reference range is bounded by=
 the<br>=C2=A0 =C2=A0navigation offset. The offset is a run-time constant, =
so the upper<br>=C2=A0 =C2=A0bound to keep during execution is fixed and ca=
n be computed<br>=C2=A0 =C2=A0directly, without any lookup. A nav with no r=
ow pattern variable<br>=C2=A0 =C2=A0just derives the position from the offs=
et and reads it from the<br>=C2=A0 =C2=A0tuplestore. (How much to retain, p=
er nav function, is detailed in<br>=C2=A0 =C2=A0section III.)<br><br>2. bar=
e row pattern variable reference (A.col) -- equivalent to<br>=C2=A0 =C2=A0L=
AST(A.col, 0). The structure is a pos list for A -- since<br>=C2=A0 =C2=A0e=
verything in it is A, membership is implicit and no varId is<br>=C2=A0 =C2=
=A0needed. As a bare reference this is the special case with length =3D<br>=
=C2=A0 =C2=A01 (only the last pos); the full list is needed only for an A<b=
r>=C2=A0 =C2=A0aggregate or a larger FIRST/LAST offset (section III).<br><b=
r>3. SUBSET (union) variable -- for SUBSET U=3D(A,B), CLASSIFIER(U) and<br>=
=C2=A0 =C2=A0U.col are merely derived from the primary classification (whic=
h row<br>=C2=A0 =C2=A0is A/B); they are not new information. Because A and =
B are<br>=C2=A0 =C2=A0interleaved in the list and we must tell them apart, =
the structure<br>=C2=A0 =C2=A0is a list of (pos, varId) pairs.<br><br>4. ba=
re CLASSIFIER() (current row) -- unless it is inside an aggregate<br>=C2=A0=
 =C2=A0(ARRAY_AGG etc.), only the current row is needed (no list). The<br>=
=C2=A0 =C2=A0classifier comes straight from the variable (its name) that th=
e<br>=C2=A0 =C2=A0pattern element currently being consumed by the matchStat=
e<br>=C2=A0 =C2=A0designates.<br><br>5. aggregate in DEFINE -- it drives ma=
tching, so it is evaluated live<br>=C2=A0 =C2=A0during matching under RUNNI=
NG semantics (no post-processing<br>=C2=A0 =C2=A0possible). The aggregate i=
nputs (which row is which variable, its<br>=C2=A0 =C2=A0column, its classif=
ier) are all already obtained from 1-4, so no<br>=C2=A0 =C2=A0new structure=
 is needed -- only one running accumulator folding<br>=C2=A0 =C2=A0them on =
top. That is as far as the match-history view goes (no full<br>=C2=A0 =C2=
=A0history needed). Separately, there are two costs: (a) computing<br>=C2=
=A0 =C2=A0live for the many matchStates that mostly fail, and (b) cloning t=
he<br>=C2=A0 =C2=A0in-progress accumulator into children on a branch. But t=
his is<br>=C2=A0 =C2=A0aggregate accumulator management cost, not match his=
tory.<br><br>6-8 (MEASURE aggregates): since the match is already complete,=
 it is<br>better to avoid paying for a live accumulator per failing candida=
te<br>(the cost in 5) and instead process only the winning match by post<br=
>replay. What each case must store/replay is below.<br><br>6. aggregate in =
MEASURE -- variable/SUBSET scope -- e.g. sum(A.price),<br>=C2=A0 =C2=A0sum(=
U.price), ARRAY_AGG(CLASSIFIER(U)). Only membership is needed<br>=C2=A0 =C2=
=A0(values in the tuplestore), compressed as a bitmap / run length<br>=C2=
=A0 =C2=A0(alternating m A&#39;s and n non-A&#39;s; sequential, no lookup).=
 But the<br>=C2=A0 =C2=A0granularity differs: sum(A.price) / sum(U.price) n=
eed only is-A /<br>=C2=A0 =C2=A0is-U, whereas ARRAY_AGG(CLASSIFIER(U)) must=
 distinguish which<br>=C2=A0 =C2=A0sub-variable, so it needs per-sub-variab=
le membership (A and B<br>=C2=A0 =C2=A0each). Those per-sub memberships are=
 precisely the per-row member<br>=C2=A0 =C2=A0label, and when several aggre=
gates use the same sub-variable, these<br>=C2=A0 =C2=A0memberships fuse int=
o that single label. (For bare scalar<br>=C2=A0 =C2=A0CLASSIFIER(U), see 3 =
-- just the last varId in the U list.)<br><br>7. aggregate in MEASURE -- CL=
ASSIFIER(variable) inside an aggregate<br>=C2=A0 =C2=A0(special case: optim=
ized to the first-occurrence position) -- in<br>=C2=A0 =C2=A0ARRAY_AGG(CLAS=
SIFIER(A)), CLASSIFIER(A) is a running LAST, so its<br>=C2=A0 =C2=A0value i=
s null before the first A and the constant &#39;A&#39; afterwards.<br>=C2=
=A0 =C2=A0So instead of the full membership of 6, it optimizes to a single<=
br>=C2=A0 =C2=A0first-occurrence position for A (the null-&gt;A boundary) -=
- a<br>=C2=A0 =C2=A0single-variable special case. (For SUBSET CLASSIFIER(U)=
 the member<br>=C2=A0 =C2=A0varies, so this optimization does not apply; ha=
ndle it in 6.) bare<br>=C2=A0 =C2=A0scalar CLASSIFIER(A) is derived from 2 =
-- just whether A&#39;s list is<br>=C2=A0 =C2=A0empty.<br><br>8. aggregate =
in MEASURE -- universal scope -- every match row is in<br>=C2=A0 =C2=A0scop=
e. For a column (e.g. sum(price)) it is all rows, so not even<br>=C2=A0 =C2=
=A0membership is needed (values in the tuplestore). For<br>=C2=A0 =C2=A0ARR=
AY_AGG(CLASSIFIER()), each row&#39;s value is the row pattern<br>=C2=A0 =C2=
=A0variable name (the label), and the storage is a run-length encoding<br>=
=C2=A0 =C2=A0of varId (a run of the same variable as (varId, run)) -- since=
 all<br>=C2=A0 =C2=A0rows are in order, no pos is needed; just pile up varI=
d runs (order<br>=C2=A0 =C2=A0implies pos). (For bare scalar CLASSIFIER(), =
see 4 -- just the last<br>=C2=A0 =C2=A0row&#39;s varId.)<br><br>III. Retain=
ed length per nav function -- offset fixes the bound<br><br>If 1-2 above sa=
y what to hold, this pins down how much of it to hold<br>during matching, p=
er nav function. The key: the offset is a run-time<br>constant (a literal, =
embedded variable, and the like -- not a column<br>or subquery), so the siz=
e of the retained window is fixed at plan<br>time. So you can pre-allocate =
a ring buffer of that size per variable,<br>and there is no lookup during m=
atching.<br><br>Physical nav and logical nav split apart:<br><br>- physical=
 nav (PREV/NEXT) -- the offset is a physical position in the<br>=C2=A0 part=
ition, so it does not grow the variable&#39;s history at all. The<br>=C2=A0=
 anchor is just &quot;that variable&#39;s running last row&quot;, and offse=
t n<br>=C2=A0 merely indexes the tuplestore from there. Even when NEXT look=
s<br>=C2=A0 ahead, that row is already in the tuplestore (only its<br>=C2=
=A0 classification is pending). So: retain =3D 1 anchor, extra +0.<br><br>-=
 logical nav (FIRST/LAST) -- the offset is a position within the rows<br>=
=C2=A0 mapped to that variable. Their retention costs are asymmetric.<br>=
=C2=A0 FIRST(X.col, n) is the (n+1)-th from the front, and the front never<=
br>=C2=A0 changes once passed, so you count X rows and latch only the singl=
e<br>=C2=A0 row where the count reaches n+1 -- a counter + 1 holder, O(1)<b=
r>=C2=A0 regardless of n (later X rows are ignored). LAST(X.col, n) is the<=
br>=C2=A0 (n+1)-th from the back, but since it is running the end keeps<br>=
=C2=A0 moving, so you must hold X&#39;s last n+1 rows in a sliding window -=
-<br>=C2=A0 retain =3D n+1. bare X.col =3D LAST(X.col, 0) =3D 1.<br><br>- n=
ested PREV/NEXT(FIRST/LAST(X.col, k), m) -- retention follows the<br>=C2=A0=
 rule above for the inner (logical) part only: counter+holder for<br>=C2=A0=
 FIRST, k+1 sliding for LAST. The physical part m just reads the<br>=C2=A0 =
tuplestore from that row, so +0.<br><br>Boundary -- this bound applies to n=
avigation references only. An<br>aggregate reference (sum(A.price) etc.) fo=
lds the entire prefix, so it<br>is absorbed into a running accumulator (5),=
 not a window -- an O(1)<br>accumulated value, not a length. Do not mix the=
 two into one<br>structure.<br><br>IV. Compressed storage -- one run-length=
 spine<br><br>2-3 (during matching) and 6-8 (MEASURE replay) use the same<b=
r>information under different access patterns, so their encodings<br>diverg=
e:<br><br>- live / sparse (2-3) -- during matching you append only the rows=
<br>=C2=A0 mapped to X, as they come. It is a subsequence of all rows, so t=
o<br>=C2=A0 know which row is which you must carry the pos too (2&#39;s pos=
 list,<br>=C2=A0 3&#39;s pos+varId).<br><br>- replay / dense (6-8) -- you w=
alk the winning match from the start<br>=C2=A0 over every match row, so no =
pos is needed -- order is the pos. This<br>=C2=A0 is where compression pays=
 off.<br><br>The replay-side structures are all one run-length spine, speci=
alized<br>only by granularity:<br><br>- universal classifier (8) -- per-row=
 varId as (varId, run) runs. No<br>=C2=A0 pos; the cumulative run lengths g=
ive the position.<br><br>- per-variable membership (6) -- is-X as alternati=
ng runs: just a<br>=C2=A0 repetition of (present length, absent length) pai=
rs (alternative: a<br>=C2=A0 1-bit-per-row bitmap). The case where is-A alo=
ne suffices, as in<br>=C2=A0 sum(A.price).<br><br>- per-sub-member (6) -- (=
varId, run) within the union, when you must<br>=C2=A0 tell A/B apart as in =
ARRAY_AGG(CLASSIFIER(U)). Rows outside U<br>=C2=A0 (non-A/non-B) must be ca=
rried as runs of a &quot;none&quot; sentinel varId so<br>=C2=A0 that order =
=3D pos is preserved.<br><br>- single-variable boundary (7) -- ARRAY_AGG(CL=
ASSIFIER(A)) has only<br>=C2=A0 the null-&gt;A boundary, so the run degener=
ates to essentially a single<br>=C2=A0 item.<br><br>single varId RLE vs sev=
eral per-variable memberships -- for the<br>per-sub-member case the two enc=
odings trade off. (i) single varId RLE<br>(the bullet above): the per-row l=
abel comes out directly, but every<br>aggregate scans the whole span. (ii) =
several per-variable memberships:<br>is-A and is-B each as alternating runs=
 (no sentinel needed) -- an<br>aggregate can pick just the sub-variable str=
eams it uses, but a<br>CLASSIFIER(U) label must be read by merging several =
streams.<br><br>bitmap vs RLE -- a match is inherently runs (the greedy A^m=
 B^n<br>shape). So RLE is natural, and since consumption is a sequential sc=
an<br>no index is needed. A 1-bit-per-row bitmap (as long as the match) win=
s<br>only when the runs fragment finely or random access is needed.<br><br>=
Values are not stored -- the spine carries only<br>membership/label(varId);=
 the actual column values live in the<br>tuplestore, and the replay scan fe=
tches them by pos as it goes. This<br>is the principle behind 6-8 repeatedl=
y noting that values stay in the<br>tuplestore.</font><br></div>

--0000000000000549050655cbb13f--