From 8666c965e3152f5d6c3bb9438e5bb3250e700b53 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 4 May 2026 22:31:06 +0900 Subject: [PATCH 8/9] Add high-water mark tracking to NFA visited bitmap reset Track the min/max bitmapword index touched in nfa_mark_visited so the per-advance reset memsets only the touched range, not the full nfaVisitedNWords array. Each visited mark performs two int16 comparisons. For single-word bitmaps this overhead is added with no reset saving; for larger NFAs the reset walks only the slice the DFS actually touched, which is where the win comes from. Applied unconditionally for simplicity. Semantics unchanged. --- src/backend/executor/execRPR.c | 41 +++++++++++++++++++++++----- src/backend/executor/nodeWindowAgg.c | 3 ++ src/include/nodes/execnodes.h | 4 +++ 3 files changed, 41 insertions(+), 7 deletions(-) diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index 242ae9c6dcf..1e6196d6960 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -38,6 +38,21 @@ #define WORDNUM(x) ((x) / BITS_PER_BITMAPWORD) #define BITNUM(x) ((x) % BITS_PER_BITMAPWORD) +/* + * Set the visited bit for elemIdx and update the high-water marks + * (nfaVisitedMin/MaxWord) so that the next reset only has to clear + * the touched range instead of the full nfaVisitedNWords array. + */ +static inline void +nfa_mark_visited(WindowAggState *winstate, int16 elemIdx) +{ + int16 w = WORDNUM(elemIdx); + + winstate->nfaVisitedElems[w] |= ((bitmapword) 1 << BITNUM(elemIdx)); + winstate->nfaVisitedMinWord = Min(winstate->nfaVisitedMinWord, w); + winstate->nfaVisitedMaxWord = Max(winstate->nfaVisitedMaxWord, w); +} + /* Forward declarations - NFA state management */ static RPRNFAState *nfa_state_alloc(WindowAggState *winstate); static void nfa_state_free(WindowAggState *winstate, RPRNFAState *state); @@ -320,8 +335,7 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState * RPRNFAState *tail = NULL; /* Mark VAR in visited before duplicate check to prevent DFS loops */ - winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] |= - ((bitmapword) 1 << BITNUM(state->elemIdx)); + nfa_mark_visited(winstate, state->elemIdx); /* Check for duplicate and find tail */ for (s = ctx->states; s != NULL; s = s->next) @@ -1341,8 +1355,7 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, * the same VAR in a new iteration. */ if (!RPRElemIsVar(elem)) - winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] |= - ((bitmapword) 1 << BITNUM(state->elemIdx)); + nfa_mark_visited(winstate, state->elemIdx); switch (elem->varId) { @@ -1394,9 +1407,23 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) CHECK_FOR_INTERRUPTS(); savedMatchedState = ctx->matchedState; - /* Clear visited bitmap before each state's DFS expansion */ - memset(winstate->nfaVisitedElems, 0, - sizeof(bitmapword) * winstate->nfaVisitedNWords); + /* + * Clear visited bitmap before each state's DFS expansion. Only the + * range touched since the previous reset (tracked via the high-water + * marks updated in nfa_mark_visited) needs to be cleared; for small + * NFAs this is the whole array, but for large NFAs whose DFS only + * reaches a few elements per advance it avoids walking the full + * bitmap. + */ + if (winstate->nfaVisitedMaxWord >= winstate->nfaVisitedMinWord) + { + memset(&winstate->nfaVisitedElems[winstate->nfaVisitedMinWord], 0, + sizeof(bitmapword) * + (winstate->nfaVisitedMaxWord - + winstate->nfaVisitedMinWord + 1)); + winstate->nfaVisitedMinWord = INT16_MAX; + winstate->nfaVisitedMaxWord = -1; + } state = states; states = states->next; diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index af2351bccb8..d82ad8d3897 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -3054,6 +3054,9 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) (node->rpPattern->numElements - 1) / BITS_PER_BITMAPWORD + 1; winstate->nfaVisitedElems = palloc0(sizeof(bitmapword) * winstate->nfaVisitedNWords); + /* High-water mark sentinels: no bits set yet. */ + winstate->nfaVisitedMinWord = INT16_MAX; + winstate->nfaVisitedMaxWord = -1; } /* Set up row pattern recognition DEFINE clause */ diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 0cb01baa949..1fba14b892e 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2673,6 +2673,10 @@ typedef struct WindowAggState * detection */ int nfaVisitedNWords; /* number of bitmapwords in * nfaVisitedElems */ + int16 nfaVisitedMinWord; /* lowest bitmapword index touched since + * last reset (INT16_MAX = none) */ + int16 nfaVisitedMaxWord; /* highest bitmapword index touched since + * last reset (-1 = none) */ int64 nfaLastProcessedRow; /* last row processed by NFA (-1 = * none) */ -- 2.50.1 (Apple Git-155)