From f4c54f983b502626fe15e7ed91535f8d9e5756b2 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Sun, 8 Mar 2026 22:30:20 +0900 Subject: [PATCH 12/12] Extract RPR NFA engine into execRPR.c --- src/backend/executor/Makefile | 1 + src/backend/executor/execRPR.c | 3037 ++++++++++++++++++++++++++ src/backend/executor/meson.build | 1 + src/backend/executor/nodeWindowAgg.c | 2921 ++++++------------------- src/backend/optimizer/plan/rpr.c | 2 +- src/include/executor/execRPR.h | 40 + 6 files changed, 3755 insertions(+), 2247 deletions(-) create mode 100644 src/backend/executor/execRPR.c create mode 100644 src/include/executor/execRPR.h diff --git a/src/backend/executor/Makefile b/src/backend/executor/Makefile index 11118d0ce02..eeed9a904e5 100644 --- a/src/backend/executor/Makefile +++ b/src/backend/executor/Makefile @@ -26,6 +26,7 @@ OBJS = \ execPartition.o \ execProcnode.o \ execReplication.o \ + execRPR.o \ execSRF.o \ execScan.o \ execTuples.o \ diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c new file mode 100644 index 00000000000..0d5ba7516e9 --- /dev/null +++ b/src/backend/executor/execRPR.c @@ -0,0 +1,3037 @@ +/*------------------------------------------------------------------------- + * + * execRPR.c + * NFA-based Row Pattern Recognition engine for window functions. + * + * This file implements the NFA execution engine for the ROWS BETWEEN + * PATTERN clause (SQL Standard Feature R020: Row Pattern Recognition in + * Window Functions). + * + * The engine executes the compiled RPRPattern structure directly, avoiding + * regex compilation overhead. It is called by nodeWindowAgg.c and exposes + * the interface declared in executor/execRPR.h. + * + * + * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * IDENTIFICATION + * src/backend/executor/execRPR.c + * + *------------------------------------------------------------------------- + */ +#include "postgres.h" + +#include "executor/execRPR.h" +#include "executor/executor.h" +#include "optimizer/rpr.h" +#include "utils/memutils.h" + +/* + * ============================================================================ + * PostgreSQL Row Pattern Recognition: Flat-Array Stream NFA Guide + * ============================================================================ + * + * Target audience: Developers with a basic understanding of the PostgreSQL + * executor and planner architecture + * + * Scope: The entire process from PATTERN/DEFINE clause parsing to NFA + * runtime execution + * + * Related code: + * - src/backend/parser/parse_rpr.c (parser phase) + * - src/backend/optimizer/plan/rpr.c (optimizer phase) + * - src/backend/executor/nodeWindowAgg.c (executor phase, window agg) + * - src/backend/executor/execRPR.c (executor phase, NFA engine) + * - src/include/executor/execRPR.h (NFA public API) + * - src/include/nodes/plannodes.h (plan node definitions) + * - src/include/nodes/execnodes.h (execution state definitions) + * - src/include/optimizer/rpr.h (types and constants) + * + * ============================================================================ + * + * What is a Flat-Array Stream NFA? + * + * The NFA in this implementation is not a traditional state-transition graph + * but a flat array of fixed-size 16-byte elements. At runtime, it processes + * the row stream in a forward-only manner, expanding epsilon transitions + * eagerly without backtracking. + * + * - Flat-Array: Pattern compiled into a flat array, + * not a graph (Chapter IV) + * - Stream: Rows consumed sequentially in one direction, + * never revisited (Chapter XII) + * - NFA: Nondeterministic execution where multiple states + * coexist within a single context (Chapter VI) + * + * Chapter I Row Pattern Recognition Overview + * ============================================================================ + * + * Row Pattern Recognition (hereafter RPR) is a feature introduced in SQL:2016 + * that matches regex-based patterns against ordered row sets. + * + * The SQL standard defines two forms: + * + * Feature R010: MATCH_RECOGNIZE (FROM clause) + * - Dedicated table operator + * - Provides dedicated functions such as MATCH_NUMBER(), CLASSIFIER() + * - Supports ONE ROW PER MATCH / ALL ROWS PER MATCH + * + * Feature R020: RPR in a window (WINDOW clause) + * - Integrated into the existing window function framework + * - Supports ALL ROWS PER MATCH only + * - No MATCH_NUMBER() + * + * This implementation targets Feature R020. + * + * The basic syntax is as follows: + * + * SELECT ... + * OVER ( + * 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 + * PATTERN ( ) + * DEFINE AS , ... + * ) + * + * The PATTERN clause is a regular expression over row pattern variables. + * The DEFINE clause specifies boolean conditions that determine whether each + * variable evaluates to true for the current row. + * + * Example: + * + * PATTERN (A+ B) + * DEFINE A AS price > PREV(price), + * B AS price < PREV(price) + * + * This pattern matches "a span where prices rise consecutively then drop." + * + * Chapter II Overall Processing Pipeline + * ============================================================================ + * + * RPR processing is divided into three phases: + * + * +------------------------------------------------------------+ + * | 1. Parsing (Parser) | + * | SQL text -> PATTERN AST + DEFINE expression tree | + * | | + * | 2. Compilation (Optimizer/Planner) | + * | PATTERN AST -> optimization -> flat NFA element array | + * | | + * | 3. Execution (Executor) | + * | Row-by-row matching via NFA simulation | + * +------------------------------------------------------------+ + * + * Each phase uses independent data structures, and the interfaces between + * phases are well-defined: + * + * Parser -> Planner: WindowClause.rpPattern (RPRPatternNode tree) + * WindowClause.defineClause (TargetEntry list) + * + * Planner -> Executor: WindowAgg.rpPattern (RPRPattern struct) + * WindowAgg.defineClause (TargetEntry list) + * + * Chapter III Parsing Phase + * ============================================================================ + * + * III-1. Entry Point + * + * transformWindowDefinitions() (parse_clause.c) + * +-- transformRPR() (parse_rpr.c) + * + * transformRPR() is invoked when RPCommonSyntax is present and performs the + * following: + * + * (1) Frame option validation + * - Only ROWS is allowed (RANGE, GROUPS are not) + * - The start boundary must be CURRENT ROW + * - EXCLUDE option is not allowed + * + * (2) Transcription to WindowClause + * - Copies rpPattern, rpSkipTo, initial fields + * + * (3) DEFINE clause transformation (transformDefineClause) + * + * III-2. PATTERN AST + * + * The parser transforms the PATTERN clause into an RPRPatternNode tree. + * Each node has one of the following four types: + * + * RPR_PATTERN_VAR Variable reference. Name stored in varName field. + * RPR_PATTERN_SEQ Concatenation. Children node list in children. + * RPR_PATTERN_ALT Alternation. Branch node list in children. + * RPR_PATTERN_GROUP Group (parentheses). Body node list in children. + * + * All nodes have min/max fields to express quantifiers: + * + * A -> VAR(A, min=1, max=1) + * A+ -> VAR(A, min=1, max=INF) + * A* -> VAR(A, min=0, max=INF) + * A? -> VAR(A, min=0, max=1) + * A{3,5} -> VAR(A, min=3, max=5) + * + * If the reluctant field is true, the quantifier is reluctant (non-greedy). + * (RPRPatternNode.reluctant is bool; reluctant_location is the separate + * ParseLoc field holding the '?' token position, or -1 if absent.) + * + * Example: PATTERN ((A+ B) | C*) + * + * ALT + * +-- SEQ + * | +-- VAR(A, 1, INF) + * | +-- VAR(B, 1, 1) + * +-- VAR(C, 0, INF) + * + * III-3. DEFINE Clause Transformation + * + * transformDefineClause() processes each DEFINE variable as follows: + * + * (1) Checks for duplicate variable names + * (2) Transforms the expression into a standard SQL expression + * (3) Coerces to Boolean type (coerce_to_boolean) + * (4) Wraps in a TargetEntry with the variable name set in resname + * + * Variables that are used in PATTERN but not defined in DEFINE are implicitly + * evaluated as TRUE (matching all rows). + * + * Chapter IV Compilation Phase + * ============================================================================ + * + * IV-1. Entry Point + * + * create_windowagg_plan() (createplan.c) + * +-- collectPatternVariables() Collect variable names + * +-- filterDefineClause() Remove unused DEFINE entries + * +-- buildRPRPattern() NFA compilation (6 phases) + * + * IV-2. The 6 Phases of buildRPRPattern() + * + * Phase 1: AST optimization (optimizeRPRPattern) + * Phase 2: Statistics collection (scanRPRPattern) + * Phase 3: Memory allocation (allocateRPRPattern) + * Phase 4: NFA element fill (fillRPRPattern) + * Phase 5: Finalization (finalizeRPRPattern) + * Phase 6: Absorbability analysis (computeAbsorbability) + * + * IV-3. Phase 1: AST Optimization + * + * After copying the parser-generated AST, the following optimizations are + * applied: + * + * (a) SEQ flattening: Unwrap nested SEQ nodes + * SEQ(A, SEQ(B, C)) -> SEQ(A, B, C) + * + * (b) Consecutive variable merging: Merge consecutive occurrences of the + * same variable into a single quantifier + * A A -> A{2} + * A{2,3} A{1,2} -> A{3,5} + * + * (c) Consecutive group merging: Merge repeated identical groups + * (A B)+ (A B)+ -> (A B){2,INF} + * + * (d) Consecutive ALT merging: Merge repeated identical ALT nodes + * (A | B) (A | B) (A | B) -> (A | B){3} + * + * (e) Prefix/suffix absorption: Absorb identical sequences before/after + * a group + * A B (A B)+ -> (A B){2,INF} + * + * (f) ALT flattening and deduplication + * (A | (B | C)) -> (A | B | C) + * (A | B | A) -> (A | B) + * + * (g) Quantifier multiplication: Collapse nested quantifiers when safe + * (A+)+ -> A+ + * (A{2,3}){5} -> A{10,15} + * + * (h) Single-child unwrap + * SEQ(A) -> A, (A){1,1} -> A + * + * IV-4. Phase 4: NFA Element Array Generation + * + * Transforms the optimized AST into a flat array of RPRPatternElement. + * This is the core data structure used for NFA simulation at runtime. + * + * RPRPatternElement struct (16 bytes): + * + * Field Size Description + * --------------------------------------------------------- + * varId 1B Variable ID (0-251) or control code (252-255) + * depth 1B Group nesting depth + * flags 1B Bit flags (see below) + * reserved 1B Padding + * min 4B Quantifier lower bound + * max 4B Quantifier upper bound + * next 2B Next element index (sequential flow) + * jump 2B Branch target index (for ALT/GROUP) + * + * Control codes: + * + * RPR_VARID_BEGIN (252) Group start marker + * RPR_VARID_END (253) Group end marker + * RPR_VARID_ALT (254) Alternation start marker + * RPR_VARID_FIN (255) Pattern completion marker + * + * Element flags (1 byte, bitmask): + * + * 0x01 RPR_ELEM_RELUCTANT (VAR, BEGIN, END) + * Non-greedy quantifier. Prefers shorter match: try exit-loop + * first, then repeat. Set on VAR for simple (A+?), + * on BEGIN+END for group ((...)+?). + * + * 0x02 RPR_ELEM_EMPTY_LOOP (END) + * Group body can produce empty match (all children nullable). + * Creates a fast-forward exit clone alongside the normal + * loop-back so cycle detection doesn't kill legitimate + * matches. (IV-4b) + * + * 0x04 RPR_ELEM_ABSORBABLE_BRANCH (VAR, BEGIN, END, ALT) + * Element lies within an absorbable region. Used at runtime + * to track whether the current NFA state is in an absorbable + * context. + * + * 0x08 RPR_ELEM_ABSORBABLE (VAR, END) + * Absorption judgment point. Where to compare consecutive + * iterations for absorption. + * - Simple unbounded VAR (A+): set on the VAR itself + * - Unbounded GROUP ((A B)+): set on the END element only + * + * Accessor macros: + * RPRElemIsReluctant(e) (e)->flags & 0x01 + * RPRElemCanEmptyLoop(e) (e)->flags & 0x02 + * RPRElemIsAbsorbableBranch(e) (e)->flags & 0x04 + * RPRElemIsAbsorbable(e) (e)->flags & 0x08 + * + * Example: PATTERN (A+ B | C) + * + * AST: ALT(SEQ(VAR(A,1,INF), VAR(B,1,1)), VAR(C,1,1)) + * + * Compilation result: + * + * idx varId depth min max next jump Description + * ------------------------------------------------------------ + * 0 ALT 0 1 1 1 -1 Alternation start + * 1 A(0) 1 1 INF 2 3 Branch 1: A+ + * 2 B(1) 1 1 1 4 -1 Branch 1: B -> FIN + * 3 C(2) 1 1 1 4 -1 Branch 2: C -> FIN + * 4 FIN 0 1 1 -1 -1 Pattern completion + * + * - idx 0: ALT marker. next(=1) is the start of the first branch + * - idx 1: Variable A. next(=2) is B, jump(=3) is the start of the second + * branch + * - idx 2: Variable B. next(=4) is FIN + * - idx 3: Variable C. next(=4) is FIN + * - idx 4: FIN marker. Match completion signal + * + * Roles of next and jump: + * + * - next: The next element to move to "after consuming" the current element. + * For VAR, the next position after a successful match. + * For BEGIN/END, the next position inside/outside the group. + * + * - jump: The element to "skip to." + * In ALT, a jump from one branch to the next branch. + * In BEGIN, a skip path to END+1 (for groups with min=0). + * In END, a loop-back to the start of the group body. + * + * Example: PATTERN ((A B)+) + * + * idx varId depth min max next jump Description + * -------------------------------------------------------------- + * 0 BEGIN 0 1 INF 1 4 Group start + * 1 A(0) 1 1 1 2 -1 A + * 2 B(1) 1 1 1 3 -1 B + * 3 END 0 1 INF 4 1 Group end + * 4 FIN 0 1 1 -1 -1 Pattern completion + * + * - idx 0: BEGIN. next(=1) enters the group body. + * jump(=4) skips to after END = FIN (used when min=0). + * - idx 3: END. next(=4) exits the group. + * jump(=1) loops back to the start of the group body. + * + * IV-4a. Reluctant Flag (RPR_ELEM_RELUCTANT) + * + * The reluctant flag is set during Phase 4 (fillRPRPattern) when the AST node + * has reluctant == true. It reverses the priority of quantifier expansion at + * runtime: + * + * Greedy (default): try loop-back first, then exit (prefer longer match) + * Reluctant: try exit first, then loop-back (prefer shorter match) + * + * The flag is set on all elements that carry the quantifier: + * + * Simple VAR (A+?): RPR_ELEM_RELUCTANT on the VAR element + * Group ((...)+?): RPR_ELEM_RELUCTANT on BEGIN and END elements + * + * At runtime (nfa_advance), the flag controls DFS exploration order: + * + * VAR with quantifier: + * Greedy: primary path = next (continue), clone = jump (skip) + * Reluctant: primary path = jump (skip), clone = next (continue) + * + * END element: + * Greedy: primary path = jump (loop-back), clone = next (exit) + * Reluctant: primary path = next (exit), clone = jump (loop-back) + * + * BEGIN with min=0: + * Greedy: primary path = next (enter group), clone = jump (skip) + * Reluctant: primary path = jump (skip), clone = next (enter group) + * + * The absorption optimization requires greedy quantifiers. Reluctant + * quantifiers are excluded from absorbability analysis (see IV-5). + * + * IV-4b. Empty Loop Flag (RPR_ELEM_EMPTY_LOOP) + * + * The empty-loop flag is set during Phase 4 (fillRPRPatternGroup) on the END + * element when the group body is nullable -- i.e., every path through the + * body can match zero rows (all children are nullable). + * + * Example patterns that trigger this flag: + * + * (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 + * + * The flag works in conjunction with the empty match cycle detection + * (elemIdx visited bitmap). Without this flag, cycle detection alone would + * cause legitimate matches to fail. + * + * Problem example: (A*){2,3} + * - Iteration 1: A* consumes all available rows -> count=1, END reached + * - Loop-back for iteration 2: A* matches zero rows -> END reached again + * - Cycle detection sees the same elemIdx on the same row -> state killed + * - count never reaches min(2) -> match fails (incorrect) + * + * With the RPR_ELEM_EMPTY_LOOP flag, nfa_advance_end creates two paths: + * the normal loop-back (which cycle detection will eventually kill) and + * a fast-forward exit clone that bypasses the loop entirely. + * (See IX-4(c) for detailed runtime behavior.) + * - Empty match is impossible since body is not nullable + * + * IV-5. Absorbability Analysis (RPR_ELEM_ABSORBABLE) + * + * Context absorption is an optimization technique that reduces O(n^2) to O(n). + * (Runtime behavior is described in Chapter VIII.) + * + * This phase determines whether the pattern has a structure suitable for the + * absorption optimization and sets flags on the relevant elements: + * + * RPR_ELEM_ABSORBABLE Absorption comparison point + * RPR_ELEM_ABSORBABLE_BRANCH Element within an absorbable region + * + * Eligibility conditions: + * + * (1) SKIP PAST LAST ROW (not NEXT ROW) + * (2) Frame end is UNBOUNDED FOLLOWING + * + * Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive): + * + * Case 1: Simple VAR+ (e.g., A+) + * -> ABSORBABLE | ABSORBABLE_BRANCH set on the VAR + * Case 2: GROUP+ whose body consists only of {1,1} VARs (e.g., (A B)+) + * -> ABSORBABLE_BRANCH on children, + * ABSORBABLE | ABSORBABLE_BRANCH on END + * Case 3: GROUP+ whose body starts with VAR+ (e.g., (A+ B)+) + * -> Recurses from BEGIN into the body, applying Case 1. + * ABSORBABLE | ABSORBABLE_BRANCH set on A. + * B and END get no flags -> absorption stops once past A. + * + * Absorbability is determined per-element, not per-pattern. + * Absorption comparison is performed only when a state resides at an + * element with the RPR_ELEM_ABSORBABLE flag. Once a state leaves the + * flagged region, absorption is permanently disabled for that state. + * + * Through this mechanism, the runtime guarantees monotonicity: + * "a context that started earlier always subsumes a context that + * started later." + * + * Chapter V NFA Runtime Data Structures + * ============================================================================ + * + * V-1. RPRNFAState -- NFA State + * + * A single NFA state represents "how far the pattern has progressed." + * + * Field Description + * ----------------------------------------------------------- + * elemIdx Index of the current pattern element + * counts[] Repetition count per group depth + * isAbsorbable Whether the state is in an absorbable region + * next Next state in the linked list + * + * The size of the counts array is rpPattern->maxDepth (= maximum group + * nesting depth + 1), allocated as a flexible array member at the end of + * the struct. + * + * Example: In PATTERN ((A B)+ C), a state waiting for B in the 3rd iteration + * + * Element array: [0:BEGIN(d0) 1:A(d1) 2:B(d1) 3:END(d0) 4:C(d0) 5:FIN] + * + * 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 are indexed by depth, not by elemIdx. + * counts[0] is incremented when passing through END(depth 0), + * and the group repetition count is preserved even when + * the state is at B(depth 1). + * + * Definition of two states being "equal": + * + * Two states are equal if they have the same elemIdx and the same counts + * up to the depth of that element. + * nfa_states_equal() compares counts[0..elem->depth] using memcmp. + * Only counts at or below the depth of the current element are meaningful. + * + * V-2. RPRNFAContext -- Matching Context + * + * A single context represents "a matching attempt started from a specific + * start row." + * + * Field Description + * --------------------------------------------------------------------- + * states Linked list of active NFA states + * matchStartRow Row number where matching started + * matchEndRow Row number where matching completed + * (-1 if incomplete) + * lastProcessedRow Last row processed + * matchedState State that reached FIN (for greedy fallback) + * hasAbsorbableState Whether this context can absorb other contexts + * allStatesAbsorbable Whether this context can be absorbed + * next, prev Doubly-linked list + * + * 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, + * 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) + * + * 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 + * added first. + * Because DFS processes the first branch of ALT first, the state via A + * is registered first, and the state via B is discarded as a duplicate. + * This is the preferment guarantee. + * + * 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] + * nfaVisitedElems Bitmap for cycle detection + * nfaStateSize Precomputed size of RPRNFAState + * + * Memory management: + * + * States and contexts are managed through their own free lists. + * Instead of palloc, they are obtained from the reuse pool, and + * returned to the pool upon deallocation. + * This reduces the overhead of frequent allocation/deallocation. + * + * Chapter VI NFA Execution: 3-Phase Model + * ============================================================================ + * + * VI-1. Entry Point and Overall Flow + * + * When the window function processes each row, row_is_in_reduced_frame() + * is called. This function determines whether the current row belongs to + * a matched frame, and if necessary, calls update_reduced_frame() to + * drive the NFA. + * + * Flow of update_reduced_frame(): + * + * (1) Find or create a context for the target row + * (2) Enter the row processing loop + * (3) After the loop ends, record the result in reduced_frame_map + * + * Pseudocode of the row processing loop: + * + * targetCtx = ExecRPRGetHeadContext(pos) + * if targetCtx == NULL: + * targetCtx = ExecRPRStartContext(pos) + * + * for currentPos = startPos; targetCtx->states != NULL; currentPos++: + * if not nfa_evaluate_row(currentPos): -- row does not exist + * ExecRPRFinalizeAllContexts() -- finalize all contexts + * ExecRPRCleanupDeadContexts() -- clean up after finalization + * break + * + * ExecRPRProcessRow(currentPos) -- 3-phase processing + * ExecRPRStartContext(currentPos + 1) -- pre-create next start point + * ExecRPRCleanupDeadContexts() -- remove dead contexts + * + * Key point: Processing a single row may require processing multiple rows + * ahead. Due to the nature of window functions, determining the frame for + * row N requires looking at rows beyond N. + * + * VI-2. Context Creation: ExecRPRStartContext() + * + * Creates a new context and performs the initial advance. + * + * (1) Allocate context via nfa_context_alloc() + * (2) Set matchStartRow = pos + * (3) Create initial state: elemIdx=0 (first pattern element), + * counts=all zero + * (4) Call nfa_advance(initialAdvance=true) + * + * The initial advance expands epsilon transitions at the beginning of + * 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 + * + * Result: Two states in the context {waiting for A, waiting for B} + * + * During the initial advance, reaching FIN is not recorded as a match. + * This is to prevent empty matches. + * + * VI-3. Row Evaluation: nfa_evaluate_row() + * + * Evaluates all variable conditions in the DEFINE clause at once for + * the current row. + * + * for each defineClause[i]: + * result = ExecEvalExpr(defineClause[i]) + * varMatched[i] = (not null and true) + * + * To support row navigation operators such as PREV() and NEXT(), + * the previous row, current row, and next row are set in separate slots: + * + * ecxt_scantuple = previous row (for PREV reference) + * ecxt_outertuple = current row (default reference) + * ecxt_innertuple = next row (for NEXT reference) + * + * The varMatched array is referenced later in Phase 1 (Match). + * + * VI-4. ExecRPRProcessRow(): 3-Phase Processing + * + * NFA processing for a single row is divided into three phases: + * + * +--------------------------------------------+ + * | Phase 1: MATCH (convergence) | + * | Compare the current row against each VAR | + * | state. Remove states that fail to match. | + * | | + * | Phase 2: ABSORB (absorption) | + * | Merge duplicate contexts to prevent | + * | state explosion. | + * | | + * | Phase 3: ADVANCE (expansion) | + * | Expand epsilon transitions to prepare | + * | for the next row. | + * +--------------------------------------------+ + * + * This ordering is important: + * + * - Match executes first to "consume the current row." + * - Absorb executes immediately after Match, when states have been updated. + * - Advance executes last to prepare "states waiting for the next row." + * + * Chapter VII Phase 1: Match + * ============================================================================ + * + * nfa_match() iterates through each state in the context: + * + * (1) Check whether the state's elemIdx is a VAR element + * (2) Compare against the current row using nfa_eval_var_match() + * (3) Match success: increment repetition count, retain state + * (4) Match failure: remove state + * + * Match determination (nfa_eval_var_match): + * + * If varId is within the range of defineVariableList: + * Use the value of varMatched[varId] + * + * If varId exceeds the range (variable not defined in DEFINE): + * Unconditionally true (matches all rows) + * + * Immediate advance for simple VARs: + * + * For a VAR with min=1, max=1 where the next element is END, + * the Match phase processes through END 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 + * other contexts. + * + * Chapter VIII Phase 2: Absorb (Context Absorption) + * ============================================================================ + * + * VIII-1. Problem + * + * In the current implementation, a new context is started for each row + * processed. + * Applying PATTERN (A+) to 10 rows produces 10 contexts, + * each of which tracks state independently. + * + * If there are N rows, the total number of states becomes O(N^2): + * + * Context 1 (started at row 1): can match A up to N times + * Context 2 (started at row 2): can match A up to N-1 times + * ... + * Context N (started at row N): can match A 1 time + * + * VIII-2. Solution: Context Absorption + * + * Key observation: a context started earlier contains + * all matches of a later-started context (monotonicity principle). + * + * If Context 1 started at row 1 and matched A 5 times, + * the state where Context 2 (started at row 2) matched A 4 times + * is already contained within Context 1. + * + * Therefore Context 2 can be "absorbed" into Context 1. + * + * VIII-3. Absorption Conditions + * + * (1) The pattern is marked as isAbsorbable (see IV-5) + * (2) allStatesAbsorbable of the target context is true + * (3) An earlier context "covers" all states of the target + * + * Cover condition (nfa_states_covered): + * + * A state with the same elemIdx exists in the earlier context, + * and the count at that depth is greater than or equal -- then it is covered. + * + * VIII-4. Dual-Flag Design + * + * Two boolean flags make the absorption decision efficient: + * + * hasAbsorbableState (monotonic: only true->false transition possible) + * "Does this context have the ability to absorb other contexts?" + * true if at least one absorbable state exists. + * Transitions to false when states are removed leaving no absorbable + * states. + * Once false, it never becomes true again. + * + * allStatesAbsorbable (dynamic: can fluctuate) + * "Can this context be absorbed?" + * true if all states are in an absorbable region. + * Becomes false when a non-absorbable state is added; reverts to true + * when it is removed. + * + * VIII-5. Absorption Order + * + * nfa_absorb_contexts() traverses from tail (newest) to head (oldest). + * + * for ctx = tail to head: + * if ctx.allStatesAbsorbable: + * for older = ctx.prev to head: + * if older.hasAbsorbableState: + * if nfa_states_covered(older, ctx): + * free(ctx) -- absorbed + * break + * + * Since inspection starts from the newest context, the most recently started + * (= having the shortest match) context is absorbed first. + * + * Chapter IX Phase 3: Advance (Epsilon Transition Expansion) + * ============================================================================ + * + * IX-1. Overview + * + * nfa_advance() expands epsilon transitions from each state after Match, + * generating "new states waiting for the next row." + * + * An epsilon transition is a transition that moves without consuming a row: + * + * - ALT: branch to each alternative + * - BEGIN: enter group (or skip if min=0) + * - END: loop-back within group (or exit when condition is met) + * - FIN: record match completion + * - VAR loop/exit: repeat/exit according to the quantifier + * + * Expansion stops upon reaching a VAR element, and the state is added. + * This is because VAR is the element that "will consume the next row." + * + * IX-2. Processing Order: DFS and Preferment + * + * advance processes states in lexicographic order, + * performing Depth-First Search (DFS) on each state. + * + * This DFS order is what guarantees the SQL standard's "preferment": + * + * The branch that appears first in the PATTERN text takes precedence. + * + * Example: PATTERN (A | B) C + * + * The first branch A of the ALT takes precedence over the second branch B. + * When both A and B can match, the match via A is selected. + * + * nfa_add_state_unique() prevents duplicate addition of the same state, + * so the state added first (= from the preferred branch) is retained. + * + * IX-3. Routing Function: nfa_route_to_elem() + * + * All inter-element transitions in the advance phase go through + * nfa_route_to_elem(). + * This function branches its behavior based 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) + * -> Expansion stops here (VAR is the element that "will consume the next + * row") + * + * If the next element is non-VAR (ALT, BEGIN, END, FIN): + * -> Recursively call nfa_advance_state() to continue expansion + * + * With this structure, advance recursively follows epsilon transitions + * until reaching a VAR, consistently stopping only at VAR elements. + * + * IX-4. Per-Element advance Behavior + * + * (a) ALT (nfa_advance_alt) + * + * Upon encountering an ALT element, all branches are expanded in order. + * The first element of each branch is connected via a jump pointer. + * + * idx=0 (ALT) -> branch 1 start (next) -> branch 2 start (jump) -> ... + * + * nfa_advance_state() is recursively called for each branch. + * + * (b) BEGIN (nfa_advance_begin) + * + * Handles group entry. + * jump points to the element after END (= first element outside the group). + * + * Greedy (default): + * (1) Enter the group body (move via next, reset the count at that depth) + * (2) If min=0, also add a group skip path (move via jump) + * + * Reluctant: + * Order reversed -- skip path first, group entry second. + * If the skip path reaches FIN, the group entry path is not generated + * (shortest match preferred). + * + * (c) END (nfa_advance_end) + * + * Handles group termination. This is the core of the repetition logic. + * + * Let count be the count at the current depth: + * + * count < min: + * Loop-back (move via jump, repeat the group body) + * + * If the RPR_ELEM_EMPTY_LOOP flag is set: + * In addition to loop-back, also add a fast-forward exit path. + * This is because the body may produce an empty match, causing count + * to never reach min. fast-forward resets counts[depth] to 0 + * and exits via next (treating the remaining required iterations + * as empty matches). + * + * min <= count < max: + * Greedy: loop-back first, exit second + * Reluctant: exit first, loop-back second + * If the exit path reaches FIN, loop-back is omitted. + * + * count >= max: + * Unconditional exit (move via next) + * + * On exit: reset counts[depth] = 0, and if the next element is an outer END, + * increment the count at the outer depth. + * + * (d) VAR (nfa_advance_var) + * + * Handles repeat/exit for a VAR element with a quantifier. + * + * Let count be the count at the current depth: + * + * count < min: + * Unconditional loop (stay at the same elemIdx, wait for the next row) + * + * min <= count < max: + * Greedy: loop first, exit (next) second + * Reluctant: exit first, loop second + * If the exit path reaches FIN, loop is omitted. + * + * count >= max: + * Unconditional exit (move via next) + * + * On exit: reset counts[depth] = 0. + * + * (e) FIN + * + * Match success. The current state is moved to matchedState for recording, + * and matchEndRow is set to the current row. + * + * Upon reaching FIN, all remaining unprocessed states are removed + * (early termination). By DFS order, the path that reached FIN first + * has the highest preferment, so the rest are inferior paths. + * This is the core mechanism that guarantees preferment. + * + * In SKIP PAST LAST ROW mode, upon reaching FIN, subsequent contexts + * that started within the match range are immediately pruned. + * + * IX-5. State Deduplication: nfa_add_state_unique() + * + * When adding a new state to a context, it is compared against existing + * states; + * if an identical state already exists, it is not added. + * + * Comparison criteria: elemIdx + counts[0..elem->depth] (see V-1) + * + * This deduplication is the core mechanism that suppresses NFA state + * explosion. + * Because DFS order causes preferred-branch states to be added first, + * identical states from lower-priority branches are automatically discarded. + * + * IX-6. Cycle Detection: nfaVisitedElems + * + * When a group body can produce an empty match, + * looping back from END may cause an infinite loop. + * + * Example: PATTERN ((A?)*) + * + * A? has min=0, so it can pass through without matching. + * If the outer group repeats: BEGIN -> A? skip -> END -> BEGIN -> ... + * + * To prevent this: + * + * (1) At compile time: set the RPR_ELEM_EMPTY_LOOP flag on the END + * of groups whose body is nullable. + * The runtime effect of this flag is described in IX-4(c): + * when count < min, a fast-forward exit path is added, + * resolving the deadlock where count cannot increase due to empty + * matches. + * + * (2) At runtime: initialize the nfaVisitedElems bitmap immediately before + * DFS expansion of each state within advance (once per state). + * During DFS, set the corresponding elemIdx bit when visiting each + * element. + * If a previously visited elemIdx is revisited, that path is terminated. + * + * Note: the bitmap tracks only elemIdx and does not consider counts. + * Therefore, legitimate revisits to the same elemIdx but with different + * counts may also be blocked. This only occurs when the group body is + * nullable (all paths can match empty), causing END -> loop-back -> + * skip -> END within a single DFS. In such cases the END element has + * the RPR_ELEM_EMPTY_LOOP flag, so the fast-forward exit (IX-4(c)) + * provides an alternative path that bypasses the cycle. + * + * Chapter X Match Result Processing + * ============================================================================ + * + * X-1. Reduced Frame Map + * + * RPR match results are recorded in a byte array called reduced_frame_map. + * One byte is allocated per row, and the value is one of the following: + * + * RF_NOT_DETERMINED (0) Not yet processed + * RF_FRAME_HEAD (1) Start row of the match + * RF_SKIPPED (2) Interior row of the match (skipped in frame) + * RF_UNMATCHED (3) Match failure + * + * The window function references this map to determine frame inclusion for + * each row. + * + * X-2. AFTER MATCH SKIP + * + * Determines the starting point for the next match attempt after a successful + * match: + * + * SKIP TO NEXT ROW: + * New match attempt begins from the row after the match start row. + * Overlapping matches are possible. + * + * SKIP PAST LAST ROW: + * New match attempt begins from the row after the match end row. + * Only non-overlapping matches are possible. + * + * X-3. INITIAL vs SEEK + * + * Standard definition (section 6.12): + * INITIAL: "is used to look for a match whose first row is R." + * SEEK: "is used to permit a search for the first match anywhere + * from R through the end of the full window frame." + * In either case, if there is no match, the reduced window frame is empty. + * The default is INITIAL. + * + * Current implementation: + * SEEK is not supported (the parser raises an error). + * Only INITIAL is supported, searching only for matches starting at each + * row position pos. + * + * Chapter XI Worked Example: Full Execution Trace + * ============================================================================ + * + * XI-1. Query + * + * SELECT company, tdate, price, + * first_value(price) OVER w AS start_price, + * last_value(price) OVER w AS end_price + * FROM stock + * WINDOW w AS ( + * PARTITION BY company + * ORDER BY tdate + * ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + * AFTER MATCH SKIP PAST LAST ROW + * PATTERN (A+ B) + * DEFINE A AS price > PREV(price), + * B AS price < PREV(price) + * ); + * + * XI-2. Data + * + * Row# tdate price + * -------------------------- + * 0 2024-01-01 100 + * 1 2024-01-02 110 + * 2 2024-01-03 120 + * 3 2024-01-04 115 + * 4 2024-01-05 130 + * + * XI-3. Compilation Result + * + * PATTERN (A+ B) -> unchanged after optimization + * + * idx varId depth min max next jump + * ----------------------------------------- + * 0 A(0) 0 1 INF 1 -1 A+ + * 1 B(1) 0 1 1 2 -1 B + * 2 FIN 0 1 1 -1 -1 + * + * DEFINE: A -> "price > PREV(price)", B -> "price < PREV(price)" + * isAbsorbable = true (A+ is a simple unbounded VAR) + * + * XI-4. Execution Trace + * + * --- Row 0 (price=100) --- + * + * update_reduced_frame(0) called. + * + * Context C0 created (matchStartRow=0). + * Initial advance: elemIdx=0(A) -> VAR, so state is added. + * C0.states = [{elemIdx=0, counts=[0]}] + * + * nfa_evaluate_row(0): + * A: price(100) > PREV(price) -> no PREV -> false + * B: price(100) < PREV(price) -> no PREV -> false + * varMatched = [false, false] + * + * ExecRPRProcessRow(0): + * Phase 1 (Match): A(0) state vs varMatched[0]=false -> state removed + * C0.states = [] (empty) + * + * Phase 2 (Absorb): skipped (no states) + * Phase 3 (Advance): skipped (no states) + * + * C0.states is empty, so the loop terminates. + * matchEndRow < matchStartRow -> RF_UNMATCHED. + * register_reduced_frame_map(0, RF_UNMATCHED). + * + * --- Row 1 (price=110) --- + * + * update_reduced_frame(1) called. + * + * Context C1 created (matchStartRow=1). + * Initial advance: C1.states = [{elemIdx=0, counts=[0]}] + * + * nfa_evaluate_row(1): + * A: 110 > PREV(100) -> true + * B: 110 < PREV(100) -> false + * varMatched = [true, false] + * + * ExecRPRProcessRow(1): + * Phase 1 (Match): A(0) match succeeds -> counts[0]++ -> counts=[1] + * C1.states = [{elemIdx=0, counts=[1]}] + * + * Phase 3 (Advance): + * State {elemIdx=0, counts=[1]}: A+ (min=1, count=1, max=INF) + * count >= min, so: + * Greedy -> loop first: keep {elemIdx=0, counts=[1]} + * exit: reset counts[0]=0, next(=1) -> {elemIdx=1, + * counts=[0]} + * C1.states = [{elemIdx=0, counts=[1]}, {elemIdx=1, counts=[0]}] + * + * --- Row 2 (price=120) --- + * + * Context C2 created (matchStartRow=2). + * Initial advance: C2.states = [{elemIdx=0, counts=[0]}] + * + * nfa_evaluate_row(2): + * A: 120 > PREV(110) -> true + * B: 120 < PREV(110) -> false + * varMatched = [true, false] + * + * C1 ExecRPRProcessRow(2): + * Phase 1 (Match): + * {elemIdx=0, counts=[1]}: A matches -> counts=[2] + * {elemIdx=1, counts=[0]}: B does not match -> removed + * 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): + * Does C1 (started earlier) cover C2? + * C1: {elemIdx=0, counts=[2]}, C2: {elemIdx=0, counts=[1]} + * Same elemIdx, C1.counts >= C2.counts -> covered + * C2 absorbed. -> removed. + * + * Phase 3 (Advance): + * {elemIdx=0, counts=[2]}: Greedy -> loop + exit + * Loop: {elemIdx=0, counts=[2]} + * Exit: reset counts[0]=0, next(=1) -> {elemIdx=1, counts=[0]} + * C1.states = [{elemIdx=0, counts=[2]}, {elemIdx=1, counts=[0]}] + * + * Context C3 created (matchStartRow=3). + * + * --- Row 3 (price=115) --- + * + * nfa_evaluate_row(3): + * A: 115 > PREV(120) -> false + * B: 115 < PREV(120) -> true + * varMatched = [false, true] + * + * ExecRPRProcessRow(3): + * Phase 1 (Match): + * {elemIdx=0, counts=[2]}: A does not match -> removed + * {elemIdx=1, counts=[0]}: B matches -> counts=[1] + * C1.states = [{elemIdx=1, counts=[1]}] + * + * Phase 3 (Advance): + * {elemIdx=1, counts=[1]}: B (min=1, max=1) + * count(1) >= max(1) -> unconditional exit + * Reset counts[0]=0, next = 2 (FIN) + * FIN reached -> matchEndRow = 3, matchedState recorded. + * Early termination: no remaining states, so completed immediately. + * C1.states = [] (empty after reaching FIN) + * + * C1.states is empty and matchEndRow=3 >= matchStartRow=1 -> match succeeds. + * + * register_reduced_frame_map(1, RF_FRAME_HEAD) + * register_reduced_frame_map(2, RF_SKIPPED) + * register_reduced_frame_map(3, RF_SKIPPED) + * + * --- Row 4 (price=130) --- + * + * update_reduced_frame(4) called. + * C3 was already created but matchStartRow=3, so it is not applicable. + * New context C4 created (matchStartRow=4). + * + * nfa_evaluate_row(4): + * A: 130 > PREV(115) -> true + * B: 130 < PREV(115) -> false + * + * ... No subsequent rows, so ExecRPRFinalizeAllContexts() is called. + * Match incomplete -> RF_UNMATCHED. + * + * XI-5. Final Result + * + * Row 0: RF_UNMATCHED -> frame = the row itself + * Row 1: RF_FRAME_HEAD -> frame = rows 1 through 3 + * Row 2: RF_SKIPPED -> inside row 1's match + * Row 3: RF_SKIPPED -> inside row 1's match + * Row 4: RF_UNMATCHED -> frame = the row itself + * + * Chapter XII Summary of Key Design Decisions + * ============================================================================ + * + * XII-1. Flat Array vs Tree-Based NFA + * + * Choice: Flat array (RPRPatternElement[]) + * + * Rationale: + * - Cache-friendly: 16-byte fixed size, contiguous memory + * - Index-based references: 2-byte indices instead of pointers + * - Easy to serialize: can use memcpy when passing to plan nodes + * + * XII-2. Forward-only Execution vs Backtracking + * + * Choice: Forward-only (state set tracking) + * + * Rationale: + * - Backtracking takes exponential time in the worst case + * - NFA simulation guarantees polynomial time + * - DFS order naturally guarantees preferment. + * Greedy/reluctant per quantifier requires only reversing the DFS order + * - Window functions receive sorted rows sequentially. + * Forward-only fits directly into this pipeline, + * whereas backtracking requires re-fetching previous rows + * - DEFINE conditions are SQL expressions (PREV, RUNNING aggregates, etc.) + * with high re-evaluation cost. Forward-only requires only one evaluation + * per row + * + * XII-3. Per-Context Management + * + * Choice: Independent context per start row + * + * Rationale: + * - Supports overlapping matches under SKIP TO NEXT ROW + * - Determines the frame for each row independently + * - Absorption optimization can eliminate redundant contexts in O(n) + * + * XII-4. Memory Pool Management + * + * Choice: Custom free list + * + * Rationale: + * - NFA states are created and destroyed in large numbers per row + * - Avoids palloc/pfree overhead + * - State size is variable (counts[] array), but within a single query + * maxDepth is fixed, so all states have the same size + * + * XII-5. Execution Optimization Summary + * + * The following optimizations make the NFA simulation practical. + * + * -- Compile-time -- + * + * (1) AST Optimization (IV-3) + * + * Simplifies the AST before converting the pattern to an NFA. + * Reduces the number of NFA elements through consecutive variable + * merging (A A -> A{2}), SEQ flattening, quantifier multiplication, + * and other transformations. + * + * Significance: Reducing the element count directly shrinks the state + * space, decreasing the cost of all subsequent runtime phases (match, + * absorb, advance). + * + * -- Runtime: advance phase -- + * + * (2) Group Skip (IX-4(b)) + * + * At the BEGIN of a group with min=0, uses jump to skip the entire + * group. Moves directly to the first element outside the group without + * exploring the group body. Greedy enters then skips; Reluctant skips + * then enters. + * + * Significance: For optional groups (min=0), immediately generates + * a skip path without exploring the body, avoiding unnecessary DFS + * expansion. + * + * (3) State Deduplication (IX-5) + * + * During advance, DFS may generate states with the same (elemIdx, + * counts) combination through multiple paths. Additionally, unlike + * VAR repetition, group repetition cannot perform absorption + * comparison using VAR states, so inline advance is performed from + * after Phase 1 match through to 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. + * + * Significance: Prevents exponential growth of the state count in + * ALT branches and quantifier expansion. Since DFS order causes the + * preferred branch's state to be registered first, identical states + * from lower-priority branches are automatically discarded, thereby + * also guaranteeing preferment. + * + * (4) Cycle Detection and Fast-Forward (IX-6, IX-4(c)) + * + * When a nullable group body (e.g., A?) repeats empty matches, + * the END -> BEGIN loop-back can continue indefinitely. + * + * Two mechanisms resolve this: + * - A visited bitmap (nfaVisitedElems) blocks revisitation of the + * same element, preventing infinite loops (safety) + * - 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 + * added (correctness) + * + * Significance: Cycle detection guarantees termination, and + * fast-forward guarantees that the min condition is satisfied. + * Without these, patterns containing nullable groups would fall + * into infinite loops or fail to match. + * + * (5) Match Pruning (IX-4(e)) + * + * When a state reaches FIN during advance, all remaining unprocessed + * states of that context are removed. Because of DFS order, the path + * that reaches FIN first has the highest preferment, so the remaining + * paths are inferior. + * + * Significance: Once the best match is determined, exploration of + * inferior paths is immediately terminated. This mechanism achieves + * both preferment guarantees and performance optimization. + * + * -- Runtime: inter-context -- + * + * (6) Early Termination (SKIP PAST LAST ROW) + * + * In SKIP PAST LAST ROW mode, when a match is found, subsequent + * contexts whose start rows fall within the match range are pruned + * immediately without further processing. + * In SKIP TO NEXT ROW mode, overlapping contexts are preserved + * because each row requires its own independent match. + * + * Significance: Prunes subsequent contexts whose start rows overlap + * with a prior match range, avoiding unnecessary processing. + * + * (7) Context Absorption (Chapter VIII) + * + * If an independent context is created for each row, O(n^2) states + * accumulate. By exploiting the monotonicity that an earlier-started + * context subsumes the states of a later-started context, redundant + * contexts are eliminated early. + * + * Absorbability is determined per-element; comparison is performed + * only at elements with the RPR_ELEM_ABSORBABLE flag (see IV-5). + * + * Significance: Keeps the number of active contexts at a constant + * 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 + * collectPatternVariables rpr.c Variable collection + * filterDefineClause rpr.c DEFINE filtering + * buildRPRPattern rpr.c NFA compilation main + * optimizeRPRPattern rpr.c AST optimization + * fillRPRPattern rpr.c NFA element generation + * finalizeRPRPattern rpr.c Finalization + * computeAbsorbability rpr.c Absorption analysis + * update_reduced_frame nodeWindowAgg.c Execution main loop + * nfa_evaluate_row nodeWindowAgg.c 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 + * + * Appendix B. Data Structure Relationship Diagram + * ============================================================================ + * + * Parser Layer + * -------- + * RPCommonSyntax + * |--- rpSkipTo: RPSkipTo + * |--- initial: bool + * +--- rpPattern: RPRPatternNode* (tree) + * |--- nodeType: VAR | SEQ | ALT | GROUP + * |--- min, max: quantifier + * |--- varName: variable name (VAR only) + * +--- children: List* (SEQ/ALT/GROUP only) + * + * Planner Layer + * ---------- + * WindowAgg (plan node) + * |--- rpSkipTo: RPSkipTo + * |--- defineClause: List + * +--- rpPattern: RPRPattern* + * |--- numVars: int + * |--- varNames: char** + * |--- maxDepth: RPRDepth + * |--- isAbsorbable: bool + * |--- numElements: int + * +--- elements: RPRPatternElement[] (flat array) + * |--- varId (1B) + * |--- depth (1B) + * |--- flags (1B) + * |--- reserved (1B) + * |--- min, max (4B + 4B) + * +--- next, jump (2B + 2B) + * + * Executor Layer + * ---------- + * WindowAggState + * |--- rpSkipTo: RPSkipTo (AFTER MATCH SKIP mode) + * |--- rpPattern: RPRPattern* (copied from plan) + * |--- defineVariableList: List (variable names, DEFINE order) + * |--- defineClauseList: List + * |--- nfaVarMatched: bool[] (per-row cache) + * |--- nfaVisitedElems: bitmapword* (cycle detection) + * |--- nfaStateSize: Size (pre-calculated RPRNFAState allocation size) + * |--- nfaContext <-> nfaContextTail (doubly-linked list) + * | +--- RPRNFAContext + * | |--- states: RPRNFAState* (linked list) + * | | |--- elemIdx + * | | |--- counts[] + * | | +--- isAbsorbable + * | |--- matchStartRow, matchEndRow + * | |--- lastProcessedRow + * | |--- matchedState (cloned on FIN arrival) + * | |--- hasAbsorbableState + * | +--- allStatesAbsorbable + * |--- nfaContextFree (recycling pool) + * +--- nfaStateFree (recycling pool) + * + * Appendix C. NFA Element Array Examples + * ============================================================================ + * + * C-1. PATTERN (A B C) + * + * idx varId depth min max next jump + * ------------------------------------------ + * 0 A 0 1 1 1 -1 + * 1 B 0 1 1 2 -1 + * 2 C 0 1 1 3 -1 + * 3 FIN 0 1 1 -1 -1 + * + * C-2. PATTERN (A+ B*) + * + * idx varId depth min max next jump flags + * ------------------------------------------------------------------------ + * 0 A 0 1 INF 1 -1 ABSORBABLE | ABSORBABLE_BRANCH + * 1 B 0 0 INF 2 -1 + * 2 FIN 0 1 1 -1 -1 + * + * Only A+ is the absorption point (Case 1). Once past A, + * absorption is permanently disabled for that state. + * + * C-3. PATTERN (A | B | C) + * + * idx varId depth min max next jump + * ---------------------------------------- + * 0 ALT 0 1 1 1 -1 alternation start + * 1 A 1 1 1 4 2 branch 1 -> FIN, jump -> branch 2 + * 2 B 1 1 1 4 3 branch 2 -> FIN, jump -> branch 3 + * 3 C 1 1 1 4 -1 branch 3 -> FIN + * 4 FIN 0 1 1 -1 -1 + * + * C-4. PATTERN ((A B)+ C) + * + * idx varId depth min max next jump flags + * -------------------------------------------------------------------------- + * 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH + * 1 A 1 1 1 2 -1 ABSORBABLE_BRANCH + * 2 B 1 1 1 3 -1 ABSORBABLE_BRANCH + * 3 END 0 1 INF 4 1 ABSORBABLE | ABSORBABLE_BRANCH + * 4 C 0 1 1 5 -1 + * 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). + * + * C-5. PATTERN ((A | B)+? C) + * + * idx varId depth min max next jump flags + * ------------------------------------------------------------------- + * 0 BEGIN 0 1 INF 1 5 RELUCTANT, group start + * 1 ALT 1 1 1 2 -1 alternation start + * 2 A 2 1 1 4 3 branch 1 + * 3 B 2 1 1 4 -1 branch 2 + * 4 END 0 1 INF 5 1 RELUCTANT, group end + * 5 C 0 1 1 6 -1 + * 6 FIN 0 1 1 -1 -1 + * + * C-6. PATTERN ((A+ B)+ C) -- Absorbability flag example + * + * idx varId depth min max next jump flags + * --------------------------------------------------------------------------- + * 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH, group start + * 1 A 1 1 INF 2 -1 ABSORBABLE | ABSORBABLE_BRANCH + * 2 B 1 1 1 3 -1 + * 3 END 0 1 INF 4 1 group end + * 4 C 0 1 1 5 -1 + * 5 FIN 0 1 1 -1 -1 + * + * Recurses from BEGIN into the body -> A matches Case 1 (simple VAR+). + * A gets ABSORBABLE | ABSORBABLE_BRANCH, BEGIN gets ABSORBABLE_BRANCH. + * 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 + * + * idx varId depth min max next jump flags + * --------------------------------------------------------------------------- + * 0 BEGIN 0 1 INF 1 6 ABSORBABLE_BRANCH + * 1 ALT 1 1 1 2 -1 ABSORBABLE_BRANCH + * 2 A 2 1 INF 3 4 ABSORBABLE | ABSORBABLE_BRANCH + * 3 B 2 1 1 5 -1 + * 4 C 2 0 INF 5 -1 ABSORBABLE | ABSORBABLE_BRANCH + * 5 END 0 1 INF 6 1 EMPTY_LOOP + * 6 D 0 1 1 7 -1 + * 7 FIN 0 1 1 -1 -1 + * + * ALT branches are checked independently for absorbability. + * Branch 1: A+ matches Case 1 -> A gets ABSORBABLE. B has no flag. + * Branch 2: C* matches Case 1 -> C gets ABSORBABLE. + * Both A and C get ABSORBABLE_BRANCH as part of their respective branch + * paths. + * END has EMPTY_LOOP: branch 2 (C*) is nullable, making the group body + * nullable. + * BEGIN and ALT get ABSORBABLE_BRANCH (on the path to absorbable elements). + * + * ============================================================================ + * End of document + * ============================================================================ + */ + +/* Bitmap macros for NFA cycle detection (cf. bitmapset.c, tidbitmap.c) */ +#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) +#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) + +/* Forward declarations - NFA state management */ +static RPRNFAState *nfa_state_alloc(WindowAggState *winstate); +static void nfa_state_free(WindowAggState *winstate, RPRNFAState *state); +static void nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list); +static RPRNFAState *nfa_state_create(WindowAggState *winstate, int16 elemIdx, + int32 *counts, bool sourceAbsorbable); +static bool nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, + RPRNFAState *s2); +static bool nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state); +static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, int64 matchEndRow); + +/* Forward declarations - NFA context management (internal) */ +static RPRNFAContext *nfa_context_alloc(WindowAggState *winstate); +static void nfa_unlink_context(WindowAggState *winstate, RPRNFAContext *ctx); + +/* Forward declarations - NFA statistics */ +static void nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 newLen); +static void nfa_record_context_skipped(WindowAggState *winstate, int64 skippedLen); +static void nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen); + +/* Forward declarations - NFA absorption */ +static void nfa_update_absorption_flags(RPRNFAContext *ctx); +static bool nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, + RPRNFAContext *newer); +static void nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx); +static void nfa_absorb_contexts(WindowAggState *winstate); + +/* Forward declarations - NFA match and advance */ +static bool nfa_eval_var_match(WindowAggState *winstate, + RPRPatternElement *elem, bool *varMatched); +static void nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, + bool *varMatched); +static void nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, int64 currentPos); +static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *nextElem, + int64 currentPos); +static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos); +static void nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos); +static void nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos); +static void nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos); +static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, + 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, + * resulting in UNMATCHED. For reluctant min=0 patterns (A*?, A??), + * the skip path reaches FIN first and early termination prunes enter + * paths, yielding an immediate empty (unmatched) result. For + * greedy patterns (A*), the enter path adds VAR states first, then + * the skip FIN is recorded but VAR states survive for later matching. + * + * 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. + */ + +/* + * nfa_state_alloc + * + * 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_alloc(WindowAggState *winstate) +{ + RPRNFAState *state; + + /* Try to reuse from free list first */ + if (winstate->nfaStateFree != NULL) + { + state = winstate->nfaStateFree; + winstate->nfaStateFree = state->next; + } + else + { + /* Allocate in partition context for proper lifetime */ + state = MemoryContextAlloc(winstate->partcontext, winstate->nfaStateSize); + } + + /* Initialize entire state to zero */ + memset(state, 0, winstate->nfaStateSize); + + /* Update statistics */ + winstate->nfaStatesActive++; + winstate->nfaStatesTotalCreated++; + if (winstate->nfaStatesActive > winstate->nfaStatesMax) + winstate->nfaStatesMax = winstate->nfaStatesActive; + + return state; +} + +/* + * nfa_state_free + * + * Return a state to the free list for later reuse. + */ +static void +nfa_state_free(WindowAggState *winstate, RPRNFAState *state) +{ + winstate->nfaStatesActive--; + state->next = winstate->nfaStateFree; + winstate->nfaStateFree = state; +} + +/* + * nfa_state_free_list + * + * Return all states in a list to the free list. + */ +static void +nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list) +{ + RPRNFAState *next; + + for (; list != NULL; list = next) + { + next = list->next; + nfa_state_free(winstate, list); + } +} + +/* + * nfa_state_create + * + * Create a new state with given elemIdx and counts. + * isAbsorbable is computed immediately: inherited AND new element's flag. + * Monotonic property: once false, stays false through all transitions. + * + * Caller is responsible for linking the returned state. + */ +static RPRNFAState * +nfa_state_create(WindowAggState *winstate, int16 elemIdx, + int32 *counts, bool sourceAbsorbable) +{ + RPRPattern *pattern = winstate->rpPattern; + int maxDepth = pattern->maxDepth; + RPRNFAState *state = nfa_state_alloc(winstate); + RPRPatternElement *elem = &pattern->elements[elemIdx]; + + state->elemIdx = elemIdx; + if (counts != NULL && maxDepth > 0) + memcpy(state->counts, counts, sizeof(int32) * maxDepth); + + /* + * Compute isAbsorbable immediately at transition time. isAbsorbable = + * sourceAbsorbable && (elem->flags & ABSORBABLE_BRANCH) Monotonic: once + * false, stays false (can't re-enter absorbable region). + */ + state->isAbsorbable = sourceAbsorbable && RPRElemIsAbsorbableBranch(elem); + + return state; +} + +/* + * nfa_states_equal + * + * Check if two states are equivalent (same elemIdx and counts). + */ +static bool +nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elem; + int compareDepth; + + if (s1->elemIdx != s2->elemIdx) + return false; + + /* Compare counts up to current element's depth */ + elem = &pattern->elements[s1->elemIdx]; + compareDepth = elem->depth + 1; /* depth 0 needs 1 count, etc. */ + + if (memcmp(s1->counts, s2->counts, sizeof(int32) * compareDepth) != 0) + return false; + + return true; +} + +/* + * nfa_add_state_unique + * + * Add a state to ctx->states at the END, only if no duplicate exists. + * Returns true if state was added, false if duplicate found (state is freed). + * Earlier states have better lexical order (DFS traversal order), so existing wins. + */ +static bool +nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state) +{ + RPRNFAState *s; + RPRNFAState *tail = NULL; + + /* Check for duplicate and find tail */ + for (s = ctx->states; s != NULL; s = s->next) + { + if (nfa_states_equal(winstate, s, state)) + { + /* + * Duplicate found - existing has better lexical order, discard + * new + */ + nfa_state_free(winstate, state); + winstate->nfaStatesMerged++; + return false; + } + tail = s; + } + + /* No duplicate, add at end */ + state->next = NULL; + if (tail == NULL) + ctx->states = state; + else + tail->next = state; + + return true; +} + +/* + * nfa_add_matched_state + * + * Record a state that reached FIN, replacing any previous match. + * + * For SKIP PAST LAST ROW, also prune subsequent contexts whose start row + * falls within the match range, as they cannot produce output rows. + */ +static void +nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, int64 matchEndRow) +{ + if (ctx->matchedState != NULL) + nfa_state_free(winstate, ctx->matchedState); + + ctx->matchedState = state; + state->next = NULL; + ctx->matchEndRow = matchEndRow; + + /* Prune contexts that started within this match's range */ + if (winstate->rpSkipTo == ST_PAST_LAST_ROW) + { + RPRNFAContext *nextCtx; + int64 skippedLen; + + while (ctx->next != NULL && + ctx->next->matchStartRow <= matchEndRow) + { + nextCtx = ctx->next; + ctx->next = ctx->next->next; + + Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); + skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; + nfa_record_context_skipped(winstate, skippedLen); + + ExecRPRFreeContext(winstate, nextCtx); + } + if (ctx->next == NULL) + winstate->nfaContextTail = ctx; + } +} + +/* + * nfa_context_alloc + * + * Allocate an NFA context, reusing from free list if available. + */ +static RPRNFAContext * +nfa_context_alloc(WindowAggState *winstate) +{ + RPRNFAContext *ctx; + + if (winstate->nfaContextFree != NULL) + { + ctx = winstate->nfaContextFree; + winstate->nfaContextFree = ctx->next; + } + else + { + /* Allocate in partition context for proper lifetime */ + ctx = MemoryContextAlloc(winstate->partcontext, sizeof(RPRNFAContext)); + } + + ctx->next = NULL; + ctx->prev = NULL; + ctx->states = NULL; + ctx->matchStartRow = -1; + ctx->matchEndRow = -1; + ctx->lastProcessedRow = -1; + ctx->matchedState = NULL; + + /* Initialize two-flag absorption design based on pattern */ + ctx->hasAbsorbableState = winstate->rpPattern->isAbsorbable; + ctx->allStatesAbsorbable = winstate->rpPattern->isAbsorbable; + + /* Update statistics */ + winstate->nfaContextsActive++; + winstate->nfaContextsTotalCreated++; + if (winstate->nfaContextsActive > winstate->nfaContextsMax) + winstate->nfaContextsMax = winstate->nfaContextsActive; + + return ctx; +} + +/* + * nfa_unlink_context + * + * Remove a context from the doubly-linked active context list. + * Updates head (nfaContext) and tail (nfaContextTail) as needed. + */ +static void +nfa_unlink_context(WindowAggState *winstate, RPRNFAContext *ctx) +{ + if (ctx->prev != NULL) + ctx->prev->next = ctx->next; + else + winstate->nfaContext = ctx->next; /* was head */ + + if (ctx->next != NULL) + ctx->next->prev = ctx->prev; + else + winstate->nfaContextTail = ctx->prev; /* was tail */ + + ctx->next = NULL; + ctx->prev = NULL; +} + +/* + * nfa_update_length_stats + * + * Helper function to update min/max/total length statistics. + * Called when tracking match/mismatch/absorbed/skipped lengths. + */ +static void +nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 newLen) +{ + if (count == 1) + { + stats->min = newLen; + stats->max = newLen; + } + else + { + if (newLen < stats->min) + stats->min = newLen; + if (newLen > stats->max) + stats->max = newLen; + } + stats->total += newLen; +} + +/* + * nfa_record_context_skipped + * + * Record a skipped context in statistics. + */ +static void +nfa_record_context_skipped(WindowAggState *winstate, int64 skippedLen) +{ + winstate->nfaContextsSkipped++; + nfa_update_length_stats(winstate->nfaContextsSkipped, + &winstate->nfaSkippedLen, + skippedLen); +} + +/* + * nfa_record_context_absorbed + * + * Record an absorbed context in statistics. + */ +static void +nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen) +{ + winstate->nfaContextsAbsorbed++; + nfa_update_length_stats(winstate->nfaContextsAbsorbed, + &winstate->nfaAbsorbedLen, + absorbedLen); +} + +/* + * nfa_update_absorption_flags + * + * Update context's absorption flags after state changes. + * + * Two flags control absorption behavior: + * 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. + * + * Optimization: Once hasAbsorbableState becomes false, both flags remain false + * permanently, so we skip recalculation. + */ +static void +nfa_update_absorption_flags(RPRNFAContext *ctx) +{ + RPRNFAState *state; + bool hasAbsorbable = false; + bool allAbsorbable = true; + + /* + * Optimization: Once hasAbsorbableState becomes false, it stays false. No + * need to recalculate - both flags remain false permanently. + */ + if (!ctx->hasAbsorbableState) + { + ctx->allStatesAbsorbable = false; + return; + } + + /* No states means no absorbable states */ + if (ctx->states == NULL) + { + ctx->hasAbsorbableState = false; + ctx->allStatesAbsorbable = false; + return; + } + + /* + * Iterate through all states to check absorption status. Uses + * state->isAbsorbable which tracks if state is in absorbable region. This + * is different from RPRElemIsAbsorbable(elem) which checks judgment + * point. + */ + for (state = ctx->states; state != NULL; state = state->next) + { + if (state->isAbsorbable) + hasAbsorbable = true; + else + allAbsorbable = false; + } + + ctx->hasAbsorbableState = hasAbsorbable; + ctx->allStatesAbsorbable = allAbsorbable; +} + +/* + * nfa_states_covered + * + * Check if all states in newer context are "covered" by older context. + * + * A newer state is covered when older context has an absorbable state at the + * same pattern element (elemIdx) with count >= newer's count at that depth. + * The covering state must be absorbable because only absorbable states can + * guarantee to produce superset matches. + * + * If all newer states are covered, newer context's eventual matches will be + * a subset of older context's matches, making newer redundant. + */ +static bool +nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, RPRNFAContext *newer) +{ + RPRNFAState *newerState; + + for (newerState = newer->states; newerState != NULL; newerState = newerState->next) + { + RPRNFAState *olderState; + RPRPatternElement *elem; + int depth; + bool found = false; + + /* All states are absorbable (caller checks allStatesAbsorbable) */ + elem = &pattern->elements[newerState->elemIdx]; + depth = elem->depth; + + for (olderState = older->states; olderState != NULL; olderState = olderState->next) + { + /* Covering state must also be absorbable */ + if (olderState->isAbsorbable && + olderState->elemIdx == newerState->elemIdx && + olderState->counts[depth] >= newerState->counts[depth]) + { + found = true; + break; + } + } + + if (!found) + return false; + } + + return true; +} + +/* + * nfa_try_absorb_context + * + * Try to absorb ctx (newer) into an older in-progress context. + * Returns true if ctx was absorbed and freed. + * + * Absorption requires three conditions: + * 1. ctx must have all states absorbable (allStatesAbsorbable). + * If ctx has any non-absorbable state, it may produce unique matches. + * 2. older must have at least one absorbable state (hasAbsorbableState). + * Without absorbable states, older cannot cover newer's states. + * 3. All ctx states must be covered by older's absorbable states. + * This ensures older will produce all matches that ctx would produce. + * + * Context list is ordered by creation time (oldest first via prev chain). + * Each row creates at most one context, so earlier contexts have smaller + * matchStartRow values. + */ +static void +nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRNFAContext *older; + + /* Early exit: ctx must have all states absorbable */ + if (!ctx->allStatesAbsorbable) + return; + + for (older = ctx->prev; older != NULL; older = older->prev) + { + /* + * By invariant: ctx->prev chain is in creation order (oldest first), + * and each row creates at most one context. So all contexts in this + * chain have matchStartRow < ctx->matchStartRow. + */ + + /* Older must also be in-progress */ + if (older->states == NULL) + continue; + + /* Older must have at least one absorbable state */ + if (!older->hasAbsorbableState) + continue; + + /* Check if all newer states are covered by older */ + if (nfa_states_covered(pattern, older, ctx)) + { + int64 absorbedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1; + + ExecRPRFreeContext(winstate, ctx); + nfa_record_context_absorbed(winstate, absorbedLen); + return; + } + } +} + +/* + * nfa_absorb_contexts + * + * Absorb redundant contexts to reduce memory usage and computation. + * + * For patterns like A+, newer contexts starting later will produce subset + * matches of older contexts with higher counts. By absorbing these redundant + * contexts early, we avoid duplicate work. + * + * Iterates from tail (newest) toward head (oldest) via prev chain. + * Only in-progress contexts (states != NULL) are candidates for absorption; + * completed contexts represent valid match results. + */ +static void +nfa_absorb_contexts(WindowAggState *winstate) +{ + RPRNFAContext *ctx; + RPRNFAContext *nextCtx; + + for (ctx = winstate->nfaContextTail; ctx != NULL; ctx = nextCtx) + { + nextCtx = ctx->prev; + + /* + * Only absorb in-progress contexts; completed contexts are valid + * results + */ + if (ctx->states != NULL) + nfa_try_absorb_context(winstate, ctx); + } +} + +/* + * nfa_eval_var_match + * + * Evaluate if a VAR element matches the current row. + * Undefined variables (varId >= defineVariableList length) default to TRUE. + */ +static bool +nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, + bool *varMatched) +{ + /* This function should only be called for VAR elements */ + Assert(RPRElemIsVar(elem)); + + if (varMatched == NULL) + return false; + if (elem->varId >= list_length(winstate->defineVariableList)) + return true; + return varMatched[elem->varId]; +} + +/* + * nfa_match + * + * Match phase (convergence): evaluate VAR elements against current row. + * Only updates counts and removes dead states. Minimal transitions. + * + * For VAR elements: + * - matched: count++, keep state (unless count > max) + * - not matched: remove state (exit alternatives already exist from + * previous advance when count >= min was satisfied) + * + * For simple VARs (min=max=1) followed by END: + * - Advance to END and update group count before absorb phase + * - This ensures absorption can compare states by group completion + * + * Non-VAR elements (ALT, END, FIN) are kept as-is for advance phase. + */ +static void +nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elements = pattern->elements; + RPRNFAState **prevPtr = &ctx->states; + RPRNFAState *state; + RPRNFAState *nextState; + + /* + * Evaluate VAR elements against current row. For simple VARs with END + * next, advance to END and update group count inline so absorb phase can + * compare states properly. + */ + for (state = ctx->states; state != NULL; state = nextState) + { + RPRPatternElement *elem = &elements[state->elemIdx]; + + nextState = state->next; + + if (RPRElemIsVar(elem)) + { + bool matched; + int depth = elem->depth; + int32 count = state->counts[depth]; + + matched = nfa_eval_var_match(winstate, elem, varMatched); + + if (matched) + { + /* Increment count */ + if (count < RPR_COUNT_MAX) + count++; + + /* Max constraint should not be exceeded */ + Assert(elem->max == RPR_QUANTITY_INF || count <= elem->max); + + state->counts[depth] = count; + + /* + * For simple VAR (min=max=1) with END next, advance to END + * and update group count inline. This keeps state in place, + * preserving lexical order. + */ + if (elem->min == 1 && elem->max == 1 && + RPRElemIsEnd(&elements[elem->next])) + { + RPRPatternElement *endElem = &elements[elem->next]; + int endDepth = endElem->depth; + int32 endCount = state->counts[endDepth]; + + Assert(count == 1); + + /* Increment group count with overflow protection */ + if (endCount < RPR_COUNT_MAX) + endCount++; + + /* + * END's max can never be exceeded here because + * nfa_advance_end only loops when count < max, so + * endCount entering inline advance is at most max-1, and + * incrementing yields at most max. + */ + Assert(endElem->max == RPR_QUANTITY_INF || + endCount <= endElem->max); + + state->elemIdx = elem->next; + state->counts[endDepth] = endCount; + } + /* else: stay at VAR for advance phase */ + } + else + { + /* + * Not matched - remove state. Exit alternatives were already + * created by advance phase when count >= min was satisfied. + */ + *prevPtr = nextState; + nfa_state_free(winstate, state); + continue; + } + } + /* Non-VAR elements: keep as-is for advance phase */ + + prevPtr = &state->next; + } +} + +/* + * nfa_route_to_elem + * + * Route state to next element. If VAR, add to ctx->states and process + * skip path if optional. Otherwise, continue epsilon expansion via recursion. + */ +static void +nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *nextElem, + int64 currentPos) +{ + if (RPRElemIsVar(nextElem)) + { + RPRNFAState *skipState = NULL; + + /* Create skip state before add_unique, which may free state */ + if (RPRElemCanSkip(nextElem)) + skipState = nfa_state_create(winstate, nextElem->next, + state->counts, state->isAbsorbable); + + nfa_add_state_unique(winstate, ctx, state); + + if (skipState != NULL) + nfa_advance_state(winstate, ctx, skipState, currentPos); + } + else + { + nfa_advance_state(winstate, ctx, state, currentPos); + } +} + +/* + * nfa_advance_alt + * + * Handle ALT element: expand all branches in lexical order via DFS. + */ +static void +nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elements = pattern->elements; + RPRElemIdx altIdx = elem->next; + + while (altIdx >= 0 && altIdx < pattern->numElements) + { + RPRPatternElement *altElem = &elements[altIdx]; + RPRNFAState *newState; + + /* Stop if element is outside ALT scope (not a branch) */ + if (altElem->depth <= elem->depth) + break; + + /* Create independent state for each branch */ + newState = nfa_state_create(winstate, altIdx, + state->counts, state->isAbsorbable); + + /* Recursively process this branch before next */ + nfa_advance_state(winstate, ctx, newState, currentPos); + altIdx = altElem->jump; + } + + nfa_state_free(winstate, state); +} + +/* + * nfa_advance_begin + * + * Handle BEGIN element: group entry logic. + * BEGIN is only visited at initial group entry (count is always 0). + * If min=0, creates a skip path past the group. + * Loop-back from END goes directly to first child, bypassing BEGIN. + */ +static void +nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elements = pattern->elements; + RPRNFAState *skipState = NULL; + + state->counts[elem->depth] = 0; + + /* Optional group: create skip path (but don't route yet) */ + if (elem->min == 0) + { + skipState = nfa_state_create(winstate, elem->jump, + state->counts, state->isAbsorbable); + } + + if (skipState != NULL && RPRElemIsReluctant(elem)) + { + RPRNFAState *savedMatch = ctx->matchedState; + + /* Reluctant: skip first (prefer fewer iterations), enter second */ + nfa_route_to_elem(winstate, ctx, skipState, + &elements[elem->jump], currentPos); + + /* + * If skip path reached FIN, shortest match is found. Skip group entry + * to prevent longer matches. + */ + if (ctx->matchedState != savedMatch) + { + nfa_state_free(winstate, state); + return; + } + + state->elemIdx = elem->next; + nfa_route_to_elem(winstate, ctx, state, + &elements[state->elemIdx], currentPos); + } + else + { + /* Greedy: enter first, skip second */ + state->elemIdx = elem->next; + nfa_route_to_elem(winstate, ctx, state, + &elements[state->elemIdx], currentPos); + + if (skipState != NULL) + { + nfa_route_to_elem(winstate, ctx, skipState, + &elements[elem->jump], currentPos); + } + } +} + +/* + * nfa_advance_end + * + * Handle END element: group repetition logic. + * Decides whether to loop back or exit based on count vs min/max. + */ +static void +nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elements = pattern->elements; + int depth = elem->depth; + int32 count = state->counts[depth]; + + if (count < elem->min) + { + RPRPatternElement *jumpElem; + RPRNFAState *ffState = NULL; + + /* Snapshot state for ff path before modifying for loop-back */ + if (RPRElemCanEmptyLoop(elem)) + ffState = nfa_state_create(winstate, state->elemIdx, + state->counts, state->isAbsorbable); + + /* Loop back for real matches (primary path) */ + for (int d = depth + 1; d < pattern->maxDepth; d++) + state->counts[d] = 0; + state->elemIdx = elem->jump; + jumpElem = &elements[state->elemIdx]; + nfa_route_to_elem(winstate, ctx, state, jumpElem, + currentPos); + + /* + * Fast-forward fallback for nullable bodies. E.g. (A?){2,3} when A + * doesn't match: the loop-back produces empty iterations that cycle + * detection would kill. Instead, exit directly treating all + * remaining required iterations as empty. Route to elem->next (not + * nfa_advance_end) to avoid creating competing greedy/reluctant loop + * states. + */ + if (ffState != NULL) + { + RPRPatternElement *nextElem; + + ffState->counts[depth] = 0; + ffState->elemIdx = elem->next; + nextElem = &elements[ffState->elemIdx]; + + /* END->END: increment outer END's count */ + if (RPRElemIsEnd(nextElem) && + ffState->counts[nextElem->depth] < RPR_COUNT_MAX) + ffState->counts[nextElem->depth]++; + + nfa_route_to_elem(winstate, ctx, ffState, nextElem, + currentPos); + } + } + else if (elem->max != RPR_QUANTITY_INF && count >= elem->max) + { + /* Must exit: reached max iterations. */ + RPRPatternElement *nextElem; + + state->counts[depth] = 0; + state->elemIdx = elem->next; + nextElem = &elements[state->elemIdx]; + + /* END->END: increment outer END's count */ + if (RPRElemIsEnd(nextElem) && state->counts[nextElem->depth] < RPR_COUNT_MAX) + state->counts[nextElem->depth]++; + + nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); + } + else + { + /* + * Between min and max (with at least one iteration) - can exit or + * loop. Greedy: loop first (prefer more iterations). Reluctant: exit + * first (prefer fewer iterations). + */ + RPRNFAState *exitState; + RPRPatternElement *jumpElem; + RPRPatternElement *nextElem; + + /* + * Create exit state first (need original counts before modifying + * state) + */ + exitState = nfa_state_create(winstate, elem->next, + state->counts, state->isAbsorbable); + exitState->counts[depth] = 0; + nextElem = &elements[exitState->elemIdx]; + + /* END->END: increment outer END's count */ + if (RPRElemIsEnd(nextElem) && exitState->counts[nextElem->depth] < RPR_COUNT_MAX) + exitState->counts[nextElem->depth]++; + + /* Prepare loop state */ + for (int d = depth + 1; d < pattern->maxDepth; d++) + state->counts[d] = 0; + state->elemIdx = elem->jump; + jumpElem = &elements[state->elemIdx]; + + if (RPRElemIsReluctant(elem)) + { + RPRNFAState *savedMatch = ctx->matchedState; + + /* Exit first (preferred for reluctant) */ + nfa_route_to_elem(winstate, ctx, exitState, nextElem, + currentPos); + + /* + * If exit path reached FIN, shortest match is found. Skip loop to + * prevent longer matches from replacing it. + */ + if (ctx->matchedState != savedMatch) + { + nfa_state_free(winstate, state); + return; + } + + /* Loop second */ + nfa_route_to_elem(winstate, ctx, state, jumpElem, + currentPos); + } + else + { + /* Loop first (preferred for greedy) */ + nfa_route_to_elem(winstate, ctx, state, jumpElem, + currentPos); + /* Exit second */ + nfa_route_to_elem(winstate, ctx, exitState, nextElem, + currentPos); + } + } +} + +/* + * nfa_advance_var + * + * Handle VAR element: loop/exit transitions. + * After match phase, all VAR states have matched - decide next action. + */ +static void +nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, RPRPatternElement *elem, + int64 currentPos) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elements = pattern->elements; + int depth = elem->depth; + int32 count = state->counts[depth]; + bool canLoop = (elem->max == RPR_QUANTITY_INF || count < elem->max); + bool canExit = (count >= elem->min); + + /* After a successful match, count >= 1, so at least one must be true */ + Assert(canLoop || canExit); + + if (canLoop && canExit) + { + /* + * Both loop and exit possible. Greedy: loop first (prefer longer + * match). Reluctant: exit first (prefer shorter match). + */ + RPRNFAState *cloneState; + RPRPatternElement *nextElem; + bool reluctant = RPRElemIsReluctant(elem); + + /* + * Clone state for the second-priority path. For greedy, clone is the + * loop state; for reluctant, clone is the exit state. + */ + if (reluctant) + { + RPRNFAState *savedMatch = ctx->matchedState; + + /* Clone for exit, original stays for loop */ + cloneState = nfa_state_create(winstate, elem->next, + state->counts, state->isAbsorbable); + cloneState->counts[depth] = 0; + nextElem = &elements[cloneState->elemIdx]; + + /* When exiting directly to an outer END, increment its count */ + if (RPRElemIsEnd(nextElem)) + { + if (cloneState->counts[nextElem->depth] < RPR_COUNT_MAX) + cloneState->counts[nextElem->depth]++; + } + + /* Exit first (preferred for reluctant) */ + nfa_route_to_elem(winstate, ctx, cloneState, nextElem, + currentPos); + + /* + * If exit path reached FIN, the shortest match is found. Skip + * loop state to prevent longer matches from replacing it. + */ + if (ctx->matchedState != savedMatch) + { + nfa_state_free(winstate, state); + return; + } + + /* Loop second */ + nfa_add_state_unique(winstate, ctx, state); + } + else + { + /* Clone for loop, original used for exit */ + cloneState = nfa_state_create(winstate, state->elemIdx, + state->counts, state->isAbsorbable); + + /* Loop first (preferred for greedy) */ + nfa_add_state_unique(winstate, ctx, cloneState); + + /* Exit second */ + state->counts[depth] = 0; + state->elemIdx = elem->next; + nextElem = &elements[state->elemIdx]; + + /* + * When exiting directly to an outer END, increment its iteration + * count. Simple VARs (min=max=1) handle this via inline advance + * in nfa_match, but quantified VARs bypass that path. + */ + if (RPRElemIsEnd(nextElem)) + { + if (state->counts[nextElem->depth] < RPR_COUNT_MAX) + state->counts[nextElem->depth]++; + } + + nfa_route_to_elem(winstate, ctx, state, nextElem, + currentPos); + } + } + else if (canLoop) + { + /* Loop only: keep state as-is */ + nfa_add_state_unique(winstate, ctx, state); + } + else if (canExit) + { + /* Exit only: advance to next element */ + RPRPatternElement *nextElem; + + state->counts[depth] = 0; + state->elemIdx = elem->next; + nextElem = &elements[state->elemIdx]; + + /* See comment above: increment outer END count for quantified VARs */ + if (RPRElemIsEnd(nextElem)) + { + if (state->counts[nextElem->depth] < RPR_COUNT_MAX) + state->counts[nextElem->depth]++; + } + + nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); + } +} + +/* + * nfa_advance_state + * + * Recursively process a single state through epsilon transitions. + * DFS traversal ensures states are added to ctx->states in lexical order. + */ +static void +nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state, int64 currentPos) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elem; + + Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements); + + /* Cycle detection: if this elemIdx was already visited in this DFS, bail */ + if (winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] & + ((bitmapword) 1 << BITNUM(state->elemIdx))) + { + nfa_state_free(winstate, state); + return; + } + winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] |= + ((bitmapword) 1 << BITNUM(state->elemIdx)); + + elem = &pattern->elements[state->elemIdx]; + + switch (elem->varId) + { + case RPR_VARID_FIN: + /* FIN: record match */ + nfa_add_matched_state(winstate, ctx, state, currentPos); + break; + + case RPR_VARID_ALT: + nfa_advance_alt(winstate, ctx, state, elem, currentPos); + break; + + case RPR_VARID_BEGIN: + nfa_advance_begin(winstate, ctx, state, elem, currentPos); + break; + + case RPR_VARID_END: + nfa_advance_end(winstate, ctx, state, elem, currentPos); + break; + + default: + /* VAR element */ + nfa_advance_var(winstate, ctx, state, elem, currentPos); + break; + } +} + +/* + * nfa_advance + * + * Advance phase (divergence): transition from all surviving states. + * Called after match phase with matched VAR states, or at context creation + * for initial epsilon expansion (with currentPos = startPos - 1). + * + * Processes states in order, using recursive DFS to maintain lexical order. + */ +static void +nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) +{ + RPRNFAState *states = ctx->states; + RPRNFAState *state; + + ctx->states = NULL; /* Will rebuild */ + + /* Process each state in lexical order (DFS order from previous advance) */ + while (states != NULL) + { + RPRNFAState *savedMatchedState = ctx->matchedState; + + /* Clear visited bitmap before each state's DFS expansion */ + memset(winstate->nfaVisitedElems, 0, + sizeof(bitmapword) * winstate->nfaVisitedNWords); + + state = states; + states = states->next; + state->next = NULL; + + nfa_advance_state(winstate, ctx, state, currentPos); + + /* + * Early termination: if a FIN was newly reached in this advance, + * remaining old states have worse lexical order and can be pruned. + * Only check for new FIN arrivals (not ones from previous rows). + */ + if (ctx->matchedState != savedMatchedState && states != NULL) + { + nfa_state_free_list(winstate, states); + break; + } + } +} + + +/*********************************************************************** + * API exposed to nodeWindowAgg.c + ***********************************************************************/ + +/* + * ExecRPRStartContext + * + * Start a new match context at given position. + * Initializes context, state absorption flags, and performs initial advance + * to expand epsilon transitions (ALT branches, optional elements). + * Adds context to the tail of winstate->nfaContext list. + */ +RPRNFAContext * +ExecRPRStartContext(WindowAggState *winstate, int64 startPos) +{ + RPRNFAContext *ctx; + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *elem; + + ctx = nfa_context_alloc(winstate); + ctx->matchStartRow = startPos; + ctx->states = nfa_state_alloc(winstate); /* initial state at elem 0 */ + + elem = &pattern->elements[0]; + + if (RPRElemIsAbsorbableBranch(elem)) + { + ctx->states->isAbsorbable = true; + } + else + { + ctx->hasAbsorbableState = false; + ctx->allStatesAbsorbable = false; + ctx->states->isAbsorbable = false; + } + + /* Add to tail of active context list (doubly-linked, oldest-first) */ + ctx->prev = winstate->nfaContextTail; + ctx->next = NULL; + if (winstate->nfaContextTail != NULL) + winstate->nfaContextTail->next = ctx; + else + winstate->nfaContext = ctx; /* first context becomes head */ + winstate->nfaContextTail = ctx; + + /* + * Initial advance (divergence): expand ALT branches and create exit + * states for VAR elements with min=0. This prepares the context for the + * first row's match phase. + * + * Use startPos - 1 as currentPos since no row has been consumed yet. If + * FIN is reached via epsilon transitions, matchEndRow = startPos - 1 + * which is less than matchStartRow, resulting in UNMATCHED treatment. + */ + nfa_advance(winstate, ctx, startPos - 1); + + return ctx; +} + +/* + * ExecRPRGetHeadContext + * + * Return the head context if its start position matches pos. + * Returns NULL if no context exists or head doesn't match pos. + */ +RPRNFAContext * +ExecRPRGetHeadContext(WindowAggState *winstate, int64 pos) +{ + RPRNFAContext *ctx = winstate->nfaContext; + + /* + * Contexts are sorted by matchStartRow ascending. If the head context + * doesn't match pos, no context exists for this position. + */ + if (ctx == NULL || ctx->matchStartRow != pos) + return NULL; + + return ctx; +} + +/* + * ExecRPRFreeContext + * + * Unlink context from active list and return it to free list. + * Also frees any states in the context. + */ +void +ExecRPRFreeContext(WindowAggState *winstate, RPRNFAContext *ctx) +{ + /* Unlink from active list first */ + nfa_unlink_context(winstate, ctx); + + /* Update statistics */ + winstate->nfaContextsActive--; + + if (ctx->states != NULL) + nfa_state_free_list(winstate, ctx->states); + if (ctx->matchedState != NULL) + nfa_state_free(winstate, ctx->matchedState); + + ctx->states = NULL; + ctx->matchedState = NULL; + ctx->next = winstate->nfaContextFree; + winstate->nfaContextFree = ctx; +} + +/* + * ExecRPRRecordContextSuccess + * + * Record a successful context in statistics. + */ +void +ExecRPRRecordContextSuccess(WindowAggState *winstate, int64 matchLen) +{ + winstate->nfaMatchesSucceeded++; + nfa_update_length_stats(winstate->nfaMatchesSucceeded, + &winstate->nfaMatchLen, + matchLen); +} + +/* + * ExecRPRRecordContextFailure + * + * Record a failed context in statistics. + * If failedLen == 1, count as pruned (failed on first row). + * If failedLen > 1, count as mismatched and update length stats. + */ +void +ExecRPRRecordContextFailure(WindowAggState *winstate, int64 failedLen) +{ + if (failedLen == 1) + { + winstate->nfaContextsPruned++; + } + else + { + winstate->nfaMatchesFailed++; + nfa_update_length_stats(winstate->nfaMatchesFailed, + &winstate->nfaFailLen, + failedLen); + } +} + +/* + * ExecRPRProcessRow + * + * Process all contexts for one row: + * 1. Match all contexts (convergence) - evaluate VARs, prune dead states + * 2. Absorb redundant contexts - ideal timing after convergence + * 3. Advance all contexts (divergence) - create new states for next row + */ +void +ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, + bool hasLimitedFrame, int64 frameOffset) +{ + RPRNFAContext *ctx; + bool *varMatched = winstate->nfaVarMatched; + + /* + * Phase 1: Match all contexts (convergence). Evaluate VAR elements, + * update counts, remove dead states. + */ + for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + { + if (ctx->states == NULL) + continue; + + /* Check frame boundary - finalize if exceeded */ + if (hasLimitedFrame) + { + int64 ctxFrameEnd = ctx->matchStartRow + frameOffset + 1; + + if (currentPos >= ctxFrameEnd) + { + /* Frame boundary exceeded: force mismatch */ + nfa_match(winstate, ctx, NULL); + continue; + } + } + + nfa_match(winstate, ctx, varMatched); + ctx->lastProcessedRow = currentPos; + } + + /* + * Phase 2: Absorb redundant contexts. After match phase, states have + * converged - ideal for absorption. First update absorption flags that + * may have changed due to state removal. + */ + if (winstate->rpPattern->isAbsorbable) + { + for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + nfa_update_absorption_flags(ctx); + + nfa_absorb_contexts(winstate); + } + + /* + * Phase 3: Advance all contexts (divergence). Create new states + * (loop/exit) from surviving matched states. + */ + for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + { + if (ctx->states == NULL) + continue; + + /* + * Phase 1 already handled frame boundary exceeded contexts by forcing + * mismatch (nfa_match with NULL), which removes all states (all + * states are at VAR positions after advance). So any surviving + * context here must be within its frame boundary. + */ + Assert(!hasLimitedFrame || + currentPos < ctx->matchStartRow + frameOffset + 1); + + nfa_advance(winstate, ctx, currentPos); + } +} + +/* + * ExecRPRCleanupDeadContexts + * + * Remove contexts that have failed (no active states and no match). + * These are contexts that failed during normal processing and should be + * counted as pruned (if length 1) or mismatched (if length > 1). + */ +void +ExecRPRCleanupDeadContexts(WindowAggState *winstate, RPRNFAContext *excludeCtx) +{ + RPRNFAContext *ctx; + RPRNFAContext *next; + + for (ctx = winstate->nfaContext; ctx != NULL; ctx = next) + { + next = ctx->next; + + /* Skip the target context and contexts still processing */ + if (ctx == excludeCtx || ctx->states != NULL) + continue; + + /* Skip successfully matched contexts (will be handled by SKIP logic) */ + if (ctx->matchEndRow >= ctx->matchStartRow) + continue; + + /* + * This is a failed context - count and remove it. Only count if it + * actually processed its start row. Contexts created for + * beyond-partition rows are silently removed. + */ + if (ctx->lastProcessedRow >= ctx->matchStartRow) + { + int64 failedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1; + + ExecRPRRecordContextFailure(winstate, failedLen); + } + /* else: context was never processed (beyond-partition), just remove */ + + ExecRPRFreeContext(winstate, ctx); + } +} + +/* + * ExecRPRFinalizeAllContexts + * + * Finalize all active contexts when partition ends. + * Match with NULL to force mismatch, then advance to process epsilon transitions. + */ +void +ExecRPRFinalizeAllContexts(WindowAggState *winstate, int64 lastPos) +{ + RPRNFAContext *ctx; + + for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + { + if (ctx->states != NULL) + { + nfa_match(winstate, ctx, NULL); + nfa_advance(winstate, ctx, lastPos); + } + } +} diff --git a/src/backend/executor/meson.build b/src/backend/executor/meson.build index dc45be0b2ce..0ff4a5b1d83 100644 --- a/src/backend/executor/meson.build +++ b/src/backend/executor/meson.build @@ -13,6 +13,7 @@ backend_sources += files( 'execParallel.c', 'execPartition.c', 'execProcnode.c', + 'execRPR.c', 'execReplication.c', 'execSRF.c', 'execScan.c', diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 76c1a6bebef..0a9ba5bd4e7 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -39,6 +39,7 @@ #include "catalog/pg_collation_d.h" #include "catalog/pg_proc.h" #include "executor/executor.h" +#include "executor/execRPR.h" #include "executor/nodeWindowAgg.h" #include "miscadmin.h" #include "nodes/nodeFuncs.h" @@ -243,89 +244,23 @@ static void put_notnull_info(WindowObject winobj, int64 pos, int argno, bool isnull); static void attno_map(Node *node); static bool attno_map_walker(Node *node, void *context); -static int row_is_in_reduced_frame(WindowObject winobj, int64 pos); + static bool rpr_is_defined(WindowAggState *winstate); +static int row_is_in_reduced_frame(WindowObject winobj, int64 pos); static void create_reduced_frame_map(WindowAggState *winstate); +static void clear_reduced_frame_map(WindowAggState *winstate); static int get_reduced_frame_map(WindowAggState *winstate, int64 pos); static void register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val); -static void clear_reduced_frame_map(WindowAggState *winstate); static void update_reduced_frame(WindowObject winobj, int64 pos); static void check_rpr_navigation(Node *node, bool is_prev); static bool rpr_navigation_walker(Node *node, void *context); -/* Forward declarations - NFA row processing */ -static void nfa_process_row(WindowAggState *winstate, int64 currentPos, - bool hasLimitedFrame, int64 frameOffset); - -/* Forward declarations - NFA state management */ -static RPRNFAState *nfa_state_alloc(WindowAggState *winstate); -static void nfa_state_free(WindowAggState *winstate, RPRNFAState *state); -static void nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list); -static RPRNFAState *nfa_state_create(WindowAggState *winstate, int16 elemIdx, - int32 *counts, bool sourceAbsorbable); -static bool nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, - RPRNFAState *s2); -static bool nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state); -static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, int64 matchEndRow); - -/* Forward declarations - NFA context management */ -static RPRNFAContext *nfa_context_alloc(WindowAggState *winstate); -static void nfa_unlink_context(WindowAggState *winstate, RPRNFAContext *ctx); -static void nfa_context_free(WindowAggState *winstate, RPRNFAContext *ctx); -static RPRNFAContext *nfa_start_context(WindowAggState *winstate, int64 startPos); -static RPRNFAContext *nfa_get_head_context(WindowAggState *winstate, int64 pos); - -/* Forward declarations - NFA statistics */ -static void nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 newLen); -static void nfa_record_context_success(WindowAggState *winstate, int64 matchLen); -static void nfa_record_context_failure(WindowAggState *winstate, int64 failedLen); -static void nfa_record_context_skipped(WindowAggState *winstate, int64 skippedLen); -static void nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen); - /* Forward declarations - NFA row evaluation */ static bool nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched); -/* Forward declarations - NFA context lifecycle */ -static void nfa_cleanup_dead_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx); -static void nfa_finalize_all_contexts(WindowAggState *winstate, int64 lastPos); - -/* Forward declarations - NFA absorption */ -static void nfa_update_absorption_flags(RPRNFAContext *ctx); -static bool nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, - RPRNFAContext *newer); -static bool nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx); -static void nfa_absorb_contexts(WindowAggState *winstate); - -/* Forward declarations - NFA match and advance */ -static inline bool nfa_eval_var_match(WindowAggState *winstate, - RPRPatternElement *elem, bool *varMatched); -static void nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, - bool *varMatched); -static void nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, int64 currentPos); -static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *nextElem, - int64 currentPos); -static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos); -static void nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos); -static void nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos); -static void nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos); -static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, - int64 currentPos); - /* * Not null info bit array consists of 2-bit items */ @@ -343,10 +278,6 @@ static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, /* calculate shift bits */ #define NN_SHIFT(pos) ((pos) % NN_ITEM_PER_VAR) * NN_BITS_PER_MEMBER -/* Bitmap macros for NFA cycle detection (cf. bitmapset.c, tidbitmap.c) */ -#define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) -#define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) - /* * initialize_windowaggregate * parallel to initialize_aggregates in nodeAgg.c @@ -4002,822 +3933,195 @@ put_notnull_info(WindowObject winobj, int64 pos, int argno, bool isnull) mbp[bpos] = mb; } -/*********************************************************************** - * API exposed to window functions - ***********************************************************************/ - +/* + * rpr_is_defined + * return true if Row pattern recognition is defined. + */ +static bool +rpr_is_defined(WindowAggState *winstate) +{ + return winstate->rpPattern != NULL; +} /* - * WinCheckAndInitializeNullTreatment - * Check null treatment clause and sets ignore_nulls + * ----------------- + * row_is_in_reduced_frame + * Determine whether a row is in the current row's reduced window frame + * according to row pattern matching * - * Window functions should call this to check if they are being called with - * a null treatment clause when they don't allow it, or to set ignore_nulls. + * The row must has been already determined that it is in a full window frame + * and fetched it into slot. + * + * Returns: + * = 0, RPR is not defined. + * >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 unmatched row + * -2, if the row is in the reduced frame but needed to be skipped because of + * AFTER MATCH SKIP PAST LAST ROW + * ----------------- */ -void -WinCheckAndInitializeNullTreatment(WindowObject winobj, - bool allowNullTreatment, - FunctionCallInfo fcinfo) +static int +row_is_in_reduced_frame(WindowObject winobj, int64 pos) { - Assert(WindowObjectIsValid(winobj)); - if (winobj->ignore_nulls != NO_NULLTREATMENT && !allowNullTreatment) + WindowAggState *winstate = winobj->winstate; + int state; + int rtn; + + if (!rpr_is_defined(winstate)) { - const char *funcname = get_func_name(fcinfo->flinfo->fn_oid); + /* + * RPR is not defined. Assume that we are always in the the reduced + * window frame. + */ + rtn = 0; +#ifdef RPR_DEBUG + printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n", + rtn, pos); +#endif + return rtn; + } - if (!funcname) - elog(ERROR, "could not get function name"); - ereport(ERROR, - (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), - errmsg("function %s does not allow RESPECT/IGNORE NULLS", - funcname))); + state = get_reduced_frame_map(winstate, pos); + + if (state == RF_NOT_DETERMINED) + { + update_frameheadpos(winstate); + update_reduced_frame(winobj, pos); } - else if (winobj->ignore_nulls == PARSER_IGNORE_NULLS) - winobj->ignore_nulls = IGNORE_NULLS; + + state = get_reduced_frame_map(winstate, pos); + + switch (state) + { + int64 i; + int num_reduced_rows; + + case RF_FRAME_HEAD: + num_reduced_rows = 1; + for (i = pos + 1; + get_reduced_frame_map(winstate, i) == RF_SKIPPED; i++) + num_reduced_rows++; + rtn = num_reduced_rows; + break; + + case RF_SKIPPED: + rtn = -2; + break; + + case RF_UNMATCHED: + rtn = -1; + break; + + default: + elog(ERROR, "unrecognized state: %d at: " INT64_FORMAT, + state, pos); + break; + } + +#ifdef RPR_DEBUG + printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n", + rtn, pos); +#endif + return rtn; } +#define REDUCED_FRAME_MAP_INIT_SIZE 1024L + /* - * WinGetPartitionLocalMemory - * Get working memory that lives till end of partition processing - * - * On first call within a given partition, this allocates and zeroes the - * requested amount of space. Subsequent calls just return the same chunk. - * - * Memory obtained this way is normally used to hold state that should be - * automatically reset for each new partition. If a window function wants - * to hold state across the whole query, fcinfo->fn_extra can be used in the - * usual way for that. + * create_reduced_frame_map + * Create reduced frame map */ -void * -WinGetPartitionLocalMemory(WindowObject winobj, Size sz) +static void +create_reduced_frame_map(WindowAggState *winstate) { - Assert(WindowObjectIsValid(winobj)); - if (winobj->localmem == NULL) - winobj->localmem = - MemoryContextAllocZero(winobj->winstate->partcontext, sz); - return winobj->localmem; + winstate->reduced_frame_map = + MemoryContextAlloc(winstate->partcontext, + REDUCED_FRAME_MAP_INIT_SIZE); + winstate->alloc_sz = REDUCED_FRAME_MAP_INIT_SIZE; + clear_reduced_frame_map(winstate); } /* - * WinGetCurrentPosition - * Return the current row's position (counting from 0) within the current - * partition. + * clear_reduced_frame_map + * Clear reduced frame map */ -int64 -WinGetCurrentPosition(WindowObject winobj) +static void +clear_reduced_frame_map(WindowAggState *winstate) { - Assert(WindowObjectIsValid(winobj)); - return winobj->winstate->currentpos; + Assert(winstate->reduced_frame_map != NULL); + MemSet(winstate->reduced_frame_map, RF_NOT_DETERMINED, + winstate->alloc_sz); } /* - * WinGetPartitionRowCount - * Return total number of rows contained in the current partition. - * - * Note: this is a relatively expensive operation because it forces the - * whole partition to be "spooled" into the tuplestore at once. Once - * executed, however, additional calls within the same partition are cheap. + * get_reduced_frame_map + * Get reduced frame map specified by pos */ -int64 -WinGetPartitionRowCount(WindowObject winobj) +static int +get_reduced_frame_map(WindowAggState *winstate, int64 pos) { - Assert(WindowObjectIsValid(winobj)); - spool_tuples(winobj->winstate, -1); - return winobj->winstate->spooled_rows; + Assert(winstate->reduced_frame_map != NULL); + Assert(pos >= 0); + + /* + * If pos is not in the reduced frame map, it means that any info + * regarding the pos has not been registered yet. So we return + * RF_NOT_DETERMINED. + */ + if (pos >= winstate->alloc_sz) + return RF_NOT_DETERMINED; + + return winstate->reduced_frame_map[pos]; } /* - * WinSetMarkPosition - * Set the "mark" position for the window object, which is the oldest row - * number (counting from 0) it is allowed to fetch during all subsequent - * operations within the current partition. - * - * Window functions do not have to call this, but are encouraged to move the - * mark forward when possible to keep the tuplestore size down and prevent - * having to spill rows to disk. + * register_reduced_frame_map + * Add/replace reduced frame map member at pos. + * If there's no enough space, expand the map. */ -void -WinSetMarkPosition(WindowObject winobj, int64 markpos) +static void +register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val) { - WindowAggState *winstate; + int64 realloc_sz; - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; + Assert(winstate->reduced_frame_map != NULL); - if (markpos < winobj->markpos) - elog(ERROR, "cannot move WindowObject's mark position backward"); - tuplestore_select_read_pointer(winstate->buffer, winobj->markptr); - if (markpos > winobj->markpos) - { - tuplestore_skiptuples(winstate->buffer, - markpos - winobj->markpos, - true); - winobj->markpos = markpos; - } - tuplestore_select_read_pointer(winstate->buffer, winobj->readptr); - if (markpos > winobj->seekpos) + if (pos < 0) + elog(ERROR, "wrong pos: " INT64_FORMAT, pos); + + while (pos > winstate->alloc_sz - 1) { - tuplestore_skiptuples(winstate->buffer, - markpos - winobj->seekpos, - true); - winobj->seekpos = markpos; + realloc_sz = winstate->alloc_sz * 2; + + winstate->reduced_frame_map = + repalloc(winstate->reduced_frame_map, realloc_sz); + + MemSet(winstate->reduced_frame_map + winstate->alloc_sz, + RF_NOT_DETERMINED, realloc_sz - winstate->alloc_sz); + + winstate->alloc_sz = realloc_sz; } + + winstate->reduced_frame_map[pos] = val; } /* - * WinRowsArePeers - * Compare two rows (specified by absolute position in partition) to see - * if they are equal according to the ORDER BY clause. + * update_reduced_frame + * Update reduced frame info using multi-context NFA pattern matching. * - * NB: this does not consider the window frame mode. + * Maintains multiple NFA contexts simultaneously, one for each potential + * match start position. This allows sharing row evaluations across contexts, + * avoiding redundant DEFINE clause evaluations when rewinding for SKIP TO + * NEXT ROW mode. + * + * Key optimizations: + * - Row evaluations (expensive DEFINE clauses) happen only once per row + * - All active contexts share the same evaluation results + * - Contexts persist across calls, enabling O(n) DEFINE evaluations */ -bool -WinRowsArePeers(WindowObject winobj, int64 pos1, int64 pos2) -{ - WindowAggState *winstate; - WindowAgg *node; - TupleTableSlot *slot1; - TupleTableSlot *slot2; - bool res; - - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; - node = (WindowAgg *) winstate->ss.ps.plan; - - /* If no ORDER BY, all rows are peers; don't bother to fetch them */ - if (node->ordNumCols == 0) - return true; - - /* - * Note: OK to use temp_slot_2 here because we aren't calling any - * frame-related functions (those tend to clobber temp_slot_2). - */ - slot1 = winstate->temp_slot_1; - slot2 = winstate->temp_slot_2; - - if (!window_gettupleslot(winobj, pos1, slot1)) - elog(ERROR, "specified position is out of window: " INT64_FORMAT, - pos1); - if (!window_gettupleslot(winobj, pos2, slot2)) - elog(ERROR, "specified position is out of window: " INT64_FORMAT, - pos2); - - res = are_peers(winstate, slot1, slot2); - - ExecClearTuple(slot1); - ExecClearTuple(slot2); - - return res; -} - -/* - * WinGetFuncArgInPartition - * Evaluate a window function's argument expression on a specified - * row of the partition. The row is identified in lseek(2) style, - * i.e. relative to the current, first, or last row. - * - * argno: argument number to evaluate (counted from 0) - * relpos: signed rowcount offset from the seek position - * seektype: WINDOW_SEEK_CURRENT, WINDOW_SEEK_HEAD, or WINDOW_SEEK_TAIL - * set_mark: If the row is found and set_mark is true, the mark is moved to - * the row as a side-effect. - * isnull: output argument, receives isnull status of result - * isout: output argument, set to indicate whether target row position - * is out of partition (can pass NULL if caller doesn't care about this) - * - * Specifying a nonexistent row is not an error, it just causes a null result - * (plus setting *isout true, if isout isn't NULL). - */ -Datum -WinGetFuncArgInPartition(WindowObject winobj, int argno, - int relpos, int seektype, bool set_mark, - bool *isnull, bool *isout) -{ - WindowAggState *winstate; - int64 abs_pos; - int64 mark_pos; - Datum datum; - bool null_treatment; - int notnull_offset; - int notnull_relpos; - int forward; - bool myisout; - - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; - - null_treatment = (winobj->ignore_nulls == IGNORE_NULLS && relpos != 0); - - switch (seektype) - { - case WINDOW_SEEK_CURRENT: - if (null_treatment) - abs_pos = winstate->currentpos; - else - abs_pos = winstate->currentpos + relpos; - break; - case WINDOW_SEEK_HEAD: - if (null_treatment) - abs_pos = 0; - else - abs_pos = relpos; - break; - case WINDOW_SEEK_TAIL: - spool_tuples(winstate, -1); - abs_pos = winstate->spooled_rows - 1 + relpos; - break; - default: - elog(ERROR, "unrecognized window seek type: %d", seektype); - abs_pos = 0; /* keep compiler quiet */ - break; - } - - /* Easy case if IGNORE NULLS is not specified */ - if (!null_treatment) - { - /* get tuple and evaluate in partition */ - datum = gettuple_eval_partition(winobj, argno, - abs_pos, isnull, &myisout); - if (!myisout && set_mark) - WinSetMarkPosition(winobj, abs_pos); - if (isout) - *isout = myisout; - return datum; - } - - /* Prepare for loop */ - notnull_offset = 0; - notnull_relpos = abs(relpos); - forward = relpos > 0 ? 1 : -1; - myisout = false; - datum = 0; - - /* - * IGNORE NULLS + WINDOW_SEEK_CURRENT + relpos > 0 case, we would fetch - * beyond the current row + relpos to find out the target row. If we mark - * at abs_pos, next call to WinGetFuncArgInPartition or - * WinGetFuncArgInFrame (in case when a window function have multiple - * args) could fail with "cannot fetch row before WindowObject's mark - * position". So keep the mark position at currentpos. - */ - if (seektype == WINDOW_SEEK_CURRENT && relpos > 0) - mark_pos = winstate->currentpos; - else - { - /* - * For other cases we have no idea what position of row callers would - * fetch next time. Also for relpos < 0 case (we go backward), we - * cannot set mark either. For those cases we always set mark at 0. - */ - mark_pos = 0; - } - - /* - * Get the next nonnull value in the partition, moving forward or backward - * until we find a value or reach the partition's end. We cache the - * nullness status because we may repeat this process many times. - */ - do - { - int nn_info; /* NOT NULL status */ - - abs_pos += forward; - if (abs_pos < 0) /* clearly out of partition */ - break; - - /* check NOT NULL cached info */ - nn_info = get_notnull_info(winobj, abs_pos, argno); - if (nn_info == NN_NOTNULL) /* this row is known to be NOT NULL */ - notnull_offset++; - else if (nn_info == NN_NULL) /* this row is known to be NULL */ - continue; /* keep on moving forward or backward */ - else /* need to check NULL or not */ - { - /* - * NOT NULL info does not exist yet. Get tuple and evaluate func - * arg in partition. We ignore the return value from - * gettuple_eval_partition because we are just interested in - * whether we are inside or outside of partition, NULL or NOT - * NULL. - */ - (void) gettuple_eval_partition(winobj, argno, - abs_pos, isnull, &myisout); - if (myisout) /* out of partition? */ - break; - if (!*isnull) - notnull_offset++; - /* record the row status */ - put_notnull_info(winobj, abs_pos, argno, *isnull); - } - } while (notnull_offset < notnull_relpos); - - /* get tuple and evaluate func arg in partition */ - datum = gettuple_eval_partition(winobj, argno, - abs_pos, isnull, &myisout); - if (!myisout && set_mark) - WinSetMarkPosition(winobj, mark_pos); - if (isout) - *isout = myisout; - - return datum; -} - -/* - * WinGetFuncArgInFrame - * Evaluate a window function's argument expression on a specified - * row of the window frame. The row is identified in lseek(2) style, - * i.e. relative to the first or last row of the frame. (We do not - * support WINDOW_SEEK_CURRENT here, because it's not very clear what - * that should mean if the current row isn't part of the frame.) - * - * argno: argument number to evaluate (counted from 0) - * relpos: signed rowcount offset from the seek position - * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL - * set_mark: If the row is found/in frame and set_mark is true, the mark is - * moved to the row as a side-effect. - * isnull: output argument, receives isnull status of result - * isout: output argument, set to indicate whether target row position - * is out of frame (can pass NULL if caller doesn't care about this) - * - * Specifying a nonexistent or not-in-frame row is not an error, it just - * causes a null result (plus setting *isout true, if isout isn't NULL). - * - * Note that some exclusion-clause options lead to situations where the - * rows that are in-frame are not consecutive in the partition. But we - * count only in-frame rows when measuring relpos. - * - * The set_mark flag is interpreted as meaning that the caller will specify - * a constant (or, perhaps, monotonically increasing) relpos in successive - * calls, so that *if there is no exclusion clause* there will be no need - * to fetch a row before the previously fetched row. But we do not expect - * the caller to know how to account for exclusion clauses. Therefore, - * if there is an exclusion clause we take responsibility for adjusting the - * mark request to something that will be safe given the above assumption - * about relpos. - */ -Datum -WinGetFuncArgInFrame(WindowObject winobj, int argno, - int relpos, int seektype, bool set_mark, - bool *isnull, bool *isout) -{ - WindowAggState *winstate; - ExprContext *econtext; - TupleTableSlot *slot; - - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; - econtext = winstate->ss.ps.ps_ExprContext; - slot = winstate->temp_slot_1; - - if (winobj->ignore_nulls == IGNORE_NULLS) - return ignorenulls_getfuncarginframe(winobj, argno, relpos, seektype, - set_mark, isnull, isout); - - if (WinGetSlotInFrame(winobj, slot, - relpos, seektype, set_mark, - isnull, isout) == 0) - { - econtext->ecxt_outertuple = slot; - return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno), - econtext, isnull); - } - - if (isout) - *isout = true; - *isnull = true; - return (Datum) 0; -} - -/* - * WinGetSlotInFrame - * slot: TupleTableSlot to store the result - * relpos: signed rowcount offset from the seek position - * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL - * set_mark: If the row is found/in frame and set_mark is true, the mark is - * moved to the row as a side-effect. - * isnull: output argument, receives isnull status of result - * isout: output argument, set to indicate whether target row position - * is out of frame (can pass NULL if caller doesn't care about this) - * - * Returns 0 if we successfullt got the slot. false if out of frame. - * (also isout is set) - */ -static int -WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot, - int relpos, int seektype, bool set_mark, - bool *isnull, bool *isout) -{ - WindowAggState *winstate; - int64 abs_pos; - int64 mark_pos; - int num_reduced_frame; - - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; - - switch (seektype) - { - case WINDOW_SEEK_CURRENT: - elog(ERROR, "WINDOW_SEEK_CURRENT is not supported for WinGetFuncArgInFrame"); - abs_pos = mark_pos = 0; /* keep compiler quiet */ - break; - case WINDOW_SEEK_HEAD: - /* rejecting relpos < 0 is easy and simplifies code below */ - if (relpos < 0) - goto out_of_frame; - update_frameheadpos(winstate); - abs_pos = winstate->frameheadpos + relpos; - mark_pos = abs_pos; - - /* - * Account for exclusion option if one is active, but advance only - * abs_pos not mark_pos. This prevents changes of the current - * row's peer group from resulting in trying to fetch a row before - * some previous mark position. - * - * Note that in some corner cases such as current row being - * outside frame, these calculations are theoretically too simple, - * but it doesn't matter because we'll end up deciding the row is - * out of frame. We do not attempt to avoid fetching rows past - * end of frame; that would happen in some cases anyway. - */ - switch (winstate->frameOptions & FRAMEOPTION_EXCLUSION) - { - case 0: - /* no adjustment needed */ - break; - case FRAMEOPTION_EXCLUDE_CURRENT_ROW: - if (abs_pos >= winstate->currentpos && - winstate->currentpos >= winstate->frameheadpos) - abs_pos++; - break; - case FRAMEOPTION_EXCLUDE_GROUP: - update_grouptailpos(winstate); - if (abs_pos >= winstate->groupheadpos && - winstate->grouptailpos > winstate->frameheadpos) - { - int64 overlapstart = Max(winstate->groupheadpos, - winstate->frameheadpos); - - abs_pos += winstate->grouptailpos - overlapstart; - } - break; - case FRAMEOPTION_EXCLUDE_TIES: - update_grouptailpos(winstate); - if (abs_pos >= winstate->groupheadpos && - winstate->grouptailpos > winstate->frameheadpos) - { - int64 overlapstart = Max(winstate->groupheadpos, - winstate->frameheadpos); - - if (abs_pos == overlapstart) - abs_pos = winstate->currentpos; - else - abs_pos += winstate->grouptailpos - overlapstart - 1; - } - break; - default: - elog(ERROR, "unrecognized frame option state: 0x%x", - winstate->frameOptions); - break; - } - num_reduced_frame = row_is_in_reduced_frame(winobj, - winstate->frameheadpos); - if (num_reduced_frame < 0) - goto out_of_frame; - else if (num_reduced_frame > 0) - if (relpos >= num_reduced_frame) - goto out_of_frame; - break; - case WINDOW_SEEK_TAIL: - /* rejecting relpos > 0 is easy and simplifies code below */ - if (relpos > 0) - goto out_of_frame; - - /* - * RPR cares about frame head pos. Need to call - * update_frameheadpos - */ - update_frameheadpos(winstate); - - update_frametailpos(winstate); - abs_pos = winstate->frametailpos - 1 + relpos; - - /* - * Account for exclusion option if one is active. If there is no - * exclusion, we can safely set the mark at the accessed row. But - * if there is, we can only mark the frame start, because we can't - * be sure how far back in the frame the exclusion might cause us - * to fetch in future. Furthermore, we have to actually check - * against frameheadpos here, since it's unsafe to try to fetch a - * row before frame start if the mark might be there already. - */ - switch (winstate->frameOptions & FRAMEOPTION_EXCLUSION) - { - case 0: - /* no adjustment needed */ - mark_pos = abs_pos; - break; - case FRAMEOPTION_EXCLUDE_CURRENT_ROW: - if (abs_pos <= winstate->currentpos && - winstate->currentpos < winstate->frametailpos) - abs_pos--; - update_frameheadpos(winstate); - if (abs_pos < winstate->frameheadpos) - goto out_of_frame; - mark_pos = winstate->frameheadpos; - break; - case FRAMEOPTION_EXCLUDE_GROUP: - update_grouptailpos(winstate); - if (abs_pos < winstate->grouptailpos && - winstate->groupheadpos < winstate->frametailpos) - { - int64 overlapend = Min(winstate->grouptailpos, - winstate->frametailpos); - - abs_pos -= overlapend - winstate->groupheadpos; - } - update_frameheadpos(winstate); - if (abs_pos < winstate->frameheadpos) - goto out_of_frame; - mark_pos = winstate->frameheadpos; - break; - case FRAMEOPTION_EXCLUDE_TIES: - update_grouptailpos(winstate); - if (abs_pos < winstate->grouptailpos && - winstate->groupheadpos < winstate->frametailpos) - { - int64 overlapend = Min(winstate->grouptailpos, - winstate->frametailpos); - - if (abs_pos == overlapend - 1) - abs_pos = winstate->currentpos; - else - abs_pos -= overlapend - 1 - winstate->groupheadpos; - } - update_frameheadpos(winstate); - if (abs_pos < winstate->frameheadpos) - goto out_of_frame; - mark_pos = winstate->frameheadpos; - break; - default: - elog(ERROR, "unrecognized frame option state: 0x%x", - winstate->frameOptions); - mark_pos = 0; /* keep compiler quiet */ - break; - } - - num_reduced_frame = row_is_in_reduced_frame(winobj, - winstate->frameheadpos + relpos); - if (num_reduced_frame < 0) - goto out_of_frame; - else if (num_reduced_frame > 0) - abs_pos = winstate->frameheadpos + relpos + - num_reduced_frame - 1; - break; - default: - elog(ERROR, "unrecognized window seek type: %d", seektype); - abs_pos = mark_pos = 0; /* keep compiler quiet */ - break; - } - - if (!window_gettupleslot(winobj, abs_pos, slot)) - goto out_of_frame; - - /* The code above does not detect all out-of-frame cases, so check */ - if (row_is_in_frame(winobj, abs_pos, slot, false) <= 0) - goto out_of_frame; - - if (isout) - *isout = false; - if (set_mark) - WinSetMarkPosition(winobj, mark_pos); - return 0; - -out_of_frame: - if (isout) - *isout = true; - *isnull = true; - return -1; -} - -/* - * WinGetFuncArgCurrent - * Evaluate a window function's argument expression on the current row. - * - * argno: argument number to evaluate (counted from 0) - * isnull: output argument, receives isnull status of result - * - * Note: this isn't quite equivalent to WinGetFuncArgInPartition or - * WinGetFuncArgInFrame targeting the current row, because it will succeed - * even if the WindowObject's mark has been set beyond the current row. - * This should generally be used for "ordinary" arguments of a window - * function, such as the offset argument of lead() or lag(). - */ -Datum -WinGetFuncArgCurrent(WindowObject winobj, int argno, bool *isnull) -{ - WindowAggState *winstate; - ExprContext *econtext; - - Assert(WindowObjectIsValid(winobj)); - winstate = winobj->winstate; - - econtext = winstate->ss.ps.ps_ExprContext; - - econtext->ecxt_outertuple = winstate->ss.ss_ScanTupleSlot; - return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno), - econtext, isnull); -} - -/* - * rpr_is_defined - * return true if Row pattern recognition is defined. - */ -static bool -rpr_is_defined(WindowAggState *winstate) -{ - return winstate->rpPattern != NULL; -} - -/* - * ----------------- - * row_is_in_reduced_frame - * Determine whether a row is in the current row's reduced window frame - * according to row pattern matching - * - * The row must has been already determined that it is in a full window frame - * and fetched it into slot. - * - * Returns: - * = 0, RPR is not defined. - * >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 unmatched row - * -2, if the row is in the reduced frame but needed to be skipped because of - * AFTER MATCH SKIP PAST LAST ROW - * ----------------- - */ -static int -row_is_in_reduced_frame(WindowObject winobj, int64 pos) -{ - WindowAggState *winstate = winobj->winstate; - int state; - int rtn; - - if (!rpr_is_defined(winstate)) - { - /* - * RPR is not defined. Assume that we are always in the the reduced - * window frame. - */ - rtn = 0; -#ifdef RPR_DEBUG - printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n", - rtn, pos); -#endif - return rtn; - } - - state = get_reduced_frame_map(winstate, pos); - - if (state == RF_NOT_DETERMINED) - { - update_frameheadpos(winstate); - update_reduced_frame(winobj, pos); - } - - state = get_reduced_frame_map(winstate, pos); - - switch (state) - { - int64 i; - int num_reduced_rows; - - case RF_FRAME_HEAD: - num_reduced_rows = 1; - for (i = pos + 1; - get_reduced_frame_map(winstate, i) == RF_SKIPPED; i++) - num_reduced_rows++; - rtn = num_reduced_rows; - break; - - case RF_SKIPPED: - rtn = -2; - break; - - case RF_UNMATCHED: - rtn = -1; - break; - - default: - elog(ERROR, "unrecognized state: %d at: " INT64_FORMAT, - state, pos); - break; - } - -#ifdef RPR_DEBUG - printf("row_is_in_reduced_frame returns %d: pos: " INT64_FORMAT "\n", - rtn, pos); -#endif - return rtn; -} - -#define REDUCED_FRAME_MAP_INIT_SIZE 1024L - -/* - * create_reduced_frame_map - * Create reduced frame map - */ -static void -create_reduced_frame_map(WindowAggState *winstate) -{ - winstate->reduced_frame_map = - MemoryContextAlloc(winstate->partcontext, - REDUCED_FRAME_MAP_INIT_SIZE); - winstate->alloc_sz = REDUCED_FRAME_MAP_INIT_SIZE; - clear_reduced_frame_map(winstate); -} - -/* - * clear_reduced_frame_map - * Clear reduced frame map - */ -static void -clear_reduced_frame_map(WindowAggState *winstate) -{ - Assert(winstate->reduced_frame_map != NULL); - MemSet(winstate->reduced_frame_map, RF_NOT_DETERMINED, - winstate->alloc_sz); -} - -/* - * get_reduced_frame_map - * Get reduced frame map specified by pos - */ -static int -get_reduced_frame_map(WindowAggState *winstate, int64 pos) -{ - Assert(winstate->reduced_frame_map != NULL); - Assert(pos >= 0); - - /* - * If pos is not in the reduced frame map, it means that any info - * regarding the pos has not been registered yet. So we return - * RF_NOT_DETERMINED. - */ - if (pos >= winstate->alloc_sz) - return RF_NOT_DETERMINED; - - return winstate->reduced_frame_map[pos]; -} - -/* - * register_reduced_frame_map - * Add/replace reduced frame map member at pos. - * If there's no enough space, expand the map. - */ -static void -register_reduced_frame_map(WindowAggState *winstate, int64 pos, int val) -{ - int64 realloc_sz; - - Assert(winstate->reduced_frame_map != NULL); - - if (pos < 0) - elog(ERROR, "wrong pos: " INT64_FORMAT, pos); - - while (pos > winstate->alloc_sz - 1) - { - realloc_sz = winstate->alloc_sz * 2; - - winstate->reduced_frame_map = - repalloc(winstate->reduced_frame_map, realloc_sz); - - MemSet(winstate->reduced_frame_map + winstate->alloc_sz, - RF_NOT_DETERMINED, realloc_sz - winstate->alloc_sz); - - winstate->alloc_sz = realloc_sz; - } - - winstate->reduced_frame_map[pos] = val; -} - -/* - * update_reduced_frame - * Update reduced frame info using multi-context NFA pattern matching. - * - * Maintains multiple NFA contexts simultaneously, one for each potential - * match start position. This allows sharing row evaluations across contexts, - * avoiding redundant DEFINE clause evaluations when rewinding for SKIP TO - * NEXT ROW mode. - * - * Key optimizations: - * - Row evaluations (expensive DEFINE clauses) happen only once per row - * - All active contexts share the same evaluation results - * - Contexts persist across calls, enabling O(n) DEFINE evaluations - */ -static void -update_reduced_frame(WindowObject winobj, int64 pos) +static void +update_reduced_frame(WindowObject winobj, int64 pos) { WindowAggState *winstate = winobj->winstate; RPRNFAContext *targetCtx; @@ -4853,7 +4157,7 @@ update_reduced_frame(WindowObject winobj, int64 pos) /* * Case 2: Find existing context for this pos, or create new one. */ - targetCtx = nfa_get_head_context(winstate, pos); + targetCtx = ExecRPRGetHeadContext(winstate, pos); if (targetCtx == NULL) { /* @@ -4867,7 +4171,7 @@ update_reduced_frame(WindowObject winobj, int64 pos) return; } /* Not yet processed - create new context and start fresh */ - targetCtx = nfa_start_context(winstate, pos); + targetCtx = ExecRPRStartContext(winstate, pos); } else if (targetCtx->states == NULL) { @@ -4900,14 +4204,9 @@ update_reduced_frame(WindowObject winobj, int64 pos) /* No more rows in partition? Finalize all contexts */ if (!rowExists) { - nfa_finalize_all_contexts(winstate, currentPos - 1); + ExecRPRFinalizeAllContexts(winstate, currentPos - 1); /* Clean up dead contexts from finalization */ - nfa_cleanup_dead_contexts(winstate, targetCtx); - /* Absorb contexts at partition boundary */ - if (winstate->rpPattern->isAbsorbable) - { - nfa_absorb_contexts(winstate); - } + ExecRPRCleanupDeadContexts(winstate, targetCtx); break; } @@ -4920,20 +4219,20 @@ update_reduced_frame(WindowObject winobj, int64 pos) * 2. Absorb redundant * 3. Advance all (divergence) */ - nfa_process_row(winstate, currentPos, hasLimitedFrame, frameOffset); + ExecRPRProcessRow(winstate, currentPos, hasLimitedFrame, frameOffset); /* * Create a new context for the next potential start position. This * enables overlapping match detection for SKIP TO NEXT ROW. */ - nfa_start_context(winstate, currentPos + 1); + ExecRPRStartContext(winstate, currentPos + 1); /* * Clean up dead contexts (failed with no active states and no match). * This removes contexts that failed during processing and counts them * appropriately as pruned or mismatched. */ - nfa_cleanup_dead_contexts(winstate, targetCtx); + ExecRPRCleanupDeadContexts(winstate, targetCtx); } register_result: @@ -4947,648 +4246,23 @@ register_result: matchLen = targetCtx->lastProcessedRow - targetCtx->matchStartRow + 1; register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_UNMATCHED); - nfa_record_context_failure(winstate, matchLen); - nfa_context_free(winstate, targetCtx); + ExecRPRRecordContextFailure(winstate, matchLen); + ExecRPRFreeContext(winstate, targetCtx); return; } /* Match succeeded - register frame map and record statistics */ matchLen = targetCtx->matchEndRow - targetCtx->matchStartRow + 1; - register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_FRAME_HEAD); - for (int64 i = targetCtx->matchStartRow + 1; i <= targetCtx->matchEndRow; i++) - { - register_reduced_frame_map(winstate, i, RF_SKIPPED); - } - nfa_record_context_success(winstate, matchLen); - - /* Remove the matched context */ - nfa_context_free(winstate, targetCtx); -} - -/* - * 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, - * resulting in UNMATCHED. For reluctant min=0 patterns (A*?, A??), - * the skip path reaches FIN first and early termination prunes enter - * paths, yielding an immediate empty (unmatched) result. For - * greedy patterns (A*), the enter path adds VAR states first, then - * the skip FIN is recorded but VAR states survive for later matching. - * - * 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. - */ - -/* - * nfa_process_row - * - * Process all contexts for one row: - * 1. Match all contexts (convergence) - evaluate VARs, prune dead states - * 2. Absorb redundant contexts - ideal timing after convergence - * 3. Advance all contexts (divergence) - create new states for next row - */ -static void -nfa_process_row(WindowAggState *winstate, int64 currentPos, - bool hasLimitedFrame, int64 frameOffset) -{ - RPRNFAContext *ctx; - bool *varMatched = winstate->nfaVarMatched; - - /* - * Phase 1: Match all contexts (convergence). Evaluate VAR elements, - * update counts, remove dead states. - */ - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) - { - if (ctx->states == NULL) - continue; - - /* Check frame boundary - finalize if exceeded */ - if (hasLimitedFrame) - { - int64 ctxFrameEnd = ctx->matchStartRow + frameOffset + 1; - - if (currentPos >= ctxFrameEnd) - { - /* Frame boundary exceeded: force mismatch */ - nfa_match(winstate, ctx, NULL); - continue; - } - } - - nfa_match(winstate, ctx, varMatched); - ctx->lastProcessedRow = currentPos; - } - - /* - * Phase 2: Absorb redundant contexts. After match phase, states have - * converged - ideal for absorption. First update absorption flags that - * may have changed due to state removal. - */ - if (winstate->rpPattern->isAbsorbable) - { - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) - nfa_update_absorption_flags(ctx); - - nfa_absorb_contexts(winstate); - } - - /* - * Phase 3: Advance all contexts (divergence). Create new states - * (loop/exit) from surviving matched states. - */ - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) - { - if (ctx->states == NULL) - continue; - - /* - * Phase 1 already handled frame boundary exceeded contexts by forcing - * mismatch (nfa_match with NULL), which removes all states (all - * states are at VAR positions after advance). So any surviving - * context here must be within its frame boundary. - */ - Assert(!hasLimitedFrame || - currentPos < ctx->matchStartRow + frameOffset + 1); - - nfa_advance(winstate, ctx, currentPos); - } -} - -/* - * nfa_state_alloc - * - * 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_alloc(WindowAggState *winstate) -{ - RPRNFAState *state; - - /* Try to reuse from free list first */ - if (winstate->nfaStateFree != NULL) - { - state = winstate->nfaStateFree; - winstate->nfaStateFree = state->next; - } - else - { - /* Allocate in partition context for proper lifetime */ - state = MemoryContextAlloc(winstate->partcontext, winstate->nfaStateSize); - } - - /* Initialize entire state to zero */ - memset(state, 0, winstate->nfaStateSize); - - /* Update statistics */ - winstate->nfaStatesActive++; - winstate->nfaStatesTotalCreated++; - if (winstate->nfaStatesActive > winstate->nfaStatesMax) - winstate->nfaStatesMax = winstate->nfaStatesActive; - - return state; -} - -/* - * nfa_state_free - * - * Return a state to the free list for later reuse. - */ -static void -nfa_state_free(WindowAggState *winstate, RPRNFAState *state) -{ - winstate->nfaStatesActive--; - state->next = winstate->nfaStateFree; - winstate->nfaStateFree = state; -} - -/* - * nfa_state_free_list - * - * Return all states in a list to the free list. - */ -static void -nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list) -{ - RPRNFAState *next; - - for (; list != NULL; list = next) - { - next = list->next; - nfa_state_free(winstate, list); - } -} - -/* - * nfa_state_create - * - * Create a new state with given elemIdx and counts. - * isAbsorbable is computed immediately: inherited AND new element's flag. - * Monotonic property: once false, stays false through all transitions. - * - * Caller is responsible for linking the returned state. - */ -static RPRNFAState * -nfa_state_create(WindowAggState *winstate, int16 elemIdx, - int32 *counts, bool sourceAbsorbable) -{ - RPRPattern *pattern = winstate->rpPattern; - int maxDepth = pattern->maxDepth; - RPRNFAState *state = nfa_state_alloc(winstate); - RPRPatternElement *elem = &pattern->elements[elemIdx]; - - state->elemIdx = elemIdx; - if (counts != NULL && maxDepth > 0) - memcpy(state->counts, counts, sizeof(int32) * maxDepth); - - /* - * Compute isAbsorbable immediately at transition time. isAbsorbable = - * sourceAbsorbable && (elem->flags & ABSORBABLE_BRANCH) Monotonic: once - * false, stays false (can't re-enter absorbable region). - */ - state->isAbsorbable = sourceAbsorbable && RPRElemIsAbsorbableBranch(elem); - - return state; -} - -/* - * nfa_states_equal - * - * Check if two states are equivalent (same elemIdx and counts). - */ -static bool -nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) -{ - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elem; - int compareDepth; - - if (s1->elemIdx != s2->elemIdx) - return false; - - /* Compare counts up to current element's depth */ - elem = &pattern->elements[s1->elemIdx]; - compareDepth = elem->depth + 1; /* depth 0 needs 1 count, etc. */ - - if (memcmp(s1->counts, s2->counts, sizeof(int32) * compareDepth) != 0) - return false; - - return true; -} - -/* - * nfa_add_state_unique - * - * Add a state to ctx->states at the END, only if no duplicate exists. - * Returns true if state was added, false if duplicate found (state is freed). - * Earlier states have better lexical order (DFS traversal order), so existing wins. - */ -static bool -nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state) -{ - RPRNFAState *s; - RPRNFAState *tail = NULL; - - /* Check for duplicate and find tail */ - for (s = ctx->states; s != NULL; s = s->next) - { - if (nfa_states_equal(winstate, s, state)) - { - /* - * Duplicate found - existing has better lexical order, discard - * new - */ - nfa_state_free(winstate, state); - winstate->nfaStatesMerged++; - return false; - } - tail = s; - } - - /* No duplicate, add at end */ - state->next = NULL; - if (tail == NULL) - ctx->states = state; - else - tail->next = state; - - return true; -} - -/* - * nfa_add_matched_state - * - * Record a state that reached FIN, replacing any previous match. - * - * For SKIP PAST LAST ROW, also prune subsequent contexts whose start row - * falls within the match range, as they cannot produce output rows. - */ -static void -nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, int64 matchEndRow) -{ - if (ctx->matchedState != NULL) - nfa_state_free(winstate, ctx->matchedState); - - ctx->matchedState = state; - state->next = NULL; - ctx->matchEndRow = matchEndRow; - - /* Prune contexts that started within this match's range */ - if (winstate->rpSkipTo == ST_PAST_LAST_ROW) - { - RPRNFAContext *nextCtx; - int64 skippedLen; - - while (ctx->next != NULL && - ctx->next->matchStartRow <= matchEndRow) - { - nextCtx = ctx->next; - ctx->next = ctx->next->next; - - Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); - skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; - nfa_record_context_skipped(winstate, skippedLen); - - nfa_context_free(winstate, nextCtx); - } - if (ctx->next == NULL) - winstate->nfaContextTail = ctx; - } -} - -/* - * nfa_context_alloc - * - * Allocate an NFA context, reusing from free list if available. - */ -static RPRNFAContext * -nfa_context_alloc(WindowAggState *winstate) -{ - RPRNFAContext *ctx; - - if (winstate->nfaContextFree != NULL) - { - ctx = winstate->nfaContextFree; - winstate->nfaContextFree = ctx->next; - } - else - { - /* Allocate in partition context for proper lifetime */ - ctx = MemoryContextAlloc(winstate->partcontext, sizeof(RPRNFAContext)); - } - - ctx->next = NULL; - ctx->prev = NULL; - ctx->states = NULL; - ctx->matchStartRow = -1; - ctx->matchEndRow = -1; - ctx->lastProcessedRow = -1; - ctx->matchedState = NULL; - - /* Initialize two-flag absorption design based on pattern */ - ctx->hasAbsorbableState = winstate->rpPattern->isAbsorbable; - ctx->allStatesAbsorbable = winstate->rpPattern->isAbsorbable; - - /* Update statistics */ - winstate->nfaContextsActive++; - winstate->nfaContextsTotalCreated++; - if (winstate->nfaContextsActive > winstate->nfaContextsMax) - winstate->nfaContextsMax = winstate->nfaContextsActive; - - return ctx; -} - -/* - * nfa_unlink_context - * - * Remove a context from the doubly-linked active context list. - * Updates head (nfaContext) and tail (nfaContextTail) as needed. - */ -static void -nfa_unlink_context(WindowAggState *winstate, RPRNFAContext *ctx) -{ - if (ctx->prev != NULL) - ctx->prev->next = ctx->next; - else - winstate->nfaContext = ctx->next; /* was head */ - - if (ctx->next != NULL) - ctx->next->prev = ctx->prev; - else - winstate->nfaContextTail = ctx->prev; /* was tail */ - - ctx->next = NULL; - ctx->prev = NULL; -} - -/* - * nfa_context_free - * - * Unlink context from active list and return it to free list. - * Also frees any states in the context. - */ -static void -nfa_context_free(WindowAggState *winstate, RPRNFAContext *ctx) -{ - /* Unlink from active list first */ - nfa_unlink_context(winstate, ctx); - - /* Update statistics */ - winstate->nfaContextsActive--; - - if (ctx->states != NULL) - nfa_state_free_list(winstate, ctx->states); - if (ctx->matchedState != NULL) - nfa_state_free(winstate, ctx->matchedState); - - ctx->states = NULL; - ctx->matchedState = NULL; - ctx->next = winstate->nfaContextFree; - winstate->nfaContextFree = ctx; -} - -/* - * nfa_start_context - * - * Start a new match context at given position. - * Initializes context, state absorption flags, and performs initial advance - * to expand epsilon transitions (ALT branches, optional elements). - * Adds context to the tail of winstate->nfaContext list. - */ -static RPRNFAContext * -nfa_start_context(WindowAggState *winstate, int64 startPos) -{ - RPRNFAContext *ctx; - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elem; - - ctx = nfa_context_alloc(winstate); - ctx->matchStartRow = startPos; - ctx->states = nfa_state_alloc(winstate); /* initial state at elem 0 */ - - elem = &pattern->elements[0]; - - if (RPRElemIsAbsorbableBranch(elem)) - { - ctx->states->isAbsorbable = true; - } - else - { - ctx->hasAbsorbableState = false; - ctx->allStatesAbsorbable = false; - ctx->states->isAbsorbable = false; - } - - /* Add to tail of active context list (doubly-linked, oldest-first) */ - ctx->prev = winstate->nfaContextTail; - ctx->next = NULL; - if (winstate->nfaContextTail != NULL) - winstate->nfaContextTail->next = ctx; - else - winstate->nfaContext = ctx; /* first context becomes head */ - winstate->nfaContextTail = ctx; - - /* - * Initial advance (divergence): expand ALT branches and create exit - * states for VAR elements with min=0. This prepares the context for the - * first row's match phase. - * - * Use startPos - 1 as currentPos since no row has been consumed yet. If - * FIN is reached via epsilon transitions, matchEndRow = startPos - 1 - * which is less than matchStartRow, resulting in UNMATCHED treatment. - */ - nfa_advance(winstate, ctx, startPos - 1); - - return ctx; -} - -/* - * nfa_get_head_context - * - * Return the head context if its start position matches pos. - * Returns NULL if no context exists or head doesn't match pos. - */ -static RPRNFAContext * -nfa_get_head_context(WindowAggState *winstate, int64 pos) -{ - RPRNFAContext *ctx = winstate->nfaContext; - - /* - * Contexts are sorted by matchStartRow ascending. If the head context - * doesn't match pos, no context exists for this position. - */ - if (ctx == NULL || ctx->matchStartRow != pos) - return NULL; - - return ctx; -} - -/* - * nfa_update_length_stats - * - * Helper function to update min/max/total length statistics. - * Called when tracking match/mismatch/absorbed/skipped lengths. - */ -static void -nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 newLen) -{ - if (count == 1) - { - stats->min = newLen; - stats->max = newLen; - } - else - { - if (newLen < stats->min) - stats->min = newLen; - if (newLen > stats->max) - stats->max = newLen; - } - stats->total += newLen; -} - -/* - * nfa_record_context_success - * - * Record a successful context in statistics. - */ -static void -nfa_record_context_success(WindowAggState *winstate, int64 matchLen) -{ - winstate->nfaMatchesSucceeded++; - nfa_update_length_stats(winstate->nfaMatchesSucceeded, - &winstate->nfaMatchLen, - matchLen); -} - -/* - * nfa_record_context_failure - * - * Record a failed context in statistics. - * If failedLen == 1, count as pruned (failed on first row). - * If failedLen > 1, count as mismatched and update length stats. - */ -static void -nfa_record_context_failure(WindowAggState *winstate, int64 failedLen) -{ - if (failedLen == 1) - { - winstate->nfaContextsPruned++; - } - else + register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_FRAME_HEAD); + for (int64 i = targetCtx->matchStartRow + 1; i <= targetCtx->matchEndRow; i++) { - winstate->nfaMatchesFailed++; - nfa_update_length_stats(winstate->nfaMatchesFailed, - &winstate->nfaFailLen, - failedLen); + register_reduced_frame_map(winstate, i, RF_SKIPPED); } -} - -/* - * nfa_record_context_skipped - * - * Record a skipped context in statistics. - */ -static void -nfa_record_context_skipped(WindowAggState *winstate, int64 skippedLen) -{ - winstate->nfaContextsSkipped++; - nfa_update_length_stats(winstate->nfaContextsSkipped, - &winstate->nfaSkippedLen, - skippedLen); -} + ExecRPRRecordContextSuccess(winstate, matchLen); -/* - * nfa_record_context_absorbed - * - * Record an absorbed context in statistics. - */ -static void -nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen) -{ - winstate->nfaContextsAbsorbed++; - nfa_update_length_stats(winstate->nfaContextsAbsorbed, - &winstate->nfaAbsorbedLen, - absorbedLen); + /* Remove the matched context */ + ExecRPRFreeContext(winstate, targetCtx); } /* @@ -5612,7 +4286,7 @@ nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched) /* * Set up slots for current, previous, and next rows. We don't call * get_slots() here to avoid recursion through row_is_in_frame -> - * update_reduced_frame -> nfa_process_row. + * update_reduced_frame -> ExecRPRProcessRow. */ /* Current row -> ecxt_outertuple */ @@ -5659,875 +4333,630 @@ nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched) return true; /* Row exists */ } -/* - * nfa_cleanup_dead_contexts - * - * Remove contexts that have failed (no active states and no match). - * These are contexts that failed during normal processing and should be - * counted as pruned (if length 1) or mismatched (if length > 1). - */ -static void -nfa_cleanup_dead_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx) -{ - RPRNFAContext *ctx; - RPRNFAContext *next; - - for (ctx = winstate->nfaContext; ctx != NULL; ctx = next) - { - next = ctx->next; - - /* Skip the target context and contexts still processing */ - if (ctx == excludeCtx || ctx->states != NULL) - continue; - - /* Skip successfully matched contexts (will be handled by SKIP logic) */ - if (ctx->matchEndRow >= ctx->matchStartRow) - continue; - - /* - * This is a failed context - count and remove it. Only count if it - * actually processed its start row. Contexts created for - * beyond-partition rows are silently removed. - */ - if (ctx->lastProcessedRow >= ctx->matchStartRow) - { - int64 failedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1; - - nfa_record_context_failure(winstate, failedLen); - } - /* else: context was never processed (beyond-partition), just remove */ - - nfa_context_free(winstate, ctx); - } -} -/* - * nfa_finalize_all_contexts - * - * Finalize all active contexts when partition ends. - * Match with NULL to force mismatch, then advance to process epsilon transitions. - */ -static void -nfa_finalize_all_contexts(WindowAggState *winstate, int64 lastPos) -{ - RPRNFAContext *ctx; +/*********************************************************************** + * API exposed to window functions + ***********************************************************************/ - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) - { - if (ctx->states != NULL) - { - nfa_match(winstate, ctx, NULL); - nfa_advance(winstate, ctx, lastPos); - } - } -} /* - * nfa_update_absorption_flags - * - * Update context's absorption flags after state changes. - * - * Two flags control absorption behavior: - * 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. + * WinCheckAndInitializeNullTreatment + * Check null treatment clause and sets ignore_nulls * - * Optimization: Once hasAbsorbableState becomes false, both flags remain false - * permanently, so we skip recalculation. + * Window functions should call this to check if they are being called with + * a null treatment clause when they don't allow it, or to set ignore_nulls. */ -static void -nfa_update_absorption_flags(RPRNFAContext *ctx) +void +WinCheckAndInitializeNullTreatment(WindowObject winobj, + bool allowNullTreatment, + FunctionCallInfo fcinfo) { - RPRNFAState *state; - bool hasAbsorbable = false; - bool allAbsorbable = true; - - /* - * Optimization: Once hasAbsorbableState becomes false, it stays false. No - * need to recalculate - both flags remain false permanently. - */ - if (!ctx->hasAbsorbableState) - { - ctx->allStatesAbsorbable = false; - return; - } - - /* No states means no absorbable states */ - if (ctx->states == NULL) + Assert(WindowObjectIsValid(winobj)); + if (winobj->ignore_nulls != NO_NULLTREATMENT && !allowNullTreatment) { - ctx->hasAbsorbableState = false; - ctx->allStatesAbsorbable = false; - return; - } + const char *funcname = get_func_name(fcinfo->flinfo->fn_oid); - /* - * Iterate through all states to check absorption status. Uses - * state->isAbsorbable which tracks if state is in absorbable region. This - * is different from RPRElemIsAbsorbable(elem) which checks judgment - * point. - */ - for (state = ctx->states; state != NULL; state = state->next) - { - if (state->isAbsorbable) - hasAbsorbable = true; - else - allAbsorbable = false; + if (!funcname) + elog(ERROR, "could not get function name"); + ereport(ERROR, + (errcode(ERRCODE_FEATURE_NOT_SUPPORTED), + errmsg("function %s does not allow RESPECT/IGNORE NULLS", + funcname))); } - - ctx->hasAbsorbableState = hasAbsorbable; - ctx->allStatesAbsorbable = allAbsorbable; + else if (winobj->ignore_nulls == PARSER_IGNORE_NULLS) + winobj->ignore_nulls = IGNORE_NULLS; } /* - * nfa_states_covered - * - * Check if all states in newer context are "covered" by older context. + * WinGetPartitionLocalMemory + * Get working memory that lives till end of partition processing * - * A newer state is covered when older context has an absorbable state at the - * same pattern element (elemIdx) with count >= newer's count at that depth. - * The covering state must be absorbable because only absorbable states can - * guarantee to produce superset matches. + * On first call within a given partition, this allocates and zeroes the + * requested amount of space. Subsequent calls just return the same chunk. * - * If all newer states are covered, newer context's eventual matches will be - * a subset of older context's matches, making newer redundant. + * Memory obtained this way is normally used to hold state that should be + * automatically reset for each new partition. If a window function wants + * to hold state across the whole query, fcinfo->fn_extra can be used in the + * usual way for that. */ -static bool -nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, RPRNFAContext *newer) +void * +WinGetPartitionLocalMemory(WindowObject winobj, Size sz) { - RPRNFAState *newerState; - - for (newerState = newer->states; newerState != NULL; newerState = newerState->next) - { - RPRNFAState *olderState; - RPRPatternElement *elem; - int depth; - bool found = false; - - /* All states are absorbable (caller checks allStatesAbsorbable) */ - elem = &pattern->elements[newerState->elemIdx]; - depth = elem->depth; - - for (olderState = older->states; olderState != NULL; olderState = olderState->next) - { - /* Covering state must also be absorbable */ - if (olderState->isAbsorbable && - olderState->elemIdx == newerState->elemIdx && - olderState->counts[depth] >= newerState->counts[depth]) - { - found = true; - break; - } - } - - if (!found) - return false; - } - - return true; + Assert(WindowObjectIsValid(winobj)); + if (winobj->localmem == NULL) + winobj->localmem = + MemoryContextAllocZero(winobj->winstate->partcontext, sz); + return winobj->localmem; } /* - * nfa_try_absorb_context - * - * Try to absorb ctx (newer) into an older in-progress context. - * Returns true if ctx was absorbed and freed. - * - * Absorption requires three conditions: - * 1. ctx must have all states absorbable (allStatesAbsorbable). - * If ctx has any non-absorbable state, it may produce unique matches. - * 2. older must have at least one absorbable state (hasAbsorbableState). - * Without absorbable states, older cannot cover newer's states. - * 3. All ctx states must be covered by older's absorbable states. - * This ensures older will produce all matches that ctx would produce. - * - * Context list is ordered by creation time (oldest first via prev chain). - * Each row creates at most one context, so earlier contexts have smaller - * matchStartRow values. + * WinGetCurrentPosition + * Return the current row's position (counting from 0) within the current + * partition. */ -static bool -nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx) +int64 +WinGetCurrentPosition(WindowObject winobj) { - RPRPattern *pattern = winstate->rpPattern; - RPRNFAContext *older; - - /* Early exit: ctx must have all states absorbable */ - if (!ctx->allStatesAbsorbable) - return false; - - for (older = ctx->prev; older != NULL; older = older->prev) - { - /* - * By invariant: ctx->prev chain is in creation order (oldest first), - * and each row creates at most one context. So all contexts in this - * chain have matchStartRow < ctx->matchStartRow. - */ - - /* Older must also be in-progress */ - if (older->states == NULL) - continue; - - /* Older must have at least one absorbable state */ - if (!older->hasAbsorbableState) - continue; - - /* Check if all newer states are covered by older */ - if (nfa_states_covered(pattern, older, ctx)) - { - int64 absorbedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1; - - nfa_context_free(winstate, ctx); - nfa_record_context_absorbed(winstate, absorbedLen); - return true; - } - } - - return false; + Assert(WindowObjectIsValid(winobj)); + return winobj->winstate->currentpos; } /* - * nfa_absorb_contexts - * - * Absorb redundant contexts to reduce memory usage and computation. - * - * For patterns like A+, newer contexts starting later will produce subset - * matches of older contexts with higher counts. By absorbing these redundant - * contexts early, we avoid duplicate work. + * WinGetPartitionRowCount + * Return total number of rows contained in the current partition. * - * Iterates from tail (newest) toward head (oldest) via prev chain. - * Only in-progress contexts (states != NULL) are candidates for absorption; - * completed contexts represent valid match results. + * Note: this is a relatively expensive operation because it forces the + * whole partition to be "spooled" into the tuplestore at once. Once + * executed, however, additional calls within the same partition are cheap. */ -static void -nfa_absorb_contexts(WindowAggState *winstate) +int64 +WinGetPartitionRowCount(WindowObject winobj) { - RPRNFAContext *ctx; - RPRNFAContext *nextCtx; - - for (ctx = winstate->nfaContextTail; ctx != NULL; ctx = nextCtx) - { - nextCtx = ctx->prev; - - /* - * Only absorb in-progress contexts; completed contexts are valid - * results - */ - if (ctx->states != NULL) - nfa_try_absorb_context(winstate, ctx); - } + Assert(WindowObjectIsValid(winobj)); + spool_tuples(winobj->winstate, -1); + return winobj->winstate->spooled_rows; } /* - * nfa_eval_var_match + * WinSetMarkPosition + * Set the "mark" position for the window object, which is the oldest row + * number (counting from 0) it is allowed to fetch during all subsequent + * operations within the current partition. * - * Evaluate if a VAR element matches the current row. - * Undefined variables (varId >= defineVariableList length) default to TRUE. + * Window functions do not have to call this, but are encouraged to move the + * mark forward when possible to keep the tuplestore size down and prevent + * having to spill rows to disk. */ -static inline bool -nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, - bool *varMatched) +void +WinSetMarkPosition(WindowObject winobj, int64 markpos) { - /* This function should only be called for VAR elements */ - Assert(RPRElemIsVar(elem)); - - if (varMatched == NULL) - return false; - if (elem->varId >= list_length(winstate->defineVariableList)) - return true; - return varMatched[elem->varId]; -} + WindowAggState *winstate; -/* - * nfa_match - * - * Match phase (convergence): evaluate VAR elements against current row. - * Only updates counts and removes dead states. Minimal transitions. - * - * For VAR elements: - * - matched: count++, keep state (unless count > max) - * - not matched: remove state (exit alternatives already exist from - * previous advance when count >= min was satisfied) - * - * For simple VARs (min=max=1) followed by END: - * - Advance to END and update group count before absorb phase - * - This ensures absorption can compare states by group completion - * - * Non-VAR elements (ALT, END, FIN) are kept as-is for advance phase. - */ -static void -nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched) -{ - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; - RPRNFAState **prevPtr = &ctx->states; - RPRNFAState *state; - RPRNFAState *nextState; + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; - /* - * Evaluate VAR elements against current row. For simple VARs with END - * next, advance to END and update group count inline so absorb phase can - * compare states properly. - */ - for (state = ctx->states; state != NULL; state = nextState) + if (markpos < winobj->markpos) + elog(ERROR, "cannot move WindowObject's mark position backward"); + tuplestore_select_read_pointer(winstate->buffer, winobj->markptr); + if (markpos > winobj->markpos) { - RPRPatternElement *elem = &elements[state->elemIdx]; - - nextState = state->next; - - if (RPRElemIsVar(elem)) - { - bool matched; - int depth = elem->depth; - int32 count = state->counts[depth]; - - matched = nfa_eval_var_match(winstate, elem, varMatched); - - if (matched) - { - /* Increment count */ - if (count < RPR_COUNT_MAX) - count++; - - /* Max constraint should not be exceeded */ - Assert(elem->max == RPR_QUANTITY_INF || count <= elem->max); - - state->counts[depth] = count; - - /* - * For simple VAR (min=max=1) with END next, advance to END - * and update group count inline. This keeps state in place, - * preserving lexical order. - */ - if (elem->min == 1 && elem->max == 1 && - RPRElemIsEnd(&elements[elem->next])) - { - RPRPatternElement *endElem = &elements[elem->next]; - int endDepth = endElem->depth; - int32 endCount = state->counts[endDepth]; - - Assert(count == 1); - - /* Increment group count with overflow protection */ - if (endCount < RPR_COUNT_MAX) - endCount++; - - /* - * END's max can never be exceeded here because - * nfa_advance_end only loops when count < max, so - * endCount entering inline advance is at most max-1, and - * incrementing yields at most max. - */ - Assert(endElem->max == RPR_QUANTITY_INF || - endCount <= endElem->max); - - state->elemIdx = elem->next; - state->counts[endDepth] = endCount; - } - /* else: stay at VAR for advance phase */ - } - else - { - /* - * Not matched - remove state. Exit alternatives were already - * created by advance phase when count >= min was satisfied. - */ - *prevPtr = nextState; - nfa_state_free(winstate, state); - continue; - } - } - /* Non-VAR elements: keep as-is for advance phase */ - - prevPtr = &state->next; + tuplestore_skiptuples(winstate->buffer, + markpos - winobj->markpos, + true); + winobj->markpos = markpos; + } + tuplestore_select_read_pointer(winstate->buffer, winobj->readptr); + if (markpos > winobj->seekpos) + { + tuplestore_skiptuples(winstate->buffer, + markpos - winobj->seekpos, + true); + winobj->seekpos = markpos; } } /* - * nfa_route_to_elem + * WinRowsArePeers + * Compare two rows (specified by absolute position in partition) to see + * if they are equal according to the ORDER BY clause. * - * Route state to next element. If VAR, add to ctx->states and process - * skip path if optional. Otherwise, continue epsilon expansion via recursion. + * NB: this does not consider the window frame mode. */ -static void -nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *nextElem, - int64 currentPos) +bool +WinRowsArePeers(WindowObject winobj, int64 pos1, int64 pos2) { - if (RPRElemIsVar(nextElem)) - { - RPRNFAState *skipState = NULL; - - /* Create skip state before add_unique, which may free state */ - if (RPRElemCanSkip(nextElem)) - skipState = nfa_state_create(winstate, nextElem->next, - state->counts, state->isAbsorbable); - - nfa_add_state_unique(winstate, ctx, state); + WindowAggState *winstate; + WindowAgg *node; + TupleTableSlot *slot1; + TupleTableSlot *slot2; + bool res; - if (skipState != NULL) - nfa_advance_state(winstate, ctx, skipState, currentPos); - } - else - { - nfa_advance_state(winstate, ctx, state, currentPos); - } -} + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; + node = (WindowAgg *) winstate->ss.ps.plan; -/* - * nfa_advance_alt - * - * Handle ALT element: expand all branches in lexical order via DFS. - */ -static void -nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos) -{ - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; - RPRElemIdx altIdx = elem->next; + /* If no ORDER BY, all rows are peers; don't bother to fetch them */ + if (node->ordNumCols == 0) + return true; - while (altIdx >= 0 && altIdx < pattern->numElements) - { - RPRPatternElement *altElem = &elements[altIdx]; - RPRNFAState *newState; + /* + * Note: OK to use temp_slot_2 here because we aren't calling any + * frame-related functions (those tend to clobber temp_slot_2). + */ + slot1 = winstate->temp_slot_1; + slot2 = winstate->temp_slot_2; - /* Stop if element is outside ALT scope (not a branch) */ - if (altElem->depth <= elem->depth) - break; + if (!window_gettupleslot(winobj, pos1, slot1)) + elog(ERROR, "specified position is out of window: " INT64_FORMAT, + pos1); + if (!window_gettupleslot(winobj, pos2, slot2)) + elog(ERROR, "specified position is out of window: " INT64_FORMAT, + pos2); - /* Create independent state for each branch */ - newState = nfa_state_create(winstate, altIdx, - state->counts, state->isAbsorbable); + res = are_peers(winstate, slot1, slot2); - /* Recursively process this branch before next */ - nfa_advance_state(winstate, ctx, newState, currentPos); - altIdx = altElem->jump; - } + ExecClearTuple(slot1); + ExecClearTuple(slot2); - nfa_state_free(winstate, state); + return res; } /* - * nfa_advance_begin + * WinGetFuncArgInPartition + * Evaluate a window function's argument expression on a specified + * row of the partition. The row is identified in lseek(2) style, + * i.e. relative to the current, first, or last row. + * + * argno: argument number to evaluate (counted from 0) + * relpos: signed rowcount offset from the seek position + * seektype: WINDOW_SEEK_CURRENT, WINDOW_SEEK_HEAD, or WINDOW_SEEK_TAIL + * set_mark: If the row is found and set_mark is true, the mark is moved to + * the row as a side-effect. + * isnull: output argument, receives isnull status of result + * isout: output argument, set to indicate whether target row position + * is out of partition (can pass NULL if caller doesn't care about this) * - * Handle BEGIN element: group entry logic. - * BEGIN is only visited at initial group entry (count is always 0). - * If min=0, creates a skip path past the group. - * Loop-back from END goes directly to first child, bypassing BEGIN. + * Specifying a nonexistent row is not an error, it just causes a null result + * (plus setting *isout true, if isout isn't NULL). */ -static void -nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos) +Datum +WinGetFuncArgInPartition(WindowObject winobj, int argno, + int relpos, int seektype, bool set_mark, + bool *isnull, bool *isout) { - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; - RPRNFAState *skipState = NULL; + WindowAggState *winstate; + int64 abs_pos; + int64 mark_pos; + Datum datum; + bool null_treatment; + int notnull_offset; + int notnull_relpos; + int forward; + bool myisout; - state->counts[elem->depth] = 0; + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; + + null_treatment = (winobj->ignore_nulls == IGNORE_NULLS && relpos != 0); - /* Optional group: create skip path (but don't route yet) */ - if (elem->min == 0) + switch (seektype) { - skipState = nfa_state_create(winstate, elem->jump, - state->counts, state->isAbsorbable); + case WINDOW_SEEK_CURRENT: + if (null_treatment) + abs_pos = winstate->currentpos; + else + abs_pos = winstate->currentpos + relpos; + break; + case WINDOW_SEEK_HEAD: + if (null_treatment) + abs_pos = 0; + else + abs_pos = relpos; + break; + case WINDOW_SEEK_TAIL: + spool_tuples(winstate, -1); + abs_pos = winstate->spooled_rows - 1 + relpos; + break; + default: + elog(ERROR, "unrecognized window seek type: %d", seektype); + abs_pos = 0; /* keep compiler quiet */ + break; } - if (skipState != NULL && RPRElemIsReluctant(elem)) + /* Easy case if IGNORE NULLS is not specified */ + if (!null_treatment) { - RPRNFAState *savedMatch = ctx->matchedState; + /* get tuple and evaluate in partition */ + datum = gettuple_eval_partition(winobj, argno, + abs_pos, isnull, &myisout); + if (!myisout && set_mark) + WinSetMarkPosition(winobj, abs_pos); + if (isout) + *isout = myisout; + return datum; + } - /* Reluctant: skip first (prefer fewer iterations), enter second */ - nfa_route_to_elem(winstate, ctx, skipState, - &elements[elem->jump], currentPos); + /* Prepare for loop */ + notnull_offset = 0; + notnull_relpos = abs(relpos); + forward = relpos > 0 ? 1 : -1; + myisout = false; + datum = 0; + /* + * IGNORE NULLS + WINDOW_SEEK_CURRENT + relpos > 0 case, we would fetch + * beyond the current row + relpos to find out the target row. If we mark + * at abs_pos, next call to WinGetFuncArgInPartition or + * WinGetFuncArgInFrame (in case when a window function have multiple + * args) could fail with "cannot fetch row before WindowObject's mark + * position". So keep the mark position at currentpos. + */ + if (seektype == WINDOW_SEEK_CURRENT && relpos > 0) + mark_pos = winstate->currentpos; + else + { /* - * If skip path reached FIN, shortest match is found. Skip group entry - * to prevent longer matches. + * For other cases we have no idea what position of row callers would + * fetch next time. Also for relpos < 0 case (we go backward), we + * cannot set mark either. For those cases we always set mark at 0. */ - if (ctx->matchedState != savedMatch) - { - nfa_state_free(winstate, state); - return; - } - - state->elemIdx = elem->next; - nfa_route_to_elem(winstate, ctx, state, - &elements[state->elemIdx], currentPos); + mark_pos = 0; } - else + + /* + * Get the next nonnull value in the partition, moving forward or backward + * until we find a value or reach the partition's end. We cache the + * nullness status because we may repeat this process many times. + */ + do { - /* Greedy: enter first, skip second */ - state->elemIdx = elem->next; - nfa_route_to_elem(winstate, ctx, state, - &elements[state->elemIdx], currentPos); + int nn_info; /* NOT NULL status */ + + abs_pos += forward; + if (abs_pos < 0) /* clearly out of partition */ + break; - if (skipState != NULL) + /* check NOT NULL cached info */ + nn_info = get_notnull_info(winobj, abs_pos, argno); + if (nn_info == NN_NOTNULL) /* this row is known to be NOT NULL */ + notnull_offset++; + else if (nn_info == NN_NULL) /* this row is known to be NULL */ + continue; /* keep on moving forward or backward */ + else /* need to check NULL or not */ { - nfa_route_to_elem(winstate, ctx, skipState, - &elements[elem->jump], currentPos); + /* + * NOT NULL info does not exist yet. Get tuple and evaluate func + * arg in partition. We ignore the return value from + * gettuple_eval_partition because we are just interested in + * whether we are inside or outside of partition, NULL or NOT + * NULL. + */ + (void) gettuple_eval_partition(winobj, argno, + abs_pos, isnull, &myisout); + if (myisout) /* out of partition? */ + break; + if (!*isnull) + notnull_offset++; + /* record the row status */ + put_notnull_info(winobj, abs_pos, argno, *isnull); } - } + } while (notnull_offset < notnull_relpos); + + /* get tuple and evaluate func arg in partition */ + datum = gettuple_eval_partition(winobj, argno, + abs_pos, isnull, &myisout); + if (!myisout && set_mark) + WinSetMarkPosition(winobj, mark_pos); + if (isout) + *isout = myisout; + + return datum; } /* - * nfa_advance_end + * WinGetFuncArgInFrame + * Evaluate a window function's argument expression on a specified + * row of the window frame. The row is identified in lseek(2) style, + * i.e. relative to the first or last row of the frame. (We do not + * support WINDOW_SEEK_CURRENT here, because it's not very clear what + * that should mean if the current row isn't part of the frame.) + * + * argno: argument number to evaluate (counted from 0) + * relpos: signed rowcount offset from the seek position + * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL + * set_mark: If the row is found/in frame and set_mark is true, the mark is + * moved to the row as a side-effect. + * isnull: output argument, receives isnull status of result + * isout: output argument, set to indicate whether target row position + * is out of frame (can pass NULL if caller doesn't care about this) + * + * Specifying a nonexistent or not-in-frame row is not an error, it just + * causes a null result (plus setting *isout true, if isout isn't NULL). + * + * Note that some exclusion-clause options lead to situations where the + * rows that are in-frame are not consecutive in the partition. But we + * count only in-frame rows when measuring relpos. * - * Handle END element: group repetition logic. - * Decides whether to loop back or exit based on count vs min/max. + * The set_mark flag is interpreted as meaning that the caller will specify + * a constant (or, perhaps, monotonically increasing) relpos in successive + * calls, so that *if there is no exclusion clause* there will be no need + * to fetch a row before the previously fetched row. But we do not expect + * the caller to know how to account for exclusion clauses. Therefore, + * if there is an exclusion clause we take responsibility for adjusting the + * mark request to something that will be safe given the above assumption + * about relpos. */ -static void -nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos) +Datum +WinGetFuncArgInFrame(WindowObject winobj, int argno, + int relpos, int seektype, bool set_mark, + bool *isnull, bool *isout) { - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; - int depth = elem->depth; - int32 count = state->counts[depth]; - - if (count < elem->min) - { - RPRPatternElement *jumpElem; - RPRNFAState *ffState = NULL; - - /* Snapshot state for ff path before modifying for loop-back */ - if (RPRElemCanEmptyLoop(elem)) - ffState = nfa_state_create(winstate, state->elemIdx, - state->counts, state->isAbsorbable); - - /* Loop back for real matches (primary path) */ - for (int d = depth + 1; d < pattern->maxDepth; d++) - state->counts[d] = 0; - state->elemIdx = elem->jump; - jumpElem = &elements[state->elemIdx]; - nfa_route_to_elem(winstate, ctx, state, jumpElem, - currentPos); - - /* - * Fast-forward fallback for nullable bodies. E.g. (A?){2,3} when A - * doesn't match: the loop-back produces empty iterations that cycle - * detection would kill. Instead, exit directly treating all - * remaining required iterations as empty. Route to elem->next (not - * nfa_advance_end) to avoid creating competing greedy/reluctant loop - * states. - */ - if (ffState != NULL) - { - RPRPatternElement *nextElem; + WindowAggState *winstate; + ExprContext *econtext; + TupleTableSlot *slot; - ffState->counts[depth] = 0; - ffState->elemIdx = elem->next; - nextElem = &elements[ffState->elemIdx]; + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; + econtext = winstate->ss.ps.ps_ExprContext; + slot = winstate->temp_slot_1; - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && - ffState->counts[nextElem->depth] < RPR_COUNT_MAX) - ffState->counts[nextElem->depth]++; + if (winobj->ignore_nulls == IGNORE_NULLS) + return ignorenulls_getfuncarginframe(winobj, argno, relpos, seektype, + set_mark, isnull, isout); - nfa_route_to_elem(winstate, ctx, ffState, nextElem, - currentPos); - } - } - else if (elem->max != RPR_QUANTITY_INF && count >= elem->max) + if (WinGetSlotInFrame(winobj, slot, + relpos, seektype, set_mark, + isnull, isout) == 0) { - /* Must exit: reached max iterations. */ - RPRPatternElement *nextElem; - - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; - - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && state->counts[nextElem->depth] < RPR_COUNT_MAX) - state->counts[nextElem->depth]++; - - nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); + econtext->ecxt_outertuple = slot; + return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno), + econtext, isnull); } - else - { - /* - * Between min and max (with at least one iteration) - can exit or - * loop. Greedy: loop first (prefer more iterations). Reluctant: exit - * first (prefer fewer iterations). - */ - RPRNFAState *exitState; - RPRPatternElement *jumpElem; - RPRPatternElement *nextElem; - - /* - * Create exit state first (need original counts before modifying - * state) - */ - exitState = nfa_state_create(winstate, elem->next, - state->counts, state->isAbsorbable); - exitState->counts[depth] = 0; - nextElem = &elements[exitState->elemIdx]; - - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && exitState->counts[nextElem->depth] < RPR_COUNT_MAX) - exitState->counts[nextElem->depth]++; - - /* Prepare loop state */ - for (int d = depth + 1; d < pattern->maxDepth; d++) - state->counts[d] = 0; - state->elemIdx = elem->jump; - jumpElem = &elements[state->elemIdx]; - - if (RPRElemIsReluctant(elem)) - { - RPRNFAState *savedMatch = ctx->matchedState; - - /* Exit first (preferred for reluctant) */ - nfa_route_to_elem(winstate, ctx, exitState, nextElem, - currentPos); - - /* - * If exit path reached FIN, shortest match is found. Skip loop to - * prevent longer matches from replacing it. - */ - if (ctx->matchedState != savedMatch) - { - nfa_state_free(winstate, state); - return; - } - /* Loop second */ - nfa_route_to_elem(winstate, ctx, state, jumpElem, - currentPos); - } - else - { - /* Loop first (preferred for greedy) */ - nfa_route_to_elem(winstate, ctx, state, jumpElem, - currentPos); - /* Exit second */ - nfa_route_to_elem(winstate, ctx, exitState, nextElem, - currentPos); - } - } + if (isout) + *isout = true; + *isnull = true; + return (Datum) 0; } /* - * nfa_advance_var + * WinGetSlotInFrame + * slot: TupleTableSlot to store the result + * relpos: signed rowcount offset from the seek position + * seektype: WINDOW_SEEK_HEAD or WINDOW_SEEK_TAIL + * set_mark: If the row is found/in frame and set_mark is true, the mark is + * moved to the row as a side-effect. + * isnull: output argument, receives isnull status of result + * isout: output argument, set to indicate whether target row position + * is out of frame (can pass NULL if caller doesn't care about this) * - * Handle VAR element: loop/exit transitions. - * After match phase, all VAR states have matched - decide next action. + * Returns 0 if we successfullt got the slot. false if out of frame. + * (also isout is set) */ -static void -nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *elem, - int64 currentPos) +static int +WinGetSlotInFrame(WindowObject winobj, TupleTableSlot *slot, + int relpos, int seektype, bool set_mark, + bool *isnull, bool *isout) { - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; - int depth = elem->depth; - int32 count = state->counts[depth]; - bool canLoop = (elem->max == RPR_QUANTITY_INF || count < elem->max); - bool canExit = (count >= elem->min); + WindowAggState *winstate; + int64 abs_pos; + int64 mark_pos; + int num_reduced_frame; - /* After a successful match, count >= 1, so at least one must be true */ - Assert(canLoop || canExit); + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; - if (canLoop && canExit) + switch (seektype) { - /* - * Both loop and exit possible. Greedy: loop first (prefer longer - * match). Reluctant: exit first (prefer shorter match). - */ - RPRNFAState *cloneState; - RPRPatternElement *nextElem; - bool reluctant = RPRElemIsReluctant(elem); + case WINDOW_SEEK_CURRENT: + elog(ERROR, "WINDOW_SEEK_CURRENT is not supported for WinGetFuncArgInFrame"); + abs_pos = mark_pos = 0; /* keep compiler quiet */ + break; + case WINDOW_SEEK_HEAD: + /* rejecting relpos < 0 is easy and simplifies code below */ + if (relpos < 0) + goto out_of_frame; + update_frameheadpos(winstate); + abs_pos = winstate->frameheadpos + relpos; + mark_pos = abs_pos; - /* - * Clone state for the second-priority path. For greedy, clone is the - * loop state; for reluctant, clone is the exit state. - */ - if (reluctant) - { - RPRNFAState *savedMatch = ctx->matchedState; + /* + * Account for exclusion option if one is active, but advance only + * abs_pos not mark_pos. This prevents changes of the current + * row's peer group from resulting in trying to fetch a row before + * some previous mark position. + * + * Note that in some corner cases such as current row being + * outside frame, these calculations are theoretically too simple, + * but it doesn't matter because we'll end up deciding the row is + * out of frame. We do not attempt to avoid fetching rows past + * end of frame; that would happen in some cases anyway. + */ + switch (winstate->frameOptions & FRAMEOPTION_EXCLUSION) + { + case 0: + /* no adjustment needed */ + break; + case FRAMEOPTION_EXCLUDE_CURRENT_ROW: + if (abs_pos >= winstate->currentpos && + winstate->currentpos >= winstate->frameheadpos) + abs_pos++; + break; + case FRAMEOPTION_EXCLUDE_GROUP: + update_grouptailpos(winstate); + if (abs_pos >= winstate->groupheadpos && + winstate->grouptailpos > winstate->frameheadpos) + { + int64 overlapstart = Max(winstate->groupheadpos, + winstate->frameheadpos); - /* Clone for exit, original stays for loop */ - cloneState = nfa_state_create(winstate, elem->next, - state->counts, state->isAbsorbable); - cloneState->counts[depth] = 0; - nextElem = &elements[cloneState->elemIdx]; + abs_pos += winstate->grouptailpos - overlapstart; + } + break; + case FRAMEOPTION_EXCLUDE_TIES: + update_grouptailpos(winstate); + if (abs_pos >= winstate->groupheadpos && + winstate->grouptailpos > winstate->frameheadpos) + { + int64 overlapstart = Max(winstate->groupheadpos, + winstate->frameheadpos); - /* When exiting directly to an outer END, increment its count */ - if (RPRElemIsEnd(nextElem)) - { - if (cloneState->counts[nextElem->depth] < RPR_COUNT_MAX) - cloneState->counts[nextElem->depth]++; + if (abs_pos == overlapstart) + abs_pos = winstate->currentpos; + else + abs_pos += winstate->grouptailpos - overlapstart - 1; + } + break; + default: + elog(ERROR, "unrecognized frame option state: 0x%x", + winstate->frameOptions); + break; } - - /* Exit first (preferred for reluctant) */ - nfa_route_to_elem(winstate, ctx, cloneState, nextElem, - currentPos); + num_reduced_frame = row_is_in_reduced_frame(winobj, + winstate->frameheadpos); + if (num_reduced_frame < 0) + goto out_of_frame; + else if (num_reduced_frame > 0) + if (relpos >= num_reduced_frame) + goto out_of_frame; + break; + case WINDOW_SEEK_TAIL: + /* rejecting relpos > 0 is easy and simplifies code below */ + if (relpos > 0) + goto out_of_frame; /* - * If exit path reached FIN, the shortest match is found. Skip - * loop state to prevent longer matches from replacing it. + * RPR cares about frame head pos. Need to call + * update_frameheadpos */ - if (ctx->matchedState != savedMatch) - { - nfa_state_free(winstate, state); - return; - } - - /* Loop second */ - nfa_add_state_unique(winstate, ctx, state); - } - else - { - /* Clone for loop, original used for exit */ - cloneState = nfa_state_create(winstate, state->elemIdx, - state->counts, state->isAbsorbable); - - /* Loop first (preferred for greedy) */ - nfa_add_state_unique(winstate, ctx, cloneState); + update_frameheadpos(winstate); - /* Exit second */ - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; + update_frametailpos(winstate); + abs_pos = winstate->frametailpos - 1 + relpos; /* - * When exiting directly to an outer END, increment its iteration - * count. Simple VARs (min=max=1) handle this via inline advance - * in nfa_match, but quantified VARs bypass that path. + * Account for exclusion option if one is active. If there is no + * exclusion, we can safely set the mark at the accessed row. But + * if there is, we can only mark the frame start, because we can't + * be sure how far back in the frame the exclusion might cause us + * to fetch in future. Furthermore, we have to actually check + * against frameheadpos here, since it's unsafe to try to fetch a + * row before frame start if the mark might be there already. */ - if (RPRElemIsEnd(nextElem)) + switch (winstate->frameOptions & FRAMEOPTION_EXCLUSION) { - if (state->counts[nextElem->depth] < RPR_COUNT_MAX) - state->counts[nextElem->depth]++; - } - - nfa_route_to_elem(winstate, ctx, state, nextElem, - currentPos); - } - } - else if (canLoop) - { - /* Loop only: keep state as-is */ - nfa_add_state_unique(winstate, ctx, state); - } - else if (canExit) - { - /* Exit only: advance to next element */ - RPRPatternElement *nextElem; - - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; - - /* See comment above: increment outer END count for quantified VARs */ - if (RPRElemIsEnd(nextElem)) - { - if (state->counts[nextElem->depth] < RPR_COUNT_MAX) - state->counts[nextElem->depth]++; - } - - nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); - } -} - -/* - * nfa_advance_state - * - * Recursively process a single state through epsilon transitions. - * DFS traversal ensures states are added to ctx->states in lexical order. - */ -static void -nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, int64 currentPos) -{ - RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elem; - - Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements); + case 0: + /* no adjustment needed */ + mark_pos = abs_pos; + break; + case FRAMEOPTION_EXCLUDE_CURRENT_ROW: + if (abs_pos <= winstate->currentpos && + winstate->currentpos < winstate->frametailpos) + abs_pos--; + update_frameheadpos(winstate); + if (abs_pos < winstate->frameheadpos) + goto out_of_frame; + mark_pos = winstate->frameheadpos; + break; + case FRAMEOPTION_EXCLUDE_GROUP: + update_grouptailpos(winstate); + if (abs_pos < winstate->grouptailpos && + winstate->groupheadpos < winstate->frametailpos) + { + int64 overlapend = Min(winstate->grouptailpos, + winstate->frametailpos); - /* Cycle detection: if this elemIdx was already visited in this DFS, bail */ - if (winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] & - ((bitmapword) 1 << BITNUM(state->elemIdx))) - { - nfa_state_free(winstate, state); - return; - } - winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] |= - ((bitmapword) 1 << BITNUM(state->elemIdx)); + abs_pos -= overlapend - winstate->groupheadpos; + } + update_frameheadpos(winstate); + if (abs_pos < winstate->frameheadpos) + goto out_of_frame; + mark_pos = winstate->frameheadpos; + break; + case FRAMEOPTION_EXCLUDE_TIES: + update_grouptailpos(winstate); + if (abs_pos < winstate->grouptailpos && + winstate->groupheadpos < winstate->frametailpos) + { + int64 overlapend = Min(winstate->grouptailpos, + winstate->frametailpos); - elem = &pattern->elements[state->elemIdx]; + if (abs_pos == overlapend - 1) + abs_pos = winstate->currentpos; + else + abs_pos -= overlapend - 1 - winstate->groupheadpos; + } + update_frameheadpos(winstate); + if (abs_pos < winstate->frameheadpos) + goto out_of_frame; + mark_pos = winstate->frameheadpos; + break; + default: + elog(ERROR, "unrecognized frame option state: 0x%x", + winstate->frameOptions); + mark_pos = 0; /* keep compiler quiet */ + break; + } - switch (elem->varId) - { - case RPR_VARID_FIN: - /* FIN: record match */ - nfa_add_matched_state(winstate, ctx, state, currentPos); + num_reduced_frame = row_is_in_reduced_frame(winobj, + winstate->frameheadpos + relpos); + if (num_reduced_frame < 0) + goto out_of_frame; + else if (num_reduced_frame > 0) + abs_pos = winstate->frameheadpos + relpos + + num_reduced_frame - 1; break; - - case RPR_VARID_ALT: - nfa_advance_alt(winstate, ctx, state, elem, currentPos); + default: + elog(ERROR, "unrecognized window seek type: %d", seektype); + abs_pos = mark_pos = 0; /* keep compiler quiet */ break; + } - case RPR_VARID_BEGIN: - nfa_advance_begin(winstate, ctx, state, elem, currentPos); - break; + if (!window_gettupleslot(winobj, abs_pos, slot)) + goto out_of_frame; - case RPR_VARID_END: - nfa_advance_end(winstate, ctx, state, elem, currentPos); - break; + /* The code above does not detect all out-of-frame cases, so check */ + if (row_is_in_frame(winobj, abs_pos, slot, false) <= 0) + goto out_of_frame; - default: - /* VAR element */ - nfa_advance_var(winstate, ctx, state, elem, currentPos); - break; - } + if (isout) + *isout = false; + if (set_mark) + WinSetMarkPosition(winobj, mark_pos); + return 0; + +out_of_frame: + if (isout) + *isout = true; + *isnull = true; + return -1; } /* - * nfa_advance + * WinGetFuncArgCurrent + * Evaluate a window function's argument expression on the current row. * - * Advance phase (divergence): transition from all surviving states. - * Called after match phase with matched VAR states, or at context creation - * for initial epsilon expansion (with currentPos = startPos - 1). + * argno: argument number to evaluate (counted from 0) + * isnull: output argument, receives isnull status of result * - * Processes states in order, using recursive DFS to maintain lexical order. + * Note: this isn't quite equivalent to WinGetFuncArgInPartition or + * WinGetFuncArgInFrame targeting the current row, because it will succeed + * even if the WindowObject's mark has been set beyond the current row. + * This should generally be used for "ordinary" arguments of a window + * function, such as the offset argument of lead() or lag(). */ -static void -nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) +Datum +WinGetFuncArgCurrent(WindowObject winobj, int argno, bool *isnull) { - RPRNFAState *states = ctx->states; - RPRNFAState *state; - - ctx->states = NULL; /* Will rebuild */ - - /* Process each state in lexical order (DFS order from previous advance) */ - while (states != NULL) - { - RPRNFAState *savedMatchedState = ctx->matchedState; - - /* Clear visited bitmap before each state's DFS expansion */ - memset(winstate->nfaVisitedElems, 0, - sizeof(bitmapword) * winstate->nfaVisitedNWords); + WindowAggState *winstate; + ExprContext *econtext; - state = states; - states = states->next; - state->next = NULL; + Assert(WindowObjectIsValid(winobj)); + winstate = winobj->winstate; - nfa_advance_state(winstate, ctx, state, currentPos); + econtext = winstate->ss.ps.ps_ExprContext; - /* - * Early termination: if a FIN was newly reached in this advance, - * remaining old states have worse lexical order and can be pruned. - * Only check for new FIN arrivals (not ones from previous rows). - */ - if (ctx->matchedState != savedMatchedState && states != NULL) - { - nfa_state_free_list(winstate, states); - break; - } - } + econtext->ecxt_outertuple = winstate->ss.ss_ScanTupleSlot; + return ExecEvalExpr((ExprState *) list_nth(winobj->argstates, argno), + econtext, isnull); } diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 009c0f5019d..b958280e94c 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -4,7 +4,7 @@ * Row Pattern Recognition pattern compilation for planner * * This file contains functions for optimizing RPR pattern AST and - * compiling it to bytecode for execution by WindowAgg. + * compiling it to a flat element array for NFA execution by WindowAgg. * * Key components: * 1. Pattern Optimization: Simplifies patterns before compilation diff --git a/src/include/executor/execRPR.h b/src/include/executor/execRPR.h new file mode 100644 index 00000000000..7b2b0febb76 --- /dev/null +++ b/src/include/executor/execRPR.h @@ -0,0 +1,40 @@ +/*------------------------------------------------------------------------- + * + * execRPR.h + * prototypes for execRPR.c (NFA-based Row Pattern Recognition engine) + * + * + * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * src/include/executor/execRPR.h + * + *------------------------------------------------------------------------- + */ +#ifndef EXECRPR_H +#define EXECRPR_H + +#include "nodes/execnodes.h" +#include "windowapi.h" + +/* NFA context management */ +extern RPRNFAContext *ExecRPRStartContext(WindowAggState *winstate, + int64 startPos); +extern RPRNFAContext *ExecRPRGetHeadContext(WindowAggState *winstate, + int64 pos); +extern void ExecRPRFreeContext(WindowAggState *winstate, RPRNFAContext *ctx); + +/* NFA processing */ +extern void ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, + bool hasLimitedFrame, int64 frameOffset); +extern void ExecRPRCleanupDeadContexts(WindowAggState *winstate, + RPRNFAContext *excludeCtx); +extern void ExecRPRFinalizeAllContexts(WindowAggState *winstate, int64 lastPos); + +/* NFA statistics */ +extern void ExecRPRRecordContextSuccess(WindowAggState *winstate, + int64 matchLen); +extern void ExecRPRRecordContextFailure(WindowAggState *winstate, + int64 failedLen); + +#endif /* EXECRPR_H */ -- 2.50.1 (Apple Git-155)