nocfbot-0008-NFA-visited-high-water-mark.txt

From 8f87a3952268ff3b4cb7fd8a09aff1df013e1d18 Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Mon, 4 May 2026 22:31:06 +0900
Subject: [PATCH 08/11] 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)