0012-extract-nfa-engine.txt
text/plain
Filename: 0012-extract-nfa-engine.txt
Type: text/plain
Part: 11
Message:
Re: Row pattern recognition
From f4c54f983b502626fe15e7ed91535f8d9e5756b2 Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
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 ( <regex> )
+ * DEFINE <variable> AS <condition>, ...
+ * )
+ *
+ * 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<TargetEntry>
+ * +--- 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<String> (variable names, DEFINE order)
+ * |--- defineClauseList: List<ExprState>
+ * |--- 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)