0004-NFA-state-memory-memory-management.patch

From b7876ef1859647c93d783b8c2f70cdb0c43795d7 Mon Sep 17 00:00:00 2001
From: Henson Choi <assam258@gmail.com>
Date: Thu, 15 Jan 2026 23:53:02 +0900
Subject: [PATCH 4/5] Row pattern recognition: Improve NFA state memory
 management

---
 src/backend/executor/nodeWindowAgg.c | 203 ++++++++++++++-------------
 src/include/nodes/execnodes.h        |   1 -
 2 files changed, 103 insertions(+), 101 deletions(-)

diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index 4af9998aacf..f02bff4251a 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -261,8 +261,7 @@ 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, int16 *counts,
-									RPRNFAState *list);
+									int16 altPriority, int16 *counts);
 static bool nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched);
 static RPRNFAContext *nfa_context_alloc(WindowAggState *winstate);
 static void nfa_unlink_context(WindowAggState *winstate, RPRNFAContext *ctx);
@@ -270,6 +269,7 @@ 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,
@@ -4791,11 +4791,7 @@ update_reduced_frame(WindowObject winobj, int64 pos)
 		/* No more rows in partition? Finalize all contexts */
 		if (!rowExists)
 		{
-			for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next)
-			{
-				if (ctx->states != NULL)
-					nfa_step(winstate, ctx, NULL, currentPos - 1);
-			}
+			nfa_finalize_all_contexts(winstate, currentPos - 1);
 			/* Absorb completed contexts at partition boundary (SKIP PAST LAST ROW only) */
 			if (winstate->rpSkipTo == ST_PAST_LAST_ROW)
 				nfa_absorb_contexts(winstate, NULL, currentPos - 1);
@@ -4882,7 +4878,6 @@ static RPRNFAState *
 nfa_state_alloc(WindowAggState *winstate)
 {
 	RPRNFAState *state;
-	int			maxDepth = winstate->rpPattern->maxDepth;
 
 	/* Try to reuse from free list first */
 	if (winstate->nfaStateFree != NULL)
@@ -4893,18 +4888,11 @@ nfa_state_alloc(WindowAggState *winstate)
 	else
 	{
 		/* Allocate in partition context for proper lifetime */
-		MemoryContext oldContext = MemoryContextSwitchTo(winstate->partcontext);
-		state = palloc(winstate->nfaStateSize);
-		MemoryContextSwitchTo(oldContext);
+		state = MemoryContextAlloc(winstate->partcontext, winstate->nfaStateSize);
 	}
 
-	/* initialize state - clear all depth counts */
-	state->next = NULL;
-	state->elemIdx = 0;
-	state->altPriority = 0;
-	/* Initialize all depth counts to 0 using memset */
-	if (maxDepth > 0)
-		memset(state->counts, 0, sizeof(int16) * maxDepth);
+	/* Initialize entire state to zero */
+	memset(state, 0, winstate->nfaStateSize);
 
 	return state;
 }
@@ -4964,12 +4952,12 @@ nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2)
  *
  * Add a state to ctx->states at the END, only if no duplicate exists.
  * Returns true if state was added, false if duplicate found (state is freed).
