From 23686befee2e6bb71d391b446d66a04abe476b3e Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 28 Sep 2026 15:53:21 +0900 Subject: [PATCH 03/10] Fix DEFINE memory leak and empty-iteration looping in RPR executor This commit fixes three problems and makes some cleanups that change no behavior. 1. Empty iterations that loop (changes query results) ISO/IEC 19075-5 7.2.8 stops a quantifier once its lower bound is met and an iteration matches empty. The cycle guard in nfa_advance_state() enforced this by marking a nullable group's END on arrival and treating a second arrival within the same expansion as an empty iteration. A group entered through its BEGIN had no mark yet, so an empty first iteration went unrecognized and, at a count between min and a finite max, looped back, keeping a derivation the standard excludes. Over rows {B},{A,C},{C}, PATTERN ((A? | B){1,2} C) matched rows 1-2 instead of rows 1-3, and ((B?? | B*){0,2} C) over {B},{B},{B,C},{C} matched rows 1-4 instead of rows 1-3; Perl agrees with the standard in both cases. Mark a nullable group's END when the group is entered through its BEGIN. To reach the END in one step, BEGIN.jump in the compiled pattern now names the group's own END instead of the element after it, and the skip taken when min is 0 leaves through END.next. END.next is already redirected past an enclosing alternation with the rest of the branch tail, so the separate redirect fillRPRPatternAlt() applied to a branch-terminal BEGIN.jump is removed. 2. DEFINE memory leak A DEFINE predicate was evaluated with ExecEvalExpr(), which does not switch memory contexts, so its scratch went to ExecutorState and accumulated for the whole scan; only the navigation copies reached rprContext, the context reserved for it. Compile each DEFINE condition with ExecInitQual() and evaluate it with ExecQual(), which switches to that context's per-tuple memory; a null result still counts as no match. On 300k rows of 200-character values, DEFINE a AS upper(s) > '' now peaks at 18MB instead of 94MB. Also reset rprContext in nfa_eval_var_match(), immediately before each predicate, instead of once per row in rpr_prepare_row() and once per context in the match_start invalidation, so one row's contexts no longer accumulate their scratch until the row boundary. That invalidation function evaluates nothing, so nfa_reevaluate_dependent_vars() becomes nfa_invalidate_dependent_vars(), and its guards move inside it. Query results are unchanged. 3. Cancellation The epsilon expansion in nfa_advance_state() and its helpers had no interrupt check of its own. A long expansion, such as one for PATTERN ((A? | B?){24} C) when C never matches, stayed cancellable only through the check in nfa_append_state_unique()'s duplicate scan, which fires only incidentally. Add CHECK_FOR_INTERRUPTS() next to check_stack_depth() in nfa_advance_state(), which every cycle in the recursion passes through, so the interval between checks is bounded by the recursion depth. 4. Cleanups with no behavior change - Frame end and start row: ExecRPRProcessRow() reads the frame end offset from WindowAggState, with -1 meaning "to the partition end", and advance_reduced_frame_nfa() takes its start row from the target context, instead of both being passed down from update_reduced_frame(). The limited-frame test no longer checks FRAMEOPTION_ROWS, which transformRPR() now asserts, and Phase 3 of ExecRPRProcessRow() no longer recomputes the frame end to assert what Phase 1 enforced. update_reduced_frame() loses its goto and records the result from matchedState alone. The unused ExecRPRGetHeadContext() is removed, and ExecRPRFreeContext() clears every field of a context it puts on the free list. - The SKIP PAST LAST ROW pruning moves out of nfa_add_matched_state() into nfa_prune_skipped_contexts(), which ExecRPRProcessRow() calls after advancing a context that recorded a match. nfa_update_absorption_flags() walks all contexts itself, and both it and nfa_absorb_contexts() test pattern->isAbsorbable at the top. - Names and macros: rename nfa_exit_to() to nfa_state_exit_to() and nfa_add_state_unique() to nfa_append_state_unique(). Add RPRElemIsUnbounded(), RPRElemCanLoop(), RPRElemCanExit(), RPRElemWithinMax() and RPRCountIncrement() to optimizer/rpr.h and use them in place of the quantifier tests and saturating increments spelled out in execRPR.c, explain.c and rpr.c. The two skip paths that land on an outer END call nfa_state_exit_to() instead of bumping its iteration count by hand; the rest of what it does, clearing a count slot that is already zero and recomputing isAbsorbable, is a no-op there. - The absorbability walk in rpr.c passes elements instead of indexes. isFixedLengthChildren() now tests min == max on every element up to the END that closes the group rather than recursing by depth, which would have skipped the children of a GROUP{1,1} that tryUnwrapGroup() had not removed; it always removes them, so nothing changes today. - get_reduced_frame_status() decides the record's own row first, and ExecEvalRPRNavSet() asserts currentpos >= 0 once and subtracts directly in the LAST arm and the inner half of compound navigation. - A non-VAR state in nfa_match() and a NIL DEFINE list or NULL varMatched cache (DEFINE is mandatory) become assertions, and rprNodeRowCount() ends in pg_unreachable(). show_window_def() names RPR_NAV_OFFSET_RETAIN_ALL instead of a default label, so -Wswitch checks that switch again. ExecRPRStartContext() takes the initial state's absorbability from the pattern. buildRPRPattern() no longer pstrdup()s DEFINE names into its scratch array, which the pattern copies from anyway. _jumbleWindowClause_defineClause() calls JUMBLE_STRING() instead of an inline copy of it, so query ids are unchanged. EXPLAIN output, error messages and deparse output are unchanged. 5. Tests New regression tests cover the empty-first-iteration cases (lower bound 0 and 1, greedy and reluctant first branches, both skip modes), an int64 overflow computing a FIRST position, plain and inside a compound navigation, a volatile compound outer offset, collation and system-column navigation, GROUPING() in DEFINE, and group bodies too large to measure as fixed length. Author: jian he Author: Henson Choi --- src/backend/commands/explain.c | 15 +- src/backend/executor/execExprInterp.c | 20 +- src/backend/executor/execRPR.c | 711 +++++++++++++------------ src/backend/executor/nodeWindowAgg.c | 218 ++++---- src/backend/nodes/queryjumblefuncs.c | 10 +- src/backend/optimizer/plan/rpr.c | 185 +++---- src/backend/parser/parse_rpr.c | 2 + src/include/executor/execRPR.h | 5 +- src/include/nodes/execnodes.h | 10 +- src/include/nodes/plannodes.h | 4 +- src/include/optimizer/rpr.h | 12 + src/test/regress/expected/rpr.out | 50 ++ src/test/regress/expected/rpr_base.out | 153 ++++++ src/test/regress/expected/rpr_nfa.out | 163 ++++++ src/test/regress/sql/rpr.sql | 32 ++ src/test/regress/sql/rpr_base.sql | 96 ++++ src/test/regress/sql/rpr_nfa.sql | 131 +++++ 17 files changed, 1202 insertions(+), 615 deletions(-) diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index 32dde24e711..7a9479dc043 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -2912,13 +2912,13 @@ static void append_rpr_quantifier(StringInfo buf, RPRPatternElement *elem) { /* Append quantifier if not {1,1} */ - if (elem->min == 0 && elem->max == RPR_QUANTITY_INF) + if (elem->min == 0 && RPRElemIsUnbounded(elem)) appendStringInfoChar(buf, '*'); - else if (elem->min == 1 && elem->max == RPR_QUANTITY_INF) + else if (elem->min == 1 && RPRElemIsUnbounded(elem)) appendStringInfoChar(buf, '+'); else if (elem->min == 0 && elem->max == 1) appendStringInfoChar(buf, '?'); - else if (elem->max == RPR_QUANTITY_INF) + else if (RPRElemIsUnbounded(elem)) appendStringInfo(buf, "{%d,}", elem->min); else if (elem->min == elem->max && elem->min != 1) appendStringInfo(buf, "{%d}", elem->min); @@ -2940,7 +2940,7 @@ append_rpr_quantifier(StringInfo buf, RPRPatternElement *elem) */ if (RPRElemIsAbsorbable(elem)) { - Assert(elem->max == RPR_QUANTITY_INF); + Assert(RPRElemIsUnbounded(elem)); appendStringInfoChar(buf, '#'); } else if (RPRElemIsAbsorbableBranch(elem)) @@ -3246,12 +3246,9 @@ show_window_def(WindowAggState *planstate, List *ancestors, ExplainState *es) ExplainPropertyInteger("Nav Mark Lookahead", NULL, planstate->navFirstOffset, es); break; - default: + case RPR_NAV_OFFSET_RETAIN_ALL: /* a forward reach is unbounded, never retain all */ - Assert(planstate->navFirstOffsetKind == - RPR_NAV_OFFSET_NEEDS_EVAL || - planstate->navFirstOffsetKind == - RPR_NAV_OFFSET_FIXED); + Assert(false); break; } } diff --git a/src/backend/executor/execExprInterp.c b/src/backend/executor/execExprInterp.c index d19e20a2eaa..a252450423a 100644 --- a/src/backend/executor/execExprInterp.c +++ b/src/backend/executor/execExprInterp.c @@ -6047,6 +6047,7 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) offset = DatumGetInt64(rprnavstate->offset.value); compound_offset = DatumGetInt64(rprnavstate->compound_offset.value); + Assert(winstate->currentpos >= 0); Assert(offset >= 0 && compound_offset >= 0); /* @@ -6058,11 +6059,9 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) case RPR_NAV_PREV: /* - * currentpos and offset are both non-negative, so the subtraction - * cannot underflow; assert the invariant rather than guarding an - * unreachable overflow. + * currentpos and offset are both non-negative, asserted above, so + * the subtraction cannot underflow. */ - Assert(!pg_sub_s64_overflow(winstate->currentpos, offset, &target_pos)); target_pos = winstate->currentpos - offset; break; case RPR_NAV_NEXT: @@ -6078,9 +6077,8 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) break; case RPR_NAV_LAST: /* LAST: offset backward from currentpos, clamped to match_start */ - if (pg_sub_s64_overflow(winstate->currentpos, offset, &target_pos)) - target_pos = -1; - else if (target_pos < winstate->nav_match_start) + target_pos = winstate->currentpos - offset; + if (target_pos < winstate->nav_match_start) target_pos = -1; /* before match_start */ break; @@ -6108,7 +6106,6 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) * inner_pos is in [0, currentpos] and compound_offset is * non-negative, so this cannot underflow. */ - Assert(!pg_sub_s64_overflow(inner_pos, compound_offset, &target_pos)); target_pos = inner_pos - compound_offset; } else @@ -6125,11 +6122,7 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) int64 inner_pos; /* Inner: currentpos - offset */ - if (pg_sub_s64_overflow(winstate->currentpos, offset, &inner_pos)) - { - target_pos = -1; - break; - } + inner_pos = winstate->currentpos - offset; if (inner_pos < winstate->nav_match_start) { target_pos = -1; @@ -6144,7 +6137,6 @@ ExecEvalRPRNavSet(ExprState *state, ExprEvalStep *op, ExprContext *econtext) * and compound_offset is non-negative, so this cannot * underflow. */ - Assert(!pg_sub_s64_overflow(inner_pos, compound_offset, &target_pos)); target_pos = inner_pos - compound_offset; } else diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index abff970bf4e..45ad10c8c78 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -53,6 +53,27 @@ nfa_mark_visited(WindowAggState *winstate, int16 elemIdx) winstate->nfaVisitedMaxWord = Max(winstate->nfaVisitedMaxWord, w); } +/* + * A group entered through its BEGIN has consumed nothing yet in this + * iteration, and the DFS that follows takes only epsilon transitions, so any + * arrival at the group's END within it is an empty iteration. Mark the END + * now: its arrival-time mark comes too late for the first arrival, and the + * cycle guard would otherwise let an empty first iteration at count >= min + * loop back (TR 19075-5 7.2.8). A loop-back arrives at the END first, so + * only entry through BEGIN needs this. + */ +static inline void +nfa_mark_group_entered(WindowAggState *winstate, RPRPatternElement *begin) +{ + RPRPatternElement *end = &winstate->rpPattern->elements[begin->jump]; + + Assert(RPRElemIsBegin(begin)); + Assert(RPRElemIsEnd(end) && end->depth == begin->depth); + + if (RPRElemCanEmptyLoop(end)) + nfa_mark_visited(winstate, begin->jump); +} + /* Forward declarations */ static RPRNFAState *nfa_state_make(WindowAggState *winstate); static void nfa_state_free(WindowAggState *winstate, RPRNFAState *state); @@ -61,8 +82,8 @@ static RPRNFAState *nfa_state_clone(WindowAggState *winstate, int16 elemIdx, int32 *counts, bool sourceAbsorbable); static bool nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2); -static void nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state); +static void nfa_append_state_unique(WindowAggState *winstate, + RPRNFAContext *ctx, RPRNFAState *state); static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, int64 matchEndRow); @@ -73,19 +94,21 @@ static void nfa_update_length_stats(int64 count, NFALengthStats *stats, int64 ne static void nfa_record_context_skipped(WindowAggState *winstate, int64 skippedLen); static void nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen); -static void nfa_update_absorption_flags(RPRNFAContext *ctx); +static void nfa_update_absorption_flags(WindowAggState *winstate); static bool nfa_states_covered(RPRPattern *pattern, RPRNFAContext *older, RPRNFAContext *newer); static void nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx); static void nfa_absorb_contexts(WindowAggState *winstate); +static void nfa_prune_skipped_contexts(WindowAggState *winstate, + RPRNFAContext *ctx); static bool nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, RPRVarMatch *varMatched); static void nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, RPRVarMatch *varMatched, int64 currentPos); static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *nextElem, - int64 currentPos); + RPRNFAState *state, + RPRPatternElement *targetElem, int64 currentPos); static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, RPRPatternElement *elem, int64 currentPos); @@ -103,7 +126,7 @@ static void nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, static void nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos); -static void nfa_reevaluate_dependent_vars(WindowAggState *winstate, +static void nfa_invalidate_dependent_vars(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos); @@ -220,7 +243,7 @@ nfa_state_clone(WindowAggState *winstate, int16 elemIdx, } /* - * nfa_exit_to + * nfa_state_exit_to * * Move state out of the construct owning depth and onto targetIdx, then * return the target element. Callers route from there. @@ -235,24 +258,23 @@ nfa_state_clone(WindowAggState *winstate, int16 elemIdx, * Reapplying it is idempotent, so clone and in-place callers share this path. */ static RPRPatternElement * -nfa_exit_to(WindowAggState *winstate, RPRNFAState *state, int depth, - int16 targetIdx) +nfa_state_exit_to(WindowAggState *winstate, RPRNFAState *state, int depth, + int16 targetIdx) { RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *nextElem; + RPRPatternElement *targetElem; state->counts[depth] = 0; state->elemIdx = targetIdx; - nextElem = &pattern->elements[targetIdx]; + targetElem = &pattern->elements[targetIdx]; state->isAbsorbable = state->isAbsorbable && - RPRElemIsAbsorbableBranch(nextElem); + RPRElemIsAbsorbableBranch(targetElem); - if (RPRElemIsEnd(nextElem) && - state->counts[nextElem->depth] < RPR_COUNT_INF) - state->counts[nextElem->depth]++; + if (RPRElemIsEnd(targetElem)) + RPRCountIncrement(state->counts[targetElem->depth]); - return nextElem; + return targetElem; } /* @@ -288,11 +310,14 @@ nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) if (memcmp(s1->counts, s2->counts, sizeof(int32) * compareDepth) != 0) return false; + /* isAbsorbable follows from the element and the counts compared above */ + Assert(s1->isAbsorbable == s2->isAbsorbable); + return true; } /* - * nfa_add_state_unique + * nfa_append_state_unique * * Add the state to the end of the ctx->states linked list, but only if a * duplicate state is not already present. @@ -300,7 +325,8 @@ nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) * wins; the new state is freed when a duplicate is found. */ static void -nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state) +nfa_append_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, + RPRNFAState *state) { RPRNFAState *s; RPRNFAState *tail = NULL; @@ -342,9 +368,6 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState * * nfa_add_matched_state * * Record a state that reached FIN, replacing any previous match. - * - * For SKIP PAST LAST ROW, also prune subsequent contexts whose start row - * falls within the match range, as they cannot produce output rows. */ static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, @@ -371,26 +394,6 @@ nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, * this and stop rather than record again. */ ctx->matchUpdated = true; - - /* Prune contexts that started within this match's range */ - if (winstate->rpSkipTo == ST_PAST_LAST_ROW) - { - int64 skippedLen; - - while (ctx->next != NULL && - ctx->next->matchStartRow <= matchEndRow) - { - RPRNFAContext *nextCtx = ctx->next; - - /* Only later-starting contexts are freed; callers walk forward */ - Assert(nextCtx->matchStartRow > ctx->matchStartRow); - Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); - skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; - nfa_record_context_skipped(winstate, skippedLen); - - ExecRPRFreeContext(winstate, nextCtx); - } - } } /* @@ -512,7 +515,7 @@ nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen) /* * nfa_update_absorption_flags * - * Update context's absorption flags after state changes. + * Update every live context's absorption flags after state changes. * * Two flags control absorption behavior: * hasAbsorbableState: true if context has at least one absorbable state. @@ -527,55 +530,61 @@ nfa_record_context_absorbed(WindowAggState *winstate, int64 absorbedLen) * permanently, so we skip recalculation. */ static void -nfa_update_absorption_flags(RPRNFAContext *ctx) +nfa_update_absorption_flags(WindowAggState *winstate) { - RPRNFAState *state; - bool hasAbsorbable = false; - bool allAbsorbable = true; - - /* - * Optimization: Once hasAbsorbableState becomes false, it stays false. No - * need to recalculate - both flags remain false permanently. - */ - if (!ctx->hasAbsorbableState) - { - ctx->allStatesAbsorbable = false; + if (!winstate->rpPattern->isAbsorbable) return; - } - /* No states means no absorbable states */ - if (ctx->states == NULL) + for (RPRNFAContext *ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) { - ctx->hasAbsorbableState = false; - ctx->allStatesAbsorbable = false; - return; - } + bool hasAbsorbable = false; + bool allAbsorbable = true; - /* - * Iterate through all states to check absorption status. Uses - * state->isAbsorbable which tracks if state is in absorbable region. This - * is different from RPRElemIsAbsorbable(elem) which checks comparison - * point. - */ - for (state = ctx->states; state != NULL; state = state->next) - { - CHECK_FOR_INTERRUPTS(); + /* + * Optimization: Once hasAbsorbableState becomes false, it stays + * false. No need to recalculate - both flags remain false + * permanently. + */ + if (!ctx->hasAbsorbableState) + { + ctx->allStatesAbsorbable = false; + continue; + } - if (state->isAbsorbable) - hasAbsorbable = true; - else - allAbsorbable = false; - } + /* No states means no absorbable states */ + if (ctx->states == NULL) + { + ctx->hasAbsorbableState = false; + ctx->allStatesAbsorbable = false; + continue; + } - /* - * A recorded match makes this context non-absorbable: absorption would - * free the match, which no absorbing context can reproduce. - */ - if (ctx->matchedState != NULL) - allAbsorbable = false; + /* + * Iterate through all states to check absorption status. Uses + * state->isAbsorbable which tracks if state is in absorbable region. + * This is different from RPRElemIsAbsorbable(elem) which checks + * comparison point. + */ + for (RPRNFAState *state = ctx->states; state != NULL; state = state->next) + { + CHECK_FOR_INTERRUPTS(); + + if (state->isAbsorbable) + hasAbsorbable = true; + else + allAbsorbable = false; + } - ctx->hasAbsorbableState = hasAbsorbable; - ctx->allStatesAbsorbable = allAbsorbable; + /* + * A recorded match makes this context non-absorbable: absorption + * would free the match, which no absorbing context can reproduce. + */ + if (ctx->matchedState != NULL) + allAbsorbable = false; + + ctx->hasAbsorbableState = hasAbsorbable; + ctx->allStatesAbsorbable = allAbsorbable; + } } /* @@ -710,10 +719,12 @@ nfa_try_absorb_context(WindowAggState *winstate, RPRNFAContext *ctx) static void nfa_absorb_contexts(WindowAggState *winstate) { - RPRNFAContext *ctx; RPRNFAContext *nextCtx; - for (ctx = winstate->nfaContextTail; ctx != NULL; ctx = nextCtx) + if (!winstate->rpPattern->isAbsorbable) + return; + + for (RPRNFAContext *ctx = winstate->nfaContextTail; ctx != NULL; ctx = nextCtx) { nextCtx = ctx->prev; @@ -726,6 +737,39 @@ nfa_absorb_contexts(WindowAggState *winstate) } } +/* + * nfa_prune_skipped_contexts + * + * Free the contexts that SKIP PAST LAST ROW makes unreachable. + * + * A context whose match runs to matchEndRow consumes every row through it, so + * a later context that started inside that range can never produce an output + * row. Only contexts after ctx are freed, which is what lets the callers walk + * the list forward. + */ +static void +nfa_prune_skipped_contexts(WindowAggState *winstate, RPRNFAContext *ctx) +{ + int64 matchEndRow = ctx->matchEndRow; + + Assert(winstate->rpSkipTo == ST_PAST_LAST_ROW); + + while (ctx->next != NULL && + ctx->next->matchStartRow <= matchEndRow) + { + RPRNFAContext *nextCtx = ctx->next; + int64 skippedLen; + + Assert(nextCtx->matchStartRow > ctx->matchStartRow); + Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); + + skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; + nfa_record_context_skipped(winstate, skippedLen); + + ExecRPRFreeContext(winstate, nextCtx); + } +} + /* * nfa_eval_var_match * @@ -741,8 +785,8 @@ nfa_absorb_contexts(WindowAggState *winstate) * mismatch at a frame boundary and at partition-end finalization. * * The caller must have set up the current row (ecxt_outertuple, currentpos, - * nav_match_start, nav_slot cache) via rpr_prepare_row() / - * nfa_reevaluate_dependent_vars() before consumption. + * nav_match_start) and invalidated the nav slot cache, via rpr_prepare_row() + * or nfa_invalidate_dependent_vars(), before consumption. * * Per ISO/IEC 19075-5 Feature R020, pattern variables not listed in DEFINE * are implicitly TRUE -- they match every row. This is checked via @@ -768,12 +812,20 @@ nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, if (varMatched[varId] == RPR_VAR_UNEVALUATED) { ExprState *exprState = list_nth(winstate->defineClauseExprs, varId); - Datum result; - bool isnull; - result = ExecEvalExpr(exprState, winstate->rprContext, &isnull); - varMatched[varId] = (!isnull && DatumGetBool(result)) ? - RPR_VAR_TRUE : RPR_VAR_FALSE; + /* + * Free the previous predicate evaluation's storage. A DEFINE + * predicate leaves nothing behind but the RPRVarMatch stored below -- + * the navigation steps stabilize pass-by-ref results in this same + * context, and those are consumed before the predicate returns -- so + * resetting here is always safe and no caller has to arrange it. + */ + ResetExprContext(winstate->rprContext); + + if (ExecQual(exprState, winstate->rprContext)) + varMatched[varId] = RPR_VAR_TRUE; + else + varMatched[varId] = RPR_VAR_FALSE; } return (varMatched[varId] == RPR_VAR_TRUE); @@ -819,149 +871,140 @@ nfa_match(WindowAggState *winstate, RPRNFAContext *ctx, RPRVarMatch *varMatched, for (state = ctx->states; state != NULL; state = nextState) { RPRPatternElement *elem = &elements[state->elemIdx]; + int depth; + int32 count; CHECK_FOR_INTERRUPTS(); nextState = state->next; - if (RPRElemIsVar(elem)) + /* + * The advance phase parks only VAR states, and a fresh context is + * advanced before its first match. + */ + Assert(RPRElemIsVar(elem)); + + if (!nfa_eval_var_match(winstate, elem, varMatched)) { - bool matched; - int depth = elem->depth; - int32 count = state->counts[depth]; + /* + * Not matched - remove state. Exit alternatives were already + * created by advance phase when count >= min was satisfied. + */ + *prevPtr = nextState; + nfa_state_free(winstate, state); + continue; + } - matched = nfa_eval_var_match(winstate, elem, varMatched); + prevPtr = &state->next; - if (matched) - { - /* - * Increment count, saturating at RPR_COUNT_INF to avoid int32 - * overflow; a saturated count then compares as "unbounded". - */ - if (count < RPR_COUNT_INF) - count++; + depth = elem->depth; + count = state->counts[depth]; - /* Max constraint should not be exceeded */ - Assert(elem->max == RPR_QUANTITY_INF || count <= elem->max); + /* + * Increment count, saturating at RPR_COUNT_INF to avoid int32 + * overflow; a saturated count then compares as "unbounded". + */ + RPRCountIncrement(count); - state->counts[depth] = count; + /* Max constraint should not be exceeded */ + Assert(RPRElemWithinMax(elem, count)); - /* - * For VAR at max count with END next, advance through END - * chain to reach the absorption comparison point. Only - * deterministic exits (count >= max, max finite) are handled; - * unbounded VARs stay for advance phase. - * - * In nested patterns like ((A (B C){2}){2})+, a VAR reaching - * its max triggers an exit cascade: inner END increments - * inner group count, which may itself reach max, requiring an - * exit to the next outer END. The loop below walks this - * chain. - * - * ABSORBABLE_BRANCH marks elements inside the absorbable - * region; ABSORBABLE marks the outermost comparison point - * where count-dominance is evaluated. We chain through - * BRANCH elements until reaching the ABSORBABLE point or an - * element that can still loop (count < max). - */ - if (RPRElemIsAbsorbableBranch(elem) && - !RPRElemIsAbsorbable(elem) && - count >= elem->max && - RPRElemIsEnd(&elements[elem->next])) - { - RPRPatternElement *endElem = &elements[elem->next]; - int endDepth = endElem->depth; - int32 endCount = state->counts[endDepth]; - - /* Increment group count */ - if (endCount < RPR_COUNT_INF) - endCount++; - Assert(endElem->max == RPR_QUANTITY_INF || - endCount <= endElem->max); - - state->elemIdx = elem->next; - state->counts[endDepth] = endCount; - - /* - * Leaf VAR exited (reached max): clear its own count so - * the next occupant enters with zero, as nfa_advance_var - * does on exit (this inline path replaces that exit). - * depth > endDepth, so this leaves the group count just - * written intact. - */ - Assert(endDepth < depth); - state->counts[depth] = 0; - - /* - * Chain through END elements within the absorbable region - * (ABSORBABLE_BRANCH) until reaching the comparison point - * (ABSORBABLE). Continue only on must-exit path (count - * >= max) with END next. - */ - while (RPRElemIsAbsorbableBranch(endElem) && - !RPRElemIsAbsorbable(endElem) && - endCount >= endElem->max && - RPRElemIsEnd(&elements[endElem->next])) - { - RPRPatternElement *outerEnd = &elements[endElem->next]; - int outerDepth = outerEnd->depth; - int32 outerCount = state->counts[outerDepth]; - - /* - * Exit this intermediate group: clear its own count - * (count-clear policy). It sits below the absorbable - * comparison point, so it is excluded from the - * dominance comparison; the comparison point where - * the chain stops keeps its count. - */ - state->counts[endDepth] = 0; - - /* Increment outer group count */ - if (outerCount < RPR_COUNT_INF) - outerCount++; - Assert(outerEnd->max == RPR_QUANTITY_INF || - outerCount <= outerEnd->max); - - state->elemIdx = endElem->next; - state->counts[outerDepth] = outerCount; - - /* Advance to next END in chain */ - endElem = outerEnd; - endDepth = outerDepth; - endCount = outerCount; - } - } - /* else: stay at VAR for advance phase */ - } - else + state->counts[depth] = count; + + /* + * For VAR at max count with END next, advance through END chain to + * reach the absorption comparison point. Only deterministic exits + * (count >= max, max finite) are handled; unbounded VARs stay for + * advance phase. + * + * In nested patterns like ((A (B C){2}){2})+, a VAR reaching its max + * triggers an exit cascade: inner END increments inner group count, + * which may itself reach max, requiring an exit to the next outer + * END. The loop below walks this chain. + * + * ABSORBABLE_BRANCH marks elements inside the absorbable region; + * ABSORBABLE marks the outermost comparison point where + * count-dominance is evaluated. We chain through BRANCH elements + * until reaching the ABSORBABLE point or an element that can still + * loop (count < max). + */ + if (RPRElemIsAbsorbableBranch(elem) && + !RPRElemIsAbsorbable(elem) && + count >= elem->max && + RPRElemIsEnd(&elements[elem->next])) + { + RPRPatternElement *endElem = &elements[elem->next]; + int endDepth = endElem->depth; + int32 endCount = state->counts[endDepth]; + + /* Increment group count */ + RPRCountIncrement(endCount); + Assert(RPRElemWithinMax(endElem, endCount)); + + state->elemIdx = elem->next; + state->counts[endDepth] = endCount; + + /* + * Leaf VAR exited (reached max): clear its own count so the next + * occupant enters with zero, as nfa_advance_var does on exit + * (this inline path replaces that exit). depth > endDepth, so + * this leaves the group count just written intact. + */ + Assert(endDepth < depth); + state->counts[depth] = 0; + + /* + * Chain through END elements within the absorbable region + * (ABSORBABLE_BRANCH) until reaching the comparison point + * (ABSORBABLE). Continue only on must-exit path (count >= max) + * with END next. + */ + while (RPRElemIsAbsorbableBranch(endElem) && + !RPRElemIsAbsorbable(endElem) && + endCount >= endElem->max && + RPRElemIsEnd(&elements[endElem->next])) { + RPRPatternElement *outerEnd = &elements[endElem->next]; + int outerDepth = outerEnd->depth; + int32 outerCount = state->counts[outerDepth]; + /* - * Not matched - remove state. Exit alternatives were already - * created by advance phase when count >= min was satisfied. + * Exit this intermediate group: clear its own count + * (count-clear policy). It sits below the absorbable + * comparison point, so it is excluded from the dominance + * comparison; the comparison point where the chain stops + * keeps its count. */ - *prevPtr = nextState; - nfa_state_free(winstate, state); - continue; + state->counts[endDepth] = 0; + + /* Increment outer group count */ + RPRCountIncrement(outerCount); + Assert(RPRElemWithinMax(outerEnd, outerCount)); + + state->elemIdx = endElem->next; + state->counts[outerDepth] = outerCount; + + /* Advance to next END in chain */ + endElem = outerEnd; + endDepth = outerDepth; + endCount = outerCount; } } - /* Non-VAR elements: keep as-is for advance phase */ - - prevPtr = &state->next; } } /* * nfa_route_to_elem * - * Route state to next element. If VAR, add to ctx->states and process + * Route state to the target element. If VAR, add to ctx->states and process * skip path if optional. Otherwise, continue epsilon expansion via recursion. */ static void nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, - RPRNFAState *state, RPRPatternElement *nextElem, + RPRNFAState *state, RPRPatternElement *targetElem, int64 currentPos) { - if (RPRElemIsVar(nextElem)) + if (RPRElemIsVar(targetElem)) { RPRNFAState *skipState = NULL; @@ -972,14 +1015,12 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, * (see nfa_advance_var / nfa_advance_end exit handling and the inline * fast path in nfa_match). */ - Assert(state->counts[nextElem->depth] == 0); + Assert(state->counts[targetElem->depth] == 0); /* Create skip state before add_unique, which may free state */ - if (RPRElemCanSkip(nextElem)) + if (RPRElemCanSkip(targetElem)) { - RPRPatternElement *landElem; - - skipState = nfa_state_clone(winstate, nextElem->next, + skipState = nfa_state_clone(winstate, targetElem->next, state->counts, state->isAbsorbable); /* @@ -989,13 +1030,11 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, * group's min check and the cycle guard's below-min fall-through * both read. */ - landElem = &winstate->rpPattern->elements[skipState->elemIdx]; - if (RPRElemIsEnd(landElem) && - skipState->counts[landElem->depth] < RPR_COUNT_INF) - skipState->counts[landElem->depth]++; + nfa_state_exit_to(winstate, skipState, targetElem->depth, + targetElem->next); } - if (skipState != NULL && RPRElemIsReluctant(nextElem)) + if (skipState != NULL && RPRElemIsReluctant(targetElem)) { /* * Reluctant optional VAR: prefer skipping. Explore the skip path @@ -1012,12 +1051,12 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, return; } - nfa_add_state_unique(winstate, ctx, state); + nfa_append_state_unique(winstate, ctx, state); } else { /* Greedy (or non-skippable): enter first, then skip */ - nfa_add_state_unique(winstate, ctx, state); + nfa_append_state_unique(winstate, ctx, state); if (skipState != NULL) nfa_advance_state(winstate, ctx, skipState, currentPos); @@ -1110,6 +1149,9 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, RPRPatternElement *elements = pattern->elements; RPRNFAState *skipState = NULL; + /* The skip leaves through the END's exit without arriving at the END */ + RPRElemIdx skipIdx = elements[elem->jump].next; + /* * Entry-side check of the count-clear policy: the group's own count slot * is already zero here. BEGIN is only visited at initial group entry, @@ -1118,28 +1160,23 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, Assert(state->counts[elem->depth] == 0); /* Optional group: create skip path (but don't route yet) */ - if (elem->min == 0) + if (RPRElemCanSkip(elem)) { - RPRPatternElement *landElem; - - skipState = nfa_state_clone(winstate, elem->jump, + skipState = nfa_state_clone(winstate, skipIdx, state->counts, state->isAbsorbable); /* * As in nfa_route_to_elem, a skip that lands directly on an outer END * still counts as an iteration of that END's group. */ - landElem = &elements[elem->jump]; - if (RPRElemIsEnd(landElem) && - skipState->counts[landElem->depth] < RPR_COUNT_INF) - skipState->counts[landElem->depth]++; + nfa_state_exit_to(winstate, skipState, elem->depth, skipIdx); } if (skipState != NULL && RPRElemIsReluctant(elem)) { /* Reluctant: skip first (prefer fewer iterations), enter second */ nfa_route_to_elem(winstate, ctx, skipState, - &elements[elem->jump], currentPos); + &elements[skipIdx], currentPos); /* The skip matched: do not enter the group over it */ if (ctx->matchUpdated) @@ -1148,6 +1185,7 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, return; } + nfa_mark_group_entered(winstate, elem); state->elemIdx = elem->next; nfa_route_to_elem(winstate, ctx, state, &elements[state->elemIdx], currentPos); @@ -1160,6 +1198,7 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, * skip path; for non-nullable groups (skipState == NULL, min>0) the * skip-path action is suppressed by the guard below. */ + nfa_mark_group_entered(winstate, elem); state->elemIdx = elem->next; nfa_route_to_elem(winstate, ctx, state, &elements[state->elemIdx], currentPos); @@ -1175,7 +1214,7 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, if (skipState != NULL) { nfa_route_to_elem(winstate, ctx, skipState, - &elements[elem->jump], currentPos); + &elements[skipIdx], currentPos); } } } @@ -1196,7 +1235,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, int depth = elem->depth; int32 count = state->counts[depth]; - if (count < elem->min) + if (!RPRElemCanExit(elem, count)) { RPRPatternElement *jumpElem; RPRNFAState *ffState = NULL; @@ -1229,10 +1268,11 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, state->counts, state->isAbsorbable); /* - * nfa_exit_to()'s isAbsorbable recompute is a no-op here: + * nfa_state_exit_to()'s isAbsorbable recompute is a no-op here: * EMPTY_LOOP groups are never in an absorbable region. */ - nextElem = nfa_exit_to(winstate, ffState, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, ffState, depth, + elem->next); } /* @@ -1278,12 +1318,12 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, currentPos); } } - else if (elem->max != RPR_QUANTITY_INF && count >= elem->max) + else if (!RPRElemCanLoop(elem, count)) { /* Must exit: reached max iterations. */ RPRPatternElement *nextElem; - nextElem = nfa_exit_to(winstate, state, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); } @@ -1304,7 +1344,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, */ exitState = nfa_state_clone(winstate, elem->next, state->counts, state->isAbsorbable); - nextElem = nfa_exit_to(winstate, exitState, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, exitState, depth, elem->next); /* Prepare loop state */ state->elemIdx = elem->jump; @@ -1358,19 +1398,16 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, RPRPatternElement *elem, int64 currentPos) { - PG_USED_FOR_ASSERTS_ONLY RPRPattern *pattern = winstate->rpPattern; int depth = elem->depth; int32 count = state->counts[depth]; - bool canLoop = (elem->max == RPR_QUANTITY_INF || count < elem->max); - bool canExit = (count >= elem->min); - /* min <= max, so !canExit (count < min) implies canLoop (count < max) */ - Assert(canLoop || canExit); + Assert(RPRElemCanLoop(elem, count) || RPRElemCanExit(elem, count)); /* elem->next must be a valid index for any reachable VAR */ - Assert(elem->next >= 0 && elem->next < pattern->numElements); + Assert(elem->next >= 0 && + elem->next < winstate->rpPattern->numElements); - if (canLoop && canExit) + if (RPRElemCanLoop(elem, count) && RPRElemCanExit(elem, count)) { /* * Both loop and exit possible. Greedy: loop first (prefer longer @@ -1378,18 +1415,18 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, */ RPRNFAState *cloneState; RPRPatternElement *nextElem; - bool reluctant = RPRElemIsReluctant(elem); /* * Clone state for the first-priority path. For greedy, clone is the * loop state; for reluctant, clone is the exit state. */ - if (reluctant) + if (RPRElemIsReluctant(elem)) { /* Clone for exit, original stays for loop */ cloneState = nfa_state_clone(winstate, elem->next, state->counts, state->isAbsorbable); - nextElem = nfa_exit_to(winstate, cloneState, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, cloneState, depth, + elem->next); /* Exit first (preferred for reluctant) */ nfa_route_to_elem(winstate, ctx, cloneState, nextElem, @@ -1403,7 +1440,7 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, } /* Loop second */ - nfa_add_state_unique(winstate, ctx, state); + nfa_append_state_unique(winstate, ctx, state); } else { @@ -1412,27 +1449,38 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, state->counts, state->isAbsorbable); /* Loop first (preferred for greedy) */ - nfa_add_state_unique(winstate, ctx, cloneState); + nfa_append_state_unique(winstate, ctx, cloneState); /* Exit second: nfa_match handles only deterministic exits */ - nextElem = nfa_exit_to(winstate, state, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); } } - else if (canLoop) + else if (!RPRElemCanExit(elem, count)) { - /* Loop only: keep state as-is */ - nfa_add_state_unique(winstate, ctx, state); + /* + * Below the minimum, so exiting is illegal and matching this VAR + * again on the next row is the only legal continuation. This row's + * match already incremented counts[depth] in the match phase, and the + * advance phase only decides where the state goes next, so staying + * parked at the same VAR is expressed by appending the state + * unchanged to the new generation. Dropping it instead would strand + * every quantifier below its minimum: (A B){2} would lose its state + * after the first A B match and never complete. + * + * No clone is needed. With a single continuation, ownership of the + * original simply transfers to the list. + */ + nfa_append_state_unique(winstate, ctx, state); } else { - /* Exit only: advance to next element (canExit necessarily true) */ + /* Exit only: advance to next element */ RPRPatternElement *nextElem; - Assert(canExit); - nextElem = nfa_exit_to(winstate, state, depth, elem->next); + nextElem = nfa_state_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); } @@ -1453,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 @@ -1472,7 +1526,7 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, Assert(RPRElemIsEnd(hitElem) && RPRElemCanEmptyLoop(hitElem)); - if (state->counts[hitElem->depth] >= hitElem->min) + if (RPRElemCanExit(hitElem, state->counts[hitElem->depth])) { RPRPatternElement *nextElem; @@ -1488,8 +1542,8 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, * (SQL/RPR follows Perl here). */ - nextElem = nfa_exit_to(winstate, state, hitElem->depth, - hitElem->next); + nextElem = nfa_state_exit_to(winstate, state, hitElem->depth, + hitElem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); return; @@ -1526,7 +1580,6 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, switch (elem->varId) { case RPR_VARID_FIN: - /* FIN: record match */ nfa_add_matched_state(winstate, ctx, state, currentPos); break; @@ -1543,7 +1596,7 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, break; default: - /* VAR element; a SEP would land here, so see fillRPRPatternAlt */ + /* VAR element; a SEP should not land here */ Assert(!RPRElemIsSep(elem) && RPRElemIsVar(elem)); nfa_advance_var(winstate, ctx, state, elem, currentPos); break; @@ -1599,7 +1652,7 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) * crossing into nfa_advance_state's epsilon-expansion DFS. The inner * branches (nfa_advance_var, nfa_advance_begin/end/alt) treat * state->next as already-NULL and don't reset it themselves; the - * other linking site is nfa_add_state_unique, which sets it when + * other linking site is nfa_append_state_unique, which sets it when * appending to ctx->states. */ state->next = NULL; @@ -1620,14 +1673,14 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) } /* - * nfa_reevaluate_dependent_vars + * nfa_invalidate_dependent_vars * Invalidate match_start-dependent DEFINE variables for a context whose * matchStartRow differs from the shared evaluation's nav_match_start. * * Only variables in defineMatchStartDependent are affected: they are reset to * RPR_VAR_UNEVALUATED so nfa_match() re-evaluates them lazily against this - * context's matchStartRow. match_start-independent variables keep their - * cached value across contexts, since they do not read nav_match_start. + * context's matchStartRow. The remaining variables keep their cached value + * across contexts, since they do not read nav_match_start. * * nav_match_start is installed for this context and left in place: FIRST/LAST * read it at evaluation time, which happens later during nfa_match(), so it @@ -1635,24 +1688,18 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) * row's shared setup in advance_reduced_frame_nfa, overwrites it. */ static void -nfa_reevaluate_dependent_vars(WindowAggState *winstate, RPRNFAContext *ctx, +nfa_invalidate_dependent_vars(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) { int varIdx = -1; + if (bms_is_empty(winstate->defineMatchStartDependent) || + ctx->matchStartRow == winstate->nav_match_start) + return; + /* Caller keeps winstate->currentpos at the scan position for lazy eval. */ Assert(winstate->currentpos == currentPos); - /* - * Release the previous context's DEFINE evaluation memory. Match-start- - * dependent variables are re-evaluated once per context (they are reset - * to UNEVALUATED below), so without this reset their per-tuple scratch - * would accumulate across every context of a row -- bounded only by the - * per-row reset in rpr_prepare_row. rprContext is the dedicated DEFINE - * context, so this frees neither the input nor the output tuple memory. - */ - ResetExprContext(winstate->rprContext); - /* Install this context's match_start for FIRST/LAST and keep it in place. */ winstate->nav_match_start = ctx->matchStartRow; @@ -1683,24 +1730,20 @@ ExecRPRStartContext(WindowAggState *winstate, int64 startPos) { RPRNFAContext *ctx; RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elem; ctx = nfa_context_make(winstate); ctx->matchStartRow = startPos; ctx->states = nfa_state_make(winstate); /* initial state at elem 0 */ - elem = &pattern->elements[0]; - - if (RPRElemIsAbsorbableBranch(elem)) - { - ctx->states->isAbsorbable = true; - } - else - { - ctx->hasAbsorbableState = false; - ctx->allStatesAbsorbable = false; - ctx->states->isAbsorbable = false; - } + /* + * The only state so far sits on element 0, and computeAbsorbability() + * marks that element ABSORBABLE_BRANCH exactly when it calls the pattern + * absorbable, so the pattern's flag answers for the state -- as it + * already did for the context flags nfa_context_make() set. + */ + Assert(RPRElemIsAbsorbableBranch(&pattern->elements[0]) == + pattern->isAbsorbable); + ctx->states->isAbsorbable = pattern->isAbsorbable; /* * Add to tail of active context list (doubly-linked, oldest-first). @@ -1733,27 +1776,6 @@ ExecRPRStartContext(WindowAggState *winstate, int64 startPos) return ctx; } -/* - * ExecRPRGetHeadContext - * - * Return the head context if its start position matches pos. - * Returns NULL if no context exists or head doesn't match pos. - */ -RPRNFAContext * -ExecRPRGetHeadContext(WindowAggState *winstate, int64 pos) -{ - RPRNFAContext *ctx = winstate->nfaContext; - - /* - * Contexts are sorted by matchStartRow ascending. If the head context - * doesn't match pos, no context exists for this position. - */ - if (ctx == NULL || ctx->matchStartRow != pos) - return NULL; - - return ctx; -} - /* * ExecRPRFreeContext * @@ -1774,9 +1796,15 @@ ExecRPRFreeContext(WindowAggState *winstate, RPRNFAContext *ctx) if (ctx->matchedState != NULL) nfa_state_free(winstate, ctx->matchedState); + ctx->next = winstate->nfaContextFree; ctx->states = NULL; + ctx->matchStartRow = -1; + ctx->matchEndRow = -1; + ctx->lastProcessedRow = -1; ctx->matchedState = NULL; - ctx->next = winstate->nfaContextFree; + ctx->matchUpdated = false; + ctx->hasAbsorbableState = false; + ctx->allStatesAbsorbable = false; winstate->nfaContextFree = ctx; } @@ -1826,12 +1854,17 @@ ExecRPRRecordContextFailure(WindowAggState *winstate, int64 failedLen) * 3. Advance all contexts (divergence) - create new states for next row */ void -ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, - bool hasLimitedFrame, int64 frameOffset) +ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos) { - RPRNFAContext *ctx; RPRVarMatch *varMatched = winstate->nfaVarMatched; - bool hasDependent = !bms_is_empty(winstate->defineMatchStartDependent); + int64 frameOffset = -1; /* -1 = frame runs to the partition end */ + + /* + * Check if we have a limited frame (ROWS ... N FOLLOWING). Each context + * needs its own frame end based on matchStartRow + offset. + */ + if (!(winstate->frameOptions & FRAMEOPTION_END_UNBOUNDED_FOLLOWING)) + frameOffset = DatumGetInt64(winstate->endOffsetValue); /* Allow query cancellation once per row for simple/low-state patterns */ CHECK_FOR_INTERRUPTS(); @@ -1840,13 +1873,13 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, * Phase 1: Match all contexts (convergence). Evaluate VAR elements, * update counts, remove dead states. */ - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + for (RPRNFAContext *ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) { if (ctx->states == NULL) continue; /* Check frame boundary - finalize the context when it is reached */ - if (hasLimitedFrame) + if (frameOffset >= 0) { int64 ctxFrameEnd; @@ -1893,8 +1926,8 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, Assert(ctx != winstate->nfaContext || ctx->matchStartRow == winstate->nav_match_start); - if (hasDependent && ctx->matchStartRow != winstate->nav_match_start) - nfa_reevaluate_dependent_vars(winstate, ctx, currentPos); + nfa_invalidate_dependent_vars(winstate, ctx, currentPos); + nfa_match(winstate, ctx, varMatched, currentPos); ctx->lastProcessedRow = currentPos; } @@ -1904,47 +1937,22 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, * converged - ideal for absorption. First update absorption flags that * may have changed due to state removal. */ - if (winstate->rpPattern->isAbsorbable) - { - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) - nfa_update_absorption_flags(ctx); - - nfa_absorb_contexts(winstate); - } + nfa_update_absorption_flags(winstate); + nfa_absorb_contexts(winstate); /* * Phase 3: Advance all contexts (divergence). Create new states * (loop/exit) from surviving matched states. */ - for (ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) + for (RPRNFAContext *ctx = winstate->nfaContext; ctx != NULL; ctx = ctx->next) { if (ctx->states == NULL) continue; - /* - * Phase 1 already handled frame boundary exceeded contexts by forcing - * mismatch (nfa_match with NULL), which removes all states (all - * states are at VAR positions after advance). So any surviving - * context here must be within its frame boundary. - * - * Compute the (clamped) frame end the same way as Phase 1, using two - * separately checked adds so that "frameOffset + 1" cannot overflow - * when frameOffset is near PG_INT64_MAX. - */ -#ifdef USE_ASSERT_CHECKING - if (hasLimitedFrame) - { - int64 ctxFrameEnd; - - if (pg_add_s64_overflow(ctx->matchStartRow, frameOffset, - &ctxFrameEnd) || - pg_add_s64_overflow(ctxFrameEnd, 1, &ctxFrameEnd)) - ctxFrameEnd = PG_INT64_MAX; - Assert(currentPos < ctxFrameEnd); - } -#endif - nfa_advance(winstate, ctx, currentPos); + + if (ctx->matchUpdated && winstate->rpSkipTo == ST_PAST_LAST_ROW) + nfa_prune_skipped_contexts(winstate, ctx); } } @@ -1987,9 +1995,8 @@ ExecRPRCleanupDeadContexts(WindowAggState *winstate, RPRNFAContext *excludeCtx) */ if (ctx->lastProcessedRow >= ctx->matchStartRow) { - int64 failedLen = ctx->lastProcessedRow - ctx->matchStartRow + 1; - - ExecRPRRecordContextFailure(winstate, failedLen); + ExecRPRRecordContextFailure(winstate, + ctx->lastProcessedRow - ctx->matchStartRow + 1); } ExecRPRFreeContext(winstate, ctx); diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 9ab73c614dc..7b106c9d743 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -43,6 +43,7 @@ #include "executor/instrument.h" #include "executor/nodeWindowAgg.h" #include "miscadmin.h" +#include "nodes/makefuncs.h" #include "nodes/nodeFuncs.h" #include "nodes/plannodes.h" #include "optimizer/clauses.h" @@ -255,8 +256,7 @@ static void clear_reduced_frame(WindowAggState *winstate); static int get_reduced_frame_status(WindowAggState *winstate, int64 pos); static void advance_nav_mark(WindowAggState *winstate, int64 currentPos); static void advance_reduced_frame_nfa(WindowObject winobj, - RPRNFAContext *targetCtx, int64 pos, - bool hasLimitedFrame, int64 frameOffset); + RPRNFAContext *targetCtx); static void update_reduced_frame(WindowObject winobj, int64 pos); /* Forward declarations - DEFINE row evaluation */ @@ -2555,12 +2555,12 @@ ExecWindowAgg(PlanState *pstate) /* don't evaluate the window functions when we're in pass-through mode */ if (winstate->status == WINDOWAGG_RUN) { - /* - * If RPR is defined and skip mode is next row, clear the current - * match so the next row triggers re-evaluation. - */ if (rpr_is_defined(winstate)) { + /* + * Under SKIP TO NEXT ROW, clear the recorded match so this + * row is matched again from its own start. + */ if (winstate->rpSkipTo == ST_NEXT_ROW) clear_reduced_frame(winstate); @@ -3083,7 +3083,7 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) { ExprState *exprstate; - exprstate = ExecInitExpr(te->expr, (PlanState *) winstate); + exprstate = ExecInitQual(make_ands_implicit(te->expr), (PlanState *) winstate); winstate->defineClauseExprs = lappend(winstate->defineClauseExprs, exprstate); @@ -3101,12 +3101,14 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) * Allocate the per-row varMatched cache. varNames are built in * DEFINE order, so varId equals the DEFINE list index and no mapping * is needed. + * + * The grammar makes DEFINE mandatory for a row pattern window, and + * this branch runs only for one, so the list is never empty and + * rpr_prepare_row() can reset the cache unconditionally. */ - if (winstate->defineClauseExprs != NIL) - winstate->nfaVarMatched = palloc0(sizeof(RPRVarMatch) * - list_length(winstate->defineClauseExprs)); - else - winstate->nfaVarMatched = NULL; + Assert(winstate->defineClauseExprs != NIL); + winstate->nfaVarMatched = palloc0(sizeof(RPRVarMatch) * + list_length(winstate->defineClauseExprs)); /* Copy match_start dependency bitmapset for per-context evaluation */ winstate->defineMatchStartDependent = bms_copy(node->defineMatchStartDependent); @@ -4545,9 +4547,6 @@ clear_reduced_frame(WindowAggState *winstate) * start >= 0, length == -1 unmatched (covers only the start row) * start >= 0, length == 0 empty match (zero-length match at start) * start >= 0, length >= 1 real match spanning [start, start + length) - * - * The tests below form a cascade with early returns, so their order is - * significant. */ static int get_reduced_frame_status(WindowAggState *winstate, int64 pos) @@ -4555,30 +4554,35 @@ get_reduced_frame_status(WindowAggState *winstate, int64 pos) int64 start = winstate->rpr_match_start; int64 length = winstate->rpr_match_length; + Assert(pos >= 0); + Assert(start < 0 || length >= -1); + + /* cleared slot: no result recorded yet */ if (start < 0) - return RF_NOT_DETERMINED; /* cleared slot: no result recorded yet */ + return RF_NOT_DETERMINED; /* - * Unmatched (length -1) and empty match (length 0) do not describe a - * positive-length range, so they are classified before the range test. - * Each covers only its own start row; any other position is not part of - * this record and is still undetermined. + * The record's own row: the length gives the verdict directly, and no + * other row can produce any of these three. */ - if (length == -1) - return (pos == start) ? RF_UNMATCHED : RF_NOT_DETERMINED; - if (length == 0) - return (pos == start) ? RF_EMPTY_MATCH : RF_NOT_DETERMINED; + if (pos == start) + { + if (length == -1) + return RF_UNMATCHED; + if (length == 0) + return RF_EMPTY_MATCH; + return RF_FRAME_HEAD; + } /* - * By here length >= 1, so [start, start + length) is a well-formed range. + * Any other row is covered only by a real match, over [start, start + + * length). The sentinels need no special casing: -1 and 0 leave that + * range empty, so every pos != start falls out here. */ if (pos < start || pos >= start + length) return RF_NOT_DETERMINED; - /* pos lies within a real match. */ - if (pos == start) - return RF_FRAME_HEAD; - + /* inside a real match, after its head */ return RF_SKIPPED; } @@ -4640,8 +4644,7 @@ advance_nav_mark(WindowAggState *winstate, int64 currentPos) * evaluations are shared across all active contexts. */ static void -advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, - int64 pos, bool hasLimitedFrame, int64 frameOffset) +advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx) { WindowAggState *winstate = winobj->winstate; int64 currentPos; @@ -4650,11 +4653,12 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, /* * Determine where to start processing. Usually nfaLastProcessedRow+1 >= - * pos since contexts are created at currentPos+1 during processing. - * However, pos can exceed this when rows are skipped (e.g., unmatched - * rows don't update nfaLastProcessedRow). + * matchStartRow since contexts are created at currentPos+1 during + * processing. However, matchStartRow can exceed this when rows are + * skipped (e.g., unmatched rows don't update nfaLastProcessedRow). */ - startPos = Max(pos, winstate->nfaLastProcessedRow + 1); + startPos = Max(targetCtx->matchStartRow, + winstate->nfaLastProcessedRow + 1); /* * Process rows until target context completes or we hit boundaries. Each @@ -4668,8 +4672,6 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, */ for (currentPos = startPos; targetCtx->states != NULL; currentPos++) { - bool rowExists; - /* * Evaluate variables for this row - done only once, shared by all * contexts. @@ -4681,10 +4683,9 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, */ winstate->currentpos = currentPos; winstate->nav_match_start = targetCtx->matchStartRow; - rowExists = rpr_prepare_row(winobj, currentPos, winstate->nfaVarMatched); /* No more rows in partition? Finalize all contexts */ - if (!rowExists) + if (!rpr_prepare_row(winobj, currentPos, winstate->nfaVarMatched)) { ExecRPRFinalizeAllContexts(winstate, currentPos - 1); /* Clean up dead contexts from finalization */ @@ -4701,7 +4702,7 @@ advance_reduced_frame_nfa(WindowObject winobj, RPRNFAContext *targetCtx, * 2. Absorb redundant * 3. Advance all (divergence) */ - ExecRPRProcessRow(winstate, currentPos, hasLimitedFrame, frameOffset); + ExecRPRProcessRow(winstate, currentPos); /* * Create a new context for the next potential start position. This @@ -4742,40 +4743,32 @@ static void update_reduced_frame(WindowObject winobj, int64 pos) { WindowAggState *winstate = winobj->winstate; - RPRNFAContext *targetCtx; - int frameOptions = winstate->frameOptions; - bool hasLimitedFrame; - int64 frameOffset = 0; - int64 matchLen; + RPRNFAContext *targetCtx = NULL; - /* - * Check if we have a limited frame (ROWS ... N FOLLOWING). Each context - * needs its own frame end based on matchStartRow + offset. - */ - hasLimitedFrame = (frameOptions & FRAMEOPTION_ROWS) && - !(frameOptions & FRAMEOPTION_END_UNBOUNDED_FOLLOWING); - if (hasLimitedFrame) - frameOffset = DatumGetInt64(winstate->endOffsetValue); + winstate->rpr_match_start = pos; + winstate->rpr_match_length = -1; - /* - * Case 1: pos is before any existing context's start position. This means - * the position was already processed and determined unmatched. Head is - * the oldest context (lowest matchStartRow) since contexts are added at - * tail with increasing positions. - */ - if (winstate->nfaContext != NULL && - pos < winstate->nfaContext->matchStartRow) + if (winstate->nfaContext != NULL) { - /* already processed, unmatched */ - winstate->rpr_match_start = pos; - winstate->rpr_match_length = -1; - return; + /* + * Case 1: pos is before any existing context's start position. This + * means the position was already processed and determined unmatched. + * Head is the oldest context (lowest matchStartRow) since contexts + * are added at tail with increasing positions. + */ + if (winstate->nfaContext->matchStartRow > pos) + return; + + /* + * Case 2: the head context starts exactly at pos, it holds this row's + * pending result: either still in flight, or already completed by an + * earlier call's driver loop. Later contexts can't apply: the list + * ascends by matchStartRow. + */ + if (winstate->nfaContext->matchStartRow == pos) + targetCtx = winstate->nfaContext; } - /* - * Case 2: Find existing context for this pos, or create new one. - */ - targetCtx = ExecRPRGetHeadContext(winstate, pos); if (targetCtx == NULL) { /* @@ -4784,67 +4777,54 @@ update_reduced_frame(WindowObject winobj, int64 pos) * reprocess. */ if (pos <= winstate->nfaLastProcessedRow) - { - /* already processed, unmatched */ - winstate->rpr_match_start = pos; - winstate->rpr_match_length = -1; return; - } + /* Not yet processed - create new context and start fresh */ targetCtx = ExecRPRStartContext(winstate, pos); } - else if (targetCtx->states == NULL) - { - /* - * The head context already completed in an earlier call. Reachable - * under SKIP TO NEXT ROW, where overlapping contexts let one reach - * FIN -- recording its result -- before the call for its own start - * row arrives. Register that result. - */ - goto register_result; - } - /* Drive the NFA forward until pos's match is resolved. */ - advance_reduced_frame_nfa(winobj, targetCtx, pos, hasLimitedFrame, - frameOffset); - -register_result: + /* + * Either branch above settles targetCtx on pos, which the driver relies + * on to resume from and which the result recorded at the top is keyed by. + */ Assert(pos == targetCtx->matchStartRow); /* - * Record match result. A determined slot has rpr_match_start >= 0; the - * length then gives the kind: -1 unmatched, 0 empty match, >= 1 real - * match. A cleared slot keeps rpr_match_start < 0. + * Drive the NFA forward, unless this context already finished in an + * earlier call. That happens in any skip mode: the driver runs rows on + * behalf of an older context, and an overlapping context can complete + * before the call for its own start row arrives. The result it recorded + * is registered below. */ - winstate->rpr_match_start = targetCtx->matchStartRow; + if (targetCtx->states != NULL) + advance_reduced_frame_nfa(winobj, targetCtx); - if (targetCtx->matchEndRow < targetCtx->matchStartRow) + if (targetCtx->matchedState == NULL) { - matchLen = targetCtx->lastProcessedRow - targetCtx->matchStartRow + 1; - - if (targetCtx->matchedState != NULL) - { - /* Empty match: FIN reached but 0 rows consumed */ - winstate->rpr_match_length = 0; - ExecRPRRecordContextSuccess(winstate, 0); - } - else - { - /* No match */ - winstate->rpr_match_length = -1; - ExecRPRRecordContextFailure(winstate, matchLen); - } - ExecRPRFreeContext(winstate, targetCtx); - return; + /* No match */ + winstate->rpr_match_length = -1; + ExecRPRRecordContextFailure(winstate, + targetCtx->lastProcessedRow - targetCtx->matchStartRow + 1); } + else + { + /* + * Match: an empty one ends at matchStartRow - 1, so the row count + * comes out 0 with no case of its own. Nothing ends earlier than + * that -- FIN either consumes rows or is reached before the first. + */ + Assert(targetCtx->matchEndRow >= targetCtx->matchStartRow - 1); - /* Match succeeded */ - matchLen = targetCtx->matchEndRow - targetCtx->matchStartRow + 1; + winstate->rpr_match_length = + targetCtx->matchEndRow - targetCtx->matchStartRow + 1; - winstate->rpr_match_length = matchLen; - ExecRPRRecordContextSuccess(winstate, matchLen); + ExecRPRRecordContextSuccess(winstate, winstate->rpr_match_length); + } - /* Remove the matched context */ + /* + * The result for pos is recorded; matched or not, this context is + * consumed, so release it. + */ ExecRPRFreeContext(winstate, targetCtx); } @@ -4873,9 +4853,6 @@ rpr_prepare_row(WindowObject winobj, int64 pos, RPRVarMatch *varMatched) ExprContext *econtext = winstate->rprContext; TupleTableSlot *slot; - /* Release the previous row's DEFINE evaluation memory */ - ResetExprContext(econtext); - /* Fetch current row into temp_slot_1 */ slot = winstate->temp_slot_1; if (!window_gettupleslot(winobj, pos, slot)) @@ -4891,9 +4868,8 @@ rpr_prepare_row(WindowObject winobj, int64 pos, RPRVarMatch *varMatched) * Reset the per-row cache to "unevaluated"; each variable's DEFINE is * evaluated lazily at first consumption in nfa_eval_var_match. */ - if (varMatched != NULL) - memset(varMatched, 0, - sizeof(RPRVarMatch) * list_length(winstate->defineClauseExprs)); + memset(varMatched, 0, + sizeof(RPRVarMatch) * list_length(winstate->defineClauseExprs)); return true; /* Row exists */ } diff --git a/src/backend/nodes/queryjumblefuncs.c b/src/backend/nodes/queryjumblefuncs.c index f29cb09e4aa..63bb8bdd710 100644 --- a/src/backend/nodes/queryjumblefuncs.c +++ b/src/backend/nodes/queryjumblefuncs.c @@ -800,14 +800,8 @@ _jumbleWindowClause_defineClause(JumbleState *jstate, _jumbleNode(jstate, (Node *) defineClause); /* Then add the variable names, which TargetEntry.resname hides. */ - foreach_node(TargetEntry, tle, defineClause) - { - if (tle->resname) - AppendJumble(jstate, (const unsigned char *) tle->resname, - strlen(tle->resname) + 1); - else - AppendJumbleNull(jstate); - } + foreach_node(TargetEntry, expr, defineClause) + JUMBLE_STRING(resname); } /* diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 2fc27796af8..f88704e47ec 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -87,11 +87,11 @@ static RPRElemFlags fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth); static void finalizeRPRPattern(RPRPattern *result); -static bool isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, - RPRDepth scopeDepth); -static bool isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx); +static bool isFixedLengthChildren(RPRPattern *pattern, + RPRPatternElement *elem); +static bool isUnboundedStart(RPRPattern *pattern, RPRPatternElement *elem); static void computeAbsorbabilityRecursive(RPRPattern *pattern, - RPRElemIdx startIdx, + RPRPatternElement *elem, bool *hasAbsorbable); static void computeAbsorbability(RPRPattern *pattern); @@ -99,14 +99,12 @@ static void computeAbsorbability(RPRPattern *pattern); * rprPatternEqual * Compare two RPRPatternNode trees for equality. * - * Returns true if the trees are structurally identical. + * Returns true if the trees are structurally identical. Neither argument + * may be NULL: a children list never holds one. */ static bool rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b) { - /* Pattern nodes in children lists must never be NULL */ - Assert(a != NULL && b != NULL); - /* Must have same node type and quantifiers */ if (a->nodeType != b->nodeType) return false; @@ -203,6 +201,8 @@ rprNodeRowCount(RPRPatternNode *node) return -1; return len; } + + pg_unreachable(); return -1; } @@ -1326,13 +1326,15 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * Element layout for (A B){2,3}: * * [BEGIN] [A] [B] [END] [next element...] - * | | ^ - * | +-- jump --+ (loop back to first child) - * +---- jump -------------------+ (skip to after END) - * - * BEGIN.jump points past END (the skip path taken when min == 0; a count is - * only tested at END, so a BEGIN never takes it for reaching max). - * END.jump points to the first child (loop-back path). + * | ^ | | ^ + * | +-- jump ---+ +-next--+ (END.jump: loop back to first child) + * +------- jump ------^ (BEGIN.jump: this group's END) + * + * BEGIN.jump points at the group's own END, so either marker finds the other + * in one step. The skip path taken when min == 0 leaves through END.next + * without arriving at the END: a count is only tested there, so a BEGIN + * never takes the skip for reaching max. END.jump points to the first child + * (loop-back path). * BEGIN.next and END.next are set later by finalizeRPRPattern(). * * Returns the group's empty-match flags. RPR_ELEM_EMPTY_LOOP is set when the @@ -1396,10 +1398,10 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de /* The END carries the body's bits, not the group's; see README IV-4b */ endElem->flags |= bodyFlags; - (*idx)++; + /* Set BEGIN's link to its END (next is set by finalize) */ + beginElem->jump = *idx; - /* Set BEGIN skip pointer (next is set by finalize) */ - beginElem->jump = *idx; /* skip: go to after END */ + (*idx)++; } result = bodyFlags; @@ -1421,7 +1423,7 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de * terminating every alternative (including the last) with a SEP * branch-separator marker. The branch link runs from ALT through the SEP * chain, never through the branch content: a branch's first element may - * itself be a group BEGIN, whose jump is that group's skip-past-END path. + * itself be a group BEGIN, whose jump is that group's END. * * ALT.next -> first branch content SEP.next -> next branch content * ALT.jump -> first SEP (post-ALT on the last) @@ -1547,16 +1549,6 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept pat->elements[endPos].next = afterAltIdx; } - /* - * A branch-terminal group's BEGIN skip-past-END path points at the - * element following the group, which is this branch's SEP; redirect - * it past the alternation too so the skip never lands on a SEP. - */ - for (elemIdx = branchStart; elemIdx <= endPos; elemIdx++) - { - if (pat->elements[elemIdx].jump == sepIdx) - pat->elements[elemIdx].jump = afterAltIdx; - } } list_free(altBranchStarts); @@ -1741,63 +1733,43 @@ finalizeRPRPattern(RPRPattern *result) /* * isFixedLengthChildren - * Check if all children at scopeDepth have fixed-length quantifiers - * (min == max), recursively for nested subgroups. + * Check if every element in elem's scope has a fixed-length + * quantifier (min == max), nested subgroups included. * * A fixed-length group is semantically equivalent to unrolling each child * to {1,1} copies, which is the existing Case 2 already proven correct * for absorption. This check recognizes fixed-length groups at compile * time without actually unrolling them. * - * Traverses the flat element array starting at idx. For VAR elements, - * checks min == max. For BEGIN elements (nested subgroups), recurses - * into the subgroup and also checks the subgroup's END quantifier. - * ALT elements are rejected (alternation inside absorbable group is - * not supported). + * Walks the next chain from elem to the element that closes the enclosing + * group, testing min == max on everything it passes. A group's quantifier + * sits on its BEGIN as well as on its END, so one test per element covers + * a nested subgroup as well, and the walk needs no notion of how deeply + * that subgroup nests: a GROUP{1,1} that tryUnwrapGroup() has not removed + * emits no markers at all, and its children still have to be fixed-length + * for the region to be. ALT elements are rejected (alternation inside an + * absorbable group is not supported). * - * Returns true if all children are fixed-length, stopping at the END - * element at scopeDepth - 1. + * Returns true if every element in the scope is fixed-length. */ static bool -isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth) +isFixedLengthChildren(RPRPattern *pattern, RPRPatternElement *elem) { - RPRPatternElement *e = &pattern->elements[idx]; + RPRDepth scopeDepth = elem->depth; - check_stack_depth(); - - while (e->depth == scopeDepth) + /* FIN bounds the walk where depth cannot, as in isUnboundedStart() */ + for (; elem->depth >= scopeDepth && !RPRElemIsFin(elem); + elem = &pattern->elements[elem->next]) { - if (RPRElemIsVar(e)) - { - if (e->min != e->max) - return false; - } - else if (RPRElemIsBegin(e)) - { - RPRElemIdx childIdx = e->next; - - /* Recurse into subgroup children at scopeDepth + 1 */ - if (!isFixedLengthChildren(pattern, childIdx, scopeDepth + 1)) - return false; + /* FIN is the only element without a successor, and it stopped us */ + Assert(elem->next != RPR_ELEMIDX_INVALID); - /* Advance past the subgroup to its END element */ - e = &pattern->elements[e->next]; - while (e->depth > scopeDepth) - e = &pattern->elements[e->next]; - - /* e is now the END at scopeDepth; check its quantifier */ - Assert(RPRElemIsEnd(e) && e->depth == scopeDepth); - if (e->min != e->max) - return false; - } - else - { - /* ALT inside group: not supported for absorption */ + /* Alternation inside an absorbable group is not supported */ + if (RPRElemIsAlt(elem)) return false; - } - Assert(e->next != RPR_ELEMIDX_INVALID); - e = &pattern->elements[e->next]; + if (elem->min != elem->max) + return false; } return true; @@ -1805,9 +1777,9 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth) /* * isUnboundedStart - * Check if the element at idx starts an unbounded greedy sequence. + * Check if elem starts an unbounded greedy sequence. * - * For context absorption to work, the sequence starting at idx must be: + * For context absorption to work, the sequence starting at elem must be: * - Unbounded (max = infinity) * - Greedy (not reluctant) * - At the start of current scope @@ -1841,14 +1813,13 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth) * computeAbsorbabilityRecursive(), before this function is reached. */ static bool -isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) +isUnboundedStart(RPRPattern *pattern, RPRPatternElement *elem) { - RPRPatternElement *elem = &pattern->elements[idx]; RPRDepth startDepth = elem->depth; RPRPatternElement *e; /* Case 1: Simple unbounded VAR at start (greedy only) */ - if (RPRElemIsVar(elem) && elem->max == RPR_QUANTITY_INF && + if (RPRElemIsVar(elem) && RPRElemIsUnbounded(elem) && !RPRElemIsReluctant(elem)) { /* Set both flags on first element */ @@ -1861,31 +1832,34 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) * have min == max (recursively for nested subgroups), ensuring a fixed * step size per iteration so that count-dominance holds. */ - if (!isFixedLengthChildren(pattern, idx, startDepth)) + if (!isFixedLengthChildren(pattern, elem)) return false; /* - * Find the END that closes the group beginning at idx, at startDepth - 1. - * FIN bounds the walk: depth alone cannot when startDepth is 0, and FIN's - * next is RPR_ELEMIDX_INVALID, so the walk would read outside the array. - * Only a tree optimizeRPRPattern() did not produce reaches it that way. + * Find the END that closes the group, at startDepth - 1. Group markers + * sit at their parent's depth, so the first element shallower than + * startDepth is that END, not a nested subgroup's, which sits at + * startDepth. FIN bounds the walk where depth cannot: at startDepth == 0 + * nothing is shallower and FIN's next would walk off the array. */ - e = &pattern->elements[idx]; + e = elem; while (e->depth >= startDepth && !RPRElemIsFin(e)) e = &pattern->elements[e->next]; /* END must be unbounded greedy */ if (e->depth == startDepth - 1 && - RPRElemIsEnd(e) && e->max == RPR_QUANTITY_INF && + RPRElemIsEnd(e) && RPRElemIsUnbounded(e) && !RPRElemIsReluctant(e)) { - Assert(e->jump == idx); /* END points back to first child */ + RPRPatternElement *endElem = e; + + /* END points back to first child */ + Assert(&pattern->elements[e->jump] == elem); /* Set ABSORBABLE_BRANCH on all children, ABSORBABLE on END only */ - for (e = elem; !RPRElemIsEnd(e) || e->depth >= startDepth; - e = &pattern->elements[e->next]) + for (e = elem; e != endElem; e = &pattern->elements[e->next]) e->flags |= RPR_ELEM_ABSORBABLE_BRANCH; - e->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE; + endElem->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE; return true; } @@ -1894,11 +1868,11 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) /* * computeAbsorbabilityRecursive - * Recursively check absorbability starting from given index. + * Recursively check absorbability starting from the given element. * - * If the element at startIdx is ALT, recursively checks each branch - * independently. Each branch gets its own absorbability status, and if - * any branch is absorbable, the ALT element itself is marked with + * If elem is ALT, recursively checks each branch independently. Each + * branch gets its own absorbability status, and if any branch is + * absorbable, the ALT element itself is marked with * RPR_ELEM_ABSORBABLE_BRANCH. * * If BEGIN, skips to first child -- but only when the group's own @@ -1910,17 +1884,16 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) * isUnboundedStart. */ static void -computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, +computeAbsorbabilityRecursive(RPRPattern *pattern, + RPRPatternElement *elem, bool *hasAbsorbable) { - RPRPatternElement *elem = &pattern->elements[startIdx]; - check_stack_depth(); if (RPRElemIsAlt(elem)) { /* ALT: recursively check each branch via the SEP chain */ - RPRElemIdx branchStart = elem->next; + RPRPatternElement *branch = &pattern->elements[elem->next]; RPRElemIdx sepIdx = elem->jump; while (sepIdx != RPR_ELEMIDX_INVALID) @@ -1929,8 +1902,7 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, bool branchAbsorbable = false; /* Recursively check this branch's content */ - computeAbsorbabilityRecursive(pattern, branchStart, - &branchAbsorbable); + computeAbsorbabilityRecursive(pattern, branch, &branchAbsorbable); if (branchAbsorbable) *hasAbsorbable = true; @@ -1939,7 +1911,7 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, Assert(RPRElemIsSep(sepElem)); /* The last branch's SEP has no link, ending the walk */ - branchStart = sepElem->next; + branch = &pattern->elements[sepElem->next]; sepIdx = sepElem->jump; } @@ -1962,14 +1934,16 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, * B{3}){2})+). If that fails, skip to first child and recurse as * before. */ - if (isUnboundedStart(pattern, elem->next)) + if (isUnboundedStart(pattern, &pattern->elements[elem->next])) { *hasAbsorbable = true; elem->flags |= RPR_ELEM_ABSORBABLE_BRANCH; } else { - computeAbsorbabilityRecursive(pattern, elem->next, hasAbsorbable); + computeAbsorbabilityRecursive(pattern, + &pattern->elements[elem->next], + hasAbsorbable); /* Mark BEGIN element if contents are absorbable */ if (*hasAbsorbable) @@ -1978,11 +1952,14 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, } else { - /* Should never reach END - structural invariant of pattern parse tree */ + /* + * A recursion starts only at the first element of a scope, never an + * END: the BEGIN case above covers a group's body through its END. + */ Assert(!RPRElemIsEnd(elem)); /* Non-ALT, non-BEGIN: check if unbounded start */ - if (isUnboundedStart(pattern, startIdx)) + if (isUnboundedStart(pattern, elem)) *hasAbsorbable = true; } } @@ -2028,7 +2005,7 @@ computeAbsorbability(RPRPattern *pattern) Assert(pattern->numElements >= 2); /* Start recursion from first element */ - computeAbsorbabilityRecursive(pattern, 0, &hasAbsorbable); + computeAbsorbabilityRecursive(pattern, pattern->elements, &hasAbsorbable); pattern->isAbsorbable = hasAbsorbable; } @@ -2078,7 +2055,7 @@ buildRPRPattern(RPRPatternNode *pattern, List *defineClause, /* Parser always assigns a name to each DEFINE entry */ Assert(te->resname != NULL); - varNamesStack[numVars++] = pstrdup(te->resname); + varNamesStack[numVars++] = te->resname; } /* Scan pattern: collect variables, count elements, validate limits */ diff --git a/src/backend/parser/parse_rpr.c b/src/backend/parser/parse_rpr.c index ae03cb30edb..e10260f2f7c 100644 --- a/src/backend/parser/parse_rpr.c +++ b/src/backend/parser/parse_rpr.c @@ -113,6 +113,8 @@ transformRPR(ParseState *pstate, WindowClause *wc, WindowDef *windef, parser_errposition(pstate, location)); } + Assert(wc->frameOptions & FRAMEOPTION_ROWS); + /* Assign AFTER MATCH SKIP TO flag */ wc->rpSkipTo = windef->rpCommonSyntax->rpSkipTo; diff --git a/src/include/executor/execRPR.h b/src/include/executor/execRPR.h index fb7dc63a4c6..265a53efc57 100644 --- a/src/include/executor/execRPR.h +++ b/src/include/executor/execRPR.h @@ -19,13 +19,10 @@ /* NFA context management */ extern RPRNFAContext *ExecRPRStartContext(WindowAggState *winstate, int64 startPos); -extern RPRNFAContext *ExecRPRGetHeadContext(WindowAggState *winstate, - int64 pos); extern void ExecRPRFreeContext(WindowAggState *winstate, RPRNFAContext *ctx); /* NFA processing */ -extern void ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, - bool hasLimitedFrame, int64 frameOffset); +extern void ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos); extern void ExecRPRCleanupDeadContexts(WindowAggState *winstate, RPRNFAContext *excludeCtx); extern void ExecRPRFinalizeAllContexts(WindowAggState *winstate, int64 lastPos); diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 98f0c711d40..40cf83b2350 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2587,7 +2587,15 @@ typedef struct RPRNFAContext int64 matchEndRow; /* last row of the match; below matchStartRow * for an empty one, -1 before any */ int64 lastProcessedRow; /* last row processed (for fail depth) */ - RPRNFAState *matchedState; /* this context's match candidate, or NULL */ + + /* + * The state that reached FIN, or NULL. Its being non-NULL is what + * records a match; matchEndRow cannot, because an empty match ends below + * matchStartRow and would read as a failure. The state itself is never + * read. + */ + RPRNFAState *matchedState; + bool matchUpdated; /* matchedState was set or replaced during the * advance now running */ diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index aa4aa84b3df..db18c9728e6 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -1274,8 +1274,8 @@ typedef struct RPRPatternElement RPRQuantity min; /* quantifier minimum */ RPRQuantity max; /* quantifier maximum */ RPRElemIdx next; /* next element index */ - RPRElemIdx jump; /* ALT/SEP branch link, or GROUP - * skip/loop-back */ + RPRElemIdx jump; /* ALT/SEP branch link; BEGIN: its END; END: + * loop-back to first child */ } RPRPatternElement; /* diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h index 682ed75b48a..0c1e0898397 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -79,6 +79,18 @@ #define RPRElemIsSep(e) ((e)->varId == RPR_VARID_SEP) #define RPRElemIsFin(e) ((e)->varId == RPR_VARID_FIN) #define RPRElemCanSkip(e) ((e)->min == 0) +#define RPRElemIsUnbounded(e) ((e)->max == RPR_QUANTITY_INF) +/* Quantifier tests; a saturated count compares as unbounded */ +#define RPRElemCanLoop(e, count) \ + (RPRElemIsUnbounded(e) || (count) < (e)->max) +#define RPRElemCanExit(e, count) ((count) >= (e)->min) +/* Whether count has stayed inside the bound, not whether it may grow */ +#define RPRElemWithinMax(e, count) \ + (RPRElemIsUnbounded(e) || (count) <= (e)->max) + +/* Count one more iteration, saturating so that int32 cannot overflow */ +#define RPRCountIncrement(count) \ + do { if ((count) < RPR_COUNT_INF) (count)++; } while (0) extern RPRPattern *buildRPRPattern(RPRPatternNode *pattern, List *defineClause, RPSkipTo rpSkipTo, int frameOptions, diff --git a/src/test/regress/expected/rpr.out b/src/test/regress/expected/rpr.out index 7b7524b42ef..c713588c6a3 100644 --- a/src/test/regress/expected/rpr.out +++ b/src/test/regress/expected/rpr.out @@ -1218,6 +1218,16 @@ WINDOW w AS ( DEFINE A AS PREV(price, random()::int) > 0 ); ERROR: DEFINE clause cannot contain volatile functions +-- Non-constant offset: volatile function as compound outer offset +SELECT price FROM stock +WINDOW w AS ( + PARTITION BY company + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + INITIAL + PATTERN (A) + DEFINE A AS PREV(LAST(price, 1), random()::int) > 0 +); +ERROR: DEFINE clause cannot contain volatile functions -- Non-constant offset: subquery as offset SELECT price FROM stock WINDOW w AS ( @@ -3266,6 +3276,46 @@ SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( 6 | 10 | 0 (6 rows) +-- Inner offset overflows int64. The cases above all overflow while applying +-- the outer offset; these two overflow while computing the inner position, +-- before any outer offset is applied. A is false at the first row, so no +-- match starts there and match_start is at least 1 wherever B is evaluated; +-- match_start + INT64_MAX then overflows. With match_start 0 the sum still +-- fits and the clamp below it answers instead. +SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B+) + DEFINE A AS val > 10, B AS FIRST(val, 9223372036854775807) IS NULL +); + id | val | count +----+-----+------- + 1 | 10 | 0 + 2 | 20 | 5 + 3 | 30 | 0 + 4 | 10 | 0 + 5 | 50 | 0 + 6 | 10 | 0 +(6 rows) + +-- The same overflow reached through a compound navigation, where it happens +-- before the outer offset is applied +SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B+) + DEFINE A AS val > 10, B AS NEXT(FIRST(val, 9223372036854775807), 1) IS NULL +); + id | val | count +----+-----+------- + 1 | 10 | 0 + 2 | 20 | 5 + 3 | 30 | 0 + 4 | 10 | 0 + 5 | 50 | 0 + 6 | 10 | 0 +(6 rows) + -- Compound: default offsets on both sides -- PREV(FIRST(val)): inner=0 (match_start), outer=1 -> target = match_start - 1 SELECT id, val, first_value(id) OVER w AS mf, count(*) OVER w AS cnt diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index f2c3cfbbfa6..adcdcaffd7f 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -454,6 +454,67 @@ ORDER BY id; (3 rows) DROP TABLE rpr_lazy; +-- A navigation result carrying a collation. Both forms make the parser ask +-- for the collation of the navigation node itself rather than of its argument. +CREATE TABLE rpr_navcoll (id INT, s TEXT); +INSERT INTO rpr_navcoll VALUES (1, 'a'), (2, 'B'), (3, 'c'); +-- COLLATE applied to the navigation result +SELECT id, s, count(*) OVER w AS cnt +FROM rpr_navcoll +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS PREV(s) COLLATE "C" < s +); + id | s | cnt +----+---+----- + 1 | a | 0 + 2 | B | 0 + 3 | c | 1 +(3 rows) + +-- Simple CASE over the navigation result: the placeholder takes its collation +-- from the tested expression +SELECT id, s, count(*) OVER w AS cnt +FROM rpr_navcoll +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS CASE PREV(s) WHEN 'a' THEN true ELSE false END +); + id | s | cnt +----+---+----- + 1 | a | 0 + 2 | B | 1 + 3 | c | 0 +(3 rows) + +DROP TABLE rpr_navcoll; +-- A system column in a DEFINE expression. It reaches the expression as a +-- scan system attribute rather than an outer Var, and navigation still +-- applies to it: PREV(ctid) is the previous row of the match, not this row. +CREATE TABLE rpr_navsys (i INT); +INSERT INTO rpr_navsys SELECT generate_series(1, 5); +SELECT i, count(*) OVER w AS cnt +FROM rpr_navsys +WINDOW w AS ( + ORDER BY i + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS PREV(ctid) IS DISTINCT FROM ctid +); + i | cnt +---+----- + 1 | 5 + 2 | 0 + 3 | 0 + 4 | 0 + 5 | 0 +(5 rows) + +DROP TABLE rpr_navsys; -- ============================================================ -- FRAME Options Tests -- ============================================================ @@ -4824,6 +4885,22 @@ WINDOW w AS ( ERROR: aggregate functions are not allowed in DEFINE LINE 7: DEFINE A AS COUNT(*) > 0 ^ +-- ERROR: grouping operation in DEFINE is not supported. This shares the +-- EXPR_KIND_RPR_DEFINE arm with the aggregate case above, but takes the +-- GroupingFunc half of it. parseCheckAggregates() relies on this rejection +-- to leave DEFINE out of finalize_grouping_exprs(). +SELECT COUNT(*) OVER w +FROM rpr_err +GROUP BY id +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS GROUPING(id) = 0 +); +ERROR: grouping operations are not allowed in DEFINE +LINE 8: DEFINE A AS GROUPING(id) = 0 + ^ -- ERROR: set-returning function in DEFINE is not supported SELECT FROM rpr_err WINDOW w AS ( ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING PATTERN (A+) DEFINE A AS 1 > generate_series(1 ,2)); @@ -6968,6 +7045,82 @@ WINDOW w AS ( 6 | {A} | | (6 rows) +-- Measuring a group body for absorbability. The optimizer only measures a +-- body an unbounded quantifier wraps, so each pattern below puts the shape +-- under test inside one. None of the three can match real rows; the point is +-- that the measurement reports "not a fixed length" instead of overflowing. +-- A nested group whose repetition count is a range has no fixed length +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A B){1,2} C)+ D) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0, D AS val > 0 +); + id | val | cnt +----+-----+----- + 1 | 10 | 0 + 2 | 20 | 0 + 3 | 30 | 4 + 4 | 40 | 0 + 5 | 50 | 0 + 6 | 60 | 0 + 7 | 70 | 0 + 8 | 80 | 0 + 9 | 90 | 0 + 10 | 100 | 0 +(10 rows) + +-- A fixed repetition whose body length times its count reaches the ceiling +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A B C){1000000000})+ D) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0, D AS val > 0 +); + id | val | cnt +----+-----+----- + 1 | 10 | 0 + 2 | 20 | 0 + 3 | 30 | 0 + 4 | 40 | 0 + 5 | 50 | 0 + 6 | 60 | 0 + 7 | 70 | 0 + 8 | 80 | 0 + 9 | 90 | 0 + 10 | 100 | 0 +(10 rows) + +-- A body whose members sum past the ceiling +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A{2000000000} B{2000000000})+ C) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0 +); + id | val | cnt +----+-----+----- + 1 | 10 | 0 + 2 | 20 | 0 + 3 | 30 | 0 + 4 | 40 | 0 + 5 | 50 | 0 + 6 | 60 | 0 + 7 | 70 | 0 + 8 | 80 | 0 + 9 | 90 | 0 + 10 | 100 | 0 +(10 rows) + -- ALT Both Branches Absorbable: A+ C | B+ -- A+ C never completes (C absent) so its A+ run keeps expanding and dominates; -- a finalized B+ match on the other branch (id=1, id=6) must survive absorption diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index b133a0c99f6..bcb7cecd862 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -6909,6 +6909,169 @@ WINDOW w AS ( 3 | {C} | 3 | 3 (3 rows) +-- (A? | B){1,2} C over the same rows: the lower bound is met by the first +-- iteration, so an empty first iteration via A? stops the loop at once; +-- C fails at row 1 and backtracking takes B, then A, C = rows 1-3, as Perl's +-- (?:a?|b){1,2}c does. This is the first arrival at the group's END, which +-- the cycle guard has to recognize as empty although it has not seen that +-- END before; an engine that misses it keeps the empty iteration and +-- returns rows 1-2 through empty, B, C. +WITH test_728_stop_first_iteration AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){1,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 3 + 2 | {A,C} | 2 | 3 + 3 | {C} | 3 | 3 +(3 rows) + +-- The same with a lower bound of zero, which the standard groups with one. +WITH test_728_stop_first_iteration_min0 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_min0 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){0,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 3 + 2 | {A,C} | 2 | 3 + 3 | {C} | 3 | 3 +(3 rows) + +-- The same under SKIP PAST LAST ROW: rows 2 and 3 fall inside the match. +WITH test_728_stop_first_iteration_past AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_past +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){1,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 3 + 2 | {A,C} | | + 3 | {C} | | +(3 rows) + +-- (B?? | B*){0,2} C: the reluctant first branch goes empty first, which at +-- min 0 stops the loop, and C fails at row 1. Backtracking lets B?? take +-- row 1, the second iteration goes empty and stops, C fails at row 2, so +-- B?? takes row 2 as well and C matches row 3: rows 1-3, as in Perl. +-- Missing the empty first iteration instead lets the loop run again after +-- it, and the match becomes the longer rows 1-4 (empty, then B* over rows +-- 1-3, then C) -- a derivation 7.2.8 excludes. +WITH test_728_stop_first_iteration_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, ARRAY['B','C']), + (4, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((B?? | B*){0,2} C) + DEFINE + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 3 + 2 | {B} | 2 | 3 + 3 | {B,C} | 3 | 3 + 4 | {C} | 4 | 4 +(4 rows) + +-- (A?? | B*){0,2} C: the reluctant empty iteration stops the loop, and +-- backtracking reaches B* over rows 1-2, then A?? taking row 3 in the +-- second iteration and C on row 4: rows 1-4, as in Perl. Missing the empty +-- first iteration returns rows 1-2 instead. +WITH test_728_stop_first_iteration_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B','C']), + (3, ARRAY['A']), + (4, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_mixed +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?? | B*){0,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 4 + 2 | {B,C} | 2 | 2 + 3 | {A} | 3 | 4 + 4 | {C} | 4 | 4 +(4 rows) + -- (A? | B){3} C over the same rows: with an exact bound the two empty -- iterations sit below min, so the loop must continue; the third takes B -- and the match is rows 1-2. Contrast with the {2,3} case above. diff --git a/src/test/regress/sql/rpr.sql b/src/test/regress/sql/rpr.sql index 271ae074340..acb70dd3b5b 100644 --- a/src/test/regress/sql/rpr.sql +++ b/src/test/regress/sql/rpr.sql @@ -604,6 +604,16 @@ WINDOW w AS ( DEFINE A AS PREV(price, random()::int) > 0 ); +-- Non-constant offset: volatile function as compound outer offset +SELECT price FROM stock +WINDOW w AS ( + PARTITION BY company + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + INITIAL + PATTERN (A) + DEFINE A AS PREV(LAST(price, 1), random()::int) > 0 +); + -- Non-constant offset: subquery as offset SELECT price FROM stock WINDOW w AS ( @@ -1933,6 +1943,28 @@ SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( DEFINE A AS NEXT(LAST(val), 9223372036854775807) IS NULL ); +-- Inner offset overflows int64. The cases above all overflow while applying +-- the outer offset; these two overflow while computing the inner position, +-- before any outer offset is applied. A is false at the first row, so no +-- match starts there and match_start is at least 1 wherever B is evaluated; +-- match_start + INT64_MAX then overflows. With match_start 0 the sum still +-- fits and the clamp below it answers instead. +SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B+) + DEFINE A AS val > 10, B AS FIRST(val, 9223372036854775807) IS NULL +); + +-- The same overflow reached through a compound navigation, where it happens +-- before the outer offset is applied +SELECT id, val, count(*) OVER w FROM rpr_nav WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B+) + DEFINE A AS val > 10, B AS NEXT(FIRST(val, 9223372036854775807), 1) IS NULL +); + -- Compound: default offsets on both sides -- PREV(FIRST(val)): inner=0 (match_start), outer=1 -> target = match_start - 1 SELECT id, val, first_value(id) OVER w AS mf, count(*) OVER w AS cnt diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index b3a698889a3..4dfa0a609a2 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -370,6 +370,50 @@ ORDER BY id; DROP TABLE rpr_lazy; +-- A navigation result carrying a collation. Both forms make the parser ask +-- for the collation of the navigation node itself rather than of its argument. +CREATE TABLE rpr_navcoll (id INT, s TEXT); +INSERT INTO rpr_navcoll VALUES (1, 'a'), (2, 'B'), (3, 'c'); + +-- COLLATE applied to the navigation result +SELECT id, s, count(*) OVER w AS cnt +FROM rpr_navcoll +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS PREV(s) COLLATE "C" < s +); + +-- Simple CASE over the navigation result: the placeholder takes its collation +-- from the tested expression +SELECT id, s, count(*) OVER w AS cnt +FROM rpr_navcoll +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS CASE PREV(s) WHEN 'a' THEN true ELSE false END +); + +DROP TABLE rpr_navcoll; + +-- A system column in a DEFINE expression. It reaches the expression as a +-- scan system attribute rather than an outer Var, and navigation still +-- applies to it: PREV(ctid) is the previous row of the match, not this row. +CREATE TABLE rpr_navsys (i INT); +INSERT INTO rpr_navsys SELECT generate_series(1, 5); +SELECT i, count(*) OVER w AS cnt +FROM rpr_navsys +WINDOW w AS ( + ORDER BY i + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS PREV(ctid) IS DISTINCT FROM ctid +); + +DROP TABLE rpr_navsys; + -- ============================================================ -- FRAME Options Tests -- ============================================================ @@ -3122,6 +3166,20 @@ WINDOW w AS ( DEFINE A AS COUNT(*) > 0 ); +-- ERROR: grouping operation in DEFINE is not supported. This shares the +-- EXPR_KIND_RPR_DEFINE arm with the aggregate case above, but takes the +-- GroupingFunc half of it. parseCheckAggregates() relies on this rejection +-- to leave DEFINE out of finalize_grouping_exprs(). +SELECT COUNT(*) OVER w +FROM rpr_err +GROUP BY id +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A+) + DEFINE A AS GROUPING(id) = 0 +); + -- ERROR: set-returning function in DEFINE is not supported SELECT FROM rpr_err WINDOW w AS ( ROWS BETWEEN CURRENT ROW AND 1 FOLLOWING PATTERN (A+) DEFINE A AS 1 > generate_series(1 ,2)); @@ -4161,6 +4219,44 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- Measuring a group body for absorbability. The optimizer only measures a +-- body an unbounded quantifier wraps, so each pattern below puts the shape +-- under test inside one. None of the three can match real rows; the point is +-- that the measurement reports "not a fixed length" instead of overflowing. + +-- A nested group whose repetition count is a range has no fixed length +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A B){1,2} C)+ D) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0, D AS val > 0 +); + +-- A fixed repetition whose body length times its count reaches the ceiling +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A B C){1000000000})+ D) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0, D AS val > 0 +); + +-- A body whose members sum past the ceiling +SELECT id, val, COUNT(*) OVER w AS cnt +FROM rpr_plan +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A{2000000000} B{2000000000})+ C) + DEFINE A AS val <= 30, B AS val > 30, C AS val > 0 +); + -- ALT Both Branches Absorbable: A+ C | B+ -- A+ C never completes (C absent) so its A+ run keeps expanding and dominates; -- a finalized B+ match on the other branch (id=1, id=6) must survive absorption diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 6c2cb3822e0..e6d1d9a11ab 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -5198,6 +5198,137 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- (A? | B){1,2} C over the same rows: the lower bound is met by the first +-- iteration, so an empty first iteration via A? stops the loop at once; +-- C fails at row 1 and backtracking takes B, then A, C = rows 1-3, as Perl's +-- (?:a?|b){1,2}c does. This is the first arrival at the group's END, which +-- the cycle guard has to recognize as empty although it has not seen that +-- END before; an engine that misses it keeps the empty iteration and +-- returns rows 1-2 through empty, B, C. +WITH test_728_stop_first_iteration AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){1,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- The same with a lower bound of zero, which the standard groups with one. +WITH test_728_stop_first_iteration_min0 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_min0 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){0,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- The same under SKIP PAST LAST ROW: rows 2 and 3 fall inside the match. +WITH test_728_stop_first_iteration_past AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_past +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){1,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- (B?? | B*){0,2} C: the reluctant first branch goes empty first, which at +-- min 0 stops the loop, and C fails at row 1. Backtracking lets B?? take +-- row 1, the second iteration goes empty and stops, C fails at row 2, so +-- B?? takes row 2 as well and C matches row 3: rows 1-3, as in Perl. +-- Missing the empty first iteration instead lets the loop run again after +-- it, and the match becomes the longer rows 1-4 (empty, then B* over rows +-- 1-3, then C) -- a derivation 7.2.8 excludes. +WITH test_728_stop_first_iteration_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, ARRAY['B','C']), + (4, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((B?? | B*){0,2} C) + DEFINE + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- (A?? | B*){0,2} C: the reluctant empty iteration stops the loop, and +-- backtracking reaches B* over rows 1-2, then A?? taking row 3 in the +-- second iteration and C on row 4: rows 1-4, as in Perl. Missing the empty +-- first iteration returns rows 1-2 instead. +WITH test_728_stop_first_iteration_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B','C']), + (3, ARRAY['A']), + (4, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_728_stop_first_iteration_mixed +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?? | B*){0,2} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + -- (A? | B){3} C over the same rows: with an exact bound the two empty -- iterations sit below min, so the loop must continue; the third takes B -- and the match is rows 1-2. Contrast with the {2,3} case above. -- 2.54.0 (Apple Git-157)