From bde5be36ed8bb59214984f0cb76a50f37ba9e856 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 10 Aug 2026 16:05:18 +0900 Subject: [PATCH] Refresh stale RPR comments and drop three duplicated blocks The comments and the README describing row pattern recognition had drifted from the code in many places. Correct them: - README.rpr credited createplan.c with the navigation offset computation, which lives in the executor. - The syntax summary put INITIAL and SEEK ahead of AFTER MATCH SKIP TO, an order the grammar does not accept; the two are the other way round. - Three helpers in rpr.c return a new list and four edit cells in place; say which does which, since a caller must always assign the return value. - The frame-option list and the absorption eligibility list each omitted a condition the code enforces: a frame end of CURRENT ROW is rejected, and absorption also requires that no DEFINE variable depend on match_start. The GROUP merge conditions likewise omitted the fixed-length body. - The element enumerations for the absorption flags omitted the group's BEGIN, and the ABSORBABLE_BRANCH description claimed the flag covers the unbounded start's scope, which is neither what the code marks nor all of it. The plan node comment's list of absorbable cases was missing the group whose body starts with an unbounded variable. - Several worked examples used patterns that Phase 1 rewrites into something else, so they never reach the case they illustrate; replace them with patterns that survive normalization. Others numbered their elements as if an alternation had no SEP branch terminators. - The match-phase fast path is gated on the absorbable region and a count that has reached max, not on min=1, max=1. The ALT walk stops at the first branch that records a match; a group's BEGIN can jump past an enclosing alternation; a state parked in a group always enters with a zero count slot; DEFINE conditions are cached per row but re-evaluated per context when they depend on match_start; a reluctant optional variable explores its skip path first; and the visited bitmap routes a repeated empty iteration out of the group rather than blocking it. - The DEFINE transformation coerces to boolean inside the per-variable loop, and the walker visits a compound form's inner offset twice, once per phase. - row_is_in_reduced_frame() returns -2 for any interior row of the current match, whatever the skip mode. - A header claimed a return value from a function returning void. Three blocks stated what is written elsewhere. Remove them: - The 94-line design overview at the head of execRPR.c restated README.rpr chapters VIII and IX and the RPRNFAContext comment in execnodes.h, directly below the pointer to that README. Leave a short orientation comment naming the three phases and where the rest is documented. - The free-standing DEFINE validator block in parse_rpr.c repeated the rule list that the define_walker header carries; keep only its description of the two-phase walk. - Appendix A of README.rpr listed thirty functions and the file each lives in. It carries no information the code does not, and it had already drifted -- when the navigation offset computation moved to the executor, the createplan.c entry went away and the six functions that took it over never replaced it. Renumber the two remaining appendices and the example labels inside them, and point the rpr.h header comment at the letter the examples now carry. Also drop the line telling the reader that an NFA state uses a flexible array member for its counts, which the declaration in execnodes.h says itself. No code changes. --- src/backend/executor/README.rpr | 206 +++++++++++++------------- src/backend/executor/execRPR.c | 133 ++++------------- src/backend/executor/nodeWindowAgg.c | 10 +- src/backend/optimizer/path/allpaths.c | 5 + src/backend/optimizer/plan/rpr.c | 57 ++++--- src/backend/parser/parse_rpr.c | 41 ++--- src/include/executor/execExpr.h | 2 +- src/include/nodes/execnodes.h | 6 +- src/include/nodes/plannodes.h | 16 +- src/include/optimizer/rpr.h | 7 +- 10 files changed, 207 insertions(+), 276 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index c8443a9d831..e223a39a309 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -21,7 +21,7 @@ - src/include/nodes/plannodes.h (plan node definitions) - src/include/nodes/execnodes.h (execution state definitions) - src/include/optimizer/rpr.h (types and constants) - - src/backend/optimizer/plan/createplan.c (nav offset computation) + - src/backend/optimizer/plan/createplan.c (match_start dependency metadata) ============================================================================ @@ -73,8 +73,8 @@ The basic syntax is as follows: PARTITION BY ... ORDER BY ... ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - [INITIAL | SEEK] -- SEEK is defined in the standard but not implemented AFTER MATCH SKIP TO NEXT ROW | SKIP PAST LAST ROW + [INITIAL | SEEK] -- SEEK is defined in the standard but not implemented PATTERN ( ) DEFINE AS , ... ) @@ -135,6 +135,8 @@ following: - Only ROWS is allowed (RANGE, GROUPS are not) - The start boundary must be CURRENT ROW - EXCLUDE option is not allowed + - The end boundary must not be CURRENT ROW (UNBOUNDED FOLLOWING or a + positive offset FOLLOWING only) (2) Transcription to WindowClause - Copies rpPattern, rpSkipTo, initial fields @@ -164,24 +166,33 @@ If the reluctant field is true, the quantifier is reluctant (non-greedy). Example: PATTERN ((A+ B) | C*) ALT - +-- SEQ - | +-- VAR(A, 1, INF) - | +-- VAR(B, 1, 1) + +-- GROUP(1, 1) + | +-- SEQ + | +-- VAR(A, 1, INF) + | +-- VAR(B, 1, 1) +-- VAR(C, 0, INF) +Parentheses always produce a GROUP node; a GROUP(1, 1) like the one above is +unwrapped later, by Phase 1 (h). + III-3. DEFINE Clause Transformation -transformDefineClause() processes each DEFINE variable as follows: +transformDefineClause() first validates the PATTERN variable count and +collects the names, then rejects any DEFINE variable that PATTERN does not +use. After that it processes each DEFINE variable as follows: (1) Checks for duplicate variable names - (2) Transforms the expression via transformExpr() - (3) Extracts Var nodes via pull_var_clause() and ensures each is + (2) Transforms the expression via transformExpr() and coerces it to + Boolean (coerce_to_boolean) right away, so that the steps below see + the final expression form + (3) Wraps in a TargetEntry with the variable name set in resname + (4) Extracts Var nodes via pull_var_clause() and ensures each is present in the query targetlist, so the planner propagates the referenced columns through the plan tree - (4) Wraps in a TargetEntry with the variable name set in resname After all variables are processed: - (5) Coerces each expression to Boolean type (coerce_to_boolean) + (5) Validates navigation nesting and offsets (define_walker), marks + column origins and assigns collations Variables that are used in PATTERN but not defined in DEFINE are implicitly evaluated as TRUE (matching all rows). @@ -450,9 +461,9 @@ The flag is set on all elements that carry the quantifier: At runtime (nfa_advance), the flag controls Depth-First Search (DFS) exploration order: - VAR with quantifier: - Greedy: primary path = next (continue), clone = jump (skip) - Reluctant: primary path = jump (skip), clone = next (continue) + VAR with quantifier: (a VAR has no jump; looping stays on the element) + Greedy: primary path = stay (loop), clone = next (exit) + Reluctant: primary path = next (exit), clone = stay (loop) END element: Greedy: primary path = jump (loop-back), clone = next (exit) @@ -478,23 +489,26 @@ preferred one. RPR_ELEM_EMPTY_LOOP -- the body is nullable, i.e. every path through it can match zero rows: - (A?)* A is nullable (min=0), so group body is nullable -> END gets flag - (A? B?)+ Both children nullable -> body nullable -> END gets flag - (A | B*) B* is nullable, making the ALT nullable -> END gets flag + (A? B?)+ Both children nullable -> body nullable -> END gets flag + (A | B*)+ B* is nullable, making the ALT nullable -> END gets flag + +Both examples keep their BEGIN/END pair through Phase 1. A single nullable +child, as in (A?)*, is multiplied away by (g) into A*, and an unquantified +group is unwrapped by (h), so neither leaves an END to carry the flag. It marks the END for the cycle detection of IX-6, which only ever tests a nullable END, and it lets nfa_advance_end offer a fast-forward exit beside -the loop-back below min. Without it, (A*){2,3} could not reach its lower +the loop-back below min. Without it, (A? B?){2,3} could not reach its lower bound: iteration 1 consumes every available row, iteration 2 derives an empty match, and nothing would carry the count to min(2). RPR_ELEM_EMPTY_PREFERRED -- the body's preferred derivation is the empty one, which is what orders those two paths. A bare variable consumes a row; only a reluctant quantifier that may take zero repetitions prefers to -skip it. The group's own greed cannot decide this: in ((A?){2}?) min +skip it. The group's own greed cannot decide this: in ((A? B?){2}) min equals max, so the group has no choice of iteration count left to be -greedy or reluctant about, while the body A? still prefers to consume a -row. The flag is what distinguishes ((A?){2}?) from ((A??){2}). +greedy or reluctant about, while the body still prefers to consume rows. +The flag is what distinguishes ((A? B?){2}) from ((A?? B??){2}). (See IX-4(c) for detailed runtime behavior.) IV-5. Absorbability Analysis (RPR_ELEM_ABSORBABLE) @@ -512,6 +526,7 @@ Eligibility conditions: (1) SKIP PAST LAST ROW (not NEXT ROW) (2) Frame end is UNBOUNDED FOLLOWING + (3) No DEFINE variable depends on match_start (see VIII-3(c)) Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive): @@ -571,7 +586,9 @@ Example: In PATTERN ((A B)+ C), a state waiting for B in the 3rd iteration elemIdx = 2 (B, depth 1) counts[0] = 2 (depth 0: depth of END. Group completed 2 iterations) - counts[1] = 1 (depth 1: depth of B. A matched in current iteration) + counts[1] = 0 (depth 1: shared by A and B. A zeroed its own slot when it + exited, per the count-clear policy, so a state parked on B + always enters with zero) Counts are indexed by depth, not by elemIdx. counts[0] is incremented when passing through END(depth 0), @@ -605,11 +622,13 @@ start row." Since the NFA is nondeterministic, multiple states can coexist simultaneously within a single context. -Example: In PATTERN (A | B) C, if the first row matches both A and B, +Example: In PATTERN ((A | B) C), if the first row matches both A and B, two states coexist within the context: - State 1: elemIdx=3 (waiting for C, via branch A) - State 2: elemIdx=3 (waiting for C, via branch B) + Element array: [0:ALT 1:A 2:SEP 3:B 4:SEP 5:C 6:FIN] + + State 1: elemIdx=5 (waiting for C, via branch A) + State 2: elemIdx=5 (waiting for C, via branch B) In this case, since the (elemIdx, counts) of the two states are equal, nfa_add_state_unique() retains only State 1 (branch A), which was @@ -694,7 +713,8 @@ the pattern. For example, the initial advance for PATTERN ((A | B) C): Start: elemIdx=0 (ALT) -> Expand ALT branches -> elemIdx=1 (A) -- VAR, so add state; stop here - -> elemIdx=2 (B) -- VAR, so add state; stop here + -> elemIdx=3 (B) -- VAR, so add state; stop here + (element 2 is branch 1's SEP terminator) Result: Two states in the context {waiting for A, waiting for B} @@ -867,15 +887,17 @@ Match determination (nfa_eval_var_match): If varId exceeds the range (variable not defined in DEFINE): Unconditionally true (matches all rows) -Immediate advance for simple VARs: +Immediate advance to the comparison point: - For a VAR with min=1, max=1 where the next element is END, - the Match phase processes through END immediately. + For a VAR inside an absorbable region -- one carrying + RPR_ELEM_ABSORBABLE_BRANCH without being the comparison point itself -- + that has no iteration left (count >= max) and whose next element is END, + the Match phase advances through the END chain immediately. This is necessary for accurate state comparison in Phase 2 (Absorb). - Example: In PATTERN ((A B)+), when A matches, it immediately advances - to B, and when B matches, it immediately advances through END to - complete the group count. This enables absorption comparison with + Example: In PATTERN ((A B)+), A stays where it is when it matches, since + its next element is B; when B matches, the state advances through END so + that the group count is complete for the absorption comparison with other contexts. Chapter VIII Phase 2: Absorb (Context Absorption) @@ -1017,11 +1039,13 @@ Two boolean flags make the absorption decision efficient: states. Once false, it never becomes true again. - allStatesAbsorbable (dynamic: can fluctuate) + allStatesAbsorbable (dynamic until a match is recorded) "Can this context be absorbed?" - true if all states are in an absorbable region. + true if all states are in an absorbable region and no match is + recorded. Becomes false when a non-absorbable state is added; reverts to true - when it is removed. + when it is removed. Recording a match also sets it false and that + does not revert, since absorbing would free the match. VIII-5. Absorption Order @@ -1088,7 +1112,9 @@ nfa_route_to_elem() branches on the type of the next element: If the next element is VAR: (1) Add the state to the context (nfa_add_state_unique) - (2) If the VAR has min=0, also add a skip path (recurse via next) + (2) If the VAR has min=0, also add a skip path (recurse via next). + A reluctant VAR (A??, A*?) reverses the order: the skip path goes + first, and the waiting state is dropped if it reaches FIN -> Expansion stops here (VAR is the element that "will consume the next row") @@ -1102,10 +1128,12 @@ IX-4. Per-Element advance Behavior (a) ALT (nfa_advance_alt) - Upon encountering an ALT element, all branches are expanded in order via the - SEP branch-separator chain. ALT.next is the first branch's content and - ALT.jump is that branch's terminating SEP; each SEP.jump links to the next - branch's SEP (-1 on the last) and each SEP.next is the next branch's content. + Upon encountering an ALT element, branches are expanded in preference order + via the SEP branch-separator chain, stopping at the first branch that + records a match -- a later branch's FIN would replace the preferred one. + ALT.next is the first branch's content and ALT.jump is that branch's + terminating SEP; each SEP.jump links to the next branch's SEP (-1 on the + last) and each SEP.next is the next branch's content. ALT.next -> branch 1 content; ALT.jump -> SEP1 -> SEP2 -> ... (jump chain) SEP_i.next -> branch (i+1) content @@ -1115,7 +1143,8 @@ IX-4. Per-Element advance Behavior (b) BEGIN (nfa_advance_begin) Handles group entry. - jump points to the element after END (= first element outside the group). + jump points past the group: the element after END, or the post-ALT element + when the group ends an alternation branch (IV-4). BEGIN does not reset the count at its depth; it only asserts the slot is already zero. Under the count-clear policy the previous occupant @@ -1213,10 +1242,11 @@ IX-6. Cycle Detection: nfaVisitedEnds When a group body can produce an empty match, looping back from END may cause an infinite loop. -Example: PATTERN ((A?)*) +Example: PATTERN ((A? B?)+) - A? has min=0, so it can pass through without matching. - If the outer group repeats: BEGIN -> A? skip -> END -> BEGIN -> ... + A? and B? both have min=0, so the body can pass through without + matching. If the group repeats: BEGIN -> A? skip -> B? skip -> END -> + BEGIN -> ... To prevent this: @@ -1448,15 +1478,12 @@ RPR_VAR_UNEVALUATED. B: 120 < PREV(110) -> false varMatched = [true, false] - C1 ExecRPRProcessRow(2): + ExecRPRProcessRow(2): (each phase walks every context in turn) Phase 1 (Match): - {elemIdx=0, counts=[1]}: A matches -> counts=[2] - {elemIdx=1, counts=[0]}: B does not match -> removed + C1 {elemIdx=0, counts=[1]}: A matches -> counts=[2] + C1 {elemIdx=1, counts=[0]}: B does not match -> removed + C2 {elemIdx=0, counts=[0]}: A matches -> counts=[1] C1.states = [{elemIdx=0, counts=[2]}] - - C2 ExecRPRProcessRow(2): - Phase 1 (Match): - {elemIdx=0, counts=[0]}: A matches -> counts=[1] C2.states = [{elemIdx=0, counts=[1]}] Phase 2 (Absorb): @@ -1501,7 +1528,8 @@ RPR_VAR_UNEVALUATED. --- Row 4 (price=130) --- update_reduced_frame(4) called. - C3 was already created but matchStartRow=3, so it is not applicable. + C3 was pruned when C1 recorded its match: under SKIP PAST LAST ROW every + context that started within the match's range is freed there. New context C4 created (matchStartRow=4). DEFINE values, row 4: @@ -1541,9 +1569,10 @@ XII-2. Forward-only Execution vs Backtracking window pipeline, which delivers sorted rows sequentially: it needs no re-fetching of earlier rows, and each row's DEFINE conditions (SQL expressions such as PREV or running aggregates, with high re-evaluation - cost) are evaluated only once. DFS order yields preferment naturally, - with greedy or reluctant behavior per quantifier obtained by reversing - that order. + cost) are evaluated once per row and cached; only match_start-dependent + variables are re-evaluated per context (VI-4). DFS order yields preferment + naturally, with greedy or reluctant behavior per quantifier obtained by + reversing that order. XII-3. Per-Context Management @@ -1602,8 +1631,10 @@ XII-5. Execution Optimization Summary VARs (count >= max) within the absorbable region (ABSORBABLE_BRANCH) through END chains to reach the comparison point (ABSORBABLE END). This process can also produce duplicate states reaching the same END. - nfa_add_state_unique() blocks duplicate addition of identical states - in both cases. + nfa_add_state_unique() blocks duplicate addition during advance. The + inline advance adds nothing -- it moves states in place -- so the + duplicates it leaves on an END are collapsed when the next advance + re-adds their successors. Significance: Prevents exponential growth of the state count in ALT branches and quantifier expansion. Since DFS order causes the @@ -1617,8 +1648,11 @@ XII-5. Execution Optimization Summary the END -> BEGIN loop-back can continue indefinitely. Two mechanisms resolve this: - - A visited bitmap (nfaVisitedEnds) blocks revisitation of the - same nullable END, preventing infinite empty loops (safety) + - A visited bitmap (nfaVisitedEnds) marks a nullable END whose body + has already derived an empty iteration. On a second arrival the + state leaves the group there once count >= min; below min it falls + through to the must-loop path, whose per-arrival count increment + reaches min in bounded steps (termination) - At an END with the RPR_ELEM_EMPTY_LOOP flag set, when count < min, the remaining required iterations are treated as empty matches and a fast-forward exit path out of the group is @@ -1667,43 +1701,7 @@ XII-5. Execution Optimization Summary level, achieving O(n^2) -> O(n) time complexity. Without this, performance degrades sharply on long partitions. -Appendix A. Key Function Index -============================================================================ - - Function File Role - -------------------------------------------------------------------------- - transformRPR parse_rpr.c Parser entry point - transformDefineClause parse_rpr.c DEFINE transformation - buildRPRPattern rpr.c NFA compilation main - optimizeRPRPattern rpr.c parse tree optimization - fillRPRPattern rpr.c NFA element generation - finalizeRPRPattern rpr.c Finalization - computeAbsorbability rpr.c Absorption analysis - update_reduced_frame nodeWindowAgg.c Execution main loop - 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 - nfa_absorb_contexts execRPR.c Phase 2 - nfa_advance execRPR.c Phase 3 - nfa_advance_state execRPR.c Per-state branching - nfa_route_to_elem execRPR.c Element routing - nfa_advance_alt execRPR.c ALT handling - nfa_advance_begin execRPR.c BEGIN handling - nfa_advance_end execRPR.c END handling - nfa_advance_var execRPR.c VAR handling - nfa_add_state_unique execRPR.c Deduplication - nfa_states_covered execRPR.c Absorption check - nfa_reevaluate_dependent_vars execRPR.c Per-context re-eval - ExecRPRGetHeadContext execRPR.c Context lookup - ExecRPRFreeContext execRPR.c Context deallocation - ExecRPRCleanupDeadContexts execRPR.c Dead context cleanup - ExecRPRFinalizeAllContexts execRPR.c Partition-end finalize - ExecRPRRecordContextSuccess execRPR.c Stats: match success - ExecRPRRecordContextFailure execRPR.c Stats: match failure - -Appendix B. Data Structure Relationship Diagram +Appendix A. Data Structure Relationship Diagram ============================================================================ Parser Layer @@ -1764,10 +1762,10 @@ Appendix B. Data Structure Relationship Diagram |--- nfaContextFree (recycling pool) +--- nfaStateFree (recycling pool) -Appendix C. NFA Element Array Examples +Appendix B. NFA Element Array Examples ============================================================================ -C-1. PATTERN (A B C) +B-1. PATTERN (A B C) idx varId depth min max next jump ------------------------------------------ @@ -1776,7 +1774,7 @@ C-1. PATTERN (A B C) 2 C 0 1 1 3 -1 3 FIN 0 1 1 -1 -1 -C-2. PATTERN (A+ B*) +B-2. PATTERN (A+ B*) idx varId depth min max next jump flags ------------------------------------------------------------------------ @@ -1787,7 +1785,7 @@ C-2. PATTERN (A+ B*) Only A+ is the absorption point (Case 1). Once past A, absorption is permanently disabled for that state. -C-3. PATTERN (A | B | C) +B-3. PATTERN (A | B | C) idx varId depth min max next jump ---------------------------------------- @@ -1804,7 +1802,7 @@ C-3. PATTERN (A | B | C) SEP.jump links to the next branch's SEP (-1 on the last), and each SEP.next enters the next branch's content; the branch tails are redirected to FIN. -C-4. PATTERN ((A B)+ C) +B-4. PATTERN ((A B)+ C) idx varId depth min max next jump flags -------------------------------------------------------------------------- @@ -1816,9 +1814,9 @@ C-4. PATTERN ((A B)+ C) 5 FIN 0 1 1 -1 -1 Case 2: GROUP+ with {1,1} body VARs. A, B are branches; - END is the absorption point. Compare with C-6 (Case 3). + END is the absorption point. Compare with B-6 (Case 3). -C-5. PATTERN ((A | B)+? C) +B-5. PATTERN ((A | B)+? C) idx varId depth min max next jump flags ------------------------------------------------------------------- @@ -1835,7 +1833,7 @@ C-5. PATTERN ((A | B)+? C) The ALT lives inside a group, so its branch tails are redirected to the post-ALT element (here the group's END at idx 6), not out of the group. -C-6. PATTERN ((A+ B)+ C) -- Absorbability flag example +B-6. PATTERN ((A+ B)+ C) -- Absorbability flag example idx varId depth min max next jump flags --------------------------------------------------------------------------- @@ -1851,7 +1849,7 @@ C-6. PATTERN ((A+ B)+ C) -- Absorbability flag example B and END get no flags -> absorption stops once the state advances to B. (See IV-5 Case 3) -C-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT +B-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT idx varId depth min max next jump flags --------------------------------------------------------------------------- diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index a233d6d5649..68664568556 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -108,94 +108,12 @@ static void nfa_reevaluate_dependent_vars(WindowAggState *winstate, int64 currentPos); /* - * NFA-based pattern matching implementation - * - * These functions implement direct NFA execution using the compiled - * RPRPattern structure, avoiding regex compilation overhead. - * - * Execution Flow: match -> absorb -> advance - * ----------------------------------------- - * The NFA execution follows a three-phase cycle for each row: - * - * 1. MATCH (convergence): Evaluate all waiting states against current row. - * States on VAR elements are checked against their defining conditions. - * Failed matches are removed, successful ones may transition forward. - * This is a "convergence" phase - the number of states tends to decrease. - * - * 2. ABSORB: After matching, check if any context can absorb another. - * Context absorption is an optimization that merges equivalent contexts. - * A context can only be absorbed if ALL its states are absorbable. - * - * 3. ADVANCE (divergence): Expand states through epsilon transitions. - * States advance through ALT (alternation), END (group end), and - * optional elements until reaching VAR or FIN elements where they wait. - * This is a "divergence" phase - ALT creates multiple branch states. - * - * Key Design Decisions: - * --------------------- - * - VAR->END transition in match phase: When a simple VAR (max=1) matches - * and the next element is END, we transition immediately in the match - * phase rather than waiting for advance. This is necessary for correct - * absorption: states must be at END to be marked absorbable before the - * absorption check occurs. - * - * - Optional VAR skip paths: When advance lands on a VAR with min=0, - * we create both a waiting state AND a skip state (like ALT branches). - * This ensures patterns like "A B? C" work correctly - we need a state - * waiting for B AND a state that has already skipped to C. - * - * - END->END count increment: When transitioning from one END to another - * END within advance, we must increment the outer END's count. This - * handles nested groups like "((A|B)+)+" correctly - exiting the inner - * group counts as one iteration of the outer group. - * - * - 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. - * 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: - * --------------------------- - * Absorption uses flags computed at planning time (in rpr.c) and two - * context-level flags maintained at runtime: - * - * State-level: - * state.isAbsorbable: true if state is in the absorbable region. - * - Set at creation: elem->flags & RPR_ELEM_ABSORBABLE_BRANCH - * - At transition: prevAbsorbable && (newElem->flags & ABSORBABLE_BRANCH) - * - Monotonic: once false, stays false forever - * - * Context-level: - * ctx.hasAbsorbableState: can this context absorb others? - * - True if at least one state has isAbsorbable=true - * - Monotonic: true->false only (optimization: skip recalc when false) - * - * ctx.allStatesAbsorbable: can this context be absorbed? - * - True if ALL states have isAbsorbable=true - * - Dynamic: can change false->true (when non-absorbable states die) - * - * Absorption Algorithm: - * For each pair (older Ctx1, newer Ctx2): - * 1. Pre-check: Ctx1.hasAbsorbableState && Ctx2.allStatesAbsorbable - * -> If false, skip (fast filter) - * 2. Coverage check: For each Ctx2 state with isAbsorbable=true, - * find Ctx1 state with same elemIdx and count >= Ctx2.count - * 3. If all Ctx2 absorbable states are covered, absorb Ctx2 - * - * Example: Pattern A+ B - * Row 1: Ctx1 at A (count=1) - * Row 2: Ctx1 at A (count=2), Ctx2 at A (count=1) - * -> Both at same elemIdx (A), Ctx1.count >= Ctx2.count - * -> Ctx2 absorbed - * - * The asymmetric design (Ctx1 needs hasAbsorbable, Ctx2 needs allAbsorbable) - * allows absorption even when Ctx1 has extra non-absorbable states. + * The engine runs three phases per row: match (evaluate VARs, prune dead + * states), absorb (drop contexts an older context already covers), advance + * (expand epsilon transitions until states park on VARs). Per-element + * advance behaviour, the absorption argument and the dual-flag contract are + * documented in README.rpr chapters VIII and IX and in the RPRNFAContext + * comment in nodes/execnodes.h. */ /* @@ -203,7 +121,6 @@ static void nfa_reevaluate_dependent_vars(WindowAggState *winstate, * * Allocate an NFA state, reusing from freeList if available. * freeList is stored in WindowAggState for reuse across match attempts. - * Uses flexible array member for counts[]. */ static RPRNFAState * nfa_state_make(WindowAggState *winstate) @@ -601,9 +518,10 @@ nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen) * hasAbsorbableState: true if context has at least one absorbable state. * This flag is monotonic (true -> false only). Once all absorbable states * die, no new absorbable states can be created through transitions. - * allStatesAbsorbable: true if ALL states in context are absorbable. - * This flag is dynamic and can change false -> true when non-absorbable - * states die off. + * allStatesAbsorbable: true if ALL states in context are absorbable and no + * match is recorded. Dynamic (false -> true as non-absorbable states die + * off), except that a recorded match pins it false: absorbing would free + * a match no absorbing context can reproduce. * * Optimization: Once hasAbsorbableState becomes false, both flags remain false * permanently, so we skip recalculation. @@ -721,8 +639,8 @@ nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, RPRNFAContext *new /* * nfa_try_absorb_context * - * Try to absorb ctx (newer) into an older in-progress context. - * Returns true if ctx was absorbed and freed. + * Try to absorb ctx (newer) into an older in-progress context. If one is + * found, ctx is unlinked and freed here. * * Absorption requires three conditions: * 1. ctx must have all states absorbable (allStatesAbsorbable). @@ -868,24 +786,24 @@ nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, * Only updates counts and removes dead states. Minimal transitions. * * For VAR elements: - * - matched: count++, keep state (unless count > max) + * - matched: count++ (saturating at RPR_COUNT_INF), keep state * - not matched: remove state (exit alternatives already exist from * previous advance when count >= min was satisfied) * * For VARs that reached max count followed by END: * - Advance through the END-element chain to the absorption * comparison point - * - Only deterministic exits (count >= max) are handled. An unbounded VAR - * never reaches the test: Case 1 of isUnboundedStart() gives a simple - * unbounded VAR both absorption flags, and Case 2 marks only fixed-length - * children, so the flag pair the test sits behind excludes it. + * - Only deterministic exits are handled. A count saturates at + * RPR_COUNT_INF, so count >= max does not by itself exclude an unbounded + * VAR; what excludes it is the absorbable-region test, which no unbounded + * VAR inside a still-looping group passes. * - Chains through END elements while count >= max (must-exit path) * - * Non-VAR elements (ALT, END, FIN) are kept as-is for advance phase. + * Non-VAR elements (only an END parked by the chain above) are kept as-is for + * advance phase. * - * currentPos is threaded in only for debugging visibility (nfa_match is the - * one NFA helper that otherwise lacks the row index); it has no runtime - * consumer yet. + * currentPos is unused by the matching logic itself; it is accepted so that + * every NFA helper carries the row index for debugging. */ static void nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, RPRVarMatch *varMatched, @@ -934,10 +852,11 @@ nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, RPRVarMatch *varMatched, * deterministic exits (count >= max, max finite) are handled; * unbounded VARs stay for advance phase. * - * In nested patterns like ((A B){2}){3}, a VAR reaching its - * max triggers an exit cascade: inner END increments inner - * group count, which may itself reach max, requiring an exit - * to the next outer END. The loop below walks this chain. + * In nested patterns like ((A (B C){2}){2})+, a VAR reaching + * its max triggers an exit cascade: inner END increments + * inner group count, which may itself reach max, requiring an + * exit to the next outer END. The loop below walks this + * chain. * * ABSORBABLE_BRANCH marks elements inside the absorbable * region; ABSORBABLE marks the outermost comparison point diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index cd70871fc70..4ea56428c52 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -3084,9 +3084,9 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) sizeof(int32) * node->rpPattern->maxDepth; /* - * Allocate varMatched array for NFA evaluation. With the new varNames - * ordering (DEFINE order first), varId == defineIdx for all defined - * variables, so no mapping is needed. + * Allocate the per-row varMatched cache. varNames are built in + * DEFINE order, so varId equals the DEFINE list index and no mapping + * is needed. */ if (winstate->defineClauseExprs != NIL) winstate->nfaVarMatched = palloc0(sizeof(RPRVarMatch) * @@ -4414,8 +4414,8 @@ rpr_is_defined(WindowAggState *winstate) * >0, if the row is the first in the reduced frame. Return the number of rows * in the reduced frame. * -1, if the row is an unmatched row - * -2, if the row is in the reduced frame but needed to be skipped because of - * AFTER MATCH SKIP PAST LAST ROW + * -2, if the row is inside the current match but is not its first row (an + * interior row of the match) * ----------------- */ static int64 diff --git a/src/backend/optimizer/path/allpaths.c b/src/backend/optimizer/path/allpaths.c index 559c6049243..06c90fcb98c 100644 --- a/src/backend/optimizer/path/allpaths.c +++ b/src/backend/optimizer/path/allpaths.c @@ -4945,6 +4945,11 @@ remove_unused_subquery_outputs(Query *subquery, RelOptInfo *rel, { if (wc->defineClause != NIL) { + /* + * flags == 0 is safe: DEFINE rejects aggregates, window + * functions and subqueries at parse time, and this runs + * before any PlaceHolderVar could be planted. + */ List *vars = pull_var_clause((Node *) wc->defineClause, 0); foreach_node(Var, dvar, vars) diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 5a0017d90e2..122aaa67a24 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -781,7 +781,8 @@ flattenAltChildren(List *children) * (A | B | A) -> (A | B) * (X | Y | X | Z | Y) -> (X | Y | Z) * - * Returns a new list with only unique children (first occurrence kept). + * Keeps the first of each and compacts the survivors towards the front of the + * list it was given, so the caller must assign the truncated result. */ static List * removeDuplicateAlternatives(List *children) @@ -1329,7 +1330,8 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * | +-- jump --+ (loop back to first child) * +---- jump -------------------+ (skip to after END) * - * BEGIN.jump points past END (skip path when count >= max or min == 0). + * BEGIN.jump points past END (the skip path taken when min == 0; a count is + * only tested at END, so a BEGIN never takes it for reaching max). * END.jump points to the first child (loop-back path). * BEGIN.next and END.next are set later by finalizeRPRPattern(). * @@ -1700,29 +1702,33 @@ finalizeRPRPattern(RPRPattern *result) * -> Compare at A every row. When contexts move to B, absorption stops. * * Pattern: (A B)+ C - * Element 0 (A): ABSORBABLE_BRANCH - * Element 1 (B): ABSORBABLE_BRANCH - * Element 2 (END): ABSORBABLE | ABSORBABLE_BRANCH <- comparison point - * Element 3 (C): (none) + * Element 0 (BEGIN): ABSORBABLE_BRANCH + * Element 1 (A): ABSORBABLE_BRANCH + * Element 2 (B): ABSORBABLE_BRANCH + * Element 3 (END): ABSORBABLE | ABSORBABLE_BRANCH <- comparison point + * Element 4 (C): (none) * -> Compare at END every 2 rows. When contexts move to C, absorption stops. * * Pattern: (A+ B+)+ C - * Element 0 (A): ABSORBABLE | ABSORBABLE_BRANCH <- only first A+ flagged - * Element 1 (B): (none) - * Element 2 (END): (none) - * Element 3 (C): (none) - * -> Only first unbounded portion (A+) gets flags. Absorption happens - * at A during first iteration. After moving to B+, absorption stops. + * Element 0 (BEGIN): ABSORBABLE_BRANCH + * Element 1 (A): ABSORBABLE | ABSORBABLE_BRANCH <- comparison point + * Element 2 (B): (none) + * Element 3 (END): (none) + * Element 4 (C): (none) + * -> Compare at A during the first iteration. After moving to B+, + * absorption stops. * * First Unbounded Portion Strategy: - * The algorithm only flags the FIRST unbounded portion starting from - * element 0. This is sufficient because: + * Along one path the algorithm only flags the FIRST unbounded portion + * starting from element 0; an alternation is walked branch by branch, so + * each branch may contribute one (A+ | B+ gives both). This is sufficient + * because: * - Absorption in first portion already achieves O(n) complexity * - Later portions have different synchronization characteristics * - Nested unbounded patterns are too complex for simple absorption * - Complex patterns (nested groups, etc.) naturally die from mismatch * - * Runtime Usage (in nodeWindowAgg.c): + * Runtime Usage (in execRPR.c): * - state.isAbsorbable = (previous && elem.ABSORBABLE_BRANCH) * - Monotonic: once false, stays false (cannot re-enter region) * - context.hasAbsorbableState: can absorb others (>=1 absorbable state) @@ -1999,11 +2005,13 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, * - Simple unbounded VAR: the VAR itself (e.g., A in A+) * - Unbounded GROUP: the END element (e.g., END in (A B)+) * RPR_ELEM_ABSORBABLE_BRANCH: All elements in absorbable region - * - All elements within the same scope as unbounded start + * - Simple unbounded VAR: the VAR itself only + * - Unbounded GROUP: the whole body (including nested subgroups) and the + * group's END, plus any enclosing BEGIN/ALT on the path to it * * Examples: * A+ B C - absorbable (A gets both flags) - * (A B)+ C - absorbable (A,B,END get BRANCH, END gets ABSORBABLE) + * (A B)+ C - absorbable (BEGIN,A,B,END get BRANCH, END gets ABSORBABLE) * A B+ - NOT absorbable (unbounded not at start) * A+? B C - NOT absorbable (reluctant quantifier) * (A+ B+)+ - only first A+ on first iteration (nested unbounded not supported) @@ -2099,16 +2107,23 @@ buildRPRPattern(RPRPatternNode *pattern, List *defineClause, * * Runtime conditions for absorption: * - * 1. SKIP TO PAST LAST ROW required (not SKIP TO NEXT ROW): With NEXT - * ROW, after each match the search resumes from the next row, so contexts - * are immediately discarded. No redundant contexts accumulate, making - * absorption unnecessary. + * 1. SKIP TO PAST LAST ROW required (not SKIP TO NEXT ROW): with NEXT + * ROW, matches overlap and every row must report its own match, so + * absorption (sharing one result) is not semantically possible. A + * completed context does linger until its own start row is queried; that + * is the inherent cost of per-row match reporting, not redundancy + * absorption could remove. * * 2. Unbounded frame end required (not ROWS with bounded end): With a * bounded frame (e.g., ROWS BETWEEN CURRENT ROW AND 10 FOLLOWING), * matches may be truncated at frame boundaries. This changes the * absorption semantics - older contexts don't necessarily produce longer * matches when frame limits apply differently to each context. + * + * 3. No DEFINE may depend on match_start: such a variable is evaluated + * against the start of its own match, so two contexts that differ only in + * where they started can classify the same row differently and the older + * one no longer covers the newer. */ if (rpSkipTo == ST_PAST_LAST_ROW && (frameOptions & FRAMEOPTION_END_UNBOUNDED_FOLLOWING) && diff --git a/src/backend/parser/parse_rpr.c b/src/backend/parser/parse_rpr.c index b0de0e2ab93..1779377cf86 100644 --- a/src/backend/parser/parse_rpr.c +++ b/src/backend/parser/parse_rpr.c @@ -5,7 +5,8 @@ * * This file transforms RPR-related clauses from raw parse tree to planner * structures during query analysis: - * - Validates frame options (must start at CURRENT ROW, no EXCLUDE) + * - Validates frame options (ROWS only, must start at CURRENT ROW, no + * EXCLUDE, and CURRENT ROW is not accepted as the frame end) * - Validates PATTERN variable count (max RPR_VARID_MAX + 1) * - Transforms DEFINE clause * - Stores the PATTERN parse tree and the SKIP TO/INITIAL flags @@ -63,7 +64,8 @@ static bool define_walker(Node *node, void *context); * Process Row Pattern Recognition related clauses. * * Validates and transforms RPR clauses from parse tree to planner structures: - * - Validates frame options (must start at CURRENT ROW, no EXCLUDE) + * - Validates frame options (ROWS only, must start at CURRENT ROW, no + * EXCLUDE, and CURRENT ROW is not accepted as the frame end) * - Set AFTER MATCH SKIP TO flag * - Set SEEK/INITIAL flag * - Transforms DEFINE clause into TargetEntry list @@ -279,8 +281,8 @@ transformDefineClause(ParseState *pstate, WindowDef *windef, List *patternVarNames = NIL; /* - * If Row Definition Common Syntax exists, DEFINE clause must exist. (the - * raw parser should have already checked it.) + * The grammar builds an RPCommonSyntax only for a window specification + * that carries DEFINE, so the list is never empty here. */ Assert(windef->rpCommonSyntax->rpDefs != NULL); @@ -425,27 +427,6 @@ transformDefineClause(ParseState *pstate, WindowDef *windef, return defineClause; } -/* - * Single-pass DEFINE clause validator. - * - * One walker function (define_walker) visits every node in a DEFINE - * expression exactly once and enforces, for each outer RPRNavExpr (per - * ISO/IEC 19075-5 5.6.4 nesting rules): - * - arg must contain at least one column reference - * - PREV/NEXT wrapping FIRST/LAST flattens to a compound kind - * - Other nestings are rejected (FIRST(PREV()), PREV(PREV()), ...) - * - offset_arg / compound_offset_arg must not contain column refs - * or nested navigation operations - * - * The walker uses a phase tag to know which subtree it is in: DEFINE - * body (top-level), inside a nav.arg, or inside a nav.offset_arg / - * compound_offset_arg. When entering an outer nav (PHASE_BODY), it - * walks nav.arg in PHASE_NAV_ARG to collect nesting/column-ref state, - * applies compound flatten or raises a nesting error, then walks the - * (post-flatten) offset(s) in PHASE_NAV_OFFSET to enforce the - * constant-offset and no-nested-nav rules. No subtree is walked twice. - */ - /* * define_walker * Single-pass DEFINE clause validator. At each node, enforces: @@ -461,10 +442,16 @@ transformDefineClause(ParseState *pstate, WindowDef *windef, * - must be a run-time constant (no column references) * - must not contain a row pattern navigation operation * + * Entering an outer nav, the walker walks nav.arg in PHASE_NAV_ARG to collect + * nesting and column-ref state, flattens a compound form or raises a nesting + * error, then walks the post-flatten offset(s) in PHASE_NAV_OFFSET. A + * compound form's inner offset is walked in both passes: PHASE_NAV_ARG only + * asks whether nav.arg as a whole holds a column reference, so the offset is + * walked again to catch one it would have leaked. + * * Var sightings feed the column-ref rule for the enclosing nav scope; * RPRNavExpr sightings inside PHASE_NAV_ARG feed the nesting decision. - * See the comment block above DefinePhase for the overall design and - * how each subtree is walked exactly once. + * The phases themselves are described where DefinePhase is declared. */ static bool define_walker(Node *node, void *context) diff --git a/src/include/executor/execExpr.h b/src/include/executor/execExpr.h index ac1b0be0c2a..571999365b8 100644 --- a/src/include/executor/execExpr.h +++ b/src/include/executor/execExpr.h @@ -274,7 +274,7 @@ typedef enum ExprEvalOp EEOP_MERGE_SUPPORT_FUNC, EEOP_SUBPLAN, - /* row pattern navigation (RPR PREV/NEXT) */ + /* row pattern navigation (all eight RPRNavKind kinds) */ EEOP_RPR_NAV_SET, EEOP_RPR_NAV_RESTORE, diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 09ebe60be78..436153012cb 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2603,8 +2603,10 @@ typedef struct RPRNFAState * hasAbsorbableState: can this context absorb others? (>=1 absorbable state) * - Monotonic: true->false only, cannot recover once false * - Used to skip absorption attempts once all absorbable states are gone - * allStatesAbsorbable: can this context be absorbed? (ALL states absorbable) - * - Dynamic: can change false->true (when non-absorbable states die) + * allStatesAbsorbable: can this context be absorbed? (ALL states + * absorbable, no recorded match) + * - Dynamic: false->true when non-absorbable states die; a recorded + * match pins it false * - Used to determine if this context is eligible for absorption */ typedef struct RPRNFAContext diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index c350df2eeeb..5556bfb3852 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -1300,7 +1300,8 @@ typedef struct RPRPattern int numVars; /* number of pattern variables */ char **varNames; /* array of variable names (DEFINE order * first) */ - RPRDepth maxDepth; /* maximum group nesting depth */ + RPRDepth maxDepth; /* deepest group nesting depth plus one, i.e. + * the length of a state's counts[] */ int numElements; /* number of elements */ RPRPatternElement *elements; /* array of pattern elements */ @@ -1317,13 +1318,16 @@ typedef struct RPRPattern * computeAbsorbability() marks the absorbable cases (see isUnboundedStart): * - simple unbounded VAR at the start: A+ B C * - unbounded GROUP with fixed-length children: (A B)+, (A B{2})+ - * - top-level ALT with independently absorbable branches: A+ | B+ - * (handled in computeAbsorbabilityRecursive) + * - greedy GROUP whose body starts with one of those: (A+ B)+ + * - ALT with independently absorbable branches: A+ | B+ + * (handled in computeAbsorbabilityRecursive, at any nesting: the + * branches of (A+ | B)+ are judged the same way) * * Not absorbable: an unbounded element not at the start (A B+), a - * reluctant quantifier (A+?), or an ALT inside a group ((A|B)+) -- there - * different start positions yield different match contents, so later - * matches are not suffixes of earlier ones. + * reluctant quantifier (A+?), or an alternation no branch of which starts + * with an unbounded greedy element ((A|B)+) -- there different start + * positions yield different match contents, so later matches are not + * suffixes of earlier ones. */ bool isAbsorbable; /* true if pattern supports context absorption */ } RPRPattern; diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h index fd076c10277..682ed75b48a 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -38,8 +38,9 @@ #define RPR_COUNT_INF RPR_QUANTITY_INF #define RPR_ELEMIDX_MAX PG_INT16_MAX /* max pattern elements */ #define RPR_ELEMIDX_INVALID ((RPRElemIdx) -1) /* invalid index */ -#define RPR_DEPTH_MAX PG_UINT8_MAX /* max pattern nesting depth: 255, - * the largest RPRDepth */ +#define RPR_DEPTH_MAX PG_UINT8_MAX /* 255 levels fit RPRDepth; depth + * is 0-based, so the deepest + * permitted nesting is 254 */ /* Reserved control-element varIds (high nibble 0xF; 0xF0-0xFA spare) */ #define RPR_VARID_BEGIN ((RPRVarId) 0xFB) /* group begin */ @@ -58,7 +59,7 @@ * empty match */ /* * The two absorption flags below are explained in README.rpr IV-5 - * ("Absorbability Analysis"), with worked examples in Appendix C; the + * ("Absorbability Analysis"), with worked examples in Appendix B; the * analysis that sets them is computeAbsorbability() in * optimizer/plan/rpr.c. */