+ * Earlier states have lower altPriority (lexical order), so existing wins.
  */
 static bool
 nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state)
 {
 	RPRNFAState *s;
-	RPRNFAState *prev = NULL;
 	RPRNFAState *tail = NULL;
 
 	/* Check for duplicate and find tail */
@@ -4977,26 +4965,10 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *
 	{
 		if (nfa_states_equal(winstate, s, state))
 		{
-			/*
-			 * Duplicate found - keep lower altPriority for lexical order.
-			 * Lower altPriority means earlier alternative in pattern.
-			 */
-			if (state->altPriority < s->altPriority)
-			{
-				/* New state has better priority, replace existing */
-				state->next = s->next;
-				if (prev == NULL)
-					ctx->states = state;
-				else
-					prev->next = state;
-				nfa_state_free(winstate, s);
-				return true;
-			}
-			/* Existing state has better/equal priority, discard new */
+			/* Duplicate found - existing has better lexical order, discard new */
 			nfa_state_free(winstate, state);
 			return false;
 		}
-		prev = s;
 		tail = s;
 	}
 
@@ -5014,12 +4986,11 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *
  * nfa_state_clone
  *
  * Clone a state with given elemIdx, altPriority and counts.
- * Only copies counts up to elem->depth (not entire maxDepth).
- * Prepends to the provided list and returns the new list head.
+ * Caller is responsible for linking the returned state.
  */
 static RPRNFAState *
 nfa_state_clone(WindowAggState *winstate, int16 elemIdx, int16 altPriority,
-				int16 *counts, RPRNFAState *list)
+				int16 *counts)
 {
 	RPRPattern *pattern = winstate->rpPattern;
 	int			maxDepth = pattern->maxDepth;
@@ -5027,10 +4998,8 @@ nfa_state_clone(WindowAggState *winstate, int16 elemIdx, int16 altPriority,
 
 	state->elemIdx = elemIdx;
 	state->altPriority = altPriority;
-	/* nfa_state_alloc already zeroed all counts, now copy all depth levels */
 	if (counts != NULL && maxDepth > 0)
 		memcpy(state->counts, counts, sizeof(int16) * maxDepth);
-	state->next = list;
 
 	return state;
 }
@@ -5039,55 +5008,39 @@ nfa_state_clone(WindowAggState *winstate, int16 elemIdx, int16 altPriority,
  * nfa_add_matched_state
  *
  * Record a matched state following SQL standard semantics.
- * For greedy quantifiers, longer match wins. For alternation at the same
- * match length, lexical order (lower altPriority) wins.
+ * Lexical order (lower altPriority) wins first. Among same lexical order,
+ * longer match wins (greedy).
  */
 static void
 nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx,
 					  RPRNFAState *state, int64 matchEndRow)
 {
-	bool		shouldUpdate = false;
+	bool	shouldUpdate = false;
 
 	if (ctx->matchedState == NULL)
-	{
-		/* No previous match, always save */
 		shouldUpdate = true;
-	}
 	else if (state->altPriority < ctx->matchedState->altPriority)
-	{
-		/* Better lexical order always wins (SQL standard preference) */
-		shouldUpdate = true;
-	}
+		shouldUpdate = true;	/* Better lexical order wins */
 	else if (state->altPriority == ctx->matchedState->altPriority &&
 			 matchEndRow > ctx->matchEndRow)
-	{
-		/* Same lexical order, longer match wins (greedy) */
-		shouldUpdate = true;
-	}
+		shouldUpdate = true;	/* Same lexical order, longer wins */
 
 	if (shouldUpdate)
 	{
-		/* Reuse existing matchedState or allocate from free list */
-		if (ctx->matchedState == NULL)
-			ctx->matchedState = nfa_state_alloc(winstate);
+		/* Free old matchedState if exists */
+		if (ctx->matchedState != NULL)
+			nfa_state_free(winstate, ctx->matchedState);
 
-		/* Copy state data */
-		memcpy(ctx->matchedState, state, winstate->nfaStateSize);
-		ctx->matchedState->next = NULL;
+		/* Take ownership of the new state */
+		ctx->matchedState = state;
+		state->next = NULL;
 		ctx->matchEndRow = matchEndRow;
 	}
-}
-
-/*
- * nfa_free_matched_state
- *
- * Return matchedState to free list for reuse.
- */
-static void
-nfa_free_matched_state(WindowAggState *winstate, RPRNFAState *state)
-{
-	if (state != NULL)
+	else
+	{
+		/* This state didn't win, free it */
 		nfa_state_free(winstate, state);
+	}
 }
 
 /*
@@ -5176,9 +5129,7 @@ nfa_context_alloc(WindowAggState *winstate)
 	else
 	{
 		/* Allocate in partition context for proper lifetime */
-		MemoryContext oldContext = MemoryContextSwitchTo(winstate->partcontext);
-		ctx = palloc(sizeof(RPRNFAContext));
-		MemoryContextSwitchTo(oldContext);
+		ctx = MemoryContextAlloc(winstate->partcontext, sizeof(RPRNFAContext));
 	}
 
 	ctx->next = NULL;
@@ -5229,7 +5180,7 @@ nfa_context_free(WindowAggState *winstate, RPRNFAContext *ctx)
 	if (ctx->states != NULL)
 		nfa_state_free_list(winstate, ctx->states);
 	if (ctx->matchedState != NULL)
-		nfa_free_matched_state(winstate, ctx->matchedState);
+		nfa_state_free(winstate, ctx->matchedState);
 
 	ctx->states = NULL;
 	ctx->matchedState = NULL;
@@ -5585,6 +5536,24 @@ nfa_step(WindowAggState *winstate, RPRNFAContext *ctx, bool *varMatched, int64 p
 	}
 }
 
+/*
+ * nfa_finalize_all_contexts
+ *
+ * Finalize all active contexts when partition ends.
+ * Calls nfa_step with NULL varMatched to complete without new row data.
+ */
+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_step(winstate, ctx, NULL, lastPos);
+	}
+}
+
 /*
  * nfa_process_context
  *
@@ -5628,7 +5597,8 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 {
 	RPRPattern *pattern = winstate->rpPattern;
 	RPRPatternElement *elements = pattern->elements;
-	RPRNFAState *pending = state;	/* states to process in current row */
+	RPRNFAState *pending = state;		/* states to process in current row */
+	RPRNFAState *pending_tail = state;	/* tail for FIFO append */
 
 	while (pending != NULL)
 	{
@@ -5637,8 +5607,11 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 		int16		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);
@@ -5684,7 +5657,7 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 				{
 					RPRNFAState *clone = nfa_state_clone(winstate, state->elemIdx,
 														 state->altPriority,
-														 state->counts, NULL);
+														 state->counts);
 					nfa_add_state_unique(winstate, ctx, clone);
 				}
 
