Subject: Re: Row pattern recognition

From: Tatsuo Ishii <[email-masked]>
Date: Wed, 01 Jul 2026 21:18:05 +0900 (JST)

> Will continue reviewes tomorrow.

Sorry for delay. Here is the review for
v50-0005-match-once-per-row.patch.

--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -239,6 +239,10 @@ static int64 row_is_in_reduced_frame(WindowObject winobj, int64 pos);
 
 static void clear_reduced_frame(WindowAggState *winstate);
 static int	get_reduced_frame_status(WindowAggState *winstate, int64 pos);
+static void advance_nav_mark(WindowAggState *winstate, int64 currentPos);
+static void advance_reduced_frame_nfa(WindowObject winobj,
+									  RPRNFAContext *targetCtx, int64 pos,
+									  bool hasLimitedFrame, int64 frameOffset);
 static void update_reduced_frame(WindowObject winobj, int64 pos);
 
 /* Forward declarations - NFA row evaluation */
@@ -2521,6 +2525,16 @@ ExecWindowAgg(PlanState *pstate)
 			{
 				if (winstate->rpSkipTo == ST_NEXT_ROW)
 					clear_reduced_frame(winstate);
+
+				/*
+				 * Drive the row pattern match every row, so it tracks the row
+				 * scan rather than frame access: a window function that skips
+				 * the frame (e.g. nth_value() with a NULL offset) must not
+				 * leave the match state behind currentpos.
+				 */
+				Assert(winstate->nav_winobj != NULL);
+				(void) row_is_in_reduced_frame(winstate->nav_winobj,
+											   winstate->currentpos);

Is there any reason that we call row_is_in_reduced_frame() here,
instead of something like:

   update_frameheadpos(winstate);
   update_reduced_frame(winobj, pos);

row_is_in_reduced_frame() returns row status. Ignoring it using (void)
looks a little bit confusing to me.

Regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp

---

From: Henson Choi <[email-masked]>
Date: Thu, 2 Jul 2026 09:23:28 +0900

Hi Jian,

Thanks for the review, and for basing it on the RPR branch. Responses
inline.

> ``(only possible during early development/testing).`` comment is not
necessary?

Agreed, and it is actually misleading: varMatched == NULL is a live
signal, not a dev-only artifact. nfa_match() is called with NULL to force
every VAR to not-match at a frame boundary (execRPR.c, "Frame boundary
reached: force mismatch"). I will rewrite the comment to describe that
meaning instead of the "early development/testing" note.

> nfa_match desperately needs an extra i(nt64 currentPos) argument. [...]
> adding currentPos makes it much easier to understand the current
> execution state when debugging with GDB.

Makes sense -- nfa_match() has only the state list in scope, no row
index, which is exactly the thing that is hard to place in GDB. I will
thread currentPos through.

> The comments above in nfa_match are unnecessary because in ``if
> (RPRElemIsAbsorbableBranch(elem)`` we already have many comments, and
> the meaning seems the same.

Agreed -- the loop-top overview's second sentence restates the inline
END-chain block. I will drop it and keep "Evaluate VAR elements against
current row" as a one-line lead.

> Similar to REG_DEBUG, we really need an RPR_DEBUG option. [...] verify
> that ctx->states is not a circular linked list [...] without affecting
> release builds.

Fair point, and there is some history: RPR_DEBUG did exist earlier as
debug logging, and I am the one who proposed removing it. My reason was
narrow, though. I lean on the debugger, and with AI assistance the cost of
inserting, watching, and then removing ad-hoc logs has dropped sharply --
so I treated those logs as ephemeral and optimized for a clean committed
tree rather than for someone reading execRPR.c cold.

For a new contributor that trade-off is the wrong one, and you have
convinced me: a retained set of observation points, plus the Assert-style
sanity checks you describe (non-circular state list, count and
context-ordering invariants), would genuinely lower the barrier to this
code. So I agree with the direction. Rather than settle on a shape now, I
would leave it open: which observation points and checks are actually
worth retaining behind #ifdef RPR_DEBUG can be picked out later as a
separate follow-up, and it is really Tatsuo's call since he suggested the
first version.

> <para> The SQL standard defines more subclauses: MEASURES and SUBSET
> [...] more variations in AFTER MATCH clause. </para>
> This part should stay in the Compatibility section.

Agreed. It is a standard-deviation note, and the SELECT Compatibility
section currently has no row-pattern text, so I will move this paragraph
there.

Unless Tatsuo has a different view by the weekend, I will proceed with the
concrete changes above, leaving the RPR_DEBUG shape open as noted.

Best regards,
Henson

---

From: Henson Choi <[email-masked]>
Date: Thu, 2 Jul 2026 09:23:30 +0900

Hi Tatsuo,

Thanks for the review. I agree with the direction -- the (void) is
confusing. I did try your exact suggestion and the regression tests pass
unchanged, but I would keep one guard, for the following reason.

>    update_reduced_frame(winobj, pos);

row_is_in_reduced_frame() guards the update:

    state = get_reduced_frame_status(winstate, pos);
    if (state == RF_NOT_DETERMINED)
    {
        update_frameheadpos(winstate);
        update_reduced_frame(winobj, pos);
    }

Calling update_reduced_frame() unconditionally drops that guard. When
currentpos is already determined -- e.g. an interior row of a previous
match under AFTER MATCH SKIP PAST LAST ROW (RF_SKIPPED) -- it takes an
O(1) early return and overwrites the shared rpr_match_* record, silently
reclassifying a SKIPPED row as UNMATCHED.

This is not observable today -- I confirmed with a guarded-vs-unguarded
differential (patterns, both skip modes, various aggregates: identical
output), because both paths end up with an empty reduced frame. But it
does change the state semantics and leans on that convergence, so I would
rather keep the guard. Two ways, both of which remove the (void):

  A) Keep the guard inline at the call site.

  B) Factor it into a small helper shared by the nav-driving call site
     and row_is_in_reduced_frame():

        static void
        ensure_reduced_frame(WindowObject winobj, int64 pos)
        {
            WindowAggState *winstate = winobj->winstate;

            if (get_reduced_frame_status(winstate, pos) ==
RF_NOT_DETERMINED)
            {
                update_frameheadpos(winstate);
                update_reduced_frame(winobj, pos);
            }
        }

I lean towards B (no duplicated guard, and the name states the intent),
but A is the smaller diff. Which do you prefer?

Best regards,
Henson

---

From: Tatsuo Ishii <[email-masked]>
Date: Thu, 02 Jul 2026 09:48:13 +0900 (JST)

Hi Henson,

> rather keep the guard. Two ways, both of which remove the (void):

Thanks for the explanation. That makese sense.

> but A is the smaller diff. Which do you prefer?

I like B too.

Regards,

---

From: jian he <[email-masked]>
Date: Thu, 2 Jul 2026 12:14:55 +0800

Hi,

I have 3 patches to present:

v50-0001-refactor-DEFINE-volatile-expression-check.nocfbot
v50-0002-refactor-define_walker.nocfbot
v50-0003-replace-EMPTY_LOOP-to-RPR_ELEM_EMPTY_LOOP.nocfbot

As mentioned before, it's based on
https://github.com/assam258-5892/postgres/commits/RPR.
v50-0001, v50-0002 alrady submitted once patch at [1], now it's more complete.

Except that i want to rename RPSkipTo to RPRSkipTo and rpSkipTo to rprSkipTo,
What do you think?

[1] https://postgr.es/m/CACJufxG57=ddtbN=[email-masked]

--
jian
https://www.enterprisedb.com/

---

From: jian he <[email-masked]>
Date: Fri, 3 Jul 2026 08:36:49 +0800

Hi.

``The actual mark is set to: min(lookback_mark, lookahead_mark).``
in README.rpr need update?

The attached patch is still based on
https://github.com/assam258-5892/postgres/commits/RPR.

v50-0001-Refactor-visit_nav_plan.partial
v50-0002-Refactor-visit_nav_exec.partial
v50-0003-no-need-compile-and-evaluate-offset-in-expression-evaluation.partial
v50-0004-misc.partial
v50-0001-Evaluate-navigation-offset-once-at-one-place.nocfbot

The ".partial" patch, when combined, contains the same content as the
single patch (v50-0001-Evaluate-navigation-offset-once-at-one-place.nocfbot).
(I first created separated patches, but then I felt the whole change
focuses on one main topic, so merging them made sense to me).

The commit message for the main patch
(v50-0001-Evaluate-navigation-offset-once-at-one-place.nocfbot) is
below:
------------------------------------------------
Subject: [PATCH v51 1/1] Evaluate navigation offset once at one place

Row pattern navigation (PREV/NEXT/FIRST/LAST and their compounds) resolved
offsets (transform a expression to a int64 number) in ExecInitExprRec,
ExecEvalRPRNavSet, extract_const_offset, eval_define_offsets. Serval places
transform the same offset expression to a int64 number, that is too much!

With the attached, a single place (ExecInitWindowAgg->eval_define_offsets) to
handling this.

visit_nav_exec() now evaluates every offset expression at executor init and save
the result on the RPRNavExpr (offset / compound_offset); ExecEvalRPRNavSet()
simply reads those int64 values.  This removes:

  - the RPRNavOffsetKind enum and the offset/kind fields on the
    WindowAgg plan node.  The planner walk (visit_nav_plan /
    compute_define_metadata) now only classifies match_start
    dependency, which is all buildRPRPattern() needs to decide context
    absorption.

  - the per-invocation offset machinery in the executor: the Datum*
    offset arrays in the eval step, rpr_nav_get_compound_offset(), and
    the scattered NULL/negative checks, now centralized in
    eval_nav_offset.

The "retain all" case (backward reach overflows int64) is encoded as the
sentinel navMaxOffset < 0 rather than an enum value; advance_nav_mark() disables
tuplestore trim on it.  EXPLAIN reads the resolved offsets from the planstate
(ExecInitWindowAgg is reached for EXPLAIN without ANALYZE), so it now prints
concrete offsets instead of "runtime".

```
 We must still set nav_saved_outertuple (done above) so that
EEOP_RPR_NAV_RESTORE is a harmless no-op.
```
The above in ExecEvalRPRNavSet is wrong, EEOP_RPR_NAV_RESTORE will never be a
no-op. However we can make EEOP_RPR_NAV_RESTORE no-op, so the above comments
make sense.

Rename eval_nav_offset_helper to eval_nav_offset

Based on https://github.com/assam258-5892/postgres/commits/RPR
------------------------------------------------

---

From: jian he <[email-masked]>
Date: Fri, 3 Jul 2026 11:55:43 +0800

Hi.

While at it, I found nav_traversal_walker is a little bit of
complicated (overkill).
So the attached patch is removing nav_traversal_walker.

Two files are attached:
v50-0001-Evaluate-navigation-offset-once-at-one-place.nocfbot
v50-0002-Drop-the-shared-nav_traversal_walker-for-RPR-DEFINE.nocfbot

v50-0001 is the same as posted in [1].
v50-0002 is built on top of v50-0001. Even without v50-0001,
I think the changes in v50-0002 still make sense, as they improve readability.

The commit message for v50-0002 is below:
------------------------------------------------
Subject: [PATCH v50 2/2] Drop the shared nav_traversal_walker for RPR DEFINE

Both visit_nav_exec() and visit_nav_plan() assert:

    Assert(nav->arg == NULL || !IsA(nav->arg, RPRNavExpr));
    Assert(nav->offset_arg == NULL || !IsA(nav->offset_arg, RPRNavExpr));
    Assert(nav->compound_offset_arg == NULL ||
           !IsA(nav->compound_offset_arg, RPRNavExpr));

so an RPRNavExpr is never nested inside another RPRNavExpr, and the expressions
that contain RPRNavExpr nodes are not complicated.  For that, the generic
nav_traversal_walker() -- a NavTraversal struct carrying a function pointer and
a void* context, shared between the planner and the executor is kind of
complicated.

Replace it with static RPRNavExpr_walker() in each site.  RPRNavExpr_walker will
finds RPRNavExpr nodes, and acts on them the way it wants.  Having a small
duplicated static walker in the two files is fine here, nodeWindowAgg.c no
longer need to include "optimizer/rpr.h".

rename visit_nav_plan to compute_matchStartDependent,
rename visit_nav_exec to compute_nav_offsets.
------------------------------------------------
[1]: https://www.postgresql.org/message-id/CACJufxFfMJAMc0R6g4f7Bwr47QDY%2BOBr2vzqqMRbCzjdD9vR2g%40mail.gmail.com

---

From: Tatsuo Ishii <[email-masked]>
Date: Fri, 03 Jul 2026 21:13:09 +0900 (JST)

Hi Henson, Jian,

In v50-0006-tidy-plumbing.patch, the planner cost model seems slightly
changed.  Before the cost was charged according to the number of
pattern variables in PATTERN clause.  But now it is charged according
to the number of pattern variables in DEFINE clause.  Maybe I missed
the discussion on the changing. Can you please explain the reason of
the change?

--- a/src/backend/optimizer/path/costsize.c
+++ b/src/backend/optimizer/path/costsize.c
@@ -3231,30 +3231,18 @@ cost_windowagg(Path *path, PlannerInfo *root,
 	 * so we'll just do this for now.
 	 *
 	 * Moreover, if row pattern recognition is used, we charge the DEFINE
-	 * expressions once per tuple for each variable that appears in PATTERN.
+	 * expressions once per tuple for each DEFINE variable.
 	 */
 	if (winclause->rpPattern)
 	{
-		List	   *pattern_vars;
 		QualCost	defcosts;
 
-		pattern_vars = collectPatternVariables(winclause->rpPattern);
-
-		foreach_node(String, pv, pattern_vars)
+		foreach_node(TargetEntry, def, winclause->defineClause)
 		{
-			char	   *ptname = strVal(pv);
-
-			foreach_node(TargetEntry, def, winclause->defineClause)
-			{
-				if (!strcmp(ptname, def->resname))
-				{
-					cost_qual_eval_node(&defcosts, (Node *) def->expr, root);
-					startup_cost += defcosts.startup;
-					total_cost += defcosts.per_tuple * input_tuples;
-				}
-			}
+			cost_qual_eval_node(&defcosts, (Node *) def->expr, root);
+			startup_cost += defcosts.startup;
+			total_cost += defcosts.per_tuple * input_tuples;
 		}

Regards,

---

From: Henson Choi <[email-masked]>
Date: Sat, 4 Jul 2026 07:22:10 +0900

Hi Tatsuo,

> the discussion on the changing. Can you please explain the reason of

The change is a simplification that came out of Jian's v48 review, and it
does not change the cost the model produces.

It follows Jian's suggestion from 2026-06-15 [1]:

> collectPatternVariables is not needed.
> The parser already ensures every DEFINE variable appears in PATTERN,
> so there is nothing to filter.
> Also, we don't really do anything special (like make a dummy Const)
> regarding PATTERN variables that not appearing in the DEFINE clause.

The two loops charge exactly the same set, for the following reason:

- The old loop walked the unique PATTERN variables (collectPatternVariables
  deduplicates, returning each name once) and, for each, looked up the
  matching DEFINE entry by resname and charged that DEFINE's cost.
- Every DEFINE variable is guaranteed to appear in PATTERN -- the parser
  rejects a DEFINE variable that is not used in PATTERN (errmsg "DEFINE
  variable \"%s\" is not used in PATTERN" in parse_rpr.c).  So the DEFINE
  clause is always a subset of the unique PATTERN variables, and each
  DEFINE resname is unique.
- A PATTERN variable that has no DEFINE contributes nothing to the old
  loop, because the inner resname lookup finds no match.

So the old loop already charged each DEFINE expression exactly once, and
nothing else.  Iterating defineClause directly, as v50-0006 does, visits
precisely that same set once each.  The estimate is unchanged; only the
redundant outer walk over PATTERN and the per-variable resname lookup into
the DEFINE clause are removed.

This also matches the premise of the cost model we settled on back in
February: the NFA executor evaluates every DEFINE expression once per row,
so the natural unit for the per-tuple charge is the DEFINE variable.

[1]
https://www.postgresql.org/message-id/CACJufxFAQhbOD9EVCTAy-VwDbG4446N10GsxCcgdpFnjHO1Efw%40mail.gmail.com

Best regards,
Henson

---

From: jian he <[email-masked]>
Date: Sat, 4 Jul 2026 09:22:24 +0800

On Sat, Jul 4, 2026 at 6:22 AM Henson Choi <[email-masked]> wrote:
> ....
> [1] https://www.postgresql.org/message-id/CACJufxFAQhbOD9EVCTAy-VwDbG4446N10GsxCcgdpFnjHO1Efw%40mail.gmail.com
>
> Best regards,
> Henson

I am wondering if we can have one query to enable (COSTS ON) for testing.

For many rpr tests, the table size is small, EXPLAIN ANALYZE won't
take long, and probably all rows will be sampled.
Of course, once the patch is in committable shape, we need to switch it to OFF.

---

From: Tatsuo Ishii <[email-masked]>
Date: Sat, 04 Jul 2026 16:28:41 +0900 (JST)

> the DEFINE clause are removed.

Ok, thanks for the explanation.

> so the natural unit for the per-tuple charge is the DEFINE variable.

BTW, I was thinking about cases where same DEFINE variable appears
twice or more in PATTERN for a same row. For example PATTERN
(A|A). But in this case it would be optimized out to (A). So we don't
need to worry about A appearing twice. So our cost model is correct in
this case.

Regards,

---

From: Henson Choi <[email-masked]>
Date: Sat, 4 Jul 2026 17:59:34 +0900

Hi Tatsuo,

> twice or more in PATTERN for a same row. For example PATTERN (A|A).
> But in this case it would be optimized out to (A). So we don't need
> to worry about A appearing twice. So our cost model is correct in
> this case.

Right, and I think the cost model holds even a bit more broadly than
the (A|A) case.  (A|A) does collapse to (A), but a variable can still
appear more than once in patterns that do not collapse, e.g. PATTERN
(A B | A C), or A A, or A+.

In those cases the model is still correct, for a slightly different
reason than the (A|A) rewrite: the executor evaluates each DEFINE
predicate once per row, not once per PATTERN occurrence.  For each
row it evaluates every DEFINE once and keeps the boolean results in
a varMatched array.

When the same A appears at several positions in the pattern -- for
example the A in each branch of (A B | A C), which are distinct
states -- each looks up varMatched[A], so the same entry is read
more than once; but that read reuses the already-computed value, not
a re-evaluation.  So repetition in PATTERN never multiplies DEFINE
evaluations, and charging once per DEFINE variable in the cost model
matches what the executor actually does.

The related question that does run the other way is that today we
evaluate every DEFINE for a row eagerly, not just the ones that row
actually needs.  For example, in PATTERN (A B C D) a single match
walks the sequence one variable per row -- each row only needs to
test the single variable its state expects -- yet we still evaluate
A, B, C, and D at every row.

That is the short-circuit / lazy DEFINE evaluation Jian raised on
2026-05-26 using that very (A B C D) example (evaluate a predicate
only the first time a state tests it).  If we ever adopt it, the
cost model's premise -- every DEFINE once per row -- would change
with it, so the two are tied together.

There's also a soundness angle that argues for keeping it separate.
DEFINE already forbids volatile functions and sequence operations
(nextval), so the obvious non-deterministic cases are out.  The
wrinkle lazy evaluation adds is that a predicate would then be
evaluated zero or one times per row -- skipped whenever no state
reaches it -- rather than always.  Whether that is safe for a
predicate carrying some state-affecting behavior the volatility ban
does not exclude is something I haven't worked through, so it wasn't a
call I'd want to make lightly under the current review.

As we discussed, that one is best left as a separate series after
the initial commit, and since it was Jian's idea I'd be glad to see
him drive it.  For now I'd keep it out of the in-flight review so the
commit stays small.

Best regards,
Henson

---

From: Henson Choi <[email-masked]>
Date: Sun, 5 Jul 2026 01:39:43 +0900

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.

---

From: Tatsuo Ishii <[email-masked]>
Date: Mon, 06 Jul 2026 15:02:21 +0900 (JST)

Hi Henson,

> him drive it.  For now I'd keep it out of the in-flight review so the

Agreed.

Regards,

---

From: Henson Choi <[email-masked]>
Date: Tue, 7 Jul 2026 12:40:24 +0900

Hi Jian,

Thanks for this -- consolidating the offset resolution into one place
is a direction I like, and a couple of things about it are genuinely
nice:

> EXPLAIN reads the resolved offsets from the planstate
> (ExecInitWindowAgg is reached for EXPLAIN without ANALYZE), so it now
> prints concrete offsets instead of "runtime".

That is a real improvement -- the offset becomes visible in the plan
even when it comes from a bind parameter, where today we can only show
"runtime".

It also lines up with a point Tatsuo made back in April: since the
planner already folds a constant offset expression down to a single
Const, doing the resolution in the executor means we no longer have to
care whether the offset was constant or not.  So the direction has his
backing as well.

That said, I don't think we should take it into the patch at this
stage.  The current version has one proven defect: a plain
FIRST(expr, n) with n > 0 loses its forward reach.  I added a test for
it -- "DEFINE A AS v > FIRST(v, 5)" in rpr_explain -- where the
baseline prints "Nav Mark Lookahead: 5" and the patch prints 0.  The
query result is still correct (the mark is under-advanced, so it only
keeps extra rows), but the EXPLAIN is wrong and the tuplestore trim is
lost, so it is a regression against the baseline.

The test will come with the next patch email I send, so you will have
it there to diff against.

More broadly, though, reshaping the offset handling this much right as
we are stabilizing for commit feels like the wrong time -- at this
point I would rather limit changes to minimal fixes for proven
defects.  This is a worthwhile cleanup that deserves proper review
time, and it would be more valuable if it can be refined without that
pressure.

So how about, once the current patch is verified and committed, we
pursue this as a separate follow-up?

Best regards,
Henson

---

From: Henson Choi <[email-masked]>
Date: Tue, 7 Jul 2026 13:08:42 +0900

Hi Jian,

My first reaction to the define_walker refactor was that something
about it did not sit right, but I could not put my finger on why, so I
kept putting off a clear answer -- sorry about that.  I have taken the
time to think it through now.

To be clear, the patch is good, idiomatic PostgreSQL code:
contain_var_clause() and contain_rprnavexpr() are exactly how we
express these checks elsewhere, and it trims a fair amount of code.

> The allowed nav-expression combination is limited, therefore,
> has_column_ref is not necessary.

This is where I land differently, though.  A DEFINE predicate is
context-sensitive: the same column reference is required inside a
navigation argument but rejected inside its offset.  In
"DEFINE A AS PREV(price, price) > 0", the first price (the argument)
is required and the second (the offset) is rejected.  The
phase-tracking walker models that context directly, in a single pass,
and it generalizes to whatever context-dependent nesting the clause
grows into (MEASURES, further navigation forms).  Dropping it works
today only because the allowed combinations are limited, as you note
-- it leans on that limit rather than on the shape of the clause.

It also gives up the single-pass property the walker was written for
("no subtree is walked twice"): each navigation argument and offset is
now walked about twice, once by the main walk and again by the
contain_* check.  The extra cost is small at parse time, but it is a
step back from a design that deliberately avoided it.

So my preference is to keep the context-aware walker as it stands.
This is more about which foundation we want for an inherently
context-sensitive clause than about anything being wrong in your
version -- if you see it the other way, I would be glad to hear it.

Best regards,
Henson

---

From: Henson Choi <[email-masked]>
Date: Tue, 7 Jul 2026 16:07:29 +0900

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

---

From: Henson Choi <[email-masked]>
Date: Wed, 8 Jul 2026 17:04:34 +0900

Hi Tatsuo, Jian,

I hit a wrong result in row pattern recognition: an alternation
whose last branch is a concatenation of quantified groups matches
one group short.

  WITH d(id, dd, ee) AS (VALUES
    (1, true,  false), (2, false, true),
    (3, true,  false), (4, false, true))
  SELECT id, count(*) OVER w AS cnt
  FROM d
  WINDOW w AS (
    ORDER BY id
    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
    PATTERN (A | (B C)+ (D E)+)
    DEFINE A AS false, B AS false, C AS false,
           D AS dd, E AS ee);

   id | cnt
  ----+-----
    1 |   4      <- wrong; should be 0 (no match)
    2 |   0
    3 |   0
    4 |   0

The rows are D E D E, with no B and no C.  By precedence
PATTERN (A | (B C)+ (D E)+) means A | ((B C)+ (D E)+), so a bare
(D E)+ satisfies no branch and no row should match.  Instead row 1
matches [1,4]: the pattern behaves as if it were written
A | (B C)+ | (D E)+.

Cause: the ALT branch walk follows the branch head's jump to reach
the next branch.  That jump was the branch link, but the group
BEGIN's skip-past-END path was later layered onto the same field,
so jump is now overloaded.  When the last branch is (B C)+ (D E)+,
the BEGIN of (B C)+ jumps past its END to the BEGIN of (D E)+, and
the walk mistakes that following group for another alternative.

The same overloaded jump is walked in three places:
nfa_advance_alt (match advance), computeAbsorbabilityRecursive
(absorption marking), and the deparse.  nfa_advance_alt gives the
wrong result above.  computeAbsorbabilityRecursive over-marks the
trailing group as absorbable, though that turns out inert at run
time.  The deparse already sidesteps the overload in
rpr_next_branch() with the relative test elem[j-1].next != j, so
EXPLAIN prints the pattern correctly.

Fix direction: at its core, separate the BEGIN jump (group skip)
from the ALT branch-link jump -- they share one field today, which
is the overload.  I am weighing two ways to do that.

One is to move the group BEGIN's skip-past-END onto next.  Group
entry is already the contiguous BEGIN+1, so next is free, and jump
is left to be the branch link only.  No new elements.

The other is explicit branch-separator markers (a new SEP varid)
that carry the branch link, chained ALT.jump -> SEP -> ... ->
jump = -1 on the last one; branch content still reaches the
post-ALT element through next.

Either way the ALT walk sees jump as a branch link or -1, so
nfa_advance_alt, computeAbsorbabilityRecursive and the deparse can
enumerate branches the same clean way, dropping the relative test
and the depth-based break.  Deparse output stays the same.

I can put together a patch along these lines if the direction
looks right.

Best regards,
Henson

---

From: jian he <[email-masked]>
Date: Thu, 9 Jul 2026 13:55:41 +0800

> it there to diff against.

The case you mentioned:
PATTERN (A) DEFINE A AS v > FIRST(v, 5)

is fixable easily, it was a mistake I made while refactoring
visit_nav_exec to cut
down the number of eval_nav_offset() calls.

> pursue this as a separate follow-up?

That refactor is the patch I posted in [1]. An excerpt from its commit message:
```
Row pattern navigation (PREV/NEXT/FIRST/LAST and their compounds) resolves
offsets (transforming an expression into an int64) in ExecInitExprRec,
ExecEvalRPRNavSet, extract_const_offset and eval_define_offsets.  Several
places transform the same offset expression into an int64 -- that is too much.
With the attached, a single place (ExecInitWindowAgg -> eval_define_offsets)
handles this.
```

I think this belongs in the patchset now, rather than as a follow-up after the
main patch is committed. Computing the same offset in several places hurts
readability and, as this bug shows, is error-prone; consolidating it into one
place makes the code easier to read for future reviewers.

Committing the main patch and then posting a separate "make it readable"
refactoring afterward feels weird to me.
Refactoring now benefits everyone by significantly improving readability.

Broadly, I'd defend patch [2] on the same grounds: it improves readability, and
The current patchset doesn't need code that complex. It may not be the most
future-proof approach (I'm not certain) but given how complicated the whole
patchset already is, making each part more readable is a clear win for
reviewers.

Let's improve readability now while we can. Even assuming the patch is
committable today, there are still 9 months to refine it, so there's no rush
that justifies skipping cleanups. Each refactor makes the code more readable and
easier for reviewers to follow, which benefits everyone.

There won't be unlimited rounds of readability refactoring. Each
refactor makes the code clearer.
---------------------------------------------------
I hope the above is convincing.

[1] https://www.postgresql.org/message-id/CACJufxFfMJAMc0R6g4f7Bwr47QDY%2BOBr2vzqqMRbCzjdD9vR2g%40mail.gmail.com
[2] https://postgr.es/m/[email-masked]

---

From: Tatsuo Ishii <[email-masked]>
Date: Sat, 11 Jul 2026 14:52:26 +0900 (JST)

Hi Henson,

>     DEFINE A AS false, B AS false, C AS false,

I think your analysis is correct. I see that AST is correctly
generated. So the issue is in the executor phase.

> is the overload.  I am weighing two ways to do that.

Either way works for me.

> I can put together a patch along these lines if the direction

Ok.

---

From: Tatsuo Ishii <[email-masked]>
Date: Sat, 11 Jul 2026 14:53:43 +0900 (JST)

Hi Henson, Jian,

v50-0007-tidy-plumbing-more.patch
Looks good to me.

Minor points:

In nfa_advance_alt():

	while (altIdx >= 0)
	{
		RPRPatternElement *altElem;
		RPRNFAState *newState;

		/* Branch jump/next links are always -1 or a valid index */
		Assert(altIdx < pattern->numElements);

Since inside the while loop altIndx == -1 case is already excluded by
the while condition, the comment for the Assert is a little bit
strange. Probably following is better?

		/* Branch jump/next links are always valid index */

Regards,

---

From: jian he <[email-masked]>
Date: Sat, 11 Jul 2026 15:45:54 +0800

> place makes the code easier to read for future reviewers.

Hi.
Still based on https://github.com/assam258-5892/postgres/commits/RPR

Please check the attached v51-0001, v51-0002, v51-0003.
v51-0001 fixes the regression failure
v51-0002: If the target row does not exist, skip evaluating the
navigation function's argument expression
v51-0003: Introduce execution struct RprNavState

For example:

CREATE TABLE t (id int, v int);
INSERT INTO t VALUES (1, 10);
SELECT id, count(*) OVER w AS cnt
FROM t
WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
  PATTERN (A)
  DEFINE A AS PREV(v IS NOT NULL) IS NULL);

Here the first row has no PREV row, so the argument expression (v IS NOT NULL)
must not be evaluated at all; PREV(...) itself returns NULL, and PREV(...) IS
NULL is therefore true. The expected cnt value is 1.

To implement this, an extra step EEOP_JUMP_IF_NULL is emitted right after
EEOP_RPR_NAV_SET, jumping over the argument expression's steps directly to
EEOP_RPR_NAV_RESTORE in case of row does not exists.
------------------------------------------------------------------------
Storing the resolved offset values (offset, compound_offset) on RPRNavExpr, next
to the offset expressions they are computed from (offset_arg,
compound_offset_arg),
seems wrong to me: the expressions are plan-tree fields,
but the resolved values are per-execution results, and the executor must treat
the plan tree as read-only.

Compare how FOR PORTION OF handles this in ExecInitModifyTable:

```
exprState = ExecPrepareExpr((Expr *) forPortionOf->targetRange, estate);
targetRange = ExecEvalExpr(exprState, econtext, &isNull);

/* Create state for FOR PORTION OF operation */
fpoState = makeNode(ForPortionOfState);
fpoState->fp_targetRange = targetRange;
```
The expression is evaluated at executor startup, and the resulting value is
stored in an executor-state struct — the plan node is never modified.

We should do the same here: evaluate the offset expressions at executor startup
and store the resulting values in executor state.

So in v51-0003 I added a new executor-state struct, RprNavState, which captures
everything the evaluation code in execExprInterp.c needs: the WindowAggState,
the RPRNavExpr, the resolved offset and compound_offset, and the result type
info (resulttyplen, resulttypbyval). Keeping such per-node evaluation state in
an out-of-line struct, with the ExprEvalStep holding just a pointer to it,
follows an existing convention in the expression evaluation code — see
JsonExprState for a similar example.