0001-Refactor-NFA-absorption-logic.txt
text/plain
Filename: 0001-Refactor-NFA-absorption-logic.txt
Type: text/plain
Part: 0
Message:
Re: Row pattern recognition
From 1bd8eb3ee0faf11b23689143f251de2704d3327c Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Mon, 19 Jan 2026 21:22:14 +0900
Subject: [PATCH] Row pattern recognition: Refactor NFA absorption logic
---
src/backend/commands/explain.c | 24 +-
src/backend/executor/nodeWindowAgg.c | 1473 ++++++++++++++---------
src/backend/optimizer/plan/createplan.c | 2 +-
src/backend/optimizer/plan/rpr.c | 263 +++-
src/backend/parser/gram.y | 5 +
src/include/nodes/execnodes.h | 21 +
src/include/optimizer/rpr.h | 14 +-
src/test/regress/expected/rpr.out | 60 +-
src/test/regress/sql/rpr.sql | 32 +-
9 files changed, 1247 insertions(+), 647 deletions(-)
diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c
index ba114bd491c..3cbf2ec235b 100644
--- a/src/backend/commands/explain.c
+++ b/src/backend/commands/explain.c
@@ -3675,32 +3675,32 @@ show_windowagg_info(WindowAggState *winstate, ExplainState *es)
{
ExplainPropertyInteger("NFA Match Length Min", NULL, winstate->nfaMatchLen.min, es);
ExplainPropertyInteger("NFA Match Length Max", NULL, winstate->nfaMatchLen.max, es);
- ExplainPropertyInteger("NFA Match Length Avg", NULL,
- (int64) ((winstate->nfaMatchLen.total + winstate->nfaMatchesSucceeded / 2) / winstate->nfaMatchesSucceeded),
+ ExplainPropertyFloat("NFA Match Length Avg", NULL,
+ (double) winstate->nfaMatchLen.total / winstate->nfaMatchesSucceeded, 1,
es);
}
if (winstate->nfaMatchesFailed > 0)
{
ExplainPropertyInteger("NFA Mismatch Length Min", NULL, winstate->nfaFailLen.min, es);
ExplainPropertyInteger("NFA Mismatch Length Max", NULL, winstate->nfaFailLen.max, es);
- ExplainPropertyInteger("NFA Mismatch Length Avg", NULL,
- (int64) ((winstate->nfaFailLen.total + winstate->nfaMatchesFailed / 2) / winstate->nfaMatchesFailed),
+ ExplainPropertyFloat("NFA Mismatch Length Avg", NULL,
+ (double) winstate->nfaFailLen.total / winstate->nfaMatchesFailed, 1,
es);
}
if (winstate->nfaContextsAbsorbed > 0)
{
ExplainPropertyInteger("NFA Absorbed Length Min", NULL, winstate->nfaAbsorbedLen.min, es);
ExplainPropertyInteger("NFA Absorbed Length Max", NULL, winstate->nfaAbsorbedLen.max, es);
- ExplainPropertyInteger("NFA Absorbed Length Avg", NULL,
- (int64) ((winstate->nfaAbsorbedLen.total + winstate->nfaContextsAbsorbed / 2) / winstate->nfaContextsAbsorbed),
+ ExplainPropertyFloat("NFA Absorbed Length Avg", NULL,
+ (double) winstate->nfaAbsorbedLen.total / winstate->nfaContextsAbsorbed, 1,
es);
}
if (winstate->nfaContextsSkipped > 0)
{
ExplainPropertyInteger("NFA Skipped Length Min", NULL, winstate->nfaSkippedLen.min, es);
ExplainPropertyInteger("NFA Skipped Length Max", NULL, winstate->nfaSkippedLen.max, es);
- ExplainPropertyInteger("NFA Skipped Length Avg", NULL,
- (int64) ((winstate->nfaSkippedLen.total + winstate->nfaContextsSkipped / 2) / winstate->nfaContextsSkipped),
+ ExplainPropertyFloat("NFA Skipped Length Avg", NULL,
+ (double) winstate->nfaSkippedLen.total / winstate->nfaContextsSkipped, 1,
es);
}
}
@@ -3724,7 +3724,7 @@ show_windowagg_info(WindowAggState *winstate, ExplainState *es)
{
double avgLen = (double) winstate->nfaMatchLen.total / winstate->nfaMatchesSucceeded;
appendStringInfo(es->str,
- INT64_FORMAT " matched (len " INT64_FORMAT "/" INT64_FORMAT "/%.0f)",
+ INT64_FORMAT " matched (len " INT64_FORMAT "/" INT64_FORMAT "/%.1f)",
winstate->nfaMatchesSucceeded,
winstate->nfaMatchLen.min,
winstate->nfaMatchLen.max,
@@ -3738,7 +3738,7 @@ show_windowagg_info(WindowAggState *winstate, ExplainState *es)
{
double avgFail = (double) winstate->nfaFailLen.total / winstate->nfaMatchesFailed;
appendStringInfo(es->str,
- ", " INT64_FORMAT " mismatched (len " INT64_FORMAT "/" INT64_FORMAT "/%.0f)",
+ ", " INT64_FORMAT " mismatched (len " INT64_FORMAT "/" INT64_FORMAT "/%.1f)",
winstate->nfaMatchesFailed,
winstate->nfaFailLen.min,
winstate->nfaFailLen.max,
@@ -3760,7 +3760,7 @@ show_windowagg_info(WindowAggState *winstate, ExplainState *es)
{
double avgAbsorbed = (double) winstate->nfaAbsorbedLen.total / winstate->nfaContextsAbsorbed;
appendStringInfo(es->str,
- INT64_FORMAT " absorbed (len " INT64_FORMAT "/" INT64_FORMAT "/%.0f)",
+ INT64_FORMAT " absorbed (len " INT64_FORMAT "/" INT64_FORMAT "/%.1f)",
winstate->nfaContextsAbsorbed,
winstate->nfaAbsorbedLen.min,
winstate->nfaAbsorbedLen.max,
@@ -3775,7 +3775,7 @@ show_windowagg_info(WindowAggState *winstate, ExplainState *es)
{
double avgSkipped = (double) winstate->nfaSkippedLen.total / winstate->nfaContextsSkipped;
appendStringInfo(es->str,
- ", " INT64_FORMAT " skipped (len " INT64_FORMAT "/" INT64_FORMAT "/%.0f)",
+ ", " INT64_FORMAT " skipped (len " INT64_FORMAT "/" INT64_FORMAT "/%.1f)",
winstate->nfaContextsSkipped,
winstate->nfaSkippedLen.min,
winstate->nfaSkippedLen.max,
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 6002ca05c90..5185ad40237 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -256,31 +256,70 @@ 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);
-/* NFA-based pattern matching functions */
+/* 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_clone(WindowAggState *winstate, int16 elemIdx,
- int16 altPriority, int32 *counts);
-static bool nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched);
+ int16 altPriority, 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 void nfa_step(WindowAggState *winstate, RPRNFAContext *ctx,
- bool *varMatched, int64 pos);
-static void nfa_finalize_all_contexts(WindowAggState *winstate, int64 lastPos);
-static void nfa_process_context(WindowAggState *winstate, RPRNFAContext *ctx,
- int64 currentPos, bool hasLimitedFrame, int64 frameOffset);
-static void nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
- RPRNFAState *state, bool *varMatched, int64 currentPos);
static RPRNFAContext *nfa_find_context_for_pos(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_failure(WindowAggState *winstate, int64 failedLen);
+
+/* Forward declarations - NFA row evaluation */
+static bool nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched);
+
+/* Forward declarations - NFA context lifecycle */
static void nfa_remove_contexts_up_to(WindowAggState *winstate, int64 endPos,
- RPRNFAContext *excludeCtx);
+ RPRNFAContext *excludeCtx);
static void nfa_cleanup_dead_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx);
-static void nfa_absorb_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx, int64 currentPos);
-static void update_nfa_length_stats(int64 count, NFALengthStats *stats, int64 newLen);
-static void record_nfa_context_failure(WindowAggState *winstate, int64 failedLen);
+
+/* Forward declarations - NFA absorption */
+static void nfa_update_absorption_flags(RPRNFAContext *ctx, RPRPattern *pattern);
+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 execution */
+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, bool initialAdvance);
+static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, RPRPatternElement *nextElem,
+ int64 currentPos, bool initialAdvance);
+static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, RPRPatternElement *elem,
+ int64 currentPos, bool initialAdvance);
+static void nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, RPRPatternElement *elem,
+ int64 currentPos, bool initialAdvance);
+static void nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, RPRPatternElement *elem,
+ int64 currentPos, bool initialAdvance);
+static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx,
+ int64 currentPos, bool initialAdvance);
+static void nfa_process_row(WindowAggState *winstate, int64 currentPos,
+ bool hasLimitedFrame, int64 frameOffset);
+static void nfa_finalize_all_contexts(WindowAggState *winstate, int64 lastPos);
/*
* Not null info bit array consists of 2-bit items
@@ -4834,7 +4873,6 @@ update_reduced_frame(WindowObject winobj, int64 pos)
for (currentPos = startPos; targetCtx->states != NULL; currentPos++)
{
bool rowExists;
- RPRNFAContext *ctx;
/* Evaluate variables for this row - done only once, shared by all contexts */
rowExists = nfa_evaluate_row(winobj, currentPos, winstate->nfaVarMatched);
@@ -4846,18 +4884,23 @@ update_reduced_frame(WindowObject winobj, int64 pos)
/* Clean up dead contexts from finalization */
nfa_cleanup_dead_contexts(winstate, targetCtx);
/* Absorb contexts at partition boundary */
- if (winstate->rpSkipTo == ST_PAST_LAST_ROW && !hasLimitedFrame &&
- winstate->rpPattern->isAbsorbable)
- nfa_absorb_contexts(winstate, NULL, currentPos - 1);
+ if (winstate->rpPattern->isAbsorbable)
+ {
+ nfa_absorb_contexts(winstate);
+ }
break;
}
/* Update last processed row */
winstate->nfaLastProcessedRow = currentPos;
- /* Process each active context with this row's evaluation results */
- for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next)
- nfa_process_context(winstate, ctx, currentPos, hasLimitedFrame, frameOffset);
+ /*
+ * Process all contexts for this row:
+ * 1. Match all (convergence)
+ * 2. Absorb redundant
+ * 3. Advance all (divergence)
+ */
+ nfa_process_row(winstate, currentPos, hasLimitedFrame, frameOffset);
/*
* Create a new context for the next potential start position.
@@ -4872,14 +4915,6 @@ update_reduced_frame(WindowObject winobj, int64 pos)
*/
nfa_cleanup_dead_contexts(winstate, targetCtx);
- /*
- * Absorb redundant contexts using simplified algorithm.
- * Only compares absorbable element counts (e.g., A+ or (A B)+).
- */
- if (winstate->rpSkipTo == ST_PAST_LAST_ROW && !hasLimitedFrame &&
- winstate->rpPattern->isAbsorbable)
- nfa_absorb_contexts(winstate, targetCtx, currentPos);
-
/* Check if target context is now complete */
if (targetCtx->states == NULL)
break;
@@ -4896,7 +4931,7 @@ register_result:
int64 mismatchLen = targetCtx->lastProcessedRow - targetCtx->matchStartRow + 1;
register_reduced_frame_map(winstate, targetCtx->matchStartRow, RF_UNMATCHED);
- record_nfa_context_failure(winstate, mismatchLen);
+ nfa_record_context_failure(winstate, mismatchLen);
}
else
{
@@ -4908,7 +4943,7 @@ register_result:
register_reduced_frame_map(winstate, i, RF_SKIPPED);
}
winstate->nfaMatchesSucceeded++;
- update_nfa_length_stats(winstate->nfaMatchesSucceeded,
+ nfa_update_length_stats(winstate->nfaMatchesSucceeded,
&winstate->nfaMatchLen,
matchLen);
}
@@ -4934,6 +4969,83 @@ register_result:
*
* 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.
+ *
+ * - initialAdvance flag: The first advance after context creation must
+ * skip FIN recording. Reaching FIN without evaluating any VAR would
+ * create a zero-length match, which is invalid.
+ *
+ * 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.
*/
/*
@@ -5003,6 +5115,39 @@ nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list)
}
}
+/*
+ * nfa_state_clone
+ *
+ * Clone a state with given elemIdx, altPriority 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_clone(WindowAggState *winstate, int16 elemIdx, int16 altPriority,
+ 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;
+ state->altPriority = altPriority;
+ 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
*
@@ -5059,28 +5204,6 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *
return true;
}
-/*
- * nfa_state_clone
- *
- * Clone a state with given elemIdx, altPriority and counts.
- * Caller is responsible for linking the returned state.
- */
-static RPRNFAState *
-nfa_state_clone(WindowAggState *winstate, int16 elemIdx, int16 altPriority,
- int32 *counts)
-{
- RPRPattern *pattern = winstate->rpPattern;
- int maxDepth = pattern->maxDepth;
- RPRNFAState *state = nfa_state_alloc(winstate);
-
- state->elemIdx = elemIdx;
- state->altPriority = altPriority;
- if (counts != NULL && maxDepth > 0)
- memcpy(state->counts, counts, sizeof(int32) * maxDepth);
-
- return state;
-}
-
/*
* nfa_add_matched_state
*
@@ -5120,74 +5243,6 @@ nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx,
}
}
-/*
- * nfa_evaluate_row
- *
- * Evaluate all DEFINE variables for current row.
- * Returns true if the row exists, false if out of partition.
- * If row exists, fills varMatched array.
- * varMatched[i] = true if variable i matched at current row.
- */
-static bool
-nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched)
-{
- WindowAggState *winstate = winobj->winstate;
- ExprContext *econtext = winstate->ss.ps.ps_ExprContext;
- int numDefineVars = list_length(winstate->defineVariableList);
- ListCell *lc;
- int varIdx = 0;
- TupleTableSlot *slot;
-
- /*
- * 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_match_pattern.
- */
-
- /* Current row -> ecxt_outertuple */
- slot = winstate->temp_slot_1;
- if (!window_gettupleslot(winobj, pos, slot))
- return false; /* No row exists */
- econtext->ecxt_outertuple = slot;
-
- /* Previous row -> ecxt_scantuple (for PREV) */
- if (pos > 0)
- {
- slot = winstate->prev_slot;
- if (!window_gettupleslot(winobj, pos - 1, slot))
- econtext->ecxt_scantuple = winstate->null_slot;
- else
- econtext->ecxt_scantuple = slot;
- }
- else
- econtext->ecxt_scantuple = winstate->null_slot;
-
- /* Next row -> ecxt_innertuple (for NEXT) */
- slot = winstate->next_slot;
- if (!window_gettupleslot(winobj, pos + 1, slot))
- econtext->ecxt_innertuple = winstate->null_slot;
- else
- econtext->ecxt_innertuple = slot;
-
- foreach(lc, winstate->defineClauseList)
- {
- ExprState *exprState = (ExprState *) lfirst(lc);
- Datum result;
- bool isnull;
-
- /* Evaluate DEFINE expression */
- result = ExecEvalExpr(exprState, econtext, &isnull);
-
- varMatched[varIdx] = (!isnull && DatumGetBool(result));
-
- varIdx++;
- if (varIdx >= numDefineVars)
- break;
- }
-
- return true; /* Row exists */
-}
-
/*
* nfa_context_alloc
*
@@ -5216,6 +5271,11 @@ nfa_context_alloc(WindowAggState *winstate)
ctx->matchEndRow = -1;
ctx->lastProcessedRow = -1;
ctx->matchedState = NULL;
+ /* Initialize two-flag absorption design based on pattern */
+ ctx->hasAbsorbableState = (winstate->rpPattern != NULL &&
+ winstate->rpPattern->isAbsorbable);
+ ctx->allStatesAbsorbable = (winstate->rpPattern != NULL &&
+ winstate->rpPattern->isAbsorbable);
/* Update statistics */
winstate->nfaContextsActive++;
@@ -5279,17 +5339,50 @@ nfa_context_free(WindowAggState *winstate, RPRNFAContext *ctx)
* nfa_start_context
*
* Start a new match context at given position.
+ * Initializes context and state absorption flags.
* Adds context to winstate->nfaContext list and returns the new context.
*/
static RPRNFAContext *
nfa_start_context(WindowAggState *winstate, int64 startPos)
{
RPRNFAContext *ctx;
+ RPRPattern *pattern = winstate->rpPattern;
ctx = nfa_context_alloc(winstate);
ctx->matchStartRow = startPos;
ctx->states = nfa_state_alloc(winstate); /* initial state at elem 0 */
+ /*
+ * Initialize two-flag absorption design:
+ * hasAbsorbableState: can this context absorb others? (≥1 absorbable state)
+ * allStatesAbsorbable: can this context be absorbed? (ALL states absorbable)
+ * Both initialized from pattern->isAbsorbable at context start.
+ */
+ ctx->hasAbsorbableState = (pattern != NULL && pattern->isAbsorbable);
+ ctx->allStatesAbsorbable = (pattern != NULL && pattern->isAbsorbable);
+
+ if (ctx->states != NULL && pattern != NULL && pattern->numElements > 0)
+ {
+ RPRPatternElement *elem = &pattern->elements[0];
+
+ /*
+ * Initial state at element 0.
+ * Check if element 0 is in absorbable branch.
+ */
+ if (RPRElemIsAbsorbableBranch(elem))
+ {
+ /* Element 0 is in absorbable branch - flags stay true */
+ ctx->states->isAbsorbable = true;
+ }
+ else
+ {
+ /* Element 0 is NOT in absorbable branch - turn flags OFF */
+ 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;
@@ -5299,6 +5392,16 @@ nfa_start_context(WindowAggState *winstate, int64 startPos)
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.
+ *
+ * Pass initialAdvance=true to prevent recording zero-length matches
+ * when optional patterns can skip all VARs to reach FIN immediately.
+ */
+ nfa_advance(winstate, ctx, startPos, true);
+
return ctx;
}
@@ -5328,13 +5431,13 @@ nfa_find_context_for_pos(WindowAggState *winstate, int64 pos)
}
/*
- * update_nfa_length_stats
+ * nfa_update_length_stats
*
* Helper function to update min/max/total length statistics.
* Called when tracking match/mismatch/absorbed/skipped lengths.
*/
static void
-update_nfa_length_stats(int64 count, NFALengthStats *stats, int64 newLen)
+nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 newLen)
{
if (count == 1)
{
@@ -5352,14 +5455,14 @@ update_nfa_length_stats(int64 count, NFALengthStats *stats, int64 newLen)
}
/*
- * record_nfa_context_failure
+ * 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
-record_nfa_context_failure(WindowAggState *winstate, int64 failedLen)
+nfa_record_context_failure(WindowAggState *winstate, int64 failedLen)
{
if (failedLen == 1)
{
@@ -5368,12 +5471,80 @@ record_nfa_context_failure(WindowAggState *winstate, int64 failedLen)
else
{
winstate->nfaMatchesFailed++;
- update_nfa_length_stats(winstate->nfaMatchesFailed,
+ nfa_update_length_stats(winstate->nfaMatchesFailed,
&winstate->nfaFailLen,
failedLen);
}
}
+/*
+ * nfa_evaluate_row
+ *
+ * Evaluate all DEFINE variables for current row.
+ * Returns true if the row exists, false if out of partition.
+ * If row exists, fills varMatched array.
+ * varMatched[i] = true if variable i matched at current row.
+ */
+static bool
+nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched)
+{
+ WindowAggState *winstate = winobj->winstate;
+ ExprContext *econtext = winstate->ss.ps.ps_ExprContext;
+ int numDefineVars = list_length(winstate->defineVariableList);
+ ListCell *lc;
+ int varIdx = 0;
+ TupleTableSlot *slot;
+
+ /*
+ * 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.
+ */
+
+ /* Current row -> ecxt_outertuple */
+ slot = winstate->temp_slot_1;
+ if (!window_gettupleslot(winobj, pos, slot))
+ return false; /* No row exists */
+ econtext->ecxt_outertuple = slot;
+
+ /* Previous row -> ecxt_scantuple (for PREV) */
+ if (pos > 0)
+ {
+ slot = winstate->prev_slot;
+ if (!window_gettupleslot(winobj, pos - 1, slot))
+ econtext->ecxt_scantuple = winstate->null_slot;
+ else
+ econtext->ecxt_scantuple = slot;
+ }
+ else
+ econtext->ecxt_scantuple = winstate->null_slot;
+
+ /* Next row -> ecxt_innertuple (for NEXT) */
+ slot = winstate->next_slot;
+ if (!window_gettupleslot(winobj, pos + 1, slot))
+ econtext->ecxt_innertuple = winstate->null_slot;
+ else
+ econtext->ecxt_innertuple = slot;
+
+ foreach(lc, winstate->defineClauseList)
+ {
+ ExprState *exprState = (ExprState *) lfirst(lc);
+ Datum result;
+ bool isnull;
+
+ /* Evaluate DEFINE expression */
+ result = ExecEvalExpr(exprState, econtext, &isnull);
+
+ varMatched[varIdx] = (!isnull && DatumGetBool(result));
+
+ varIdx++;
+ if (varIdx >= numDefineVars)
+ break;
+ }
+
+ return true; /* Row exists */
+}
+
/*
* nfa_remove_contexts_up_to
*
@@ -5403,7 +5574,7 @@ nfa_remove_contexts_up_to(WindowAggState *winstate, int64 endPos,
int64 skippedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1;
winstate->nfaContextsSkipped++;
- update_nfa_length_stats(winstate->nfaContextsSkipped,
+ nfa_update_length_stats(winstate->nfaContextsSkipped,
&winstate->nfaSkippedLen,
skippedLen);
}
@@ -5445,7 +5616,7 @@ nfa_cleanup_dead_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx)
if (ctx->lastProcessedRow >= ctx->matchStartRow)
{
int64 failedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1;
- record_nfa_context_failure(winstate, failedLen);
+ nfa_record_context_failure(winstate, failedLen);
}
/* else: context was never processed (beyond-partition), just remove */
@@ -5454,573 +5625,713 @@ nfa_cleanup_dead_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx)
}
/*
- * nfa_absorb_contexts
+ * nfa_update_absorption_flags
*
- * Absorb newer contexts into older ones when states are fully covered.
- * For pattern like A+, if older context (started earlier) has count >= newer
- * context's count at the same element, the newer context produces subset matches.
+ * Update context's absorption flags after state changes.
*
- * Absorption condition:
- * - For unbounded quantifiers (max=INT32_MAX): older.counts >= newer.counts
- * - For bounded quantifiers: older.counts == newer.counts
+ * 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.
*
- * Note: List is oldest-first (head=oldest, tail=newest), so we start from
- * tail (newest) and check if older contexts (via prev) can absorb it.
+ * Optimization: Once hasAbsorbableState becomes false, both flags remain false
+ * permanently, so we skip recalculation.
*/
static void
-nfa_absorb_contexts(WindowAggState *winstate, RPRNFAContext *excludeCtx, int64 currentPos)
+nfa_update_absorption_flags(RPRNFAContext *ctx, RPRPattern *pattern)
{
- RPRPattern *pattern = winstate->rpPattern;
- RPRNFAContext *ctx;
+ RPRNFAState *state;
+ bool hasAbsorbable = false;
+ bool allAbsorbable = true;
- /* Need at least 2 contexts for absorption */
- if (winstate->nfaContext == NULL || winstate->nfaContext->next == NULL)
+ /*
+ * Optimization: Once hasAbsorbableState becomes false, it stays false.
+ * No need to recalculate - both flags remain false permanently.
+ */
+ if (!ctx->hasAbsorbableState)
+ {
+ ctx->allStatesAbsorbable = false;
return;
+ }
- if (pattern == NULL)
+ /* No states means no absorbable states */
+ if (ctx->states == NULL)
+ {
+ ctx->hasAbsorbableState = false;
+ ctx->allStatesAbsorbable = false;
return;
+ }
- /*
- * Only absorb for patterns marked as absorbable during planning.
- * See computeAbsorbability() in rpr.c for criteria.
- */
- if (!pattern->isAbsorbable)
+ if (pattern == NULL)
return;
/*
- * Context absorption: A later context (started at higher row) can be
- * absorbed by an earlier context if ALL states in the later context
- * are "covered" by states in the earlier context.
- *
- * A later state is covered by an earlier state if:
- * 1. They are at the same element
- * 2. For unbounded elements (max == INT32_MAX): earlier.counts[d] >= later.counts[d]
- * for all depths d
- * 3. For bounded elements: counts must be exactly equal at all depths
- *
- * List is oldest-first (head = lowest matchStartRow, tail = highest).
- * We iterate from tail (newest) via prev and check if older contexts can absorb it.
+ * 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.
*/
- ctx = winstate->nfaContextTail;
-
- while (ctx != NULL)
+ for (state = ctx->states; state != NULL; state = state->next)
{
- RPRNFAContext *nextCtx = ctx->prev; /* traverse toward older (head) */
- RPRNFAContext *older;
- bool absorbed = false;
+ if (state->isAbsorbable)
+ hasAbsorbable = true;
+ else
+ allAbsorbable = false;
+ }
- /* Never absorb the excluded context (it's the target being completed) */
- if (ctx == excludeCtx)
- {
- ctx = nextCtx;
- continue;
- }
+ ctx->hasAbsorbableState = hasAbsorbable;
+ ctx->allStatesAbsorbable = allAbsorbable;
+}
- /* Skip contexts that haven't started processing yet (just created for future row) */
- if (ctx->matchStartRow > currentPos)
- {
- ctx = nextCtx;
- continue;
- }
-
- /*
- * Handle completed contexts (states == NULL) separately.
- * A completed context can be absorbed by an older completed context
- * if the older one has the same or later matchEndRow.
- */
- if (ctx->states == NULL)
- {
- /* Only completed contexts with valid matchEndRow can be absorbed */
- if (ctx->matchEndRow < 0)
- {
- ctx = nextCtx;
- continue;
- }
-
- /* Check if any older completed context can absorb this one */
- for (older = ctx->prev; older != NULL && !absorbed; older = older->prev)
- {
- /* Must have started earlier */
- if (older->matchStartRow >= ctx->matchStartRow)
- continue;
-
- /* Older must also be completed with valid matchEndRow */
- if (older->states != NULL || older->matchEndRow < 0)
- continue;
+/*
+ * 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;
- /*
- * Older context absorbs newer if it has the same or later
- * matchEndRow, meaning all matches from newer are subsets.
- */
- if (older->matchEndRow >= ctx->matchEndRow)
- {
- /* Track absorbed context length statistics */
- int64 absorbedLen = ctx->matchEndRow - ctx->matchStartRow + 1;
-
- /* Absorb: remove ctx (newer) */
- nfa_context_free(winstate, ctx);
- winstate->nfaContextsAbsorbed++;
- update_nfa_length_stats(winstate->nfaContextsAbsorbed,
- &winstate->nfaAbsorbedLen,
- absorbedLen);
- absorbed = true;
- }
- }
+ for (newerState = newer->states; newerState != NULL; newerState = newerState->next)
+ {
+ RPRNFAState *olderState;
+ RPRPatternElement *elem;
+ int depth;
+ bool found = false;
- ctx = nextCtx;
- continue;
- }
+ /* All states are absorbable (caller checks allStatesAbsorbable) */
+ elem = &pattern->elements[newerState->elemIdx];
+ depth = elem->depth;
- /*
- * SIMPLIFIED ABSORPTION: Compare counts at depth 0 only.
- *
- * For absorbable patterns (A+ or (A B)+), we use a simple rule:
- * If older context has count[0] >= newer context's count[0] for
- * ANY state, older can absorb newer.
- *
- * This works because:
- * - A+: count[0] tracks how many A's matched
- * - (A B)+: count[0] tracks how many groups matched
- *
- * If older is ahead or equal, newer's future matches are subsets.
- */
- for (older = ctx->prev; older != NULL && !absorbed; older = older->prev)
+ for (olderState = older->states; olderState != NULL; olderState = olderState->next)
{
- int32 newerMaxCount = -1;
- int32 olderMaxCount = -1;
- RPRNFAState *s;
-
- /* Skip if not started earlier */
- if (older->matchStartRow >= ctx->matchStartRow)
- continue;
-
- /* Skip contexts that haven't started processing yet */
- if (older->matchStartRow > currentPos)
- continue;
-
- /* For in-progress ctx, older must also be in-progress */
- if (older->states == NULL)
- continue;
-
- /* Find maximum count[0] in newer context */
- for (s = ctx->states; s != NULL; s = s->next)
+ /* Covering state must also be absorbable */
+ if (olderState->isAbsorbable &&
+ olderState->elemIdx == newerState->elemIdx &&
+ olderState->counts[depth] >= newerState->counts[depth])
{
- if (s->counts[0] > newerMaxCount)
- newerMaxCount = s->counts[0];
- }
-
- /* Find maximum count[0] in older context */
- for (s = older->states; s != NULL; s = s->next)
- {
- if (s->counts[0] > olderMaxCount)
- olderMaxCount = s->counts[0];
- }
-
- /* If older is ahead or equal, absorb newer */
- if (olderMaxCount >= 0 && newerMaxCount >= 0 &&
- olderMaxCount >= newerMaxCount)
- {
- int64 absorbedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1;
-
- nfa_context_free(winstate, ctx);
- winstate->nfaContextsAbsorbed++;
- update_nfa_length_stats(winstate->nfaContextsAbsorbed,
- &winstate->nfaAbsorbedLen,
- absorbedLen);
- absorbed = true;
+ found = true;
+ break;
}
}
- ctx = nextCtx;
+ if (!found)
+ return false;
}
+
+ return true;
}
/*
- * nfa_step
+ * nfa_try_absorb_context
+ *
+ * Try to absorb ctx (newer) into an older in-progress context.
+ * Returns true if ctx was absorbed and freed.
*
- * Process all states in context through NFA for one row.
- * Calls nfa_step_single for each state.
+ * 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_step(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched, int64 pos)
+static bool
+nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx)
{
- RPRNFAState *states = ctx->states;
- RPRNFAState *state;
- RPRNFAState *nextState;
-
- ctx->states = NULL;
+ RPRPattern *pattern = winstate->rpPattern;
+ RPRNFAContext *older;
- /* Track last processed row for failed match statistics */
- if (pos > ctx->lastProcessedRow)
- ctx->lastProcessedRow = pos;
+ /* Early exit: ctx must have all states absorbable */
+ if (!ctx->allStatesAbsorbable)
+ return false;
- for (state = states; state != NULL; state = nextState)
+ for (older = ctx->prev; older != NULL; older = older->prev)
{
- nextState = state->next;
- state->next = NULL;
- nfa_step_single(winstate, ctx, state, varMatched, pos);
+ /*
+ * 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);
+ winstate->nfaContextsAbsorbed++;
+ nfa_update_length_stats(winstate->nfaContextsAbsorbed,
+ &winstate->nfaAbsorbedLen,
+ absorbedLen);
+ return true;
+ }
}
+
+ return false;
}
/*
- * nfa_finalize_all_contexts
+ * nfa_absorb_contexts
*
- * Finalize all active contexts when partition ends.
- * Calls nfa_step with NULL varMatched to complete without new row data.
+ * 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_finalize_all_contexts(WindowAggState *winstate, int64 lastPos)
+nfa_absorb_contexts(WindowAggState *winstate)
{
RPRNFAContext *ctx;
+ RPRNFAContext *nextCtx;
- for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next)
+ 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_step(winstate, ctx, NULL, lastPos);
+ nfa_try_absorb_context(winstate, ctx);
}
}
/*
- * nfa_process_context
+ * nfa_eval_var_match
*
- * Process one context for the current row.
- * Handles frame boundary check and NFA step.
+ * Evaluate if a VAR element matches the current row.
+ * Undefined variables (varId >= defineVariableList length) default to TRUE.
*/
-static void
-nfa_process_context(WindowAggState *winstate, RPRNFAContext *ctx,
- int64 currentPos, bool hasLimitedFrame, int64 frameOffset)
+static inline bool
+nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem,
+ bool *varMatched)
{
- /* Skip already-completed contexts */
- if (ctx->states == NULL)
- return;
-
- /* Check frame boundary */
- if (hasLimitedFrame)
- {
- int64 ctxFrameEnd = ctx->matchStartRow + frameOffset + 1;
- if (currentPos >= ctxFrameEnd)
- {
- nfa_step(winstate, ctx, NULL, ctxFrameEnd - 1);
- return;
- }
- }
-
- /* Process states for this context */
- nfa_step(winstate, ctx, winstate->nfaVarMatched, currentPos);
+ if (varMatched == NULL)
+ return false;
+ if (elem->varId >= list_length(winstate->defineVariableList))
+ return true;
+ return varMatched[elem->varId];
}
/*
- * nfa_step_single
+ * nfa_match
*
- * Process one state through NFA for one row.
- * New states are added to ctx->states.
- * Match (FIN) is recorded in ctx->matchedState.
- * When FIN is reached by matching (not skipping), matchEndRow is updated.
+ * 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_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
- RPRNFAState *state, bool *varMatched, int64 currentPos)
+nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched)
{
RPRPattern *pattern = winstate->rpPattern;
RPRPatternElement *elements = pattern->elements;
- RPRNFAState *pending = state; /* states to process in current row */
- RPRNFAState *pending_tail = state; /* tail for FIFO append */
+ RPRNFAState **prevPtr = &ctx->states;
+ RPRNFAState *state;
- while (pending != NULL)
+ /*
+ * 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; )
{
- RPRPatternElement *elem;
- bool matched;
- int32 count;
- int depth;
-
- /* Pop from head */
- state = pending;
- pending = pending->next;
- if (pending == NULL)
- pending_tail = NULL;
- state->next = NULL;
-
- Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements);
- elem = &elements[state->elemIdx];
- depth = elem->depth;
+ RPRNFAState *nextState = state->next;
+ RPRPatternElement *elem = &elements[state->elemIdx];
if (RPRElemIsVar(elem))
{
- /*
- * Variable: check if it matches current row.
- * If varMatched is NULL (boundary), all variables are forced to false.
- * Otherwise, varId < numDefines uses DEFINE expr,
- * varId >= numDefines defaults to TRUE.
- */
- if (varMatched == NULL)
- matched = false;
- else
- {
- int numDefines = list_length(winstate->defineVariableList);
-
- if (elem->varId >= numDefines)
- matched = true; /* Not defined in DEFINE, defaults to TRUE */
- else
- matched = varMatched[elem->varId];
- }
+ bool matched;
+ int depth = elem->depth;
+ int32 count = state->counts[depth];
- count = state->counts[depth];
+ matched = nfa_eval_var_match(winstate, elem, varMatched);
if (matched)
{
- /*
- * Clamp count to prevent overflow with very large partitions.
- * Once count reaches RPR_COUNT_MAX, we stop incrementing.
- * This is safe because for unbounded quantifiers, only the
- * comparison with min matters, and for bounded quantifiers,
- * max is always < RPR_COUNT_MAX.
- */
+ /* Increment count */
if (count < RPR_COUNT_MAX)
count++;
+ /* Check max constraint */
if (elem->max != RPR_QUANTITY_INF && count > elem->max)
{
+ /* Exceeded max - remove state */
+ *prevPtr = nextState;
nfa_state_free(winstate, state);
+ state = nextState;
continue;
}
state->counts[depth] = count;
- /* Can repeat more? Clone for staying */
- if (elem->max == RPR_QUANTITY_INF || count < elem->max)
- {
- RPRNFAState *clone = nfa_state_clone(winstate, state->elemIdx,
- state->altPriority,
- state->counts);
- nfa_add_state_unique(winstate, ctx, clone);
- }
-
- /* Satisfied? Advance to next element */
- if (count >= elem->min)
+ /*
+ * 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 && count == 1 &&
+ RPRElemIsEnd(&elements[elem->next]))
{
- RPRPatternElement *nextElem;
+ RPRPatternElement *endElem = &elements[elem->next];
+ int endDepth = endElem->depth;
+ int32 endCount = state->counts[endDepth];
- state->counts[depth] = 0;
- state->elemIdx = elem->next;
- nextElem = &elements[state->elemIdx];
+ /* Increment group count with overflow protection */
+ if (endCount < RPR_COUNT_MAX)
+ endCount++;
- if (RPRElemIsFin(nextElem))
- {
- /* Match ends at current row since we matched */
- nfa_add_matched_state(winstate, ctx, state, currentPos);
- }
- else if (RPRElemIsEnd(nextElem))
+ /* Check END's max constraint */
+ if (endElem->max != RPR_QUANTITY_INF && endCount > endElem->max)
{
- /*
- * END is epsilon transition - process immediately on same row.
- * This ensures match end position is recorded at the row where
- * the last VAR matched, not the next row.
- */
- state->next = NULL;
- if (pending_tail)
- pending_tail->next = state;
- else
- pending = state;
- pending_tail = state;
- }
- else
- {
- /*
- * VAR, ALT - wait for next row. ALT dispatches to VARs that
- * need input, so it must wait for the next row after VAR
- * consumed the current row.
- */
- nfa_add_state_unique(winstate, ctx, state);
+ /* Exceeded END's max - remove state */
+ *prevPtr = nextState;
+ nfa_state_free(winstate, state);
+ state = nextState;
+ continue;
}
+
+ state->elemIdx = elem->next;
+ state->counts[endDepth] = endCount;
+
+ /* Clear deeper counts */
+ for (int d = endDepth + 1; d < pattern->maxDepth; d++)
+ state->counts[d] = 0;
}
- else
- {
- nfa_state_free(winstate, state);
- }
+ /* else: stay at VAR for advance phase */
}
else
{
- /* Not matched: can we skip? */
- if (count >= elem->min)
- {
- RPRPatternElement *nextElem;
+ /*
+ * Not matched - remove state.
+ * Exit alternatives were already created by advance phase
+ * when count >= min was satisfied.
+ */
+ *prevPtr = nextState;
+ nfa_state_free(winstate, state);
+ state = nextState;
+ continue;
+ }
+ }
+ /* Non-VAR elements: keep as-is for advance phase */
- state->counts[depth] = 0;
- state->elemIdx = elem->next;
- nextElem = &elements[state->elemIdx];
+ prevPtr = &state->next;
+ state = nextState;
+ }
+}
- if (RPRElemIsFin(nextElem))
- {
- /* Match ends at previous row since current didn't match */
- nfa_add_matched_state(winstate, ctx, state, currentPos - 1);
- }
- else if (RPRElemIsVar(nextElem))
- {
- /*
- * Current row was NOT consumed (skip case), so next VAR
- * must be tried on the SAME row via pending list
- */
- state->next = NULL;
- if (pending_tail)
- pending_tail->next = state;
- else
- pending = state;
- pending_tail = state;
- }
- else
- {
- state->next = NULL;
- if (pending_tail)
- pending_tail->next = state;
- else
- pending = state;
- pending_tail = state;
- }
- }
- else
- {
- nfa_state_free(winstate, state);
- }
- }
+/*
+ * 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, bool initialAdvance)
+{
+ if (RPRElemIsVar(nextElem))
+ {
+ nfa_add_state_unique(winstate, ctx, state);
+ if (RPRElemCanSkip(nextElem))
+ {
+ RPRNFAState *skipState;
+ skipState = nfa_state_clone(winstate, nextElem->next,
+ state->altPriority, state->counts,
+ state->isAbsorbable);
+ nfa_advance_state(winstate, ctx, skipState, currentPos, initialAdvance);
}
- else if (RPRElemIsFin(elem))
+ }
+ else
+ {
+ nfa_advance_state(winstate, ctx, state, currentPos, initialAdvance);
+ }
+}
+
+/*
+ * nfa_advance_alt
+ *
+ * Handle ALT element: expand all branches in lexical order (DFS).
+ * Sets altPriority to element index to preserve lexical order for match selection.
+ */
+static void
+nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, RPRPatternElement *elem,
+ int64 currentPos, bool initialAdvance)
+{
+ RPRPattern *pattern = winstate->rpPattern;
+ RPRPatternElement *elements = pattern->elements;
+ RPRElemIdx altIdx = elem->next;
+ bool first = true;
+
+ while (altIdx >= 0 && altIdx < pattern->numElements)
+ {
+ RPRPatternElement *altElem = &elements[altIdx];
+ RPRNFAState *newState;
+
+ if (first)
{
- /* Already at FIN - match ends at current row */
- nfa_add_matched_state(winstate, ctx, state, currentPos);
+ state->elemIdx = altIdx;
+ state->altPriority = altIdx;
+ newState = state;
+ first = false;
}
- else if (RPRElemIsAlt(elem))
+ else
{
- RPRElemIdx altIdx = elem->next;
- bool first = true;
+ newState = nfa_state_clone(winstate, altIdx, altIdx,
+ state->counts, state->isAbsorbable);
+ }
- /*
- * ALT doesn't consume a row - it's just a dispatch point.
- * All branches should be evaluated on the CURRENT row.
- * Set altPriority to branch's elemIdx for lexical order tracking.
- * Append to pending_tail to maintain lexical order.
- */
- while (altIdx >= 0 && altIdx < pattern->numElements)
- {
- RPRPatternElement *altElem = &elements[altIdx];
- RPRNFAState *newState;
+ /* Recursively process this branch before next */
+ nfa_advance_state(winstate, ctx, newState, currentPos, initialAdvance);
+ altIdx = altElem->jump;
+ }
- if (first)
- {
- state->elemIdx = altIdx;
- state->altPriority = altIdx;
- newState = state;
- first = false;
- }
- else
- {
- newState = nfa_state_clone(winstate, altIdx, altIdx,
- state->counts);
- }
+ if (first)
+ nfa_state_free(winstate, state);
+}
- /* Append to tail for lexical order */
- newState->next = NULL;
- if (pending_tail)
- pending_tail->next = newState;
- else
- pending = newState;
- pending_tail = newState;
+/*
+ * 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, bool initialAdvance)
+{
+ RPRPattern *pattern = winstate->rpPattern;
+ RPRPatternElement *elements = pattern->elements;
+ int depth = elem->depth;
+ int32 count = state->counts[depth];
- altIdx = altElem->jump;
- }
+ if (count < elem->min)
+ {
+ /* Must loop back */
+ RPRPatternElement *jumpElem;
- if (first)
- nfa_state_free(winstate, state);
- }
- else if (RPRElemIsEnd(elem))
- {
- count = state->counts[depth] + 1;
+ for (int d = depth + 1; d < pattern->maxDepth; d++)
+ state->counts[d] = 0;
+ state->elemIdx = elem->jump;
+ jumpElem = &elements[state->elemIdx];
- if (count < elem->min)
- {
- /*
- * Haven't reached minimum yet - must loop back.
- * Add to ctx->states (next row) not pending (same row).
- */
- state->counts[depth] = count;
- for (int d = depth + 1; d < pattern->maxDepth; d++)
- state->counts[d] = 0;
- state->elemIdx = elem->jump;
- nfa_add_state_unique(winstate, ctx, state);
- }
- else if (elem->max != RPR_QUANTITY_INF && count >= elem->max)
- {
- /* Reached maximum - must exit, continue processing */
- state->counts[depth] = 0;
- state->elemIdx = elem->next;
- state->next = NULL;
- if (pending_tail)
- pending_tail->next = state;
- else
- pending = state;
- pending_tail = state;
- }
+ nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos, initialAdvance);
+ }
+ else if (elem->max != RPR_QUANTITY_INF && count >= elem->max)
+ {
+ /* Must exit */
+ 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, initialAdvance);
+ }
+ else
+ {
+ /* Between min and max - can exit or loop */
+ RPRElemIdx exitAltPriority;
+ RPRNFAState *exitState;
+ RPRPatternElement *jumpElem;
+ RPRPatternElement *nextElem;
+
+ /* Preserve altPriority for greedy extension */
+ exitAltPriority = state->altPriority;
+ if (ctx->matchedState != NULL)
+ exitAltPriority = ctx->matchedState->altPriority;
+
+ /* Create exit state first (need original counts before modifying state) */
+ exitState = nfa_state_clone(winstate, elem->next, exitAltPriority,
+ 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]++;
+
+ /* Route loop state first (earlier in pattern = lexical order) */
+ state->counts[depth] = count;
+ 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, initialAdvance);
+
+ /* Then route exit state */
+ nfa_route_to_elem(winstate, ctx, exitState, nextElem, currentPos, initialAdvance);
+ }
+}
+
+/*
+ * 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, bool initialAdvance)
+{
+ 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);
+
+ if (canLoop && canExit)
+ {
+ /* Both: clone for loop, modify original for exit */
+ RPRNFAState *loopState;
+ RPRPatternElement *nextElem;
+
+ loopState = nfa_state_clone(winstate, state->elemIdx, state->altPriority,
+ state->counts, state->isAbsorbable);
+ nfa_add_state_unique(winstate, ctx, loopState);
+
+ /* Exit: advance to next element */
+ state->counts[depth] = 0;
+ state->elemIdx = elem->next;
+ nextElem = &elements[state->elemIdx];
+
+ nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos, initialAdvance);
+ }
+ else if (canLoop)
+ {
+ /* Loop only: keep state as-is */
+ nfa_add_state_unique(winstate, ctx, state);
+ }
+ else if (canExit)
+ {
+ /* Exit only: modify state */
+ RPRPatternElement *nextElem;
+
+ state->counts[depth] = 0;
+ state->elemIdx = elem->next;
+ nextElem = &elements[state->elemIdx];
+
+ nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos, initialAdvance);
+ }
+ else
+ {
+ /* Neither - shouldn't happen, free state */
+ nfa_state_free(winstate, state);
+ }
+}
+
+/*
+ * nfa_advance_state
+ *
+ * Recursively process a single state through epsilon transitions.
+ * Uses DFS traversal to maintain lexical order: lower altPriority paths
+ * are fully processed before higher altPriority paths, ensuring states
+ * are added to ctx->states in lexical order.
+ */
+static void
+nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx,
+ RPRNFAState *state, int64 currentPos, bool initialAdvance)
+{
+ RPRPattern *pattern = winstate->rpPattern;
+ RPRPatternElement *elem;
+
+ Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements);
+ elem = &pattern->elements[state->elemIdx];
+
+ switch (elem->varId)
+ {
+ case RPR_VARID_FIN:
+ /* FIN: record match (skip for initial advance) */
+ if (!initialAdvance)
+ nfa_add_matched_state(winstate, ctx, state, currentPos);
else
- {
- /*
- * Between min and max - can exit or continue.
- * Exit state handling depends on what comes next:
- * - If next is FIN: process on same row (match ends here)
- * - If next is VAR/ALT: wait for next row (needs new input)
- * Loop state always waits for next row.
- */
- RPRPatternElement *nextElem = &elements[elem->next];
- RPRElemIdx exitAltPriority;
- RPRNFAState *exitState;
+ nfa_state_free(winstate, state);
+ break;
- /*
- * For greedy extension: if context already has a match recorded,
- * preserve its altPriority. This ensures that iterations of a
- * quantified group don't compete on lexical order - the first
- * iteration's choice sets the preference, and subsequent
- * iterations can extend it if they produce a longer match.
- */
- exitAltPriority = state->altPriority;
- if (ctx->matchedState != NULL)
- exitAltPriority = ctx->matchedState->altPriority;
+ case RPR_VARID_ALT:
+ nfa_advance_alt(winstate, ctx, state, elem, currentPos, initialAdvance);
+ break;
- exitState = nfa_state_clone(winstate, elem->next,
- exitAltPriority,
- state->counts);
- exitState->counts[depth] = 0;
+ case RPR_VARID_END:
+ nfa_advance_end(winstate, ctx, state, elem, currentPos, initialAdvance);
+ break;
- if (RPRElemIsFin(nextElem))
- {
- /* Match ends at current row - append to pending */
- exitState->next = NULL;
- if (pending_tail)
- pending_tail->next = exitState;
- else
- pending = exitState;
- pending_tail = exitState;
- }
- else
- {
- /* Next element (VAR/ALT) needs new row input */
- nfa_add_state_unique(winstate, ctx, exitState);
- }
+ default:
+ /* VAR element */
+ nfa_advance_var(winstate, ctx, state, elem, currentPos, initialAdvance);
+ break;
+ }
+}
- state->counts[depth] = count;
- for (int d = depth + 1; d < pattern->maxDepth; d++)
- state->counts[d] = 0;
- state->elemIdx = elem->jump;
- nfa_add_state_unique(winstate, ctx, state);
+/*
+ * 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 (initialAdvance=true skips FIN matches).
+ *
+ * Processes states in order, using recursive DFS to maintain lexical order.
+ */
+static void
+nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos,
+ bool initialAdvance)
+{
+ RPRNFAState *states = ctx->states;
+ RPRNFAState *state;
+
+ ctx->states = NULL; /* Will rebuild */
+
+ /* Process each state in order */
+ while (states != NULL)
+ {
+ state = states;
+ states = states->next;
+ state->next = NULL;
+
+ nfa_advance_state(winstate, ctx, state, currentPos, initialAdvance);
+ }
+}
+
+/*
+ * nfa_process_row
+ *
+ * Process all contexts for one row using the new flow:
+ * 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: match with NULL (force mismatch), then advance */
+ nfa_match(winstate, ctx, NULL);
+ nfa_advance(winstate, ctx, ctxFrameEnd - 1, false);
+ continue;
}
}
- else
+
+ 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)
+ {
+ RPRPattern *pattern = winstate->rpPattern;
+
+ for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next)
+ nfa_update_absorption_flags(ctx, pattern);
+
+ 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;
+
+ /* Skip contexts already finalized in phase 1 */
+ if (hasLimitedFrame)
{
- state->elemIdx = elem->next;
- state->next = NULL;
- if (pending_tail)
- pending_tail->next = state;
- else
- pending = state;
- pending_tail = state;
+ int64 ctxFrameEnd = ctx->matchStartRow + frameOffset + 1;
+ if (currentPos >= ctxFrameEnd)
+ continue;
}
+
+ nfa_advance(winstate, ctx, currentPos, false);
}
}
+/*
+ * 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;
+
+ for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next)
+ {
+ if (ctx->states != NULL)
+ {
+ nfa_match(winstate, ctx, NULL);
+ nfa_advance(winstate, ctx, lastPos, false);
+ }
+ }
+}
diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c
index 99180ba339e..00dbcaed72c 100644
--- a/src/backend/optimizer/plan/createplan.c
+++ b/src/backend/optimizer/plan/createplan.c
@@ -2556,7 +2556,7 @@ create_windowagg_plan(PlannerInfo *root, WindowAggPath *best_path)
ordCollations,
best_path->runCondition,
wc->rpSkipTo,
- buildRPRPattern(wc->rpPattern, defineVariableList),
+ buildRPRPattern(wc->rpPattern, defineVariableList, wc->rpSkipTo, wc->frameOptions),
wc->defineClause,
best_path->qual,
best_path->topwindow,
diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c
index 9b847c5e8b1..6883bc5466d 100644
--- a/src/backend/optimizer/plan/rpr.c
+++ b/src/backend/optimizer/plan/rpr.c
@@ -6,6 +6,25 @@
* This file contains functions for optimizing RPR pattern AST and
* compiling it to bytecode for execution by WindowAgg.
*
+ * Key components:
+ * 1. Pattern Optimization: Simplifies patterns before compilation
+ * (e.g., flatten nested SEQ/ALT, merge consecutive vars)
+ * 2. Pattern Compilation: Converts AST to flat element array for NFA
+ * 3. Absorption Analysis: Computes flags for O(n^2)->O(n) optimization
+ *
+ * Context Absorption Optimization:
+ * When a pattern starts with an unbounded element (e.g., A+ or (A B)+),
+ * newer contexts cannot produce longer matches than older contexts.
+ * By absorbing (eliminating) redundant newer contexts, we reduce
+ * complexity from O(n^2) to O(n) for patterns like A+ B.
+ *
+ * The absorption analysis uses two element flags:
+ * - RPR_ELEM_ABSORBABLE: marks WHERE to compare (judgment point)
+ * - RPR_ELEM_ABSORBABLE_BRANCH: marks the absorbable region
+ *
+ * See computeAbsorbability() and the detailed comments before
+ * isUnboundedStart() for the full design explanation.
+ *
* Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
*
@@ -1124,14 +1143,13 @@ finalizeRPRPattern(RPRPattern *result)
int i;
RPRPatternElement *finElem;
- /* Set up next pointers for elements that don't have one yet */
+ /* Set up next pointers for elements that don't have one */
for (i = 0; i < finIdx; i++)
{
- if (result->elements[i].next == RPR_ELEMIDX_INVALID)
- {
- /* Point to next element, or to FIN if this is the last */
- result->elements[i].next = (i < finIdx - 1) ? i + 1 : finIdx;
- }
+ RPRPatternElement *elem = &result->elements[i];
+
+ if (elem->next == RPR_ELEMIDX_INVALID)
+ elem->next = (i < finIdx - 1) ? i + 1 : finIdx;
}
/* Add FIN marker at the end */
@@ -1145,6 +1163,87 @@ finalizeRPRPattern(RPRPattern *result)
finElem->jump = RPR_ELEMIDX_INVALID;
}
+/*-------------------------------------------------------------------------
+ * CONTEXT ABSORPTION: TWO-FLAG DESIGN
+ *-------------------------------------------------------------------------
+ *
+ * Context absorption eliminates redundant match searches by absorbing newer
+ * contexts that cannot produce longer matches than older contexts. This
+ * achieves O(n^2) -> O(n) performance improvement for patterns like A+ B.
+ *
+ * Core Insight:
+ * For pattern A+ B, if Ctx1 starts at row 0 and Ctx2 starts at row 1,
+ * both matching A continuously, Ctx1 will always have more A matches.
+ * When B finally appears, Ctx1's match (0 to current) is always longer
+ * than Ctx2's match (1 to current). So Ctx2 can be safely eliminated.
+ *
+ * Two Flags:
+ * 1. RPR_ELEM_ABSORBABLE - "Absorption judgment point"
+ * WHERE contexts can be compared for absorption.
+ * - Simple unbounded VAR (A+): the VAR element itself
+ * - Unbounded GROUP ((A B)+): the END element only
+ *
+ * 2. RPR_ELEM_ABSORBABLE_BRANCH - "Absorbable region marker"
+ * ALL elements within the absorbable region.
+ * - Used for tracking state.isAbsorbable at runtime
+ * - States leaving this region become non-absorbable permanently
+ *
+ * Why Two Flags?
+ * For pattern "(A B)+", contexts at different positions (one at A,
+ * another at B) cannot be compared - they must synchronize at END.
+ *
+ * Example: "(A B)+" with input A B A B A B...
+ * Row 0 (A): Ctx1 starts, matches A
+ * Row 1 (B): Ctx1 matches B -> END (count=1)
+ * Row 2 (A): Ctx1 loops to A, Ctx2 starts at A
+ * Row 3 (B): Ctx1 at END (count=2), Ctx2 at END (count=1)
+ * -> Both at END, comparable! Ctx1 absorbs Ctx2.
+ *
+ * Contexts synchronize at END every group-length rows. Therefore:
+ * - ABSORBABLE marks END as judgment point (where to compare)
+ * - ABSORBABLE_BRANCH keeps state.isAbsorbable=true through A->B->END
+ *
+ * Pattern Examples:
+ *
+ * Pattern: A+ B
+ * Element 0 (A): ABSORBABLE | ABSORBABLE_BRANCH <- judgment point
+ * Element 1 (B): (none)
+ * -> Compare at A every row. When contexts move to B, absorption stops.
+ *
+ * Pattern: (A B)+ C
+ * Element 0 (A): ABSORBABLE_BRANCH
+ * Element 1 (B): ABSORBABLE_BRANCH
+ * Element 2 (END): ABSORBABLE | ABSORBABLE_BRANCH <- judgment point
+ * Element 3 (C): (none)
+ * -> Compare at END every 2 rows. When contexts move to C, absorption stops.
+ *
+ * Pattern: (A+ B+)+ C
+ * Element 0 (A): ABSORBABLE | ABSORBABLE_BRANCH <- only first A+ flagged
+ * Element 1 (B): (none)
+ * Element 2 (END): (none)
+ * Element 3 (C): (none)
+ * -> Only first unbounded portion (A+) gets flags. Absorption happens
+ * at A during first iteration. After moving to B+, absorption stops.
+ *
+ * First Unbounded Portion Strategy:
+ * The algorithm only flags the FIRST unbounded portion starting from
+ * element 0. This is sufficient because:
+ * - Absorption in first portion already achieves O(n) complexity
+ * - Later portions have different synchronization characteristics
+ * - Nested unbounded patterns are too complex for simple absorption
+ * - Complex patterns (nested groups, etc.) naturally die from mismatch
+ *
+ * Runtime Usage (in nodeWindowAgg.c):
+ * - state.isAbsorbable = (previous && elem.ABSORBABLE_BRANCH)
+ * - Monotonic: once false, stays false (cannot re-enter region)
+ * - context.hasAbsorbableState: can absorb others (>=1 absorbable state)
+ * - context.allStatesAbsorbable: can be absorbed (ALL states absorbable)
+ * - Absorption check: if Ctx1.hasAbsorbable && Ctx2.allAbsorbable,
+ * compare counts at same elemIdx, absorb if Ctx1.count >= Ctx2.count
+ *
+ *-------------------------------------------------------------------------
+ */
+
/*
* isUnboundedStart
* Check if the element at idx starts an unbounded sequence.
@@ -1152,6 +1251,11 @@ finalizeRPRPattern(RPRPattern *result)
* For context absorption to work, the sequence starting at idx must be
* unbounded (max = infinity) so that we can "shift" by decrementing count.
*
+ * Algorithm:
+ * - Descend through ALT/GROUP structures to find first actual VAR
+ * - For GROUP: must be unbounded AND contain only simple {1,1} VARs
+ * - Check if that VAR is unbounded
+ *
* Two cases are handled:
* 1. Simple var: A+ B C - first element A has max=INF
* 2. Group: (A B){2,} C - group END has max=INF, and all elements
@@ -1180,7 +1284,7 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
e = &pattern->elements[i];
/* Exit when depth drops (left the group) or reached FIN */
- if (e->depth < startDepth || e->varId == RPR_VARID_FIN)
+ if (e->depth < startDepth || RPRElemIsFin(e))
{
lastElem = e;
break;
@@ -1202,7 +1306,7 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
Assert(lastElem != NULL);
/* Case 2: Unbounded group - END element points back to idx */
- if (lastElem->varId == RPR_VARID_END &&
+ if (RPRElemIsEnd(lastElem) &&
lastElem->jump == idx &&
lastElem->max == RPR_QUANTITY_INF)
{
@@ -1219,9 +1323,9 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
{
RPRPatternElement *e = &pattern->elements[j];
- if (e->varId == RPR_VARID_FIN)
+ if (RPRElemIsFin(e))
break; /* Reached end, no outer nesting */
- if (e->varId == RPR_VARID_END && e->depth < lastElem->depth)
+ if (RPRElemIsEnd(e) && e->depth < lastElem->depth)
return false; /* Found outer END, nested structure */
}
@@ -1232,24 +1336,99 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
return RPRElemIsVar(elem) && elem->max == RPR_QUANTITY_INF;
}
+/*
+ * setAbsorbabilityFlagsForBranch
+ * Set absorption flags for a single branch.
+ *
+ * For unbounded GROUP (e.g., (A B)+):
+ * - ABSORBABLE_BRANCH on all elements (A, B, END)
+ * - ABSORBABLE on END only (judgment point)
+ *
+ * For simple unbounded VAR (e.g., A+):
+ * - Both flags on first element only
+ */
+static void
+setAbsorbabilityFlagsForBranch(RPRPattern *pattern, RPRElemIdx branchIdx)
+{
+ RPRPatternElement *branchFirst = &pattern->elements[branchIdx];
+ RPRDepth startDepth = branchFirst->depth;
+ bool isUnboundedGroup = false;
+ RPRElemIdx endIdx = RPR_ELEMIDX_INVALID;
+ RPRElemIdx i;
+
+ /*
+ * First pass: detect if this is an unbounded GROUP pattern.
+ * Look for END element with unbounded max that jumps back to branch start.
+ * Note: END is at parent depth (less than content depth), so check END
+ * before the depth-based break condition.
+ */
+ for (i = branchIdx; i < pattern->numElements; i++)
+ {
+ RPRPatternElement *e = &pattern->elements[i];
+
+ /* Check for unbounded END first (END is at lower depth than content) */
+ if (RPRElemIsEnd(e) &&
+ e->jump == branchIdx &&
+ e->max == RPR_QUANTITY_INF)
+ {
+ isUnboundedGroup = true;
+ endIdx = i;
+ break;
+ }
+
+ if (e->depth < startDepth || RPRElemIsFin(e))
+ break;
+ }
+
+ /*
+ * Set flags based on pattern type.
+ */
+ if (isUnboundedGroup)
+ {
+ /*
+ * Unbounded GROUP: set ABSORBABLE_BRANCH on all elements from
+ * branchIdx to endIdx, and ABSORBABLE on END only.
+ */
+ for (i = branchIdx; i <= endIdx; i++)
+ {
+ RPRPatternElement *e = &pattern->elements[i];
+
+ e->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
+ if (i == endIdx)
+ e->flags |= RPR_ELEM_ABSORBABLE;
+ }
+ }
+ else
+ {
+ /*
+ * Simple unbounded VAR: set both flags on first element only.
+ */
+ branchFirst->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE;
+ }
+}
+
/*
* computeAbsorbability
* Determine if pattern supports context absorption optimization.
*
- * Context absorption allows the executor to reuse NFA match states from
- * previous row positions. When a match at position P can be "shifted" to
- * position P+1 by decrementing the count of the first unbounded element,
- * we avoid re-running the NFA from scratch.
+ * Context absorption eliminates redundant match searches by absorbing
+ * newer contexts that cannot produce longer matches than older contexts.
+ * This achieves O(n²) → O(n) performance improvement.
*
- * This function sets RPR_ELEM_ABSORBABLE on elements that can be shifted,
- * and pattern->isAbsorbable if any element is absorbable.
+ * This function sets two flags:
+ * RPR_ELEM_ABSORBABLE: Absorption judgment point
+ * - Simple unbounded VAR: the VAR itself (e.g., A in A+)
+ * - Unbounded GROUP: the END element (e.g., END in (A B)+)
+ * RPR_ELEM_ABSORBABLE_BRANCH: All elements in absorbable region
+ * - All elements at same depth as unbounded start
*
* Examples:
- * A+ B C - absorbable (unbounded var at start)
- * (A B){2,} C - absorbable (unbounded group)
- * A B+ - NOT absorbable (unbounded not at start)
- * A+ | B+ C - both branches absorbable (checked independently)
- * A+ B | C D - first branch only
+ * A+ B C - absorbable (A gets both flags)
+ * (A B)+ C - absorbable (A,B,END get BRANCH, END gets ABSORBABLE)
+ * A B+ - NOT absorbable (unbounded not at start)
+ * (A+ B+)+ - only first A+ on first iteration (nested unbounded not supported)
+ * A+ | B+ - both branches absorbable independently
+ * A+ | C D - only A+ branch absorbable (C D branch not absorbable)
*/
static void
computeAbsorbability(RPRPattern *pattern)
@@ -1261,10 +1440,11 @@ computeAbsorbability(RPRPattern *pattern)
if (pattern->numElements < 2) /* At minimum: one element + FIN */
return;
- if (first->varId == RPR_VARID_ALT)
+ if (RPRElemIsAlt(first))
{
/* ALT: check each branch */
RPRElemIdx branchIdx = first->next;
+ bool hasAbsorbableBranch = false;
while (branchIdx != RPR_ELEMIDX_INVALID &&
branchIdx < pattern->numElements - 1)
@@ -1273,20 +1453,28 @@ computeAbsorbability(RPRPattern *pattern)
if (isUnboundedStart(pattern, branchIdx))
{
- branchFirst->flags |= RPR_ELEM_ABSORBABLE;
pattern->isAbsorbable = true;
+ hasAbsorbableBranch = true;
+ setAbsorbabilityFlagsForBranch(pattern, branchIdx);
}
branchIdx = branchFirst->jump;
}
+
+ /*
+ * If any branch is absorbable, mark ALT element too.
+ * This allows efficient branch-level flag management.
+ */
+ if (hasAbsorbableBranch)
+ first->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
}
else
{
/* Non-ALT: check first element */
if (isUnboundedStart(pattern, 0))
{
- first->flags |= RPR_ELEM_ABSORBABLE;
pattern->isAbsorbable = true;
+ setAbsorbabilityFlagsForBranch(pattern, 0);
}
}
}
@@ -1307,7 +1495,8 @@ computeAbsorbability(RPRPattern *pattern)
* Returns NULL if pattern is NULL.
*/
RPRPattern *
-buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList)
+buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList,
+ RPSkipTo rpSkipTo, int frameOptions)
{
RPRPattern *result;
RPRPatternNode *optimized;
@@ -1316,6 +1505,7 @@ buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList)
int numElements;
RPRDepth maxDepth;
int idx;
+ bool hasLimitedFrame;
if (pattern == NULL)
return NULL;
@@ -1336,11 +1526,28 @@ buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList)
idx = 0;
fillRPRPattern(optimized, result, &idx, 0);
- /* Finalize: set up next pointers and add FIN marker */
+ /* Finalize: set up next pointers, flags, and add FIN marker */
finalizeRPRPattern(result);
- /* Compute context absorption eligibility */
- computeAbsorbability(result);
+ /*
+ * Compute context absorption eligibility.
+ * Absorption requires both structural absorbability and runtime conditions.
+ * Check runtime conditions first to avoid unnecessary pattern analysis.
+ */
+ hasLimitedFrame = (frameOptions & FRAMEOPTION_ROWS) &&
+ !(frameOptions & FRAMEOPTION_END_UNBOUNDED_FOLLOWING);
+
+ if (rpSkipTo == ST_PAST_LAST_ROW && !hasLimitedFrame)
+ {
+ /* Runtime conditions met - check structural absorbability */
+ computeAbsorbability(result);
+ }
+ else
+ {
+ /* Runtime conditions not met - skip pattern analysis */
+ result->isAbsorbable = false;
+ }
return result;
}
+
diff --git a/src/backend/parser/gram.y b/src/backend/parser/gram.y
index 984316d9a61..a0fbdb196d4 100644
--- a/src/backend/parser/gram.y
+++ b/src/backend/parser/gram.y
@@ -20324,6 +20324,11 @@ makeRPRQuantifier(int min, int max, bool reluctant)
{
RPRPatternNode *n = makeNode(RPRPatternNode);
+ if (reluctant)
+ ereport(ERROR,
+ (errcode(ERRCODE_FEATURE_NOT_SUPPORTED),
+ errmsg("reluctant quantifiers are not yet supported")));
+
n->min = min;
n->max = max;
n->reluctant = reluctant;
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index a25d7642d3a..8bc51e3750b 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2523,17 +2523,34 @@ typedef enum WindowAggStatus
*
* counts[] tracks repetition counts at each nesting depth.
* altPriority tracks lexical order for alternation (lower = earlier alternative).
+ *
+ * isAbsorbable tracks if state is in absorbable region (ABSORBABLE_BRANCH).
+ * Monotonic property: once false, stays false (can't re-enter region).
+ *
+ * Absorption comparison uses elemIdx and counts[depth] directly because:
+ * - VAR elements consume a row, forcing states to wait for next row
+ * - END loop puts states at group start with iteration count preserved
+ * - At row end, comparable states are at the same position (elemIdx)
*/
typedef struct RPRNFAState
{
struct RPRNFAState *next; /* next state in linked list */
int16 elemIdx; /* current pattern element index */
int16 altPriority; /* lexical order priority (lower = preferred) */
+ bool isAbsorbable; /* true if state is in absorbable region */
int32 counts[FLEXIBLE_ARRAY_MEMBER]; /* repetition counts by depth */
} RPRNFAState;
/*
* RPRNFAContext - context for NFA pattern matching execution
+ *
+ * Two-flag absorption design:
+ * hasAbsorbableState: can this context absorb others? (≥1 absorbable state)
+ * - Monotonic: true→false only, cannot recover once false
+ * - Used to skip absorption attempts once all absorbable states are gone
+ * allStatesAbsorbable: can this context be absorbed? (ALL states absorbable)
+ * - Dynamic: can change false→true (when non-absorbable states die)
+ * - Used to determine if this context is eligible for absorption
*/
typedef struct RPRNFAContext
{
@@ -2545,6 +2562,10 @@ typedef struct RPRNFAContext
int64 matchEndRow; /* row where match ended (-1 = no match) */
int64 lastProcessedRow; /* last row processed (for fail depth) */
RPRNFAState *matchedState; /* FIN state for greedy fallback (cloned) */
+
+ /* Two-flag absorption optimization */
+ bool hasAbsorbableState; /* can absorb others (≥1 absorbable state) */
+ bool allStatesAbsorbable; /* can be absorbed (ALL states absorbable) */
} RPRNFAContext;
/*
diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h
index 4846ad6f2b7..be2ebb02c33 100644
--- a/src/include/optimizer/rpr.h
+++ b/src/include/optimizer/rpr.h
@@ -18,7 +18,6 @@
/* Limits and special values */
#define RPR_VARID_MAX 252 /* max pattern variables: 252 */
-#define RPR_DEPTH_MAX UINT8_MAX /* max nesting depth: 255 */
#define RPR_QUANTITY_INF INT32_MAX /* unbounded quantifier */
#define RPR_COUNT_MAX INT32_MAX /* max runtime count (NFA state) */
#define RPR_ELEMIDX_MAX INT16_MAX /* max pattern elements */
@@ -30,18 +29,21 @@
#define RPR_VARID_FIN ((RPRVarId) 255) /* pattern finish */
/* Element flags */
-#define RPR_ELEM_RELUCTANT 0x01 /* reluctant (non-greedy) quantifier */
-#define RPR_ELEM_ABSORBABLE 0x02 /* branch supports context absorption */
+#define RPR_ELEM_RELUCTANT 0x01 /* reluctant (non-greedy) quantifier */
+#define RPR_ELEM_ABSORBABLE_BRANCH 0x02 /* element in absorbable region */
+#define RPR_ELEM_ABSORBABLE 0x04 /* absorption judgment point */
/* Accessor macros for RPRPatternElement */
-#define RPRElemIsReluctant(e) ((e)->flags & RPR_ELEM_RELUCTANT)
-#define RPRElemIsAbsorbable(e) ((e)->flags & RPR_ELEM_ABSORBABLE)
+#define RPRElemIsReluctant(e) ((e)->flags & RPR_ELEM_RELUCTANT)
+#define RPRElemIsAbsorbableBranch(e) ((e)->flags & RPR_ELEM_ABSORBABLE_BRANCH)
+#define RPRElemIsAbsorbable(e) ((e)->flags & RPR_ELEM_ABSORBABLE)
#define RPRElemIsVar(e) ((e)->varId <= RPR_VARID_MAX)
#define RPRElemIsAlt(e) ((e)->varId == RPR_VARID_ALT)
#define RPRElemIsEnd(e) ((e)->varId == RPR_VARID_END)
#define RPRElemIsFin(e) ((e)->varId == RPR_VARID_FIN)
#define RPRElemCanSkip(e) ((e)->min == 0)
-extern RPRPattern *buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList);
+extern RPRPattern *buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList,
+ RPSkipTo rpSkipTo, int frameOptions);
#endif /* OPTIMIZER_RPR_H */
diff --git a/src/test/regress/expected/rpr.out b/src/test/regress/expected/rpr.out
index dad454b858b..5a96ced4b52 100644
--- a/src/test/regress/expected/rpr.out
+++ b/src/test/regress/expected/rpr.out
@@ -2623,7 +2623,7 @@ SELECT company, tdate, price, first_value(price) OVER w, last_value(price) OVER
UP AS price > PREV(1),
DOWN AS price < PREV(1)
);
-ERROR: row pattern navigation operation's argument must include at least one column reference
+ERROR: reluctant quantifiers are not yet supported
-- Maximum pattern variables is 252 (RPR_VARID_MAX)
-- Ok: 252 variables (maximum allowed)
DO $$
@@ -2776,6 +2776,44 @@ WINDOW w AS (
-- Row 1: A B C D E (1-5)
-- Row 2: B C D (2-4) <- ends first!
-- Row 3: C D E F (3-6) <- ends last!
+-- Test 1b: Longer pattern FAILS, shorter pattern should survive
+-- Pattern: A+ B C D | A+ B (greedy at front for absorption)
+-- Data: A B C X (D expected but X found)
+-- A+ B C D fails at row 4 (X instead of D)
+-- A+ B succeeds at row 2
+-- Result should be match 1-2 (A+ B)
+WITH test_overlap1b AS (
+ SELECT * FROM (VALUES
+ (1, ARRAY['A']),
+ (2, ARRAY['B']),
+ (3, ARRAY['C']),
+ (4, ARRAY['D']),
+ (5, ARRAY['X'])
+ ) AS t(id, flags)
+)
+SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end
+FROM test_overlap1b
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ AFTER MATCH SKIP PAST LAST ROW
+ PATTERN (A+ B C D E | B+ C)
+ DEFINE
+ A AS 'A' = ANY(flags),
+ B AS 'B' = ANY(flags),
+ C AS 'C' = ANY(flags),
+ D AS 'D' = ANY(flags),
+ E AS 'E' = ANY(flags)
+);
+ id | flags | match_start | match_end
+----+-------+-------------+-----------
+ 1 | {A} | |
+ 2 | {B} | 2 | 3
+ 3 | {C} | |
+ 4 | {D} | |
+ 5 | {X} | |
+(5 rows)
+
-- Test 2: A B+ C | B+ D - long B sequence with different endings
WITH test_overlap2 AS (
SELECT * FROM (VALUES
@@ -3592,7 +3630,7 @@ WINDOW w AS (
-- Expected: 1-4 (A C B C)
-- ============================================
--- RELUCTANT quantifiers (parser only - executor TODO)
+-- RELUCTANT quantifiers (not yet supported)
-- ============================================
-- Test: A+? B (reluctant) - CURRENTLY ACTS LIKE A+ (GREEDY)
-- Parser accepts the syntax but executor doesn't differentiate
@@ -3615,14 +3653,7 @@ WINDOW w AS (
A AS 'A' = ANY(flags),
B AS 'B' = ANY(flags)
);
- id | flags | match_start | match_end
-----+-------+-------------+-----------
- 1 | {A} | 1 | 4
- 2 | {A} | |
- 3 | {A} | |
- 4 | {B} | |
-(4 rows)
-
+ERROR: reluctant quantifiers are not yet supported
-- Current: 1-4 (A A A B) - greedy behavior
-- Expected when RELUCTANT implemented: 3-4 (A B) - shortest A before B
-- Test: A{1,3}? B (reluctant bounded)
@@ -3645,13 +3676,6 @@ WINDOW w AS (
A AS 'A' = ANY(flags),
B AS 'B' = ANY(flags)
);
- id | flags | match_start | match_end
-----+-------+-------------+-----------
- 1 | {A} | 1 | 4
- 2 | {A} | |
- 3 | {A} | |
- 4 | {B} | |
-(4 rows)
-
+ERROR: reluctant quantifiers are not yet supported
-- Current: 1-4 (greedy, takes max A before B)
-- Expected when RELUCTANT implemented: 3-4 (takes min A before B)
diff --git a/src/test/regress/sql/rpr.sql b/src/test/regress/sql/rpr.sql
index 4586eb4b04e..f9c161a791a 100644
--- a/src/test/regress/sql/rpr.sql
+++ b/src/test/regress/sql/rpr.sql
@@ -1320,6 +1320,36 @@ WINDOW w AS (
-- Row 2: B C D (2-4) <- ends first!
-- Row 3: C D E F (3-6) <- ends last!
+-- Test 1b: Longer pattern FAILS, shorter pattern should survive
+-- Pattern: A+ B C D | A+ B (greedy at front for absorption)
+-- Data: A B C X (D expected but X found)
+-- A+ B C D fails at row 4 (X instead of D)
+-- A+ B succeeds at row 2
+-- Result should be match 1-2 (A+ B)
+WITH test_overlap1b AS (
+ SELECT * FROM (VALUES
+ (1, ARRAY['A']),
+ (2, ARRAY['B']),
+ (3, ARRAY['C']),
+ (4, ARRAY['D']),
+ (5, ARRAY['X'])
+ ) AS t(id, flags)
+)
+SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end
+FROM test_overlap1b
+WINDOW w AS (
+ ORDER BY id
+ ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
+ AFTER MATCH SKIP PAST LAST ROW
+ PATTERN (A+ B C D E | B+ C)
+ DEFINE
+ A AS 'A' = ANY(flags),
+ B AS 'B' = ANY(flags),
+ C AS 'C' = ANY(flags),
+ D AS 'D' = ANY(flags),
+ E AS 'E' = ANY(flags)
+);
+
-- Test 2: A B+ C | B+ D - long B sequence with different endings
WITH test_overlap2 AS (
SELECT * FROM (VALUES
@@ -1945,7 +1975,7 @@ WINDOW w AS (
-- Expected: 1-4 (A C B C)
-- ============================================
--- RELUCTANT quantifiers (parser only - executor TODO)
+-- RELUCTANT quantifiers (not yet supported)
-- ============================================
-- Test: A+? B (reluctant) - CURRENTLY ACTS LIKE A+ (GREEDY)
--
2.50.1 (Apple Git-155)