From 6055522a2cf9223bbe8987a093d5123544970d40 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 20 Jul 2026 17:07:30 +0900 Subject: [PATCH] Simplify RPR DEFINE evaluation and match-result tracking Following the 2026-07-20 review with Jian He, three related cleanups to the row pattern recognition executor: - Evaluate DEFINE predicates lazily via a tri-state nfaVarMatched cache (RPRVarMatch), so a variable no NFA state tests is never evaluated. rpr_evaluate_row becomes rpr_prepare_row; nfa_eval_var_match evaluates and caches on first consumption. - Encode the match result with rpr_match_start/length alone, dropping the rpr_match_valid and rpr_match_matched flags (start < 0 not determined; length -1 unmatched, 0 empty match, >= 1 real match). - Remove the redundant defineVariableList (only its length was used). Reviewed-by: Jian He --- src/backend/executor/README.rpr | 110 +++++++++++------- src/backend/executor/execRPR.c | 122 ++++++++++++-------- src/backend/executor/nodeWindowAgg.c | 148 +++++++++++-------------- src/backend/optimizer/plan/rpr.c | 4 +- src/include/nodes/execnodes.h | 37 +++++-- src/test/regress/expected/rpr_base.out | 22 ++++ src/test/regress/sql/rpr_base.sql | 17 +++ src/tools/pgindent/typedefs.list | 1 + 8 files changed, 277 insertions(+), 184 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 35fd4ba2b03..8d24383b0e3 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -571,7 +571,7 @@ V-3. RPR Fields of WindowAggState nfaContext / nfaContextTail Doubly-linked list of active contexts nfaContextFree Reuse pool for contexts nfaStateFree Reuse pool for states - nfaVarMatched Per-row cache: varMatched[varId] + nfaVarMatched Per-row tri-state cache: varMatched[varId] (lazy) nfaVisitedEnds Nullable ENDs reached in this DFS (cycle detection) nfaVisitedMinWord Lowest bitmapword index touched since last reset nfaVisitedMaxWord Highest bitmapword index touched since last reset @@ -612,7 +612,7 @@ Pseudocode of the row processing loop: targetCtx = ExecRPRStartContext(pos) for currentPos = startPos; targetCtx->states != NULL; currentPos++: - if not rpr_evaluate_row(currentPos): -- row does not exist + if not rpr_prepare_row(currentPos): -- row does not exist ExecRPRFinalizeAllContexts() -- finalize all contexts ExecRPRCleanupDeadContexts() -- clean up after finalization break @@ -657,14 +657,25 @@ paths, so the empty match is final. Greedy (A*): the enter path adds its VAR states before the skip path records FIN, so those states survive and may match a longer span on a later row. -VI-3. Row Evaluation: rpr_evaluate_row() +VI-3. Row Preparation: rpr_prepare_row() -Evaluates all variable conditions in the DEFINE clause at once for -the current row. +Prepares the DEFINE evaluation context for the current row. DEFINE +predicates are NOT evaluated here; each variable is evaluated lazily the +first time the NFA consumes it (Phase 1 / nfa_eval_var_match), so a +variable that no active state tests at this row is never evaluated. - for each defineClause[i]: - result = ExecEvalExpr(defineClause[i]) - varMatched[i] = (not null and true) + fetch current row into temp_slot_1 -- return false if out of partition + set ecxt_outertuple = current row + invalidate nav_slot_pos + reset nfaVarMatched[] to RPR_VAR_UNEVALUATED + +nfaVarMatched is a tri-state array (RPRVarMatch): RPR_VAR_UNEVALUATED, +RPR_VAR_TRUE, or RPR_VAR_FALSE. nfa_eval_var_match() evaluates a +variable's DEFINE on first consumption and caches the result; a NULL +result folds to RPR_VAR_FALSE (non-True is not mapped). The caller +(advance_reduced_frame_nfa) holds winstate->currentpos at the scan +position for the whole row (restored after the loop) because the deferred +navigation opcodes read currentpos. To support row navigation operators (PREV, NEXT, FIRST, LAST), a 1-slot model is used: only ecxt_outertuple is set to the current @@ -687,33 +698,44 @@ nav_slot caches the last fetched position (nav_slot_pos) to avoid redundant tuplestore lookups when multiple navigation calls target the same row. -The varMatched array is referenced later in Phase 1 (Match). +The nfaVarMatched entries are filled lazily during Phase 1 (Match) as +variables are consumed. -VI-4. Per-Context Re-evaluation (match_start_dependent variables) +VI-4. Per-Context Invalidation (match_start_dependent variables) DEFINE variables that depend on match_start (those containing FIRST, LAST-with-offset, or compound PREV_FIRST/NEXT_FIRST/PREV_LAST/NEXT_LAST) -are identified at plan time via defineMatchStartDependent. The shared -evaluation in rpr_evaluate_row() uses the head context's matchStartRow -for FIRST/LAST base position. - -When processing a context whose matchStartRow differs from the shared -value, nfa_reevaluate_dependent_vars() temporarily sets nav_match_start -to that context's matchStartRow and re-evaluates only the dependent -variables. The original nav_match_start and currentpos are saved and -restored after re-evaluation. - -Summary of evaluation strategy by navigation content: +are identified at plan time via defineMatchStartDependent. For the head +context, advance_reduced_frame_nfa sets nav_match_start to its +matchStartRow before matching, so lazy evaluation uses the correct +FIRST/LAST base position. + +When processing a context whose matchStartRow differs, +nfa_reevaluate_dependent_vars() resets only the dependent variables to +RPR_VAR_UNEVALUATED so they are re-evaluated lazily against this context's +matchStartRow, installs nav_match_start to that value, and invalidates the +nav_slot cache. match_start-independent variables keep their cached value +across contexts (they do not read nav_match_start). + +nav_match_start is left installed and NOT restored: FIRST/LAST read it at +evaluation time, which happens later during nfa_match(); the next +context's invalidation or the next row's setup overwrites it. The +function also resets rprContext so one context's DEFINE scratch does not +accumulate across every context of a row. + +Summary of evaluation strategy by navigation content (a variable is +evaluated once per row and cached, except dependent ones which are +re-evaluated once per differing context): Navigation content evaluation ------------------------------------------------------- - No navigation shared (once per row) - PREV/NEXT only shared (once per row) - LAST (no offset) shared (once per row) + No navigation cached (once per row) + PREV/NEXT only cached (once per row) + LAST (no offset) cached (once per row) LAST (with offset) per-context FIRST (any) per-context Compound (inner FIRST) per-context - Compound (inner LAST, no off.) shared (once per row) + Compound (inner LAST, no off.) cached (once per row) Compound (inner LAST, w/off.) per-context VI-5. Tuplestore Mark and Trim (nodeWindowAgg.c) @@ -777,7 +799,7 @@ nfa_match() iterates through each state in the context: Match determination (nfa_eval_var_match): - If varId is within the range of defineVariableList: + If varId is within the range of defineClauseExprs: Use the value of varMatched[varId] If varId exceeds the range (variable not defined in DEFINE): @@ -1180,13 +1202,12 @@ Chapter X Match Result Processing X-1. Match Result 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). +with two fields: rpr_match_start and rpr_match_length. When +rpr_match_start is >= 0 the entry describes the result for that position, +and rpr_match_length gives the kind: -1 for an unmatched row, 0 for an +empty match (pattern matched but consumed no rows), and >= 1 for a real +match of that many rows. When rpr_match_start is < 0, the position has +not been evaluated yet (RF_NOT_DETERMINED). A row's status against the current match result can be obtained by calling get_reduced_frame_status(). @@ -1281,6 +1302,11 @@ XI-3. Compilation Result XI-4. Execution Trace +The trace lists every variable's DEFINE value together for readability. In +the lazy model each variable is evaluated only when a state consumes it +(nfa_eval_var_match); a variable no state tests at a row stays +RPR_VAR_UNEVALUATED. + --- Row 0 (price=100) --- update_reduced_frame(0) called. @@ -1289,7 +1315,7 @@ XI-4. Execution Trace Initial advance: elemIdx=0(A) -> VAR, so state is added. C0.states = [{elemIdx=0, counts=[0]}] - rpr_evaluate_row(0): + DEFINE values, row 0: A: price(100) > PREV(price) -> no PREV -> false B: price(100) < PREV(price) -> no PREV -> false varMatched = [false, false] @@ -1311,7 +1337,7 @@ XI-4. Execution Trace Context C1 created (matchStartRow=1). Initial advance: C1.states = [{elemIdx=0, counts=[0]}] - rpr_evaluate_row(1): + DEFINE values, row 1: A: 110 > PREV(100) -> true B: 110 < PREV(100) -> false varMatched = [true, false] @@ -1333,7 +1359,7 @@ XI-4. Execution Trace Context C2 created (matchStartRow=2). Initial advance: C2.states = [{elemIdx=0, counts=[0]}] - rpr_evaluate_row(2): + DEFINE values, row 2: A: 120 > PREV(110) -> true B: 120 < PREV(110) -> false varMatched = [true, false] @@ -1365,7 +1391,7 @@ XI-4. Execution Trace --- Row 3 (price=115) --- - rpr_evaluate_row(3): + DEFINE values, row 3: A: 115 > PREV(120) -> false B: 115 < PREV(120) -> true varMatched = [false, true] @@ -1394,7 +1420,7 @@ XI-4. Execution Trace C3 was already created but matchStartRow=3, so it is not applicable. New context C4 created (matchStartRow=4). - rpr_evaluate_row(4): + DEFINE values, row 4: A: 130 > PREV(115) -> true B: 130 < PREV(115) -> false @@ -1570,7 +1596,8 @@ Appendix A. Key Function Index finalizeRPRPattern rpr.c Finalization computeAbsorbability rpr.c Absorption analysis update_reduced_frame nodeWindowAgg.c Execution main loop - rpr_evaluate_row nodeWindowAgg.c DEFINE evaluation + rpr_prepare_row nodeWindowAgg.c Row prep (lazy DEFINE) + nfa_eval_var_match execRPR.c Lazy DEFINE evaluation ExecRPRStartContext execRPR.c Context creation ExecRPRProcessRow execRPR.c 3-phase processing nfa_match execRPR.c Phase 1 @@ -1631,9 +1658,8 @@ Appendix B. Data Structure Relationship Diagram WindowAggState |--- rpSkipTo: RPSkipTo (AFTER MATCH SKIP mode) |--- rpPattern: RPRPattern* (copied from plan) - |--- defineVariableList: List (variable names, DEFINE order) - |--- defineClauseExprs: List - |--- nfaVarMatched: bool[] (per-row cache) + |--- defineClauseExprs: List (DEFINE order, index == varId) + |--- nfaVarMatched: RPRVarMatch[] (per-row tri-state cache, lazy) |--- defineMatchStartDependent: Bitmapset* (match_start_dependent | DEFINE vars; see VI-4) |--- nfaVisitedEnds: bitmapword* (cycle detection) diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index da91a4152f3..48d01e4a50a 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -80,9 +80,9 @@ static void nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx) static void nfa_absorb_contexts(WindowAggState *winstate); static bool nfa_eval_var_match(WindowAggState *winstate, - RPRPatternElement *elem, bool *varMatched); + RPRPatternElement *elem, RPRVarMatch *varMatched); static void nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, - bool *varMatched, int64 currentPos); + RPRVarMatch *varMatched, int64 currentPos); static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, RPRPatternElement *nextElem, int64 currentPos); @@ -798,10 +798,18 @@ nfa_absorb_contexts(WindowAggState *winstate) * * Evaluate if a VAR element matches the current row. * - * varMatched is a pre-evaluated boolean array indexed by varId, computed - * once per row by evaluating all DEFINE expressions. A NULL varMatched makes - * every VAR not match; nfa_match() is called that way to force a mismatch at a - * frame boundary and at partition-end finalization. + * varMatched is a per-row tri-state cache indexed by varId. Evaluation is + * lazy: the variable's DEFINE predicate is evaluated here the first time the + * NFA consumes the variable (cache is RPR_VAR_UNEVALUATED), then cached, so a + * variable that no active state tests at this row is never evaluated. This + * matches ISO/IEC 19075-5, where a Boolean condition is evaluated only with + * the current row tentatively mapped to that variable. A NULL varMatched + * makes every VAR not match; nfa_match() is called that way to force a + * mismatch at a frame boundary and at partition-end finalization. + * + * The caller must have set up the current row (ecxt_outertuple, currentpos, + * nav_match_start, nav_slot cache) via rpr_prepare_row() / + * nfa_reevaluate_dependent_vars() before consumption. * * Per ISO/IEC 19075-5 Feature R020, pattern variables not listed in DEFINE * are implicitly TRUE -- they match every row. This is checked via @@ -809,16 +817,33 @@ nfa_absorb_contexts(WindowAggState *winstate) */ static bool nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, - bool *varMatched) + RPRVarMatch *varMatched) { + int varId; + /* This function should only be called for VAR elements */ Assert(RPRElemIsVar(elem)); if (varMatched == NULL) return false; - if (elem->varId >= list_length(winstate->defineVariableList)) + + varId = elem->varId; + if (varId >= list_length(winstate->defineClauseExprs)) return true; - return varMatched[elem->varId]; + + /* Lazily evaluate this variable's DEFINE predicate on first consumption. */ + if (varMatched[varId] == RPR_VAR_UNEVALUATED) + { + ExprState *exprState = list_nth(winstate->defineClauseExprs, varId); + Datum result; + bool isnull; + + result = ExecEvalExpr(exprState, winstate->rprContext, &isnull); + varMatched[varId] = (!isnull && DatumGetBool(result)) ? + RPR_VAR_TRUE : RPR_VAR_FALSE; + } + + return (varMatched[varId] == RPR_VAR_TRUE); } /* @@ -846,7 +871,7 @@ nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, * consumer yet. */ static void -nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched, +nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, RPRVarMatch *varMatched, int64 currentPos) { RPRPattern *pattern = winstate->rpPattern; @@ -1651,50 +1676,49 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) /* * nfa_reevaluate_dependent_vars - * Re-evaluate match_start-dependent DEFINE variables for a specific - * context whose matchStartRow differs from the shared evaluation's - * nav_match_start. - * - * Only variables in defineMatchStartDependent are re-evaluated. The - * current row's slot (ecxt_outertuple) must already be set up by - * rpr_evaluate_row(). + * Invalidate match_start-dependent DEFINE variables for a context whose + * matchStartRow differs from the shared evaluation's nav_match_start. + * + * Only variables in defineMatchStartDependent are affected: they are reset to + * RPR_VAR_UNEVALUATED so nfa_match() re-evaluates them lazily against this + * context's matchStartRow. match_start-independent variables keep their + * cached value across contexts, since they do not read nav_match_start. + * + * nav_match_start is installed for this context and left in place: FIRST/LAST + * read it at evaluation time, which now happens later during nfa_match(), so + * it must NOT be restored here (unlike the former eager version). The next + * context's invalidation, or the next row's shared setup in + * advance_reduced_frame_nfa, overwrites it. */ static void nfa_reevaluate_dependent_vars(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) { - ExprContext *econtext = winstate->rprContext; - int64 saved_match_start = winstate->nav_match_start; - int64 saved_pos = winstate->currentpos; + int varIdx = -1; + + /* Caller keeps winstate->currentpos at the scan position for lazy eval. */ + Assert(winstate->currentpos == currentPos); - /* Release the previous evaluation's DEFINE expression memory */ - ResetExprContext(econtext); + /* + * Release the previous context's DEFINE evaluation memory. Match-start- + * dependent variables are re-evaluated once per context (they are reset + * to UNEVALUATED below), so without this reset their per-tuple scratch + * would accumulate across every context of a row -- bounded only by the + * per-row reset in rpr_prepare_row. rprContext is the dedicated DEFINE + * context, so this frees neither the input nor the output tuple memory. + */ + ResetExprContext(winstate->rprContext); - /* Temporarily set nav_match_start and currentpos for FIRST/LAST */ + /* Install this context's match_start for FIRST/LAST and keep it in place. */ winstate->nav_match_start = ctx->matchStartRow; - winstate->currentpos = currentPos; /* Invalidate nav_slot cache since match_start changed */ winstate->nav_slot_pos = -1; - foreach_ptr(ExprState, exprState, winstate->defineClauseExprs) - { - int varIdx = foreach_current_index(exprState); - - if (bms_is_member(varIdx, winstate->defineMatchStartDependent)) - { - Datum result; - bool isnull; - - result = ExecEvalExpr(exprState, econtext, &isnull); - winstate->nfaVarMatched[varIdx] = (!isnull && DatumGetBool(result)); - } - } - - /* Restore original match_start, currentpos, and invalidate cache */ - winstate->nav_match_start = saved_match_start; - winstate->currentpos = saved_pos; - winstate->nav_slot_pos = -1; + /* Reset only the dependent variables so they re-evaluate lazily. */ + while ((varIdx = bms_next_member(winstate->defineMatchStartDependent, + varIdx)) >= 0) + winstate->nfaVarMatched[varIdx] = RPR_VAR_UNEVALUATED; } @@ -1860,7 +1884,7 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, bool hasLimitedFrame, int64 frameOffset) { RPRNFAContext *ctx; - bool *varMatched = winstate->nfaVarMatched; + RPRVarMatch *varMatched = winstate->nfaVarMatched; bool hasDependent = !bms_is_empty(winstate->defineMatchStartDependent); /* Allow query cancellation once per row for simple/low-state patterns */ @@ -1911,12 +1935,14 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, /* * If this context has a different matchStartRow than the one used in - * the shared evaluation, re-evaluate match_start-dependent variables - * with this context's matchStartRow. + * the shared evaluation, invalidate its match_start-dependent + * variables so nfa_match() re-evaluates them lazily with this + * context's matchStartRow. * - * Re-evaluation overwrites nfaVarMatched without restoring it, so the - * head context, which the shared values are keyed on, must be reached - * before any other. + * The head context carries no explicit invalidation: it relies on the + * ambient nav_match_start installed by advance_reduced_frame_nfa, so + * it must be reached before any other context overwrites + * nav_match_start. */ Assert(ctx != winstate->nfaContext || ctx->matchStartRow == winstate->nav_match_start); diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 71f27995244..0688d4e7b46 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -247,7 +247,7 @@ static void advance_reduced_frame_nfa(WindowObject winobj, static void update_reduced_frame(WindowObject winobj, int64 pos); /* Forward declarations - DEFINE row evaluation */ -static bool rpr_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched); +static bool rpr_prepare_row(WindowObject winobj, int64 pos, RPRVarMatch *varMatched); /* Forward declarations - navigation offset evaluation */ static void eval_define_offsets(WindowAggState *winstate, List *defineClause); @@ -3066,23 +3066,18 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) } /* Set up row pattern recognition DEFINE clause */ - winstate->defineVariableList = NIL; winstate->defineClauseExprs = NIL; /* * Compile DEFINE clause expressions. PREV/NEXT navigation is handled by * EEOP_RPR_NAV_SET/RESTORE opcodes emitted during ExecInitExpr, so no - * varno rewriting is needed here. + * varno rewriting is needed here. Expressions are kept in DEFINE order, + * so their list index equals the variable's varId. */ foreach_node(TargetEntry, te, node->defineClause) { - char *name = te->resname; ExprState *exprstate; - winstate->defineVariableList = - lappend(winstate->defineVariableList, - makeString(pstrdup(name))); - exprstate = ExecInitExpr(te->expr, (PlanState *) winstate); winstate->defineClauseExprs = @@ -3103,9 +3098,9 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) * ordering (DEFINE order first), varId == defineIdx for all defined * variables, so no mapping is needed. */ - if (winstate->defineVariableList != NIL) - winstate->nfaVarMatched = palloc0(sizeof(bool) * - list_length(winstate->defineVariableList)); + if (winstate->defineClauseExprs != NIL) + winstate->nfaVarMatched = palloc0(sizeof(RPRVarMatch) * + list_length(winstate->defineClauseExprs)); else winstate->nfaVarMatched = NULL; winstate->all_first = true; @@ -4311,10 +4306,8 @@ ensure_reduced_frame(WindowObject winobj, int64 pos) static void clear_reduced_frame(WindowAggState *winstate) { - winstate->rpr_match_valid = false; - winstate->rpr_match_matched = false; - winstate->rpr_match_start = -1; - winstate->rpr_match_length = 0; + winstate->rpr_match_start = -1; /* start < 0: no result determined yet */ + winstate->rpr_match_length = -1; } /* @@ -4328,14 +4321,16 @@ clear_reduced_frame(WindowAggState *winstate) * RF_UNMATCHED pos is processed but not part of any match * RF_EMPTY_MATCH pos is the start of an empty (zero-length) match * - * update_reduced_frame() records the current match as exactly one of three - * (rpr_match_matched, rpr_match_length) shapes: (false, 1) for unmatched, - * (true, 0) for an empty match, and (true, >= 1) for a real match. The - * tests below form a cascade with early returns: each is a minimal check - * that relies on the negations the preceding returns have already - * established, so their order is significant. The "by here" notes spell - * out the running invariant; reordering a test would misclassify one of - * the three shapes. + * The result slot encodes four states across two fields, with no separate + * "valid"/"matched" flags: + * + * start < 0 not determined (cleared slot) + * start >= 0, length == -1 unmatched (covers only the start row) + * start >= 0, length == 0 empty match (zero-length match at start) + * start >= 0, length >= 1 real match spanning [start, start + length) + * + * The tests below form a cascade with early returns, so their order is + * significant. */ static int get_reduced_frame_status(WindowAggState *winstate, int64 pos) @@ -4343,34 +4338,27 @@ get_reduced_frame_status(WindowAggState *winstate, int64 pos) int64 start = winstate->rpr_match_start; int64 length = winstate->rpr_match_length; - if (!winstate->rpr_match_valid) - return RF_NOT_DETERMINED; + if (start < 0) + return RF_NOT_DETERMINED; /* cleared slot: no result recorded yet */ /* - * By here the record is valid and holds one of the three shapes above. - * - * The empty match (true, 0) must be classified first: it has length 0, so - * the range test below would compute start + length == start and reject - * its own start position as out of range. + * Unmatched (length -1) and empty match (length 0) do not describe a + * positive-length range, so they are classified before the range test. + * Each covers only its own start row; any other position is not part of + * this record and is still undetermined. */ - if (pos == start && winstate->rpr_match_matched && length == 0) - return RF_EMPTY_MATCH; + if (length == -1) + return (pos == start) ? RF_UNMATCHED : RF_NOT_DETERMINED; + if (length == 0) + return (pos == start) ? RF_EMPTY_MATCH : RF_NOT_DETERMINED; /* - * By here length >= 1 -- the only zero-length record, the empty match, - * has been handled -- so [start, start + length) is a well-formed range. + * By here length >= 1, so [start, start + length) is a well-formed range. */ if (pos < start || pos >= start + length) return RF_NOT_DETERMINED; - /* - * By here pos lies within [start, start + length). An unmatched record - * is (false, 1), so this returns for its single in-range position. - */ - if (!winstate->rpr_match_matched) - return RF_UNMATCHED; - - /* By here the match is real (true, >= 1) and pos is one of its rows. */ + /* pos lies within a real match. */ if (pos == start) return RF_FRAME_HEAD; @@ -4447,6 +4435,7 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, WindowAggState *winstate = winobj->winstate; int64 currentPos; int64 startPos; + int64 saved_currentpos = winstate->currentpos; /* * Determine where to start processing. Usually nfaLastProcessedRow+1 >= @@ -4459,6 +4448,12 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, /* * Process rows until target context completes or we hit boundaries. Each * row evaluation is shared across all active contexts. + * + * winstate->currentpos is set to the scan position for the whole row and + * left in place across ExecRPRProcessRow, because DEFINE predicates are + * now evaluated lazily during matching (nfa_eval_var_match) and their + * EEOP_RPR_NAV_SET opcodes read currentpos. It is restored after the + * loop. */ for (currentPos = startPos; targetCtx->states != NULL; currentPos++) { @@ -4473,8 +4468,9 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, * LAST-with-offset) are re-evaluated per-context in ExecRPRProcessRow * when matchStartRow differs. */ + winstate->currentpos = currentPos; winstate->nav_match_start = targetCtx->matchStartRow; - rowExists = rpr_evaluate_row(winobj, currentPos, winstate->nfaVarMatched); + rowExists = rpr_prepare_row(winobj, currentPos, winstate->nfaVarMatched); /* No more rows in partition? Finalize all contexts */ if (!rowExists) @@ -4512,6 +4508,9 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, /* Advance the nav mark to the frontier so trim can free old rows. */ advance_nav_mark(winstate, currentPos); } + + /* Restore the output row position borrowed for the NFA scan. */ + winstate->currentpos = saved_currentpos; } /* @@ -4557,10 +4556,8 @@ update_reduced_frame(WindowObject winobj, int64 pos) pos < winstate->nfaContext->matchStartRow) { /* already processed, unmatched */ - winstate->rpr_match_valid = true; - winstate->rpr_match_matched = false; winstate->rpr_match_start = pos; - winstate->rpr_match_length = 1; + winstate->rpr_match_length = -1; return; } @@ -4578,10 +4575,8 @@ update_reduced_frame(WindowObject winobj, int64 pos) if (pos <= winstate->nfaLastProcessedRow) { /* already processed, unmatched */ - winstate->rpr_match_valid = true; - winstate->rpr_match_matched = false; winstate->rpr_match_start = pos; - winstate->rpr_match_length = 1; + winstate->rpr_match_length = -1; return; } /* Not yet processed - create new context and start fresh */ @@ -4606,9 +4601,10 @@ register_result: Assert(pos == targetCtx->matchStartRow); /* - * Record match result. + * Record match result. A determined slot has rpr_match_start >= 0; the + * length then gives the kind: -1 unmatched, 0 empty match, >= 1 real + * match. A cleared slot keeps rpr_match_start < 0. */ - winstate->rpr_match_valid = true; winstate->rpr_match_start = targetCtx->matchStartRow; if (targetCtx->matchEndRow < targetCtx->matchStartRow) @@ -4618,15 +4614,13 @@ register_result: 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; + winstate->rpr_match_length = -1; ExecRPRRecordContextFailure(winstate, matchLen); } ExecRPRFreeContext(winstate, targetCtx); @@ -4636,7 +4630,6 @@ register_result: /* Match succeeded */ matchLen = targetCtx->matchEndRow - targetCtx->matchStartRow + 1; - winstate->rpr_match_matched = true; winstate->rpr_match_length = matchLen; ExecRPRRecordContextSuccess(winstate, matchLen); @@ -4645,24 +4638,29 @@ register_result: } /* - * rpr_evaluate_row + * rpr_prepare_row * - * Evaluate all DEFINE variables for current row. + * Prepare the DEFINE evaluation context for the current row and reset the + * per-row tri-state cache to RPR_VAR_UNEVALUATED. * Returns true if the row exists, false if out of partition. - * If row exists, fills varMatched array. - * varMatched[i] = true if variable i matched at current row. + * + * DEFINE predicates are NOT evaluated here. Each variable is evaluated lazily + * the first time the NFA consumes it (nfa_eval_var_match), so a variable that + * no active state tests at this row is never evaluated. The caller + * (advance_reduced_frame_nfa) sets winstate->currentpos to pos for the whole + * row, so the deferred evaluation's EEOP_RPR_NAV_SET opcodes calculate target + * positions (currentpos +/- offset) correctly. * * Uses 1-slot model: only ecxt_outertuple is set to the current row. * PREV/NEXT/FIRST/LAST navigation is handled by EEOP_RPR_NAV_SET/RESTORE * opcodes during expression evaluation, which temporarily swap the slot. */ static bool -rpr_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched) +rpr_prepare_row(WindowObject winobj, int64 pos, RPRVarMatch *varMatched) { WindowAggState *winstate = winobj->winstate; ExprContext *econtext = winstate->rprContext; TupleTableSlot *slot; - int64 saved_pos; /* Release the previous row's DEFINE evaluation memory */ ResetExprContext(econtext); @@ -4675,29 +4673,16 @@ rpr_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched) /* Set up 1-slot context: only ecxt_outertuple */ econtext->ecxt_outertuple = slot; - /* - * Save and set currentpos so that EEOP_RPR_NAV_SET opcodes can calculate - * target positions (currentpos +/- offset). - */ - saved_pos = winstate->currentpos; - winstate->currentpos = pos; - /* Invalidate nav_slot cache so PREV/NEXT re-fetch for new row */ winstate->nav_slot_pos = -1; - foreach_ptr(ExprState, exprState, winstate->defineClauseExprs) - { - int varIdx = foreach_current_index(exprState); - Datum result; - bool isnull; - - /* Evaluate DEFINE expression */ - result = ExecEvalExpr(exprState, econtext, &isnull); - - varMatched[varIdx] = (!isnull && DatumGetBool(result)); - } - - winstate->currentpos = saved_pos; + /* + * Reset the per-row cache to "unevaluated"; each variable's DEFINE is + * evaluated lazily at first consumption in nfa_eval_var_match. + */ + if (varMatched != NULL) + memset(varMatched, 0, + sizeof(RPRVarMatch) * list_length(winstate->defineClauseExprs)); return true; /* Row exists */ } @@ -4883,6 +4868,7 @@ WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot, num_reduced_frame = row_is_in_reduced_frame(winobj, winstate->frameheadpos); + /* TODO: 0: non-RPR window, no reduced frame */ if (num_reduced_frame < 0) goto out_of_frame; else if (num_reduced_frame > 0) diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index bfcbd5d567a..3462e9a922e 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -1108,8 +1108,8 @@ scanRPRPatternRecursive(RPRPatternNode *node, char **varNames, int *numVars, /* * Variable not in DEFINE clause - this is valid per ISO/IEC * 19075-5 Feature R020. Such variables are implicitly TRUE. Add - * to varNames so they get a varId >= defineVariableList length, - * which executor treats as TRUE. + * to varNames so they get a varId >= the number of DEFINE clause + * expressions, which executor treats as TRUE. */ Assert(*numVars <= RPR_VARID_MAX); varNames[(*numVars)++] = node->varName; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index f8c95b76ed2..84844a2ea6c 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2593,6 +2593,21 @@ typedef struct NFALengthStats int64 total; /* total length (for computing average) */ } NFALengthStats; +/* + * Tri-state result of a DEFINE predicate for one row pattern variable at the + * current row. RPR_VAR_UNEVALUATED is the "not yet evaluated" sentinel and + * must be zero so palloc0 initializes the per-row cache to it; the DEFINE is + * evaluated lazily at the point the NFA first consumes the variable (see + * nfa_eval_var_match). A NULL DEFINE result folds to RPR_VAR_FALSE + * (non-True = not mapped, per ISO/IEC 19075-5). + */ +typedef enum RPRVarMatch +{ + RPR_VAR_UNEVALUATED = 0, /* not yet evaluated (sentinel) */ + RPR_VAR_FALSE, /* evaluated to non-True (FALSE or NULL) */ + RPR_VAR_TRUE, /* evaluated to True */ +} RPRVarMatch; + typedef struct WindowAggState { ScanState ss; /* its first field is NodeTag */ @@ -2655,18 +2670,17 @@ typedef struct WindowAggState /* these fields are used in Row pattern recognition: */ RPSkipTo rpSkipTo; /* Row Pattern Skip To type */ struct RPRPattern *rpPattern; /* compiled pattern for NFA execution */ - List *defineVariableList; /* list of row pattern definition - * variables (list of String) */ - List *defineClauseExprs; /* expression for row pattern definition - * search conditions ExprState list */ + List *defineClauseExprs; /* row pattern DEFINE search conditions as + * an ExprState list, in DEFINE order + * (list index == varId) */ RPRNFAContext *nfaContext; /* active matching contexts (head) */ RPRNFAContext *nfaContextTail; /* tail of active contexts (for reverse * traversal) */ RPRNFAContext *nfaContextFree; /* recycled NFA context nodes */ RPRNFAState *nfaStateFree; /* recycled NFA state nodes */ Size nfaStateSize; /* pre-calculated RPRNFAState size */ - bool *nfaVarMatched; /* per-row cache: varMatched[varId] for varId - * < numDefines */ + RPRVarMatch *nfaVarMatched; /* per-row tri-state cache: varMatched[varId] + * for varId < numDefines, evaluated lazily */ Bitmapset *defineMatchStartDependent; /* DEFINE vars needing per-context * evaluation * (match_start-dependent) */ @@ -2732,7 +2746,7 @@ typedef struct WindowAggState bool hasFirstNav; /* FIRST() present in DEFINE */ RPRNavOffsetKind navFirstOffsetKind; /* status of navFirstOffset */ int64 navFirstOffset; /* min FIRST() offset (when FIXED) */ - struct WindowObjectData *nav_winobj; /* winobj for RPR nav fetch */ + struct WindowObjectData *nav_winobj; /* winobj for RPR */ int64 nav_slot_pos; /* position cached in nav_slot, or -1 */ TupleTableSlot *nav_slot; /* slot for PREV/NEXT/FIRST/LAST target row */ TupleTableSlot *nav_saved_outertuple; /* saved slot during nav swap */ @@ -2740,10 +2754,11 @@ typedef struct WindowAggState int64 nav_match_start; /* match_start for FIRST/LAST nav */ /* 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) */ + int64 rpr_match_start; /* start of the result; < 0 = not + * determined */ + int64 rpr_match_length; /* result kind when start >= 0: -1 + * unmatched, 0 empty match, >= 1 real + * match length */ } WindowAggState; /* ---------------- diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index d9b73464690..54fa490a4e1 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -433,6 +433,28 @@ ERROR: DEFINE variable "b" is not used in PATTERN LINE 7: DEFINE A AS id > 0, B AS id > 5 -- B not in pattern ^ DROP TABLE rpr_unused; +-- A DEFINE predicate is evaluated only when its variable is tentatively +-- mapped. A is false at every row, so B is never reached; B's condition +-- (which would divide by zero) must never run, and every row is unmatched. +CREATE TABLE rpr_lazy (id INT, v INT); +INSERT INTO rpr_lazy VALUES (1, 1), (2, 2), (3, 3); +SELECT id, v, count(*) OVER w AS cnt +FROM rpr_lazy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B) + DEFINE A AS v < 0, B AS 1 / (v - v) > 0 +) +ORDER BY id; + id | v | cnt +----+---+----- + 1 | 1 | 0 + 2 | 2 | 0 + 3 | 3 | 0 +(3 rows) + +DROP TABLE rpr_lazy; -- ============================================================ -- FRAME Options Tests -- ============================================================ diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index 0e08f97adb8..33856187d62 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -354,6 +354,23 @@ ORDER BY id; DROP TABLE rpr_unused; +-- A DEFINE predicate is evaluated only when its variable is tentatively +-- mapped. A is false at every row, so B is never reached; B's condition +-- (which would divide by zero) must never run, and every row is unmatched. +CREATE TABLE rpr_lazy (id INT, v INT); +INSERT INTO rpr_lazy VALUES (1, 1), (2, 2), (3, 3); +SELECT id, v, count(*) OVER w AS cnt +FROM rpr_lazy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B) + DEFINE A AS v < 0, B AS 1 / (v - v) > 0 +) +ORDER BY id; + +DROP TABLE rpr_lazy; + -- ============================================================ -- FRAME Options Tests -- ============================================================ diff --git a/src/tools/pgindent/typedefs.list b/src/tools/pgindent/typedefs.list index 11888d86b35..0bc36d9fccc 100644 --- a/src/tools/pgindent/typedefs.list +++ b/src/tools/pgindent/typedefs.list @@ -2551,6 +2551,7 @@ RPRPatternNode RPRPatternNodeType RPRQuantity RPRVarId +RPRVarMatch RPSkipTo RTEKind RTEPermissionInfo -- 2.50.1 (Apple Git-155)