From 24a19226ef1fe100fc1680b178103e997c0c48bb Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Thu, 2 Apr 2026 14:09:12 +0900 Subject: [PATCH] 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. --- src/backend/executor/execRPR.c | 56 +++--- src/backend/executor/nodeWindowAgg.c | 221 ++++++++-------------- src/include/nodes/execnodes.h | 21 +- src/test/regress/expected/rpr_explain.out | 8 +- 4 files changed, 126 insertions(+), 180 deletions(-) diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index 58f9da0b814..1cbe8e14780 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 valid is true, the entry describes the + * match result for the position at rpr_match_start: matched indicates + * success or failure, and length gives the number of rows consumed. + * A match with length 0 represents an empty match (pattern matched but + * consumed no rows). When 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. + * The window function calls get_reduced_frame_status() to look up a + * row's status against the current match result. * * 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..1c925e0221d 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -249,11 +249,8 @@ 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 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); @@ -1037,12 +1034,6 @@ eval_windowaggregates(WindowAggState *winstate) { int ret; -#ifdef RPR_DEBUG - printf("===== loop in frame starts: aggregatedupto: " INT64_FORMAT " aggregatedbase: " INT64_FORMAT "\n", - winstate->aggregatedupto, - winstate->aggregatedbase); -#endif - /* 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))); @@ -3974,8 +3943,6 @@ row_is_in_reduced_frame(WindowObject winobj, int64 pos) WindowAggState *winstate = winobj->winstate; int state; int rtn; - int64 i; - int num_reduced_rows; 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 - */ -static void -create_reduced_frame_map(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); -} - /* - * clear_reduced_frame_map - * Clear reduced frame map + * clear_reduced_frame + * Clear reduced frame status */ static void -clear_reduced_frame_map(WindowAggState *winstate) +clear_reduced_frame(WindowAggState *winstate) { - Assert(winstate->reduced_frame_map != NULL); - MemSet(winstate->reduced_frame_map, RF_NOT_DETERMINED, - winstate->alloc_sz); + winstate->rpr_match_valid = false; + winstate->rpr_match_matched = false; + winstate->rpr_match_start = -1; + winstate->rpr_match_length = 0; } /* - * 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]; -} - -/* - * 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); + /* Empty match: covers only the start position */ + if (pos == start && winstate->rpr_match_matched && length == 0) + return RF_EMPTY_MATCH; - 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 */ 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)