nocfbot-0008-Replace-reduced-frame-map-with-single-match-result.txt
text/plain
Filename: nocfbot-0008-Replace-reduced-frame-map-with-single-match-result.txt
Type: text/plain
Part: 7
Message:
Re: Row pattern recognition
From ca171084b7c52e27a1f0bb2a17a8747f375e6a2f Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Thu, 2 Apr 2026 14:09:12 +0900
Subject: [PATCH 08/40] Replace reduced frame map with single match result
The reduced frame map was a per-row byte array tracking match status.
Since rows are processed sequentially and only one match is active
at a time, replace it with four scalar fields: valid, matched,
start, and length.
Also distinguish empty matches (FIN reached with zero rows consumed)
from unmatched rows via RF_EMPTY_MATCH, counted as matched in NFA
statistics.
Widen row_is_in_reduced_frame() return type from int to int64,
since it returns rpr_match_length which is int64.
---
src/backend/executor/execRPR.c | 56 +++---
src/backend/executor/nodeWindowAgg.c | 233 +++++++++-------------
src/include/nodes/execnodes.h | 21 +-
src/test/regress/expected/rpr_explain.out | 8 +-
4 files changed, 132 insertions(+), 186 deletions(-)
diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c
index 58f9da0b814..7d0f8fd401c 100644
--- a/src/backend/executor/execRPR.c
+++ b/src/backend/executor/execRPR.c
@@ -549,7 +549,7 @@
*
* (1) Find or create a context for the target row
* (2) Enter the row processing loop
- * (3) After the loop ends, record the result in reduced_frame_map
+ * (3) After the loop ends, record the match result
*
* Pseudocode of the row processing loop:
*
@@ -923,18 +923,19 @@
* Chapter X Match Result Processing
* ============================================================================
*
- * X-1. Reduced Frame Map
+ * X-1. Match Result
*
- * RPR match results are recorded in a byte array called reduced_frame_map.
- * One byte is allocated per row, and the value is one of the following:
+ * RPR tracks the current match result as a single entry in WindowAggState
+ * with four fields: rpr_match_valid, rpr_match_matched, rpr_match_start,
+ * and rpr_match_length. When rpr_match_valid is true, the entry describes
+ * the match result for the position at rpr_match_start: rpr_match_matched
+ * indicates success or failure, and rpr_match_length gives the number of
+ * rows consumed. A match with rpr_match_length 0 represents an empty match
+ * (pattern matched but consumed no rows). When rpr_match_valid is false,
+ * the position has not been evaluated yet (RF_NOT_DETERMINED).
*
- * RF_NOT_DETERMINED (0) Not yet processed
- * RF_FRAME_HEAD (1) Start row of the match
- * RF_SKIPPED (2) Interior row of the match (skipped in frame)
- * RF_UNMATCHED (3) Match failure
- *
- * The window function references this map to determine frame inclusion for
- * each row.
+ * A row's status against the current match result can be obtained by
+ * calling get_reduced_frame_status().
*
* X-2. AFTER MATCH SKIP
*
@@ -1028,8 +1029,7 @@
* Phase 3 (Advance): skipped (no states)
*
* C0.states is empty, so the loop terminates.
- * matchEndRow < matchStartRow -> RF_UNMATCHED.
- * register_reduced_frame_map(0, RF_UNMATCHED).
+ * matchEndRow < matchStartRow -> unmatched.
*
* --- Row 1 (price=110) ---
*
@@ -1113,9 +1113,7 @@
*
* C1.states is empty and matchEndRow=3 >= matchStartRow=1 -> match succeeds.
*
- * register_reduced_frame_map(1, RF_FRAME_HEAD)
- * register_reduced_frame_map(2, RF_SKIPPED)
- * register_reduced_frame_map(3, RF_SKIPPED)
+ * rpr_match_start = 1, rpr_match_length = 3
*
* --- Row 4 (price=130) ---
*
@@ -1128,15 +1126,15 @@
* B: 130 < PREV(115) -> false
*
* ... No subsequent rows, so ExecRPRFinalizeAllContexts() is called.
- * Match incomplete -> RF_UNMATCHED.
+ * Match incomplete -> unmatched.
*
* XI-5. Final Result
*
- * Row 0: RF_UNMATCHED -> frame = the row itself
- * Row 1: RF_FRAME_HEAD -> frame = rows 1 through 3
- * Row 2: RF_SKIPPED -> inside row 1's match
- * Row 3: RF_SKIPPED -> inside row 1's match
- * Row 4: RF_UNMATCHED -> frame = the row itself
+ * Row 0: unmatched -> frame = the row itself
+ * Row 1: match head -> frame = rows 1 through 3
+ * Row 2: inside match -> skipped
+ * Row 3: inside match -> skipped
+ * Row 4: unmatched -> frame = the row itself
*
* Chapter XII Summary of Key Design Decisions
* ============================================================================
@@ -1579,12 +1577,14 @@ static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx,
*
* - Empty match handling: The initial advance uses currentPos =
* startPos - 1 (before any row is consumed). If FIN is reached via
- * epsilon transitions alone, matchEndRow = startPos - 1 < matchStartRow,
- * resulting in UNMATCHED. For reluctant min=0 patterns (A*?, A??),
- * the skip path reaches FIN first and early termination prunes enter
- * paths, yielding an immediate empty (unmatched) result. For
- * greedy patterns (A*), the enter path adds VAR states first, then
- * the skip FIN is recorded but VAR states survive for later matching.
+ * epsilon transitions alone, matchEndRow = startPos - 1 < matchStartRow.
+ * If matchedState is set (FIN was reached), this is an empty match
+ * (RF_EMPTY_MATCH); otherwise it is unmatched (RF_UNMATCHED).
+ * For reluctant min=0 patterns (A*?, A??), the skip path reaches
+ * FIN first and early termination prunes enter paths, yielding an
+ * immediate empty match result. For greedy patterns (A*), the enter
+ * path adds VAR states first, then the skip FIN is recorded but VAR
+ * states survive for later matching.
*
* Context Absorption Runtime:
* ---------------------------
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index aed7cbef99a..dca2de570e8 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -247,13 +247,10 @@ static void attno_map(Node *node);
static bool attno_map_walker(Node *node, void *context);
static bool rpr_is_defined(WindowAggState *winstate);
-static int row_is_in_reduced_frame(WindowObject winobj, int64 pos);
+static int64 row_is_in_reduced_frame(WindowObject winobj, int64 pos);
-static void create_reduced_frame_map(WindowAggState *winstate);
-static void clear_reduced_frame_map(WindowAggState *winstate);
-static int get_reduced_frame_map(WindowAggState *winstate, int64 pos);
-static void register_reduced_frame_map(WindowAggState *winstate, int64 pos,
- int val);
+static void clear_reduced_frame(WindowAggState *winstate);
+static int get_reduced_frame_status(WindowAggState *winstate, int64 pos);
static void update_reduced_frame(WindowObject winobj, int64 pos);
static void check_rpr_navigation(Node *node, bool is_prev);
@@ -1035,13 +1032,7 @@ eval_windowaggregates(WindowAggState *winstate)
*/
for (;;)
{
- int ret;
-
-#ifdef RPR_DEBUG
- printf("===== loop in frame starts: aggregatedupto: " INT64_FORMAT " aggregatedbase: " INT64_FORMAT "\n",
- winstate->aggregatedupto,
- winstate->aggregatedbase);
-#endif
+ int64 ret;
/* Fetch next row if we didn't already */
if (TupIsNull(agg_row_slot))
@@ -1065,27 +1056,18 @@ eval_windowaggregates(WindowAggState *winstate)
if (rpr_is_defined(winstate))
{
-#ifdef RPR_DEBUG
- printf("reduced_frame_map: %d aggregatedupto: " INT64_FORMAT " aggregatedbase: " INT64_FORMAT "\n",
- get_reduced_frame_map(winstate,
- winstate->aggregatedupto),
- winstate->aggregatedupto,
- winstate->aggregatedbase);
-#endif
-
/*
- * If the row status at currentpos is already decided and current
- * row status is not decided yet, it means we passed the last
- * reduced frame. Time to break the loop.
+ * If currentpos is already decided but aggregatedupto is not yet
+ * determined, we've passed the last reduced frame.
*/
- if (get_reduced_frame_map(winstate, winstate->currentpos)
+ if (get_reduced_frame_status(winstate, winstate->currentpos)
!= RF_NOT_DETERMINED &&
- get_reduced_frame_map(winstate, winstate->aggregatedupto)
+ get_reduced_frame_status(winstate, winstate->aggregatedupto)
== RF_NOT_DETERMINED)
break;
/*
- * Otherwise we need to calculate the reduced frame.
+ * Calculate the reduced frame for aggregatedupto.
*/
ret = row_is_in_reduced_frame(winstate->agg_winobj,
winstate->aggregatedupto);
@@ -1093,17 +1075,13 @@ eval_windowaggregates(WindowAggState *winstate)
break;
/*
- * Check if current row needs to be skipped due to no match.
+ * Check if current row is inside a match but not the head
+ * (skipped), and it's the base row for aggregation.
*/
- if (get_reduced_frame_map(winstate,
- winstate->aggregatedupto) == RF_SKIPPED &&
+ if (get_reduced_frame_status(winstate,
+ winstate->aggregatedupto) == RF_SKIPPED &&
winstate->aggregatedupto == winstate->aggregatedbase)
- {
-#ifdef RPR_DEBUG
- printf("skip current row for aggregation\n");
-#endif
break;
- }
}
/* Set tuple context for evaluation of aggregate arguments */
@@ -1358,7 +1336,8 @@ begin_partition(WindowAggState *winstate)
winstate->framehead_valid = false;
winstate->frametail_valid = false;
winstate->grouptail_valid = false;
- create_reduced_frame_map(winstate);
+ if (rpr_is_defined(winstate))
+ clear_reduced_frame(winstate);
winstate->spooled_rows = 0;
winstate->currentpos = 0;
winstate->frameheadpos = 0;
@@ -1581,9 +1560,8 @@ release_partition(WindowAggState *winstate)
winstate->partition_spooled = false;
winstate->next_partition = true;
- /* Reset RPR reduced frame map */
- winstate->reduced_frame_map = NULL;
- winstate->alloc_sz = 0;
+ /* Reset RPR match results */
+ clear_reduced_frame(winstate);
/* Reset NFA state for new partition */
winstate->nfaContext = NULL;
@@ -2366,11 +2344,6 @@ ExecWindowAgg(PlanState *pstate)
CHECK_FOR_INTERRUPTS();
-#ifdef RPR_DEBUG
- printf("ExecWindowAgg called. pos: " INT64_FORMAT "\n",
- winstate->currentpos);
-#endif
-
if (winstate->status == WINDOWAGG_DONE)
return NULL;
@@ -2480,14 +2453,13 @@ ExecWindowAgg(PlanState *pstate)
if (winstate->status == WINDOWAGG_RUN)
{
/*
- * If RPR is defined and skip mode is next row, we need to clear
- * existing reduced frame info so that we newly calculate the info
- * starting from current row.
+ * If RPR is defined and skip mode is next row, clear the current
+ * match so the next row triggers re-evaluation.
*/
if (rpr_is_defined(winstate))
{
if (winstate->rpSkipTo == ST_NEXT_ROW)
- clear_reduced_frame_map(winstate);
+ clear_reduced_frame(winstate);
}
/*
@@ -2986,9 +2958,6 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags)
name = te->resname;
expr = te->expr;
-#ifdef RPR_DEBUG
- printf("defineVariable name: %s\n", name);
-#endif
winstate->defineVariableList =
lappend(winstate->defineVariableList,
makeString(pstrdup(name)));
@@ -3668,7 +3637,7 @@ ignorenulls_getfuncarginframe(WindowObject winobj, int argno,
int notnull_offset;
int notnull_relpos;
int forward;
- int num_reduced_frame;
+ int64 num_reduced_frame;
Assert(WindowObjectIsValid(winobj));
winstate = winobj->winstate;
@@ -3968,14 +3937,12 @@ rpr_is_defined(WindowAggState *winstate)
* AFTER MATCH SKIP PAST LAST ROW
* -----------------
*/
-static int
+static int64
row_is_in_reduced_frame(WindowObject winobj, int64 pos)
{
WindowAggState *winstate = winobj->winstate;
int state;
- int rtn;
- int64 i;
- int num_reduced_rows;
+ int64 rtn;
if (!rpr_is_defined(winstate))
{
@@ -3984,14 +3951,10 @@ row_is_in_reduced_frame(WindowObject winobj, int64 pos)
* window frame.
*/
rtn = 0;
-#ifdef RPR_DEBUG
- printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n",
- rtn, pos);
-#endif
return rtn;
}
- state = get_reduced_frame_map(winstate, pos);
+ state = get_reduced_frame_status(winstate, pos);
if (state == RF_NOT_DETERMINED)
{
@@ -3999,16 +3962,12 @@ row_is_in_reduced_frame(WindowObject winobj, int64 pos)
update_reduced_frame(winobj, pos);
}
- state = get_reduced_frame_map(winstate, pos);
+ state = get_reduced_frame_status(winstate, pos);
switch (state)
{
case RF_FRAME_HEAD:
- num_reduced_rows = 1;
- for (i = pos + 1;
- get_reduced_frame_map(winstate, i) == RF_SKIPPED; i++)
- num_reduced_rows++;
- rtn = num_reduced_rows;
+ rtn = winstate->rpr_match_length;
break;
case RF_SKIPPED:
@@ -4016,6 +3975,7 @@ row_is_in_reduced_frame(WindowObject winobj, int64 pos)
break;
case RF_UNMATCHED:
+ case RF_EMPTY_MATCH:
rtn = -1;
break;
@@ -4025,91 +3985,56 @@ row_is_in_reduced_frame(WindowObject winobj, int64 pos)
break;
}
-#ifdef RPR_DEBUG
- printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n",
- rtn, pos);
-#endif
return rtn;
}
-#define REDUCED_FRAME_MAP_INIT_SIZE 1024L
-
/*
- * create_reduced_frame_map
- * Create reduced frame map
+ * clear_reduced_frame
+ * Clear reduced frame status
*/
static void
-create_reduced_frame_map(WindowAggState *winstate)
+clear_reduced_frame(WindowAggState *winstate)
{
- winstate->reduced_frame_map =
- MemoryContextAlloc(winstate->partcontext,
- REDUCED_FRAME_MAP_INIT_SIZE);
- winstate->alloc_sz = REDUCED_FRAME_MAP_INIT_SIZE;
- clear_reduced_frame_map(winstate);
+ winstate->rpr_match_valid = false;
+ winstate->rpr_match_matched = false;
+ winstate->rpr_match_start = -1;
+ winstate->rpr_match_length = 0;
}
/*
- * clear_reduced_frame_map
- * Clear reduced frame map
- */
-static void
-clear_reduced_frame_map(WindowAggState *winstate)
-{
- Assert(winstate->reduced_frame_map != NULL);
- MemSet(winstate->reduced_frame_map, RF_NOT_DETERMINED,
- winstate->alloc_sz);
-}
-
-/*
- * get_reduced_frame_map
- * Get reduced frame map specified by pos
+ * get_reduced_frame_status
+ * Look up a position against the current match.
+ *
+ * Returns one of the RF_* constants:
+ * RF_NOT_DETERMINED pos has not been processed yet
+ * RF_FRAME_HEAD pos is the start of the current match
+ * RF_SKIPPED pos is inside the current match but not the start
+ * RF_UNMATCHED pos is processed but not part of any match
*/
static int
-get_reduced_frame_map(WindowAggState *winstate, int64 pos)
+get_reduced_frame_status(WindowAggState *winstate, int64 pos)
{
- Assert(winstate->reduced_frame_map != NULL);
- Assert(pos >= 0);
+ int64 start = winstate->rpr_match_start;
+ int64 length = winstate->rpr_match_length;
- /*
- * If pos is not in the reduced frame map, it means that any info
- * regarding the pos has not been registered yet. So we return
- * RF_NOT_DETERMINED.
- */
- if (pos >= winstate->alloc_sz)
+ if (!winstate->rpr_match_valid)
return RF_NOT_DETERMINED;
- return winstate->reduced_frame_map[pos];
-}
+ /* Empty match: covers only the start position */
+ if (pos == start && winstate->rpr_match_matched && length == 0)
+ return RF_EMPTY_MATCH;
-/*
- * register_reduced_frame_map
- * Add/replace reduced frame map member at pos.
- * If there's no enough space, expand the map.
- */
-static void
-register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val)
-{
- int64 realloc_sz;
-
- Assert(winstate->reduced_frame_map != NULL);
-
- if (pos < 0)
- elog(ERROR, "wrong pos: " INT64_FORMAT, pos);
-
- while (pos > winstate->alloc_sz - 1)
- {
- realloc_sz = winstate->alloc_sz * 2;
-
- winstate->reduced_frame_map =
- repalloc(winstate->reduced_frame_map, realloc_sz);
+ /* Outside the result range */
+ if (pos < start || pos >= start + length)
+ return RF_NOT_DETERMINED;
- MemSet(winstate->reduced_frame_map + winstate->alloc_sz,
- RF_NOT_DETERMINED, realloc_sz - winstate->alloc_sz);
+ if (!winstate->rpr_match_matched)
+ return RF_UNMATCHED;
- winstate->alloc_sz = realloc_sz;
- }
+ if (pos == start)
+ return RF_FRAME_HEAD;
- winstate->reduced_frame_map[pos] = val;
+ return RF_SKIPPED;
}
/*
@@ -4156,7 +4081,11 @@ update_reduced_frame(WindowObject winobj, int64 pos)
if (winstate->nfaContext != NULL &&
pos < winstate->nfaContext->matchStartRow)
{
- register_reduced_frame_map(winstate, pos, RF_UNMATCHED);
+ /* already processed, unmatched */
+ winstate->rpr_match_valid = true;
+ winstate->rpr_match_matched = false;
+ winstate->rpr_match_start = pos;
+ winstate->rpr_match_length = 1;
return;
}
@@ -4173,7 +4102,11 @@ update_reduced_frame(WindowObject winobj, int64 pos)
*/
if (pos <= winstate->nfaLastProcessedRow)
{
- register_reduced_frame_map(winstate, pos, RF_UNMATCHED);
+ /* already processed, unmatched */
+ winstate->rpr_match_valid = true;
+ winstate->rpr_match_matched = false;
+ winstate->rpr_match_start = pos;
+ winstate->rpr_match_length = 1;
return;
}
/* Not yet processed - create new context and start fresh */
@@ -4245,26 +4178,38 @@ register_result:
Assert(pos == targetCtx->matchStartRow);
/*
- * Register reduced frame map based on match result.
+ * Record match result.
*/
+ winstate->rpr_match_valid = true;
+ winstate->rpr_match_start = targetCtx->matchStartRow;
+
if (targetCtx->matchEndRow < targetCtx->matchStartRow)
{
matchLen = targetCtx->lastProcessedRow - targetCtx->matchStartRow + 1;
- register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_UNMATCHED);
- ExecRPRRecordContextFailure(winstate, matchLen);
+ if (targetCtx->matchedState != NULL)
+ {
+ /* Empty match: FIN reached but 0 rows consumed */
+ winstate->rpr_match_matched = true;
+ winstate->rpr_match_length = 0;
+ ExecRPRRecordContextSuccess(winstate, 0);
+ }
+ else
+ {
+ /* No match */
+ winstate->rpr_match_matched = false;
+ winstate->rpr_match_length = 1;
+ ExecRPRRecordContextFailure(winstate, matchLen);
+ }
ExecRPRFreeContext(winstate, targetCtx);
return;
}
- /* Match succeeded - register frame map and record statistics */
+ /* Match succeeded */
matchLen = targetCtx->matchEndRow - targetCtx->matchStartRow + 1;
- register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_FRAME_HEAD);
- for (int64 i = targetCtx->matchStartRow + 1; i <= targetCtx->matchEndRow; i++)
- {
- register_reduced_frame_map(winstate, i, RF_SKIPPED);
- }
+ winstate->rpr_match_matched = true;
+ winstate->rpr_match_length = matchLen;
ExecRPRRecordContextSuccess(winstate, matchLen);
/* Remove the matched context */
@@ -4747,7 +4692,7 @@ WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot,
WindowAggState *winstate;
int64 abs_pos;
int64 mark_pos;
- int num_reduced_frame;
+ int64 num_reduced_frame;
Assert(WindowObjectIsValid(winobj));
winstate = winobj->winstate;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 33028c3f10b..c672d29f35b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2499,10 +2499,12 @@ typedef enum WindowAggStatus
* tuples during spool */
} WindowAggStatus;
-#define RF_NOT_DETERMINED 0
-#define RF_FRAME_HEAD 1
-#define RF_SKIPPED 2
-#define RF_UNMATCHED 3
+/* RPR reduced frame states returned by get_reduced_frame_status() */
+#define RF_NOT_DETERMINED 0 /* not yet processed */
+#define RF_FRAME_HEAD 1 /* start row of a match */
+#define RF_SKIPPED 2 /* interior row of a match */
+#define RF_UNMATCHED 3 /* no match at this row */
+#define RF_EMPTY_MATCH 4 /* empty match (0 rows); treated as unmatched */
/*
* RPRNFAState - single NFA state for pattern matching
@@ -2694,12 +2696,11 @@ typedef struct WindowAggState
TupleTableSlot *next_slot; /* NEXT row navigation operator */
TupleTableSlot *null_slot; /* all NULL slot */
- /*
- * Each byte corresponds to a row positioned at absolute its pos in
- * partition. See above definition for RF_*. Used for RPR.
- */
- char *reduced_frame_map;
- int64 alloc_sz; /* size of the map */
+ /* RPR current match result */
+ bool rpr_match_valid; /* true if a match result is set */
+ bool rpr_match_matched; /* true if the result was a match */
+ int64 rpr_match_start; /* start position of the match result */
+ int64 rpr_match_length; /* number of rows matched (0 = empty) */
} WindowAggState;
/* ----------------
diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out
index bd345906133..79cbc246039 100644
--- a/src/test/regress/expected/rpr_explain.out
+++ b/src/test/regress/expected/rpr_explain.out
@@ -3348,8 +3348,8 @@ WINDOW w AS (
Pattern: ((a' b')+" c)*
Storage: Memory Maximum Storage: NkB
NFA States: 9 peak, 178 total, 0 merged
- NFA Contexts: 4 peak, 61 total, 22 pruned
- NFA: 1 matched (len 57/57/57.0), 0 mismatched
+ NFA Contexts: 4 peak, 61 total, 20 pruned
+ NFA: 3 matched (len 0/57/19.0), 0 mismatched
NFA: 0 absorbed, 37 skipped (len 1/3/2.0)
-> Function Scan on generate_series s (actual rows=60.00 loops=1)
(9 rows)
@@ -3385,8 +3385,8 @@ WINDOW w AS (
Pattern: (a (b c)+)*
Storage: Memory Maximum Storage: NkB
NFA States: 7 peak, 160 total, 0 merged
- NFA Contexts: 4 peak, 61 total, 22 pruned
- NFA: 1 matched (len 57/57/57.0), 0 mismatched
+ NFA Contexts: 4 peak, 61 total, 20 pruned
+ NFA: 3 matched (len 0/57/19.0), 0 mismatched
NFA: 0 absorbed, 37 skipped (len 1/3/2.0)
-> Function Scan on generate_series s (actual rows=60.00 loops=1)
(9 rows)
--
2.50.1 (Apple Git-155)