@@ -5701,7 +5674,6 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 					{
 						/* Match ends at current row since we matched */
 						nfa_add_matched_state(winstate, ctx, state, currentPos);
-						nfa_state_free(winstate, state);
 					}
 					else if (RPRElemIsEnd(nextElem))
 					{
@@ -5710,8 +5682,12 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 						 * This ensures match end position is recorded at the row where
 						 * the last VAR matched, not the next row.
 						 */
-						state->next = pending;
-						pending = state;
+						state->next = NULL;
+						if (pending_tail)
+							pending_tail->next = state;
+						else
+							pending = state;
+						pending_tail = state;
 					}
 					else
 					{
@@ -5743,7 +5719,6 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 					{
 						/* Match ends at previous row since current didn't match */
 						nfa_add_matched_state(winstate, ctx, state, currentPos - 1);
-						nfa_state_free(winstate, state);
 					}
 					else if (RPRElemIsVar(nextElem))
 					{
@@ -5751,13 +5726,21 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 						 * Current row was NOT consumed (skip case), so next VAR
 						 * must be tried on the SAME row via pending list
 						 */
-						state->next = pending;
-						pending = state;
+						state->next = NULL;
+						if (pending_tail)
+							pending_tail->next = state;
+						else
+							pending = state;
+						pending_tail = state;
 					}
 					else
 					{
-						state->next = pending;
-						pending = state;
+						state->next = NULL;
+						if (pending_tail)
+							pending_tail->next = state;
+						else
+							pending = state;
+						pending_tail = state;
 					}
 				}
 				else
@@ -5770,7 +5753,6 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 		{
 			/* Already at FIN - match ends at current row */
 			nfa_add_matched_state(winstate, ctx, state, currentPos);
-			nfa_state_free(winstate, state);
 		}
 		else if (RPRElemIsAlt(elem))
 		{
@@ -5781,25 +5763,34 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 			 * 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;
 
 				if (first)
 				{
 					state->elemIdx = altIdx;
-					state->altPriority = altIdx;	/* lexical order */
-					state->next = pending;
-					pending = state;
+					state->altPriority = altIdx;
+					newState = state;
 					first = false;
 				}
 				else
 				{
-					pending = nfa_state_clone(winstate, altIdx, altIdx,
-											  state->counts, pending);
+					newState = nfa_state_clone(winstate, altIdx, altIdx,
+											   state->counts);
 				}
 
+				/* Append to tail for lexical order */
+				newState->next = NULL;
+				if (pending_tail)
+					pending_tail->next = newState;
+				else
+					pending = newState;
+				pending_tail = newState;
+
 				altIdx = altElem->jump;
 			}
 
@@ -5827,8 +5818,12 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 				/* Reached maximum - must exit, continue processing */
 				state->counts[depth] = 0;
 				state->elemIdx = elem->next;
-				state->next = pending;
-				pending = state;
+				state->next = NULL;
+				if (pending_tail)
+					pending_tail->next = state;
+				else
+					pending = state;
+				pending_tail = state;
 			}
 			else
 			{
@@ -5856,14 +5851,18 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 
 				exitState = nfa_state_clone(winstate, elem->next,
 											exitAltPriority,
-											state->counts, NULL);
+											state->counts);
 				exitState->counts[depth] = 0;
 
 				if (RPRElemIsFin(nextElem))
 				{
-					/* Match ends at current row */
-					exitState->next = pending;
-					pending = exitState;
+					/* 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
 				{
@@ -5881,8 +5880,12 @@ nfa_step_single(WindowAggState *winstate, RPRNFAContext *ctx,
 		else
 		{
 			state->elemIdx = elem->next;
-			state->next = pending;
-			pending = state;
+			state->next = NULL;
+			if (pending_tail)
+				pending_tail->next = state;
+			else
+				pending = state;
+			pending_tail = state;
 		}
 	}
 }
diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h
index 89139583855..21ce39d0797 100644
--- a/src/include/nodes/execnodes.h
+++ b/src/include/nodes/execnodes.h
@@ -2616,7 +2616,6 @@ typedef struct WindowAggState
 								 * initials (list of String) */
 	RPRNFAContext *nfaContext;		/* active matching contexts (head) */
 	RPRNFAContext *nfaContextTail;	/* tail of active contexts (for reverse traversal) */
-	RPRNFAContext *nfaContextPending;	/* matched but awaiting earlier starts */
 	RPRNFAContext *nfaContextFree;	/* recycled NFA context nodes */
 	RPRNFAState *nfaStateFree;		/* recycled NFA state nodes */
 	Size		nfaStateSize;		/* pre-calculated RPRNFAState size */
-- 
2.50.1 (Apple Git-155)