From 4f60cf63ecba451ddac29448ea0406228ed4ce9b Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 20 Jul 2026 17:07:30 +0900 Subject: [PATCH] Evaluate an RPR DEFINE only where the NFA maps its variable Every DEFINE predicate was evaluated at every row, so a query could fail on a predicate that took no part in any match: with PATTERN (A B) and A false at every row, B's condition still ran, and one that divides by zero ended the query. ISO/IEC 19075-5 evaluates a Boolean condition only with the current row tentatively mapped to that variable, so a variable no state tests need not be evaluated at all. Skipping one loses no observable side effect either, because the planner already rejects a volatile DEFINE. Evaluate lazily instead, through a tri-state cache (RPRVarMatch) that nfa_eval_var_match fills on first consumption. rpr_evaluate_row becomes rpr_prepare_row, which sets the row up and clears the cache, and nfa_reevaluate_dependent_vars resets the match_start-dependent variables rather than re-evaluating them. winstate->currentpos is held at the scan position across the whole ExecRPRProcessRow call, since the navigation opcodes now read it during matching. Two cleanups ride along. The match result loses its rpr_match_valid and rpr_match_matched flags, which rpr_match_start and rpr_match_length carry between them (start < 0 not determined; length -1 unmatched, 0 empty match, >= 1 real match). defineVariableList goes away: only its length was read, and defineClauseExprs has that. README.rpr VI-3, VI-4 and X-1 follow the lazy model, and rpr_base gains the query above. Reviewed-by: Jian He --- src/backend/executor/README.rpr | 110 +++++++++++------- src/backend/executor/execRPR.c | 121 ++++++++++++-------- src/backend/executor/nodeWindowAgg.c | 148 +++++++++++-------------- src/backend/optimizer/plan/rpr.c | 4 +- src/include/nodes/execnodes.h | 38 +++++-- 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 5b64e0b96a5..0111382f5c4 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -599,7 +599,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 @@ -640,7 +640,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 @@ -685,14 +685,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 @@ -715,33 +726,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) @@ -805,7 +827,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): @@ -1230,13 +1252,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(). @@ -1331,6 +1352,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. @@ -1339,7 +1365,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] @@ -1361,7 +1387,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] @@ -1383,7 +1409,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] @@ -1415,7 +1441,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] @@ -1444,7 +1470,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 @@ -1620,7 +1646,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 @@ -1681,9 +1708,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 e2468fee047..a233d6d5649 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); @@ -813,10 +813,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 @@ -824,16 +832,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); } /* @@ -863,7 +888,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; @@ -1677,50 +1702,48 @@ 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 happens later during nfa_match(), so it + * must NOT be restored here. 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; } @@ -1888,7 +1911,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 */ @@ -1939,12 +1962,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 e9d2c86305a..0828fdd5f8c 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -246,7 +246,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); @@ -3062,23 +3062,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 = @@ -3099,9 +3094,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; @@ -4306,10 +4301,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; } /* @@ -4323,14 +4316,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) @@ -4338,34 +4333,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; @@ -4442,6 +4430,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 >= @@ -4454,6 +4443,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 + * 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++) { @@ -4468,8 +4463,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) @@ -4507,6 +4503,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; } /* @@ -4552,10 +4551,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; } @@ -4573,10 +4570,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 */ @@ -4601,9 +4596,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) @@ -4613,15 +4609,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); @@ -4631,7 +4625,6 @@ register_result: /* Match succeeded */ matchLen = targetCtx->matchEndRow - targetCtx->matchStartRow + 1; - winstate->rpr_match_matched = true; winstate->rpr_match_length = matchLen; ExecRPRRecordContextSuccess(winstate, matchLen); @@ -4640,24 +4633,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); @@ -4670,29 +4668,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 */ } @@ -4878,6 +4863,7 @@ WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot, num_reduced_frame = row_is_in_reduced_frame(winobj, winstate->frameheadpos); + /* zero means a non-RPR window, which has 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 1f7a9b4b6df..b13b2db7384 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -1130,8 +1130,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 2f85c325f31..aab2aa575d4 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,18 @@ 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 < list_length(defineClauseExprs), + * evaluated lazily */ Bitmapset *defineMatchStartDependent; /* DEFINE vars needing per-context * evaluation * (match_start-dependent) */ @@ -2732,7 +2747,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 +2755,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 723b9b20fcb..be2eda8adc3 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