From 0000000000000000000000000000000000000000 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Wed, 09 Sep 2026 12:20:22 +0900 Subject: [PATCH] Check for interrupts once per NFA epsilon-expansion step The RPR matcher's epsilon expansion is a mutual recursion over nfa_advance_state(), nfa_advance_alt/begin/end/var() and nfa_route_to_elem(), and none of them checks for interrupts. nfa_advance() checks once per source state, before an expansion starts, so nothing bounds how long one expansion runs. A pattern that cannot complete runs it for a long time: PATTERN ((A? | B?){24} C) with C never true takes over twenty seconds on twenty rows, and PATTERN ((A{2,} B)+ C) takes twelve seconds on 240. What keeps those cancellable is nfa_append_state_unique(), whose duplicate scan carries a check. That is incidental to the recursion. It fires only when a step parks a variable and the state list is already non-empty, so the interval it bounds follows how the deduplication happens to be written rather than the depth it is protecting. Add a check where the recursion is. Every cycle in the expansion's call graph passes back through nfa_advance_state() -- the two returning edges are from nfa_advance_alt() and nfa_route_to_elem(), both into it -- so one check on entry bounds the interval by recursion depth whatever the rest of the expansion does. It joins the check_stack_depth() already there, which it is usually paired with. The check in nfa_append_state_unique() stays. That scan is the other unbounded loop in this path, and the state list reaches Theta(n^2) entries on a pattern that cannot complete, so the two bound different things. The added one costs nothing measurable: PATTERN ((A{2,} B)+ C) over 180 rows runs in 2642 ms against 2650 ms before. Measured cancellation latency does not change either -- a one second statement_timeout fired within 1.4 ms before and within 0.8 ms after -- but it no longer rests on how the deduplication is written. --- src/backend/executor/execRPR.c | 8 +++++++- 1 file changed, 7 insertions(+), 1 deletion(-) diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index 29a503e52e7..2f9ae0572cc 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -1501,8 +1501,14 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, Assert(state->elemIdx >= 0 && state->elemIdx < pattern->numElements); - /* Protect against stack overflow for deeply complex patterns */ + /* + * Protect against stack overflow for deeply complex patterns, and bound + * how long the expansion runs uninterrupted: every cycle in this DFS + * passes back through here, so one check per entry bounds the interval by + * the recursion depth. + */ check_stack_depth(); + CHECK_FOR_INTERRUPTS(); /* * Cycle detection. Only a nullable END is marked, so a set bit means the -- 2.50.1