From 39fc31eca0cee7fe874aa4e0abfc7ebaaa69bc1e Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 23 Feb 2026 13:02:06 +0900 Subject: [PATCH 05/10] Detect zero-consumption NFA cycles using elemIdx visited bitmap --- src/backend/executor/nodeWindowAgg.c | 45 ++++++++++++++++----------- src/include/nodes/execnodes.h | 4 +++ src/test/regress/expected/rpr_nfa.out | 8 ++--- src/test/regress/sql/rpr_nfa.sql | 8 ++--- 4 files changed, 38 insertions(+), 27 deletions(-) diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 371439aad91..98546fb17f7 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -343,6 +343,10 @@ 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 @@ -3016,11 +3020,15 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) /* Set up row pattern recognition PATTERN clause (compiled NFA) */ winstate->rpPattern = node->rpPattern; - /* Calculate NFA state size for allocation */ + /* Calculate NFA state size and allocate cycle detection bitmap */ if (node->rpPattern != NULL) { winstate->nfaStateSize = offsetof(RPRNFAState, counts) + sizeof(int32) * node->rpPattern->maxDepth; + winstate->nfaVisitedNWords = + (node->rpPattern->numElements - 1) / BITS_PER_BITMAPWORD + 1; + winstate->nfaVisitedElems = palloc0(sizeof(bitmapword) * + winstate->nfaVisitedNWords); } /* Set up row pattern recognition DEFINE clause */ @@ -6214,25 +6222,9 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos, initialAdvance); } - else if ((elem->max != RPR_QUANTITY_INF && count >= elem->max) || - (count == 0 && elem->min == 0)) + else if (elem->max != RPR_QUANTITY_INF && count >= elem->max) { - /*---------- - * Must exit: either reached max iterations, or group matched empty. - * - * FIXME: The (count == 0 && min == 0) condition is insufficient for - * cycle prevention. Cycles can occur at any count value when loop back - * happens without consuming rows. For example: - * Pattern: (A*)* - * After matching 3 A's (count=3), loop back at a B row - * Inner A* matches 0 times (skip path) → same (elemIdx, count=3) - * Infinite cycle at count=3, not count=0 - * - * Currently, cycles are silently prevented by nfa_add_state_unique - * detecting duplicate states, but this is implicit and not guaranteed - * for all code paths. Explicit cycle detection is needed. - *---------- - */ + /* Must exit: reached max iterations. */ RPRPatternElement *nextElem; state->counts[depth] = 0; @@ -6452,6 +6444,17 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, 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) @@ -6506,6 +6509,10 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos, { 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; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 9a1561fce7e..3681d905bde 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2651,6 +2651,10 @@ typedef struct WindowAggState Size nfaStateSize; /* pre-calculated RPRNFAState size */ bool *nfaVarMatched; /* per-row cache: varMatched[varId] for varId * < numDefines */ + bitmapword *nfaVisitedElems; /* elemIdx visited bitmap for cycle + * detection */ + int nfaVisitedNWords; /* number of bitmapwords in + * nfaVisitedElems */ int64 nfaLastProcessedRow; /* last row processed by NFA (-1 = * none) */ diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index a2a257329b7..8ac375cfe86 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -30,7 +30,7 @@ -- Special Partition Cases -- DEFINE Special Cases -- Absorption Dynamic Flags --- FIXME Issues (Known Limitations) +-- Zero-Consumption Cycle Detection -- -- Responsibility: -- - NFA runtime execution paths @@ -2945,9 +2945,9 @@ WINDOW w AS ( (5 rows) -- ============================================================ --- FIXME Issues - Known Limitations +-- Zero-Consumption Cycle Detection -- ============================================================ --- FIXME 2 - Cycle prevention at count > 0 +-- Cycle prevention at count > 0: (A*)* inner skip cycles at count=3 WITH test_cycle_nonzero AS ( SELECT * FROM (VALUES (1, ARRAY['A']), @@ -2976,7 +2976,7 @@ WINDOW w AS ( 4 | {B} | | (4 rows) --- FIXME 2 - Cycle with mixed nullables +-- Cycle with mixed nullables: (A* B*)* multiple nullable paths WITH test_cycle_mixed AS ( SELECT * FROM (VALUES (1, ARRAY['A']), diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 0e853ca753b..be78ab760a9 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -30,7 +30,7 @@ -- Special Partition Cases -- DEFINE Special Cases -- Absorption Dynamic Flags --- FIXME Issues (Known Limitations) +-- Zero-Consumption Cycle Detection -- -- Responsibility: -- - NFA runtime execution paths @@ -2190,10 +2190,10 @@ WINDOW w AS ( ); -- ============================================================ --- FIXME Issues - Known Limitations +-- Zero-Consumption Cycle Detection -- ============================================================ --- FIXME 2 - Cycle prevention at count > 0 +-- Cycle prevention at count > 0: (A*)* inner skip cycles at count=3 WITH test_cycle_nonzero AS ( SELECT * FROM (VALUES (1, ARRAY['A']), @@ -2215,7 +2215,7 @@ WINDOW w AS ( A AS 'A' = ANY(flags) ); --- FIXME 2 - Cycle with mixed nullables +-- Cycle with mixed nullables: (A* B*)* multiple nullable paths WITH test_cycle_mixed AS ( SELECT * FROM (VALUES (1, ARRAY['A']), -- 2.50.1 (Apple Git-155)