From c59e3caf19e1324ea17f7d7818d6191b2d0d23c0 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Tue, 14 Jul 2026 18:06:02 +0900 Subject: [PATCH] Fix row pattern preferment and cycle handling in the NFA matcher The NFA matcher violated the preferment rules of ISO/IEC TR 19075-5 7.2 in several ways, and its zero-consumption cycle guard could either kill legitimate matches or recurse without bound. The guard identified a state by elemIdx alone, via a bitmap over all elements. A state is really (elemIdx, counts): looping back into a VAR or a row-consuming body with a higher iteration count is a new state, not a cycle -- (A+|B){2} over an all-A partition needs exactly that, and the guard killed it, losing the match entirely. Only a nullable END can close an iteration without consuming a row, so mark only those; the bitmap becomes nfaVisitedEnds. Reaching a marked END means the body just derived an empty match, and per 7.2.8 an empty iteration at or above the lower bound stops the quantifier, so the guard exits the group there -- at the stop's own preference rank, since discarding the state instead demoted "stop here" below the remaining alternatives and let a less-preferred branch consume rows. Below the bound the quantifier cannot exit, so the guard falls through to the normal loop-back; each empty iteration's arrival increment advances the count, so this reaches the bound in bounded steps. Clearing the marks on loop-back instead would re-arm the guard of a nested reluctant unbounded quantifier, whose empty iterations then recurse until the stack depth limit -- (A (B*?)+?){2,} over a single matching row. Below min, nfa_advance_end() ordered the fast-forward and loop-back paths by the group's own greed, which says nothing when min equals max. In ((A?){2}?) the body A? still prefers to consume a row. Decide the order by the body's preference, computed at compile time and recorded on the END as RPR_ELEM_EMPTY_PREFERRED. Several paths cut less-preferred alternatives once a preferred branch has recorded a match, and detected that by comparing saved ctx->matchedState pointers. State frees go through a LIFO free list, so two replacements within one stretch can hand back the caller's saved address and fool the guard into letting a worse match overwrite a better one. Compare a generation counter bumped on every replacement instead. Exiting a construct is a three-step convention -- clear the exited depth's count slot, recompute isAbsorbable against the target, count the arrival if the target is an END -- that was duplicated at every exit path. Fold it into nfa_exit_to() so the convention has one definition. Also count the iteration when a skip path lands on an outer END, stop the branch walk in nfa_advance_alt() once a branch has matched, and classify an empty match as a match rather than a failure in the NFA statistics. Expected outputs that pinned the wrong preferment now carry the standard's values. The new tests were cross-checked against Trino and against Perl, whose preference rules row pattern recognition follows. --- src/backend/executor/README.rpr | 90 +- src/backend/executor/execRPR.c | 334 +++-- src/backend/executor/nodeWindowAgg.c | 4 +- src/backend/optimizer/plan/rpr.c | 125 +- src/include/nodes/execnodes.h | 5 +- src/include/optimizer/rpr.h | 7 +- src/test/regress/expected/rpr_base.out | 15 +- src/test/regress/expected/rpr_explain.out | 24 +- src/test/regress/expected/rpr_nfa.out | 1562 ++++++++++++++++++++- src/test/regress/sql/rpr_base.sql | 11 +- src/test/regress/sql/rpr_nfa.sql | 1420 +++++++++++++++++-- 11 files changed, 3128 insertions(+), 469 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index f23bbb20076..35fd4ba2b03 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -572,7 +572,7 @@ V-3. RPR Fields of WindowAggState nfaContextFree Reuse pool for contexts nfaStateFree Reuse pool for states nfaVarMatched Per-row cache: varMatched[varId] - nfaVisitedElems Bitmap for cycle detection + nfaVisitedEnds Nullable ENDs reached in this DFS (cycle detection) nfaVisitedMinWord Lowest bitmapword index touched since last reset nfaVisitedMaxWord Highest bitmapword index touched since last reset nfaStateSize Precomputed size of RPRNFAState @@ -646,8 +646,16 @@ the pattern. For example, the initial advance for PATTERN ((A | B) C): Result: Two states in the context {waiting for A, waiting for B} -During the initial advance, reaching FIN is not recorded as a match. -This is to prevent empty matches. +Reaching FIN during the initial advance is recorded like any other +match. Since currentPos is pos - 1, the record has matchEndRow < +matchStartRow: an empty match (RF_EMPTY_MATCH) if matchedState is set, +otherwise unmatched (RF_UNMATCHED). + +The quantifier flavors reach it differently. Reluctant min=0 (A*?, A??): +the skip path reaches FIN first and early termination prunes the enter +paths, so the empty match is final. Greedy (A*): the enter path adds its +VAR states before the skip path records FIN, so those states survive and +may match a longer span on a later row. VI-3. Row Evaluation: rpr_evaluate_row() @@ -984,9 +992,15 @@ so the state added first (= from the preferred branch) is retained. IX-3. Routing Function: nfa_route_to_elem() -All inter-element transitions in the advance phase go through -nfa_route_to_elem(). -This function branches its behavior based on the type of the next element: +Most inter-element transitions in the advance phase go through +nfa_route_to_elem(), but three callers reach nfa_advance_state() +directly: nfa_advance() (each state it pops), nfa_advance_alt() (its +per-branch clone), and nfa_route_to_elem()'s own skip path. The result +matches either way -- for a bypassed VAR, nfa_advance_var()'s count-zero +handling produces what park-and-skip would -- so "a VAR not yet matched" +is handled in two places. + +nfa_route_to_elem() branches on the type of the next element: If the next element is VAR: (1) Add the state to the context (nfa_add_state_unique) @@ -1019,8 +1033,13 @@ IX-4. Per-Element advance Behavior Handles group entry. jump points to the element after END (= first element outside the group). + BEGIN does not reset the count at its depth; it only asserts the slot + is already zero. Under the count-clear policy the previous occupant + of a depth slot clears it on the way out, so entry finds it clean. + See IX-4(c) and V-1. + Greedy (default): - (1) Enter the group body (move via next, reset the count at that depth) + (1) Enter the group body (move via next) (2) If min=0, also add a group skip path (move via jump) Reluctant: @@ -1100,7 +1119,7 @@ explosion. Because DFS order causes preferred-branch states to be added first, identical states from lower-priority branches are automatically discarded. -IX-6. Cycle Detection: nfaVisitedElems +IX-6. Cycle Detection: nfaVisitedEnds When a group body can produce an empty match, looping back from END may cause an infinite loop. @@ -1119,22 +1138,41 @@ To prevent this: resolving the deadlock where count cannot increase due to empty matches. - (2) At runtime: initialize the nfaVisitedElems bitmap immediately before + (2) At runtime: initialize the nfaVisitedEnds bitmap immediately before DFS expansion of each state within advance (once per state). - During DFS, epsilon elements (END, ALT, BEGIN) are marked in the - bitmap at nfa_advance_state entry. VAR elements are marked later - when added to the state list (nfa_add_state_unique), so that - legitimate loop-back to the same VAR in a new group iteration - (e.g., END -> ALT -> same VAR) is not blocked. - If a previously visited elemIdx is revisited, that path is terminated. - - Note: the bitmap tracks only elemIdx and does not consider counts. - Therefore, legitimate revisits to the same elemIdx but with different - counts may also be blocked. This only occurs when the group body is - nullable (all paths can match empty), causing END -> loop-back -> - skip -> END within a single DFS. In such cases the END element has - the RPR_ELEM_EMPTY_LOOP flag, so the fast-forward exit (IX-4(c)) - provides an alternative path that bypasses the cycle. + During DFS, nfa_advance_state marks an END carrying + RPR_ELEM_EMPTY_LOOP on entry, and nothing else. Reaching a marked + END means the body derived an empty match for this iteration -- a + DFS takes only epsilon transitions, so no row was consumed since + the last visit. The state is not discarded: it leaves the group + there, so that "leave the group" keeps its rank among the + alternatives (see IX-4(c)). + + Nothing else is marked, because nothing else can cycle. A revisit is + a cycle only when it carries no progress, and a state is really + (elemIdx, counts) -- the identity nfa_add_state_unique() compares. + A VAR consumes a row, and so does every derivation of a body that + cannot match empty; a loop-back into either is progress, not a cycle. + Marking them would discard legitimate re-entry and lose the match + outright: ((A | B B){1,3}){3} would then find no match at all. + + The guard is min-aware: a marked END exits only at count >= min (an + empty iteration at or above the lower bound stops the quantifier, + TR 19075-5 7.2.8). Below min the guard falls through to the normal + must-loop path instead, so the next iteration still runs and its + consuming branches park as usual -- a derivation that goes empty + first and consumes later stays reachable. This terminates because + every arrival at an END increments its count, so the fall-through + reaches min in bounded steps and then exits through the guard. + + Marks are never cleared during a DFS. An earlier design cleared the + body's marks on each below-min loop-back instead of making the guard + min-aware; that disarmed the guard of any nested reluctant unbounded + quantifier inside the body, whose empty iterations then recursed + without bound -- (A (B*?)+?){2,} on a single matching row exceeded + the stack depth limit. The clear's termination argument ("count + stops at min") assumed the outer count advances, which is exactly + what the nested spin prevents. Chapter X Match Result Processing ============================================================================ @@ -1469,8 +1507,8 @@ XII-5. Execution Optimization Summary the END -> BEGIN loop-back can continue indefinitely. Two mechanisms resolve this: - - A visited bitmap (nfaVisitedElems) blocks revisitation of the - same element, preventing infinite loops (safety) + - A visited bitmap (nfaVisitedEnds) blocks revisitation of the + same nullable END, preventing infinite empty loops (safety) - At an END with the RPR_ELEM_EMPTY_LOOP flag set, when count < min, the remaining required iterations are treated as empty matches and a fast-forward exit path out of the group is @@ -1598,7 +1636,7 @@ Appendix B. Data Structure Relationship Diagram |--- nfaVarMatched: bool[] (per-row cache) |--- defineMatchStartDependent: Bitmapset* (match_start_dependent | DEFINE vars; see VI-4) - |--- nfaVisitedElems: bitmapword* (cycle detection) + |--- nfaVisitedEnds: bitmapword* (cycle detection) |--- nfaVisitedMinWord / nfaVisitedMaxWord: int16 | (touched-word range for fast reset) |--- nfaLastProcessedRow: int64 (-1 = none) diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index fd366dc79bf..7b7dcf975fa 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -41,14 +41,14 @@ /* * Set the visited bit for elemIdx and update the high-water marks * (nfaVisitedMin/MaxWord) so that the next reset only has to clear - * the touched range instead of the full nfaVisitedElems bitmap. + * the touched range instead of the full nfaVisitedEnds bitmap. */ static inline void nfa_mark_visited(WindowAggState *winstate, int16 elemIdx) { int16 w = WORDNUM(elemIdx); - winstate->nfaVisitedElems[w] |= ((bitmapword) 1 << BITNUM(elemIdx)); + winstate->nfaVisitedEnds[w] |= ((bitmapword) 1 << BITNUM(elemIdx)); winstate->nfaVisitedMinWord = Min(winstate->nfaVisitedMinWord, w); winstate->nfaVisitedMaxWord = Max(winstate->nfaVisitedMaxWord, w); } @@ -302,6 +302,42 @@ nfa_state_clone(WindowAggState *winstate, int16 elemIdx, return state; } +/* + * nfa_exit_to + * + * Move state out of the construct owning depth and onto targetIdx, then + * return the target element. Callers route from there. + * + * Centralizes three conventions whose violations are silent: + * + * - Count-clear: zero the exited depth slot so the next occupant enters at + * zero (asserted on entry by nfa_advance_begin/nfa_route_to_elem). + * - Arrival increment: landing on an END completes one iteration + * (saturating at RPR_COUNT_INF). + * - isAbsorbable is recomputed against the target and is monotonic. + * 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) +{ + RPRPattern *pattern = winstate->rpPattern; + RPRPatternElement *nextElem; + + state->counts[depth] = 0; + state->elemIdx = targetIdx; + nextElem = &pattern->elements[targetIdx]; + + state->isAbsorbable = state->isAbsorbable && + RPRElemIsAbsorbableBranch(nextElem); + + if (RPRElemIsEnd(nextElem) && + state->counts[nextElem->depth] < RPR_COUNT_INF) + state->counts[nextElem->depth]++; + + return nextElem; +} + /* * nfa_states_equal * @@ -352,14 +388,6 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState * RPRNFAState *s; RPRNFAState *tail = NULL; - /* - * Mark VAR in visited before duplicate check to prevent DFS loops. This - * is the deferred half of the asymmetric visited-marking scheme; see - * nfa_advance_state for the non-VAR (END/ALT/BEGIN/FIN) half and the - * rationale for the asymmetry. - */ - nfa_mark_visited(winstate, state->elemIdx); - /* Check for duplicate and find tail */ for (s = ctx->states; s != NULL; s = s->next) { @@ -405,6 +433,13 @@ nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, state->next = NULL; ctx->matchEndRow = matchEndRow; + /* + * Guards compare generations, not ctx->matchedState: the free above + * recycles that state, so a later replacement can reuse the address a + * caller saved. + */ + ctx->matchGen++; + /* Prune contexts that started within this match's range */ if (winstate->rpSkipTo == ST_PAST_LAST_ROW) { @@ -415,6 +450,8 @@ nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, { 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); @@ -452,6 +489,7 @@ nfa_context_make(WindowAggState *winstate) ctx->matchEndRow = -1; ctx->lastProcessedRow = -1; ctx->matchedState = NULL; + ctx->matchGen = 0; /* Initialize two-flag absorption design based on pattern */ ctx->hasAbsorbableState = winstate->rpPattern->isAbsorbable; @@ -797,7 +835,8 @@ nfa_eval_var_match(WindowAggState *winstate, RPRPatternElement *elem, * For VARs that reached max count followed by END: * - Advance through the END-element chain to the absorption * comparison point - * - Only deterministic exits (count >= max, max != INF) are handled + * - Only deterministic exits (count >= max) are handled. That test alone + * excludes unbounded VARs: RPR_QUANTITY_INF is PG_INT32_MAX. * - Chains through END elements while count >= max (must-exit path) * * Non-VAR elements (ALT, END, FIN) are kept as-is for advance phase. @@ -976,12 +1015,27 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, /* Create skip state before add_unique, which may free state */ if (RPRElemCanSkip(nextElem)) + { + RPRPatternElement *landElem; + skipState = nfa_state_clone(winstate, nextElem->next, state->counts, state->isAbsorbable); + /* + * When the skip lands directly on an outer END, increment its + * iteration count, just as the exit path in nfa_advance_var does. + * Without this the skipped iteration is not counted, and the + * group fails its min check even though it ran often enough. + */ + landElem = &winstate->rpPattern->elements[skipState->elemIdx]; + if (RPRElemIsEnd(landElem) && + skipState->counts[landElem->depth] < RPR_COUNT_INF) + skipState->counts[landElem->depth]++; + } + if (skipState != NULL && RPRElemIsReluctant(nextElem)) { - RPRNFAState *savedMatch = ctx->matchedState; + int64 savedGen = ctx->matchGen; /* * Reluctant optional VAR: prefer skipping. Explore the skip path @@ -992,7 +1046,7 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, */ nfa_advance_state(winstate, ctx, skipState, currentPos); - if (ctx->matchedState != savedMatch) + if (ctx->matchGen != savedGen) { nfa_state_free(winstate, state); return; @@ -1040,6 +1094,7 @@ nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, { RPRPatternElement *sepElem; RPRNFAState *newState; + int64 savedGen = ctx->matchGen; /* Create independent state at this branch's content */ newState = nfa_state_clone(winstate, brStart, @@ -1048,6 +1103,15 @@ nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, /* Recursively process this branch before the next */ nfa_advance_state(winstate, ctx, newState, currentPos); + /* + * Branches are enumerated in preference order, so once one of them + * has recorded a match the later branches must not be explored: their + * own FIN would replace the preferred match. Same technique as the + * reluctant paths in nfa_route_to_elem and nfa_advance_begin. + */ + if (ctx->matchGen != savedGen) + break; + /* The walk never lands on -1: the last SEP breaks the loop below */ Assert(sepIdx >= 0 && sepIdx < pattern->numElements); sepElem = &elements[sepIdx]; @@ -1089,13 +1153,24 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, /* Optional group: create skip path (but don't route yet) */ if (elem->min == 0) { + RPRPatternElement *landElem; + skipState = nfa_state_clone(winstate, elem->jump, 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]++; } if (skipState != NULL && RPRElemIsReluctant(elem)) { - RPRNFAState *savedMatch = ctx->matchedState; + int64 savedGen = ctx->matchGen; /* Reluctant: skip first (prefer fewer iterations), enter second */ nfa_route_to_elem(winstate, ctx, skipState, @@ -1105,7 +1180,7 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, * If skip path reached FIN, shortest match is found. Skip group entry * to prevent longer matches. */ - if (ctx->matchedState != savedMatch) + if (ctx->matchGen != savedGen) { nfa_state_free(winstate, state); return; @@ -1169,11 +1244,13 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, * Route to elem->next (not nfa_advance_end) to avoid creating * competing greedy/reluctant loop states. * - * Greedy prefers the loop-back first (more iterations); reluctant - * prefers the fast-forward (exit) first and, if it reaches FIN, drops - * the loop-back so a longer match cannot replace the shortest one -- - * mirroring the min<=countelemIdx, state->counts, state->isAbsorbable); - /* Exit the group: clear its own count (count-clear policy) */ - ffState->counts[depth] = 0; - ffState->elemIdx = elem->next; - nextElem = &elements[ffState->elemIdx]; - /* - * Unlike the must-exit path, no isAbsorbable update is needed: - * the fast-forward path runs only for EMPTY_LOOP (nullable) - * groups, which are never inside an absorbable region, so - * isAbsorbable is already false here. + * nfa_exit_to()'s isAbsorbable recompute is a no-op here: + * EMPTY_LOOP groups are never in an absorbable region. */ - - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && - ffState->counts[nextElem->depth] < RPR_COUNT_INF) - ffState->counts[nextElem->depth]++; + nextElem = nfa_exit_to(winstate, ffState, depth, elem->next); } - /* Prepare the loop-back state */ + /* + * Prepare the loop-back state. Visited marks are deliberately left + * in place: the cycle guard falls through for a marked END below its + * lower bound, so the next iteration still runs (and may consume), + * while a cleared mark would re-arm nested reluctant loops into + * unbounded epsilon recursion. + */ state->elemIdx = elem->jump; jumpElem = &elements[state->elemIdx]; - if (ffState != NULL && RPRElemIsReluctant(elem)) + if (ffState != NULL && RPRElemIsEmptyPreferred(elem)) { - RPRNFAState *savedMatch = ctx->matchedState; + int64 savedGen = ctx->matchGen; - /* Reluctant: take the fast-forward (exit) first */ + /* Body prefers empty: take the fast-forward (exit) first */ nfa_route_to_elem(winstate, ctx, ffState, nextElem, currentPos); @@ -1215,7 +1287,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, * If the exit reached FIN, the shortest match is found. Skip the * loop-back to prevent longer matches from replacing it. */ - if (ctx->matchedState != savedMatch) + if (ctx->matchGen != savedGen) { nfa_state_free(winstate, state); return; @@ -1240,18 +1312,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, /* Must exit: reached max iterations. */ RPRPatternElement *nextElem; - /* Exit: clear the group's own count (count-clear policy) */ - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; - - /* Update isAbsorbable for target element (monotonic) */ - state->isAbsorbable = state->isAbsorbable && - RPRElemIsAbsorbableBranch(nextElem); - - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && state->counts[nextElem->depth] < RPR_COUNT_INF) - state->counts[nextElem->depth]++; + nextElem = nfa_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); } @@ -1272,13 +1333,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, */ exitState = nfa_state_clone(winstate, elem->next, state->counts, state->isAbsorbable); - /* Exit branch: clear the group's own count (count-clear policy) */ - exitState->counts[depth] = 0; - nextElem = &elements[exitState->elemIdx]; - - /* END->END: increment outer END's count */ - if (RPRElemIsEnd(nextElem) && exitState->counts[nextElem->depth] < RPR_COUNT_INF) - exitState->counts[nextElem->depth]++; + nextElem = nfa_exit_to(winstate, exitState, depth, elem->next); /* Prepare loop state */ state->elemIdx = elem->jump; @@ -1286,7 +1341,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, if (RPRElemIsReluctant(elem)) { - RPRNFAState *savedMatch = ctx->matchedState; + int64 savedGen = ctx->matchGen; /* Exit first (preferred for reluctant) */ nfa_route_to_elem(winstate, ctx, exitState, nextElem, @@ -1296,7 +1351,7 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, * If exit path reached FIN, shortest match is found. Skip loop to * prevent longer matches from replacing it. */ - if (ctx->matchedState != savedMatch) + if (ctx->matchGen != savedGen) { nfa_state_free(winstate, state); return; @@ -1330,7 +1385,6 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) { RPRPattern *pattern = winstate->rpPattern; - RPRPatternElement *elements = pattern->elements; int depth = elem->depth; int32 count = state->counts[depth]; bool canLoop = (elem->max == RPR_QUANTITY_INF || count < elem->max); @@ -1358,21 +1412,12 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, */ if (reluctant) { - RPRNFAState *savedMatch = ctx->matchedState; + int64 savedGen = ctx->matchGen; /* Clone for exit, original stays for loop */ cloneState = nfa_state_clone(winstate, elem->next, state->counts, state->isAbsorbable); - /* Exit: clear the VAR's own count (count-clear policy) */ - cloneState->counts[depth] = 0; - nextElem = &elements[cloneState->elemIdx]; - - /* When exiting directly to an outer END, increment its count */ - if (RPRElemIsEnd(nextElem)) - { - if (cloneState->counts[nextElem->depth] < RPR_COUNT_INF) - cloneState->counts[nextElem->depth]++; - } + nextElem = nfa_exit_to(winstate, cloneState, depth, elem->next); /* Exit first (preferred for reluctant) */ nfa_route_to_elem(winstate, ctx, cloneState, nextElem, @@ -1382,7 +1427,7 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, * If exit path reached FIN, the shortest match is found. Skip * loop state to prevent longer matches from replacing it. */ - if (ctx->matchedState != savedMatch) + if (ctx->matchGen != savedGen) { nfa_state_free(winstate, state); return; @@ -1400,28 +1445,8 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, /* Loop first (preferred for greedy) */ nfa_add_state_unique(winstate, ctx, cloneState); - /* Exit second: clear the VAR's own count (count-clear policy) */ - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; - - /* - * Update isAbsorbable for target element (monotonic: AND - * preserves false) - */ - state->isAbsorbable = state->isAbsorbable && - RPRElemIsAbsorbableBranch(nextElem); - - /* - * When exiting directly to an outer END, increment its iteration - * count. Simple VARs (min=max=1) handle this via inline advance - * in nfa_match, but quantified VARs bypass that path. - */ - if (RPRElemIsEnd(nextElem)) - { - if (state->counts[nextElem->depth] < RPR_COUNT_INF) - state->counts[nextElem->depth]++; - } + /* Exit second: nfa_match handles only deterministic exits */ + nextElem = nfa_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); @@ -1438,24 +1463,7 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, RPRPatternElement *nextElem; Assert(canExit); - /* Exit: clear the VAR's own count (count-clear policy) */ - state->counts[depth] = 0; - state->elemIdx = elem->next; - nextElem = &elements[state->elemIdx]; - - /* - * Update isAbsorbable for target element (monotonic: AND preserves - * false) - */ - state->isAbsorbable = state->isAbsorbable && - RPRElemIsAbsorbableBranch(nextElem); - - /* See comment above: increment outer END count for quantified VARs */ - if (RPRElemIsEnd(nextElem)) - { - if (state->counts[nextElem->depth] < RPR_COUNT_INF) - state->counts[nextElem->depth]++; - } + nextElem = nfa_exit_to(winstate, state, depth, elem->next); nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); } @@ -1479,23 +1487,61 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, /* Protect against stack overflow for deeply complex patterns */ check_stack_depth(); - /* Cycle detection: if this elemIdx was already visited in this DFS, bail */ - if (winstate->nfaVisitedElems[WORDNUM(state->elemIdx)] & + /* + * Cycle detection. Only a nullable END is marked, so a set bit means the + * body just derived an empty match for this iteration: a DFS takes only + * epsilon transitions, so no row was consumed since the last visit. + * + * Nothing else needs guarding. A revisit is a cycle only when it carries + * no progress, and a state is really (elemIdx, counts) -- which is what + * nfa_add_state_unique() compares. Any other loop-back has consumed a + * row, and dropping it would lose the match outright: ((A | B B){1,3}){3} + * then finds nothing at all. + */ + if (winstate->nfaVisitedEnds[WORDNUM(state->elemIdx)] & ((bitmapword) 1 << BITNUM(state->elemIdx))) { - nfa_state_free(winstate, state); - return; + RPRPatternElement *hitElem = &pattern->elements[state->elemIdx]; + + Assert(RPRElemIsEnd(hitElem) && RPRElemCanEmptyLoop(hitElem)); + + if (state->counts[hitElem->depth] >= hitElem->min) + { + RPRPatternElement *nextElem; + + /* An END always has a valid exit target after finalization. */ + Assert(hitElem->next != RPR_ELEMIDX_INVALID); + + /* + * Leave the group here, and enumerate that exit at this rank + * rather than discarding the state: discarding demotes "leave the + * group" below the remaining alternatives, and a less-preferred + * branch then consumes rows the match should not have. At or + * above the lower bound an empty iteration stops the quantifier + * (SQL/RPR follows Perl here). + */ + + nextElem = nfa_exit_to(winstate, state, hitElem->depth, + hitElem->next); + + nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos); + return; + } + + /* + * Below the lower bound the quantifier cannot exit, so fall through + * to the normal must-loop path. Each empty iteration's arrival + * increment advances the count, so this reaches min and exits above. + * Clearing the marks here instead would also disarm the guard for + * nested reluctant loops, whose empty iterations then recurse without + * bound: (A (B*?)+?){2,} on a single matching row. + */ } elem = &pattern->elements[state->elemIdx]; - /* - * Mark epsilon elements (END, ALT, BEGIN, FIN) in visited to prevent - * infinite epsilon cycles. VAR elements are marked later when added to - * the state list (nfa_add_state_unique), allowing legitimate loop-back to - * the same VAR in a new iteration. - */ - if (!RPRElemIsVar(elem)) + /* Only a nullable END is ever tested; see the guard above. */ + if (RPRElemCanEmptyLoop(elem)) nfa_mark_visited(winstate, state->elemIdx); /* @@ -1547,7 +1593,7 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) { RPRNFAState *states = ctx->states; RPRNFAState *state; - RPRNFAState *savedMatchedState; + int64 savedGen; ctx->states = NULL; /* Will rebuild */ @@ -1555,7 +1601,7 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) while (states != NULL) { CHECK_FOR_INTERRUPTS(); - savedMatchedState = ctx->matchedState; + savedGen = ctx->matchGen; /* * Clear visited bitmap before each state's DFS expansion. Only the @@ -1567,7 +1613,7 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) */ if (winstate->nfaVisitedMaxWord >= winstate->nfaVisitedMinWord) { - memset(&winstate->nfaVisitedElems[winstate->nfaVisitedMinWord], 0, + memset(&winstate->nfaVisitedEnds[winstate->nfaVisitedMinWord], 0, sizeof(bitmapword) * (winstate->nfaVisitedMaxWord - winstate->nfaVisitedMinWord + 1)); @@ -1595,7 +1641,7 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) * remaining old states have worse lexical order and can be pruned. * Only check for new FIN arrivals (not ones from previous rows). */ - if (ctx->matchedState != savedMatchedState && states != NULL) + if (ctx->matchGen != savedGen && states != NULL) { nfa_state_free_list(winstate, states); break; @@ -1709,8 +1755,8 @@ ExecRPRStartContext(WindowAggState *winstate, int64 startPos) * first row's match phase. * * Use startPos - 1 as currentPos since no row has been consumed yet. If - * FIN is reached via epsilon transitions, matchEndRow = startPos - 1 - * which is less than matchStartRow, resulting in UNMATCHED treatment. + * FIN is reached via epsilon transitions, matchEndRow = startPos - 1, + * which is how an empty match is represented. */ nfa_advance(winstate, ctx, startPos - 1); @@ -1867,7 +1913,14 @@ ExecRPRProcessRow(WindowAggState *winstate, int64 currentPos, * If this context has a different matchStartRow than the one used in * the shared evaluation, re-evaluate match_start-dependent variables * with this context's matchStartRow. + * + * Re-evaluation overwrites nfaVarMatched without restoring it, so the + * head context, which the shared values are keyed on, must be reached + * before any other. */ + 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_match(winstate, ctx, varMatched, currentPos); @@ -1946,8 +1999,13 @@ ExecRPRCleanupDeadContexts(WindowAggState *winstate, RPRNFAContext *excludeCtx) if (ctx == excludeCtx || ctx->states != NULL) continue; - /* Skip successfully matched contexts (will be handled by SKIP logic) */ - if (ctx->matchEndRow >= ctx->matchStartRow) + /* + * Skip contexts that recorded a match (handled by SKIP logic). Test + * matchedState, not matchEndRow: an empty match ends at matchStartRow + * - 1, so a row-length test would take it for a failure and count it + * as pruned or mismatched. + */ + if (ctx->matchedState != NULL) continue; /* @@ -1984,10 +2042,12 @@ ExecRPRCleanupDeadContexts(WindowAggState *winstate, RPRNFAContext *excludeCtx) * matchEndRow >= matchStartRow): a match has been recorded and VAR * states are still looping for a longer one. * - * Killing the VAR reclassifies the first two as failures in cleanup - * (otherwise they linger without contributing to stats). The third is - * stat-neutral -- cleanup skips it either way -- but goes through the - * same uniform path so partition-end classification stays centralized. + * Killing the VAR reclassifies pure pursuit as a failure in cleanup + * (otherwise it lingers without contributing to stats). The other two both + * carry a recorded match, so cleanup skips them: an empty match is a + * length-0 success, not a failure, and update_reduced_frame registers it as + * such through its head-context path. They still go through the same + * uniform path so partition-end classification stays centralized. * * Implementation: nfa_match with NULL forces VAR mismatch; nfa_advance * then drains any remaining epsilon transitions. @@ -2004,6 +2064,8 @@ ExecRPRFinalizeAllContexts(WindowAggState *winstate, int64 lastPos) if (ctx->states != NULL) { nfa_match(winstate, ctx, NULL, lastPos); + + /* Defensive: advance leaves only VAR states, all removed above. */ nfa_advance(winstate, ctx, lastPos); } } diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 0ca09c8d4ad..5d3c6bccd58 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -3058,8 +3058,8 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) sizeof(int32) * node->rpPattern->maxDepth; nfaVisitedNWords = (node->rpPattern->numElements - 1) / BITS_PER_BITMAPWORD + 1; - winstate->nfaVisitedElems = palloc0(sizeof(bitmapword) * - nfaVisitedNWords); + winstate->nfaVisitedEnds = palloc0(sizeof(bitmapword) * + nfaVisitedNWords); /* High-water mark sentinels: no bits set yet. */ winstate->nfaVisitedMinWord = PG_INT16_MAX; winstate->nfaVisitedMaxWord = -1; diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 9f481e0daab..ca4df386e61 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -74,14 +74,14 @@ static void scanRPRPattern(RPRPatternNode *node, char **varNames, int *numVars, static RPRPattern *makeRPRPattern(int numVars, int numElements, RPRDepth maxDepth, char **varNamesStack); static RPRVarId getVarIdFromPattern(RPRPattern *pat, const char *varName); -static bool fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, - int *idx, RPRDepth depth); -static bool fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, - int *idx, RPRDepth depth); -static bool fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, - int *idx, RPRDepth depth); -static bool fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, - int *idx, RPRDepth depth); +static RPRElemFlags fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static RPRElemFlags fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static RPRElemFlags fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static RPRElemFlags fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); static void finalizeRPRPattern(RPRPattern *result); static bool isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, @@ -1247,12 +1247,16 @@ getVarIdFromPattern(RPRPattern *pat, const char *varName) * fillRPRPatternVar * Fill a VAR pattern element. * - * Returns true if this VAR is nullable (can match zero rows). + * Returns the empty-match flags for this VAR: RPR_ELEM_EMPTY_LOOP when it is + * nullable (min 0, can match zero rows), plus RPR_ELEM_EMPTY_PREFERRED when its + * preferred derivation is the empty one. A bare variable consumes a row; only + * a reluctant quantifier that may take zero repetitions prefers to skip it. */ -static bool +static RPRElemFlags fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { RPRPatternElement *elem = &pat->elements[*idx]; + RPRElemFlags flags = 0; memset(elem, 0, sizeof(RPRPatternElement)); elem->varId = getVarIdFromPattern(pat, node->varName); @@ -1267,7 +1271,14 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept elem->flags |= RPR_ELEM_RELUCTANT; (*idx)++; - return (node->min == 0); + if (node->min == 0) + { + /* nullable; a reluctant quantifier also prefers the empty match */ + flags |= RPR_ELEM_EMPTY_LOOP; + if (node->reluctant) + flags |= RPR_ELEM_EMPTY_PREFERRED; + } + return flags; } /* @@ -1288,16 +1299,20 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * END.jump points to the first child (loop-back path). * BEGIN.next and END.next are set later by finalizeRPRPattern(). * - * Returns true if this group is nullable. A group is nullable when its - * min is 0 (can be skipped entirely) or its body is nullable (every path - * through the body can match zero rows). + * Returns the group's empty-match flags. RPR_ELEM_EMPTY_LOOP is set when the + * group is nullable -- its min is 0 (can be skipped entirely) or its body is + * nullable (every path through the body can match zero rows). + * RPR_ELEM_EMPTY_PREFERRED is set when the group's preferred derivation is + * empty: a reluctant min-0 group prefers to take no iteration, and otherwise + * the group follows its body. The END element inherits the body's bits. */ -static bool +static RPRElemFlags fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { int groupStartIdx = *idx; int beginIdx = -1; - bool bodyNullable = true; + RPRElemFlags bodyFlags = RPR_ELEM_EMPTY_LOOP | RPR_ELEM_EMPTY_PREFERRED; + RPRElemFlags result; /* Add BEGIN marker if group has non-trivial quantifier (not {1,1}) */ if (node->min != 1 || node->max != 1) @@ -1320,11 +1335,9 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de groupStartIdx = *idx; /* children start after BEGIN */ } + /* A concatenation is nullable / empty-preferred iff every child is (AND) */ foreach_node(RPRPatternNode, child, node->children) - { - if (!fillRPRPattern(child, pat, idx, depth + 1)) - bodyNullable = false; - } + bodyFlags &= fillRPRPattern(child, pat, idx, depth + 1); /* Add group end marker if group has non-trivial quantifier (not {1,1}) */ if (node->min != 1 || node->max != 1) @@ -1345,12 +1358,15 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de endElem->flags |= RPR_ELEM_RELUCTANT; /* - * If the group body is nullable, mark the END element so that - * nfa_advance_end can fast-forward the iteration count to min when - * reached via empty-match skip paths. + * The END inherits the body's empty-match bits. A nullable body + * (EMPTY_LOOP) lets nfa_advance_end fast-forward the iteration count + * to min via empty-match skip paths; an empty-preferred body + * (EMPTY_PREFERRED) orders that fast-forward ahead of the loop-back + * below min. The group's own greed cannot decide the latter: in + * ((A?){2}?) min = max, so the group's greed is meaningless while the + * body A? still prefers to consume a row. */ - if (bodyNullable) - endElem->flags |= RPR_ELEM_EMPTY_LOOP; + endElem->flags |= bodyFlags; (*idx)++; @@ -1358,7 +1374,15 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de beginElem->jump = *idx; /* skip: go to after END */ } - return (node->min == 0 || bodyNullable); + result = bodyFlags; + if (node->min == 0) + { + /* skippable entirely; if reluctant, the group prefers to skip */ + result |= RPR_ELEM_EMPTY_LOOP; + if (node->reluctant) + result |= RPR_ELEM_EMPTY_PREFERRED; + } + return result; } /* @@ -1381,10 +1405,13 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de * element, so SEP markers are compile-time boundaries only and are never a * runtime state position. * - * Returns true if any branch is nullable (OR semantics: one nullable - * branch suffices for the alternation to produce an empty match). + * Returns the alternation's empty-match flags. RPR_ELEM_EMPTY_LOOP is set if + * any branch is nullable (OR: one nullable branch suffices). + * RPR_ELEM_EMPTY_PREFERRED follows the first branch alone: lexicographic order + * makes it the preferred one, so whether the later branches prefer empty does + * not matter. */ -static bool +static RPRElemFlags fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { ListCell *lc; @@ -1396,7 +1423,10 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept List *altEndPositions = NIL; List *altSepIdxs = NIL; int afterAltIdx; - bool anyNullable = false; + RPRElemFlags altFlags = 0; /* OR of branch EMPTY_LOOP bits */ + RPRElemFlags firstFlags = 0; /* first branch's flags (for + * EMPTY_PREFERRED) */ + bool firstBranch = true; /* Add alternation start marker */ elem = &pat->elements[*idx]; @@ -1418,10 +1448,18 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept int branchStart = *idx; int sepIdx; RPRPatternElement *sep; + RPRElemFlags branchFlags; altBranchStarts = lappend_int(altBranchStarts, branchStart); - if (fillRPRPattern(alt, pat, idx, depth + 1)) - anyNullable = true; + branchFlags = fillRPRPattern(alt, pat, idx, depth + 1); + + /* nullable if ANY branch is; empty-preferred per the FIRST branch */ + altFlags |= (branchFlags & RPR_ELEM_EMPTY_LOOP); + if (firstBranch) + { + firstFlags = branchFlags; + firstBranch = false; + } altEndPositions = lappend_int(altEndPositions, *idx - 1); /* SEP terminates this branch */ @@ -1505,7 +1543,7 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept list_free(altBranchStarts); list_free(altEndPositions); - return anyNullable; + return altFlags | (firstFlags & RPR_ELEM_EMPTY_PREFERRED); } /* @@ -1516,14 +1554,14 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * array. * Dispatches to type-specific fill functions. * - * Returns true if the pattern is nullable (can match zero rows). - * For SEQ nodes, all children must be nullable (AND). + * Returns the pattern's empty-match flags (RPR_ELEM_EMPTY_LOOP for nullable, + * RPR_ELEM_EMPTY_PREFERRED for empty-preferred). For a SEQ, a concatenation is + * nullable / empty-preferred only when every child is, so the children's flags + * are AND-ed together. */ -static bool +static RPRElemFlags fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { - bool allNullable = true; - /* Pattern nodes from parser are never NULL */ Assert(node != NULL); @@ -1532,12 +1570,13 @@ fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) switch (node->nodeType) { case RPR_PATTERN_SEQ: - foreach_node(RPRPatternNode, child, node->children) { - if (!fillRPRPattern(child, pat, idx, depth)) - allNullable = false; + RPRElemFlags flags = RPR_ELEM_EMPTY_LOOP | RPR_ELEM_EMPTY_PREFERRED; + + foreach_node(RPRPatternNode, child, node->children) + flags &= fillRPRPattern(child, pat, idx, depth); + return flags; } - return allNullable; case RPR_PATTERN_VAR: return fillRPRPatternVar(node, pat, idx, depth); @@ -1550,7 +1589,7 @@ fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) } pg_unreachable(); - return false; + return 0; } /* diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index d6ac6b229ca..f8c95b76ed2 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2571,6 +2571,7 @@ typedef struct RPRNFAContext int64 matchEndRow; /* row where match ended (-1 = no match) */ int64 lastProcessedRow; /* last row processed (for fail depth) */ RPRNFAState *matchedState; /* FIN state for greedy fallback (cloned) */ + int64 matchGen; /* bumped on every matchedState replacement */ /* Two-flag absorption optimization */ bool hasAbsorbableState; /* can absorb others (>=1 absorbable @@ -2669,8 +2670,8 @@ typedef struct WindowAggState Bitmapset *defineMatchStartDependent; /* DEFINE vars needing per-context * evaluation * (match_start-dependent) */ - bitmapword *nfaVisitedElems; /* elemIdx visited bitmap for cycle - * detection */ + bitmapword *nfaVisitedEnds; /* nullable ENDs reached in this DFS, indexed + * by elemIdx (cycle detection) */ int16 nfaVisitedMinWord; /* lowest bitmapword index touched since * last reset (PG_INT16_MAX = none) */ int16 nfaVisitedMaxWord; /* highest bitmapword index touched since diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h index d4d5928b739..947e939161a 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -54,18 +54,21 @@ * quantifier */ #define RPR_ELEM_EMPTY_LOOP 0x02 /* END: group body can produce * empty match */ +#define RPR_ELEM_EMPTY_PREFERRED 0x04 /* END: group body prefers the + * empty match */ /* * The two absorption flags below are explained in README.rpr IV-5 * ("Absorbability Analysis"), with worked examples in Appendix C; the * analysis that sets them is computeAbsorbability() in * optimizer/plan/rpr.c. */ -#define RPR_ELEM_ABSORBABLE_BRANCH 0x04 /* element in absorbable region */ -#define RPR_ELEM_ABSORBABLE 0x08 /* absorption comparison point */ +#define RPR_ELEM_ABSORBABLE_BRANCH 0x08 /* element in absorbable region */ +#define RPR_ELEM_ABSORBABLE 0x10 /* absorption comparison point */ /* Accessor macros for RPRPatternElement */ #define RPRElemIsReluctant(e) (((e)->flags & RPR_ELEM_RELUCTANT) != 0) #define RPRElemCanEmptyLoop(e) (((e)->flags & RPR_ELEM_EMPTY_LOOP) != 0) +#define RPRElemIsEmptyPreferred(e) (((e)->flags & RPR_ELEM_EMPTY_PREFERRED) != 0) #define RPRElemIsAbsorbableBranch(e) (((e)->flags & RPR_ELEM_ABSORBABLE_BRANCH) != 0) #define RPRElemIsAbsorbable(e) (((e)->flags & RPR_ELEM_ABSORBABLE) != 0) #define RPRElemIsVar(e) ((e)->varId <= RPR_VARID_MAX) diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index af78ae737fe..d9b73464690 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -3630,11 +3630,12 @@ SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_dp_struct'), E'\n')) DROP VIEW rpr_dp_struct; -- Execution semantics (deparse cannot show reluctant shortest-match). The --- rpr_glue rows -- an A-run followed by B rows -- make the '|B' alternative --- reachable: with "*" the greedy form matches the whole run while the --- reluctant form matches empty; with "+" the greedy form matches the run and --- the reluctant form matches one row, and on a B row (where "A+" fails) the B --- alternative fires. +-- rpr_glue rows -- an A-run followed by B rows -- show when the '|B' +-- alternative is reachable. With "*" the first branch always succeeds, so B +-- never fires: the greedy form matches the whole run and the reluctant form +-- matches empty, and on a B row the empty match still outranks B. With "+" +-- the first branch fails on a B row, so there the B alternative fires; on an +-- A row the greedy form matches the run and the reluctant form one row. SELECT id, val, count(*) OVER gs AS gstar, count(*) OVER rs AS rstar, count(*) OVER gp AS gplus, count(*) OVER rp AS rplus @@ -3649,9 +3650,9 @@ ORDER BY id; 1 | 5 | 3 | 0 | 3 | 1 2 | 8 | 0 | 0 | 0 | 1 3 | 9 | 0 | 0 | 0 | 1 - 4 | -1 | 1 | 1 | 1 | 1 + 4 | -1 | 0 | 0 | 1 | 1 5 | 6 | 1 | 0 | 1 | 1 - 6 | -2 | 1 | 1 | 1 | 1 + 6 | -2 | 0 | 0 | 1 | 1 (6 rows) -- Patterns that must stay rejected. "&" is an invalid op; a '|' with an empty diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out index a2c52588361..687d5dd2b2a 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -859,8 +859,8 @@ WINDOW w AS ( Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB NFA States: 6 peak, 18 total, 0 merged - NFA Contexts: 3 peak, 7 total, 2 pruned - NFA: 2 matched (len 2/2/2.0), 0 mismatched + NFA Contexts: 3 peak, 7 total, 0 pruned + NFA: 4 matched (len 0/2/1.0), 0 mismatched NFA: 0 absorbed, 2 skipped (len 1/1/1.0) -> Function Scan on generate_series s (actual rows=6.00 loops=1) (10 rows) @@ -2531,8 +2531,8 @@ WINDOW w AS ( Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB NFA States: 6 peak, 13 total, 0 merged - NFA Contexts: 4 peak, 5 total, 1 pruned - NFA: 3 matched (len 0/2/1.0), 0 mismatched + NFA Contexts: 4 peak, 5 total, 0 pruned + NFA: 4 matched (len 0/2/0.8), 0 mismatched -> Function Scan on generate_series s (actual rows=4.00 loops=1) (9 rows) @@ -2569,7 +2569,7 @@ WINDOW w AS ( Pattern: (a? b?){2,3} Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB - NFA States: 6 peak, 20 total, 0 merged + NFA States: 7 peak, 24 total, 0 merged NFA Contexts: 2 peak, 4 total, 0 pruned NFA: 3 matched (len 0/0/0.0), 0 mismatched -> Function Scan on generate_series s (actual rows=3.00 loops=1) @@ -5174,9 +5174,9 @@ WINDOW w AS ( Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB NFA States: 9 peak, 178 total, 0 merged - NFA Contexts: 4 peak, 61 total, 20 pruned - NFA: 3 matched (len 0/57/19.0), 0 mismatched - NFA: 0 absorbed, 37 skipped (len 1/3/2.0) + NFA Contexts: 4 peak, 61 total, 0 pruned + NFA: 4 matched (len 0/57/14.2), 0 mismatched + NFA: 0 absorbed, 56 skipped (len 1/3/1.6) -> Function Scan on generate_series s (actual rows=60.00 loops=1) (10 rows) @@ -5211,10 +5211,10 @@ WINDOW w AS ( Pattern: (a (b c)+)* Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB - NFA States: 7 peak, 160 total, 0 merged - NFA Contexts: 4 peak, 61 total, 20 pruned - NFA: 3 matched (len 0/57/19.0), 0 mismatched - NFA: 0 absorbed, 37 skipped (len 1/3/2.0) + NFA States: 8 peak, 160 total, 0 merged + NFA Contexts: 4 peak, 61 total, 0 pruned + NFA: 4 matched (len 0/57/14.2), 0 mismatched + NFA: 0 absorbed, 56 skipped (len 1/3/1.6) -> Function Scan on generate_series s (actual rows=60.00 loops=1) (10 rows) diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index 79679a076b6..9217f1c0ab6 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -1281,7 +1281,7 @@ WINDOW gg AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATT ORDER BY id; id | gg | gr | rg | rr | rr2 | ca | cs ----+----+----+----+----+-----+----+---- - 1 | 3 | 3 | 1 | 0 | 0 | 0 | 0 + 1 | 3 | 0 | 1 | 0 | 0 | 0 | 0 2 | 0 | 0 | 1 | 0 | 0 | 0 | 0 3 | 0 | 0 | 1 | 0 | 0 | 0 | 0 4 | 0 | 0 | 0 | 0 | 0 | 0 | 0 @@ -2545,6 +2545,135 @@ WINDOW w AS ( 8 | {_} | | | 0 (8 rows) +-- Optional VAR at the head of the body, re-entered across iterations: +-- (B? A+){2} with no B rows. Both iterations skip B and re-enter A. +WITH test_optvar_quant_reentry AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) 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_optvar_quant_reentry +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((B? A+){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | | +(2 rows) + +-- A skip path that lands on the group's END still counts that iteration: +-- (UP DOWN?)+ over a rising run, where DOWN never matches. +WITH test_skip_lands_on_end AS ( + SELECT * FROM (VALUES + (1, 100), + (2, 110), + (3, 120) + ) AS t(id, price) +) +SELECT id, price, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_skip_lands_on_end +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((UP DOWN?)+) + DEFINE + UP AS price > PREV(price), + DOWN AS price < PREV(price) +); + id | price | match_start | match_end +----+-------+-------------+----------- + 1 | 100 | | + 2 | 110 | 2 | 3 + 3 | 120 | | +(3 rows) + +-- Deep giveback: A+ swallows every overlapping row, then B{3} fails and +-- A+ must surrender three rows in a row. The failure is discovered five +-- rows away from the branch point, not adjacent to it. +WITH test_quant_deep_giveback AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['A','B']), + (5, ARRAY['A','B']), + (6, ARRAY['A','B']), + (7, 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_quant_deep_giveback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B{3} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 7 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {A,B} | | + 5 | {A,B} | | + 6 | {A,B} | | + 7 | {C} | | +(7 rows) + +-- A+ B+ A+ over rows that are all A and B: three quantifiers draw from one +-- pool, so shrinking the first changes what the other two can take. They +-- must renegotiate jointly, not one at a time. +WITH test_quant_coupled_spans AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['A','B']) + ) 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_quant_coupled_spans +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B+ A+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 4 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {A,B} | | +(4 rows) + -- ============================================================ -- Pathological Pattern Runtime Protection -- ============================================================ @@ -2962,7 +3091,8 @@ WINDOW w AS ( -- Optional first branch in ALT with quantifier: (A? | B){1,2} -- First branch A? exit path may loop back to ALT and trigger cycle --- detection during DFS. All branches must receive correct counts. +-- detection during DFS. On a B row the A? branch still succeeds with an +-- empty match, which outranks the B branch, so the match is empty. WITH test_alt_opt_first AS ( SELECT * FROM (VALUES (1, ARRAY['B']), @@ -2985,9 +3115,9 @@ WINDOW w AS ( ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {B} | 1 | 2 - 2 | {B} | 2 | 3 - 3 | {B} | 3 | 3 + 1 | {B} | | + 2 | {B} | | + 3 | {B} | | (3 rows) -- Mixed A/B rows across iterations of (A? | B){1,2} @@ -3013,8 +3143,8 @@ WINDOW w AS ( ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 2 - 2 | {B} | 2 | 3 + 1 | {A} | 1 | 1 + 2 | {B} | | 3 | {A,B} | 3 | 3 (3 rows) @@ -3041,9 +3171,9 @@ WINDOW w AS ( ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {B} | 1 | 2 - 2 | {B} | 2 | 3 - 3 | {B} | 3 | 3 + 1 | {B} | | + 2 | {B} | | + 3 | {B} | | (3 rows) -- Overlapping match: A B C D E | B C D | C D E F (SKIP PAST LAST ROW) @@ -3389,8 +3519,9 @@ WINDOW w AS ( 4 | {_} | | (4 rows) --- ((B C)* | A): optional group as a non-last branch; a zero-match (B C)* must --- not spill into the following A branch. +-- ((B C)* | A): optional group as a non-last branch. Where B C does start +-- the group consumes it (row 2); elsewhere the branch still succeeds with a +-- zero match, and that outranks the A branch, so A never fires (row 4). WITH test_alt_nonlast_optgroup AS ( SELECT * FROM (VALUES (1, ARRAY['_']), @@ -3418,7 +3549,7 @@ WINDOW w AS ( 1 | {_} | | 2 | {B} | 2 | 3 3 | {C} | | - 4 | {A} | 4 | 4 + 4 | {A} | | (4 rows) -- (((B C)* | A) D): the ALT is followed by D, so a zero-match (B C)* must @@ -3457,7 +3588,8 @@ WINDOW w AS ( (5 rows) -- ((B C)*? | A): a reluctant optional group as a branch prefers zero --- iterations, giving an empty match where no A is present. +-- iterations, so the first branch matches empty on every row and the A +-- branch never fires. WITH test_alt_reluctant_optgroup AS ( SELECT * FROM (VALUES (1, ARRAY['B']), @@ -3484,10 +3616,171 @@ WINDOW w AS ( ----+-------+-------------+----------- 1 | {B} | | 2 | {C} | | - 3 | {A} | 3 | 3 + 3 | {A} | | 4 | {_} | | (4 rows) +-- Same variable re-entered across iterations: (A+ | B){2} on an all-A +-- partition. Both iterations take the A+ branch, so the second one re-enters +-- VAR A with a higher iteration count -- a new state, not a cycle. +WITH test_alt_quant_reentry AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_reentry +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((A+ | B){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | +(3 rows) + +-- Branch order does not change the match: (B | A+){2} is the same. +WITH test_alt_quant_reentry_order AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_reentry_order +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((B | A+){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | +(3 rows) + +-- Hand-unrolled form. mergeConsecutiveAlts rolls it back up to {2}, so the +-- match must be the same as the two above. +WITH test_alt_quant_unrolled AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_unrolled +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((A+ | B) (A+ | B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | +(3 rows) + +-- ((A B) | (C D))+ with both branches two rows wide and every row shared: +-- the branch taken at one iteration decides which rows remain for the next. +WITH test_alt_multirow_branches AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','C']), + (2, ARRAY['B','D']), + (3, ARRAY['A','C']), + (4, ARRAY['B','D']), + (5, ARRAY['_']) + ) 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_alt_multirow_branches +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((A B) | (C D))+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,C} | 1 | 4 + 2 | {B,D} | | + 3 | {A,C} | 3 | 4 + 4 | {B,D} | | + 5 | {_} | | +(5 rows) + +-- Same rows, branches written in the other order. Both branches match the +-- same rows here, so the result must not change: the classification does, +-- but the frame does not. +WITH test_alt_multirow_swapped AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','C']), + (2, ARRAY['B','D']), + (3, ARRAY['A','C']), + (4, ARRAY['B','D']), + (5, ARRAY['_']) + ) 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_alt_multirow_swapped +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((C D) | (A B))+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,C} | 1 | 4 + 2 | {B,D} | | + 3 | {A,C} | 3 | 4 + 4 | {B,D} | | + 5 | {_} | | +(5 rows) + -- ============================================================ -- Deep Nested Groups -- ============================================================ @@ -3749,13 +4042,10 @@ WINDOW w AS ( (3 rows) -- Exact outer quantifier over a variable-length body --- ((A | B B){1,2}){2} is by definition (A | B B){1,2} (A | B B){1,2}, so the --- two must prefer the same match. The optimizer must not collapse the nested --- form to (A | B B){2,4}: the alternation branches consume a different number --- of rows, so moving an iteration across the outer block boundary changes --- which rows are matched. The collapsed form stops at A A (rows 1-2), while --- the nested form, whose second block must still take an iteration, prefers --- A (B B) A A (rows 1-5). +-- (X{1,2}){2} is by definition X{1,2} X{1,2}, so the two must prefer the same +-- match. Collapsing to (A | B B){2,4} does not: the branches consume unequal +-- rows, so moving an iteration across the block boundary changes which rows +-- match. The third query below shows the collapsed form's own preference. WITH test_nested_alt_body AS ( SELECT * FROM (VALUES (1, ARRAY['A']), @@ -3819,9 +4109,8 @@ WINDOW w AS ( 5 | {A} | | (5 rows) --- The collapsed form, written by hand. It admits the same iteration counts as --- the two above, but it is a different pattern and prefers a different match: --- with no block boundary to force a second iteration it stops at rows 1-2. +-- The collapsed form, written by hand: same iteration counts as the two above, +-- but with no block boundary forcing a second iteration it stops at rows 1-2. -- That difference is why the two above must not be rewritten into this one. WITH test_nested_alt_body AS ( SELECT * FROM (VALUES @@ -3854,42 +4143,287 @@ WINDOW w AS ( 5 | {A} | | (5 rows) --- ============================================================ --- SKIP Options (Runtime) --- ============================================================ --- SKIP PAST LAST ROW (non-overlapping matches) -WITH test_skip_past AS ( +-- Re-entry into a group whose body always consumes rows +-- A body that cannot match empty consumes a row on every derivation, so a +-- loop-back into it is progress, not a cycle. Both forms must find the same +-- match: (X){3} is by definition X X X. +WITH test_reentry_consuming AS ( SELECT * FROM (VALUES (1, ARRAY['A']), - (2, ARRAY['A']), - (3, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), (4, ARRAY['A']), - (5, ARRAY['_']) + (5, ARRAY['A']), + (6, ARRAY['A','B']), + (7, ARRAY['B']), + (8, ARRAY['A']) ) 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_skip_past +FROM test_reentry_consuming WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (A+) + PATTERN (((A | B B){1,3}){3}) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 4 - 2 | {A} | | - 3 | {A} | | + 1 | {A} | 1 | 8 + 2 | {A,B} | | + 3 | {B} | | 4 | {A} | | - 5 | {_} | | -(5 rows) + 5 | {A} | | + 6 | {A,B} | | + 7 | {B} | | + 8 | {A} | | +(8 rows) --- SKIP TO NEXT ROW (overlapping matches) -WITH test_skip_next AS ( +-- The same pattern written out. Must give the same match as the nested form. +WITH test_reentry_consuming AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']), + (6, ARRAY['A','B']), + (7, ARRAY['B']), + (8, ARRAY['A']) + ) 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_reentry_consuming +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,3} (A | B B){1,3} (A | B B){1,3}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 8 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | + 5 | {A} | | + 6 | {A,B} | | + 7 | {B} | | + 8 | {A} | | +(8 rows) + +-- Empty iteration followed by a consuming one, below min +-- A? is tried before B, so on row 1 the first two iterations go empty and the +-- third takes B, matching rows 1-2. The longer A B C match ranks lower: it +-- abandons A? in the first iteration (7.2.4 -- length breaks prefix ties only). +WITH test_empty_then_consume 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_empty_then_consume +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){3} 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 | 2 + 2 | {A,C} | | + 3 | {C} | 3 | 3 +(3 rows) + +-- The same pattern written out, with the copies renamed so that no rewrite +-- can fold them back into a loop. Must give the same match. +WITH test_empty_then_consume 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_empty_then_consume +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B) (D? | E) (F? | G) C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'A' = ANY(flags), + E AS 'B' = ANY(flags), + F AS 'A' = ANY(flags), + G AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 2 + 2 | {A,C} | | + 3 | {C} | 3 | 3 +(3 rows) + +-- (A+)+ B with an overlap row: the inner A+ must take row 3 as A, leaving +-- row 4 for B. Nested unbounded quantifiers over a row that satisfies both +-- the quantified variable and its successor. +WITH test_nest_unbounded_overlap AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A','B']), + (4, ARRAY['B']) + ) 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_nest_unbounded_overlap +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A+)+ B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A} | 2 | 4 + 3 | {A,B} | 3 | 4 + 4 | {B} | | +(4 rows) + +-- ((A+ B)+ C)+ D: three unbounded quantifiers at three depths, every row +-- shared with its successor. Iteration boundaries at each level can be +-- drawn several ways over the same rows. +WITH test_nest_three_levels AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B','C']), + (4, ARRAY['C','D']), + (5, ARRAY['D']) + ) 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_nest_three_levels +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((A+ B)+ C)+ D) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 5 + 2 | {A,B} | 2 | 5 + 3 | {B,C} | | + 4 | {C,D} | | + 5 | {D} | | +(5 rows) + +-- ((A | B)+)+ C: alternation nested inside two unbounded quantifiers, with +-- rows satisfying both alternatives. +WITH test_nest_alt_unbounded AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','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_nest_alt_unbounded +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((A | B)+)+ C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 4 + 2 | {A,B} | 2 | 4 + 3 | {B,C} | 3 | 4 + 4 | {C} | | +(4 rows) + +-- ============================================================ +-- SKIP Options (Runtime) +-- ============================================================ +-- SKIP PAST LAST ROW (non-overlapping matches) +WITH test_skip_past AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['A']), + (5, ARRAY['_']) + ) 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_skip_past +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A} | | + 3 | {A} | | + 4 | {A} | | + 5 | {_} | | +(5 rows) + +-- SKIP TO NEXT ROW (overlapping matches) +WITH test_skip_next AS ( SELECT * FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A']), @@ -4015,6 +4549,68 @@ ORDER BY mode, id; SKIP PAST | 4 | {_} | | (8 rows) +-- A* under SKIP PAST LAST ROW: row 1 matches empty, which consumes nothing +-- and so must not move the skip landing. Row 2 still starts its own match. +WITH test_skip_past_after_empty AS ( + SELECT * FROM (VALUES + (1, ARRAY['_']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['_']) + ) 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_skip_past_after_empty +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A*) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {_} | | + 2 | {A} | 2 | 3 + 3 | {A} | | + 4 | {_} | | +(4 rows) + +-- (A B)* C: row 1 matches C alone with the group taken zero times, so the +-- landing is row 2 and the A B C match at rows 2-4 is still found. +WITH test_skip_past_zero_iterations AS ( + SELECT * FROM (VALUES + (1, ARRAY['C']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (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_skip_past_zero_iterations +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)* C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {C} | 1 | 1 + 2 | {A} | 2 | 4 + 3 | {B} | | + 4 | {C} | | +(4 rows) + -- ============================================================ -- INITIAL Mode (Runtime) -- ============================================================ @@ -4802,41 +5398,211 @@ WINDOW w AS ( 4 | {C} | | (4 rows) --- ============================================================ --- Standard Clause 7: Formal Pattern Matching Rules --- ISO/IEC 19075-5, Clause 7 --- ============================================================ --- ------------------------------------------------------------ --- 7.2.2 Alternation: first alternative is preferred --- ------------------------------------------------------------ --- (A | B): A preferred over B when both could match --- Row 1 has both A and B flags: A should be chosen (first alternative) -WITH test_alt_prefer AS ( +-- (A (B*?)+?)+ : a reluctant unbounded quantifier over a nullable group, +-- inside an outer quantifier. The empty iteration ends the inner loop. +WITH test_cycle_reluctant_nullable AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['B']), - (3, ARRAY['A']) + (1, ARRAY['A']), + (2, ARRAY['A']) ) 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_alt_prefer +FROM test_cycle_reluctant_nullable WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A | B)) + PATTERN ((A (B*?)+?)+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A,B} | 1 | 1 - 2 | {B} | 2 | 2 - 3 | {A} | 3 | 3 -(3 rows) + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 2 +(2 rows) + +-- Same body under a bounded outer quantifier with lower bound zero. +WITH test_cycle_reluctant_bounded AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) 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_cycle_reluctant_bounded +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+?){0,2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 2 +(2 rows) + +-- Greedy inner over the same nullable group: the preferred path consumes a +-- row and parks in the frontier, so it cannot recurse through epsilon. +WITH test_cycle_greedy_nullable AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) 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_cycle_greedy_nullable +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | | +(2 rows) + +-- Non-nullable inner body: every derivation consumes a row, so no empty +-- iteration exists and the guard has nothing to do. +WITH test_cycle_nonnullable_inner AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) 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_cycle_nonnullable_inner +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B+)+?){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {B} | | + 3 | {A} | | + 4 | {B} | | +(4 rows) + +-- Reluctant unbounded quantifier over a nullable group, inside an outer +-- quantifier whose lower bound is above one. Below the bound the guard +-- must keep looping without unbounded epsilon recursion: each empty inner +-- iteration advances the count until the bound is met. Two iterations +-- (one A each, inner empty) satisfy min=2 and match rows 1-2. +WITH test_cycle_reluctant_below_min AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) 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_cycle_reluctant_below_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+?){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | | +(2 rows) + +-- Same shape with a reluctant outer bound: stops at exactly two iterations +-- even though a third A row is available. +WITH test_cycle_reluctant_outer_min AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_cycle_reluctant_outer_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+?){2,}?) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 3 + 3 | {A} | | +(3 rows) + +-- ============================================================ +-- Standard Clause 7: Formal Pattern Matching Rules +-- ISO/IEC 19075-5, Clause 7 +-- ============================================================ +-- ------------------------------------------------------------ +-- 7.2.2 Alternation: first alternative is preferred +-- ------------------------------------------------------------ +-- (A | B): A preferred over B when both could match +-- Row 1 has both A and B flags: A should be chosen (first alternative) +WITH test_alt_prefer AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_alt_prefer +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 1 + 2 | {B} | 2 | 2 + 3 | {A} | 3 | 3 +(3 rows) -- (A{1,2} | B{2,3}): all A-matches before all B-matches -- Standard example: preferment order is AA, A, BBB, BB @@ -4872,6 +5638,133 @@ WINDOW w AS ( 5 | {B} | | (5 rows) +-- (A | B B | C C C): three alternatives, all viable on every row. +-- Preferment order is A, BB, CCC: the first alternative wins even though +-- the later ones would match longer. +WITH test_alt_three_way AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B','C']), + (2, ARRAY['A','B','C']), + (3, ARRAY['A','B','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_alt_three_way +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B B | C C C)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+---------+-------------+----------- + 1 | {A,B,C} | 1 | 1 + 2 | {A,B,C} | 2 | 2 + 3 | {A,B,C} | 3 | 3 +(3 rows) + +-- ((A | B | C)+): three alternatives ranked on every iteration, not just +-- once. Each row carries all three flags. +WITH test_alt_three_way_loop AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B','C']), + (2, ARRAY['A','B','C']), + (3, ARRAY['A','B','C']), + (4, ARRAY['_']) + ) 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_alt_three_way_loop +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B | C)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+---------+-------------+----------- + 1 | {A,B,C} | 1 | 3 + 2 | {A,B,C} | 2 | 3 + 3 | {A,B,C} | 3 | 3 + 4 | {_} | | +(4 rows) + +-- (A B | A C): branches share the prefix A, so the choice is only decided +-- at row 2, which carries both B and C. The first alternative wins there. +WITH test_alt_shared_prefix AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B','C']), + (3, ARRAY['C']), + (4, ARRAY['_']) + ) 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_alt_shared_prefix +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A B | A C)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {B,C} | | + 3 | {C} | | + 4 | {_} | | +(4 rows) + +-- (A B C | A B): the first alternative is the longer one and it fits, so +-- length and written order agree. Compare with the reverse below. +WITH test_alt_shared_prefix_long_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, ARRAY['_']) + ) 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_alt_shared_prefix_long_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A B C | A B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {B} | | + 3 | {C} | | + 4 | {_} | | +(4 rows) + -- ------------------------------------------------------------ -- 7.2.3 Concatenation: lexicographic ordering -- ------------------------------------------------------------ @@ -5010,49 +5903,243 @@ WITH test_quant_lex_greedy AS ( SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end -FROM test_quant_lex_greedy +FROM test_quant_lex_greedy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2})) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 2 + 2 | {B} | | +(2 rows) + +-- ((A|B){1,2}?) reluctant: lexicographic > length +-- Standard example: preferment A, AA, AB, B, BA, BB +-- Single A preferred over any B-starting match +WITH test_quant_lex_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']) + ) 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_quant_lex_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2}?)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 1 + 2 | {B} | 2 | 2 +(2 rows) + +-- A+? B where every row is both A and B: stopping and continuing are both +-- viable at every step, so reluctance is actually contested. Without the +-- overlap the reluctant path is never tested against a live alternative. +WITH test_quant_reluctant_contested AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['_']) + ) 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_quant_reluctant_contested +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+? B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 2 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {_} | | +(4 rows) + +-- A+ B over the same rows: greedy takes as many as it can while still +-- leaving a B behind. Contrast with the reluctant case above. +WITH test_quant_greedy_contested AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['_']) + ) 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_quant_greedy_contested +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 3 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {_} | | +(4 rows) + +-- (A+ B)+? C: the outer quantifier is reluctant, so it stops after one +-- iteration and takes the C available at row 3. Row 3 is also an A, which +-- would let a second iteration run; reluctance declines it. +WITH test_quant_reluctant_outer AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A','C']), + (4, ARRAY['B']), + (5, 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_quant_reluctant_outer +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+? C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {B} | | + 3 | {A,C} | | + 4 | {B} | | + 5 | {C} | | +(5 rows) + +-- (A+ B)+ C over the same rows: outer greed takes the second iteration and +-- lands on the C at row 5 instead. Contrast with the reluctant outer above. +WITH test_quant_greedy_outer AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A','C']), + (4, ARRAY['B']), + (5, 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_quant_greedy_outer +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+ C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 5 + 2 | {B} | | + 3 | {A,C} | | + 4 | {B} | | + 5 | {C} | | +(5 rows) + +-- A{2}? B: an exact bound leaves no choice, so the reluctant mark must not +-- change anything. Overlap on rows 2-3 would expose a bound lowered to +-- {0,2}? or {1,2}?. +WITH test_quant_reluctant_exact AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['B']) + ) 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_quant_reluctant_exact WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (((A | B){1,2})) + PATTERN (A{2}? B) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A,B} | 1 | 2 - 2 | {B} | | -(2 rows) + 1 | {A} | 1 | 3 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {B} | | +(4 rows) --- ((A|B){1,2}?) reluctant: lexicographic > length --- Standard example: preferment A, AA, AB, B, BA, BB --- Single A preferred over any B-starting match -WITH test_quant_lex_reluctant AS ( +-- A{2} B: the greedy spelling of the same bound, for contrast. +WITH test_quant_exact AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['B']) + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['B']) ) 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_quant_lex_reluctant +FROM test_quant_exact WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (((A | B){1,2}?)) + PATTERN (A{2} B) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A,B} | 1 | 1 - 2 | {B} | 2 | 2 -(2 rows) + 1 | {A} | 1 | 3 + 2 | {A,B} | | + 3 | {A,B} | | + 4 | {B} | | +(4 rows) -- ------------------------------------------------------------ -- 7.2.6 Anchors (not yet implemented - syntax error expected) @@ -5235,6 +6322,70 @@ WINDOW w AS ( 4 | {A} | 4 | 4 (4 rows) +-- (A? | B){3}: an empty iteration below min fills the lower bound (STR06), +-- and it must outrank the later branch. Row 2 is B only, so A? derives empty +-- there; repeating that derivation fills the remaining iterations and the +-- match ends at row 1. Taking branch B instead would consume rows 2-3. +WITH test_728_empty_fills_min AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_empty_fills_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){3}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 1 + 2 | {B} | | + 3 | {A} | 3 | 3 +(3 rows) + +-- The same pattern unrolled. Consecutive identical alternations are merged +-- into the rolled form above, so the two must agree. +WITH test_728_empty_fills_min_unrolled AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_empty_fills_min_unrolled +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B) (C? | D) (E? | F)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'A' = ANY(flags), + D AS 'B' = ANY(flags), + E AS 'A' = ANY(flags), + F AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 1 + 2 | {B} | | + 3 | {A} | 3 | 3 +(3 rows) + -- (A? B?){2,3}: multi-element nullable body with real matches -- Body A? B? is nullable (both optional), but A and B DO match rows. -- Real (non-empty) iterations loop back normally; fast-forward only @@ -5340,6 +6491,261 @@ WINDOW w AS ( 5 | {B} | 5 | 5 (5 rows) +-- The stopping rule also governs an alternation body. On A,B the greedy +-- (A? | B)* takes A in iteration 1; in iteration 2 the preferred branch A? +-- matches empty, so the quantifier stops and B never consumes row 2. +WITH test_empty_stop_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']) + ) 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_empty_stop_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 1 + 2 | {B} | | +(2 rows) + +-- With min = max the group's own greed says nothing, so the body decides +-- whether the empty match is preferred: {n}? must equal {n}. A? prefers to +-- consume (both forms take two rows); A?? prefers empty (both match empty). +WITH test_fixed_quant_body_greed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + count(*) OVER g AS greedy_body, -- ((A?){2}) + count(*) OVER gr AS greedy_body_rel, -- ((A?){2}?) + count(*) OVER r AS rel_body, -- ((A??){2}) + count(*) OVER rr AS rel_body_rel -- ((A??){2}?) +FROM test_fixed_quant_body_greed +WINDOW g AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A?){2})) + DEFINE A AS 'A' = ANY(flags)), + gr AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A?){2}?)) + DEFINE A AS 'A' = ANY(flags)), + r AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A??){2})) + DEFINE A AS 'A' = ANY(flags)), + rr AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A??){2}?)) + DEFINE A AS 'A' = ANY(flags)) +ORDER BY id; + id | flags | greedy_body | greedy_body_rel | rel_body | rel_body_rel +----+-------+-------------+-----------------+----------+-------------- + 1 | {A} | 2 | 2 | 0 | 0 + 2 | {A} | 0 | 0 | 0 | 0 +(2 rows) + +-- (A* | B)*: A* is the preferred alternative and matches empty at row 3, +-- which ends the loop by the lower-bound stopping rule. B is never tried, +-- so the match stops short of the B rows even though taking them would be +-- longer. Perl agrees: (a*|b)* against "aabb" matches "aa". +WITH test_728_nullable_alt_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A* | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 2 + 3 | {B} | | + 4 | {B} | | +(4 rows) + +-- (B | A*)*: same body, alternatives swapped. B is preferred and consumes, +-- so no empty iteration arises and the loop reaches the B rows. +WITH test_728_nullable_alt_second AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_second +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((B | A*)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A} | 2 | 4 + 3 | {B} | 3 | 4 + 4 | {B} | 4 | 4 +(4 rows) + +-- (A+ | B)*: the first alternative is not nullable, so it cannot produce an +-- empty iteration and the loop reaches the B rows. Compare with (A* | B)*. +WITH test_728_nonnullable_alt_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nonnullable_alt_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A+ | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A} | 2 | 4 + 3 | {B} | 3 | 4 + 4 | {B} | 4 | 4 +(4 rows) + +-- (A? | B){2,3}: the stop rule binds at the lower bound even when the +-- upper bound could still admit more iterations. Iterations one and two +-- go empty via A?, which stops the loop at min; C then fails at row 1 and +-- backtracking REPLACES iteration two with B instead of extending, so the +-- match runs B, A, C = rows 1-3. Perl agrees: (?:a?|b){2,3}c backtracks +-- the same way. An engine that keeps iterating after the empty stop +-- returns rows 1-2 via the shorter empty-empty-B derivation instead. +WITH test_728_stop_binds_at_min 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_binds_at_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){2,3} 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) + +-- (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. +WITH test_728_exact_below_min 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_exact_below_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){3} 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 | 2 + 2 | {A,C} | 2 | 3 + 3 | {C} | 3 | 3 +(3 rows) + +-- (A? | B){2,}: the stopping rule applies above the lower bound as well. +-- Two iterations consume the A rows and satisfy min=2; the third matches +-- empty via A? and ends the loop before any B is taken. +WITH test_728_nullable_alt_min2 AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_min2 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 2 + 3 | {B} | | + 4 | {B} | | +(4 rows) + -- ------------------------------------------------------------ -- 7.3 Pattern matching in theory and practice -- ------------------------------------------------------------ diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index 571300d0d40..0e08f97adb8 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -2365,11 +2365,12 @@ WINDOW w1 AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTE SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_dp_struct'), E'\n')) AS line WHERE line ~ 'PATTERN'; DROP VIEW rpr_dp_struct; -- Execution semantics (deparse cannot show reluctant shortest-match). The --- rpr_glue rows -- an A-run followed by B rows -- make the '|B' alternative --- reachable: with "*" the greedy form matches the whole run while the --- reluctant form matches empty; with "+" the greedy form matches the run and --- the reluctant form matches one row, and on a B row (where "A+" fails) the B --- alternative fires. +-- rpr_glue rows -- an A-run followed by B rows -- show when the '|B' +-- alternative is reachable. With "*" the first branch always succeeds, so B +-- never fires: the greedy form matches the whole run and the reluctant form +-- matches empty, and on a B row the empty match still outranks B. With "+" +-- the first branch fails on a B row, so there the B alternative fires; on an +-- A row the greedy form matches the run and the reluctant form one row. SELECT id, val, count(*) OVER gs AS gstar, count(*) OVER rs AS rstar, count(*) OVER gp AS gplus, count(*) OVER rp AS rplus diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 279958678b3..cf00d550af1 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -1790,6 +1790,107 @@ WINDOW w AS ( DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); +-- Optional VAR at the head of the body, re-entered across iterations: +-- (B? A+){2} with no B rows. Both iterations skip B and re-enter A. +WITH test_optvar_quant_reentry AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) 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_optvar_quant_reentry +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((B? A+){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- A skip path that lands on the group's END still counts that iteration: +-- (UP DOWN?)+ over a rising run, where DOWN never matches. +WITH test_skip_lands_on_end AS ( + SELECT * FROM (VALUES + (1, 100), + (2, 110), + (3, 120) + ) AS t(id, price) +) +SELECT id, price, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_skip_lands_on_end +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((UP DOWN?)+) + DEFINE + UP AS price > PREV(price), + DOWN AS price < PREV(price) +); + +-- Deep giveback: A+ swallows every overlapping row, then B{3} fails and +-- A+ must surrender three rows in a row. The failure is discovered five +-- rows away from the branch point, not adjacent to it. +WITH test_quant_deep_giveback AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['A','B']), + (5, ARRAY['A','B']), + (6, ARRAY['A','B']), + (7, 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_quant_deep_giveback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B{3} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- A+ B+ A+ over rows that are all A and B: three quantifiers draw from one +-- pool, so shrinking the first changes what the other two can take. They +-- must renegotiate jointly, not one at a time. +WITH test_quant_coupled_spans AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['A','B']) + ) 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_quant_coupled_spans +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B+ A+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + -- ============================================================ -- Pathological Pattern Runtime Protection -- ============================================================ @@ -2110,7 +2211,8 @@ WINDOW w AS ( -- Optional first branch in ALT with quantifier: (A? | B){1,2} -- First branch A? exit path may loop back to ALT and trigger cycle --- detection during DFS. All branches must receive correct counts. +-- detection during DFS. On a B row the A? branch still succeeds with an +-- empty match, which outranks the B branch, so the match is empty. WITH test_alt_opt_first AS ( SELECT * FROM (VALUES (1, ARRAY['B']), @@ -2433,8 +2535,9 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); --- ((B C)* | A): optional group as a non-last branch; a zero-match (B C)* must --- not spill into the following A branch. +-- ((B C)* | A): optional group as a non-last branch. Where B C does start +-- the group consumes it (row 2); elsewhere the branch still succeeds with a +-- zero match, and that outranks the A branch, so A never fires (row 4). WITH test_alt_nonlast_optgroup AS ( SELECT * FROM (VALUES (1, ARRAY['_']), @@ -2486,7 +2589,8 @@ WINDOW w AS ( ); -- ((B C)*? | A): a reluctant optional group as a branch prefers zero --- iterations, giving an empty match where no A is present. +-- iterations, so the first branch matches empty on every row and the A +-- branch never fires. WITH test_alt_reluctant_optgroup AS ( SELECT * FROM (VALUES (1, ARRAY['B']), @@ -2510,6 +2614,133 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- Same variable re-entered across iterations: (A+ | B){2} on an all-A +-- partition. Both iterations take the A+ branch, so the second one re-enters +-- VAR A with a higher iteration count -- a new state, not a cycle. +WITH test_alt_quant_reentry AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_reentry +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((A+ | B){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Branch order does not change the match: (B | A+){2} is the same. +WITH test_alt_quant_reentry_order AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_reentry_order +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((B | A+){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Hand-unrolled form. mergeConsecutiveAlts rolls it back up to {2}, so the +-- match must be the same as the two above. +WITH test_alt_quant_unrolled AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_alt_quant_unrolled +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + INITIAL + PATTERN ((A+ | B) (A+ | B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ((A B) | (C D))+ with both branches two rows wide and every row shared: +-- the branch taken at one iteration decides which rows remain for the next. +WITH test_alt_multirow_branches AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','C']), + (2, ARRAY['B','D']), + (3, ARRAY['A','C']), + (4, ARRAY['B','D']), + (5, ARRAY['_']) + ) 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_alt_multirow_branches +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((A B) | (C D))+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + +-- Same rows, branches written in the other order. Both branches match the +-- same rows here, so the result must not change: the classification does, +-- but the frame does not. +WITH test_alt_multirow_swapped AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','C']), + (2, ARRAY['B','D']), + (3, ARRAY['A','C']), + (4, ARRAY['B','D']), + (5, ARRAY['_']) + ) 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_alt_multirow_swapped +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((C D) | (A B))+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + -- ============================================================ -- Deep Nested Groups -- ============================================================ @@ -2704,13 +2935,10 @@ WINDOW w AS ( ); -- Exact outer quantifier over a variable-length body --- ((A | B B){1,2}){2} is by definition (A | B B){1,2} (A | B B){1,2}, so the --- two must prefer the same match. The optimizer must not collapse the nested --- form to (A | B B){2,4}: the alternation branches consume a different number --- of rows, so moving an iteration across the outer block boundary changes --- which rows are matched. The collapsed form stops at A A (rows 1-2), while --- the nested form, whose second block must still take an iteration, prefers --- A (B B) A A (rows 1-5). +-- (X{1,2}){2} is by definition X{1,2} X{1,2}, so the two must prefer the same +-- match. Collapsing to (A | B B){2,4} does not: the branches consume unequal +-- rows, so moving an iteration across the block boundary changes which rows +-- match. The third query below shows the collapsed form's own preference. WITH test_nested_alt_body AS ( SELECT * FROM (VALUES (1, ARRAY['A']), @@ -2758,9 +2986,8 @@ WINDOW w AS ( B AS 'B' = ANY(flags) ); --- The collapsed form, written by hand. It admits the same iteration counts as --- the two above, but it is a different pattern and prefers a different match: --- with no block boundary to force a second iteration it stops at rows 1-2. +-- The collapsed form, written by hand: same iteration counts as the two above, +-- but with no block boundary forcing a second iteration it stops at rows 1-2. -- That difference is why the two above must not be rewritten into this one. WITH test_nested_alt_body AS ( SELECT * FROM (VALUES @@ -2785,130 +3012,367 @@ WINDOW w AS ( B AS 'B' = ANY(flags) ); --- ============================================================ --- SKIP Options (Runtime) --- ============================================================ - --- SKIP PAST LAST ROW (non-overlapping matches) -WITH test_skip_past AS ( +-- Re-entry into a group whose body always consumes rows +-- A body that cannot match empty consumes a row on every derivation, so a +-- loop-back into it is progress, not a cycle. Both forms must find the same +-- match: (X){3} is by definition X X X. +WITH test_reentry_consuming AS ( SELECT * FROM (VALUES (1, ARRAY['A']), - (2, ARRAY['A']), - (3, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), (4, ARRAY['A']), - (5, ARRAY['_']) + (5, ARRAY['A']), + (6, ARRAY['A','B']), + (7, ARRAY['B']), + (8, ARRAY['A']) ) 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_skip_past +FROM test_reentry_consuming WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (A+) + PATTERN (((A | B B){1,3}){3}) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) ); --- SKIP TO NEXT ROW (overlapping matches) -WITH test_skip_next AS ( +-- The same pattern written out. Must give the same match as the nested form. +WITH test_reentry_consuming AS ( SELECT * FROM (VALUES (1, ARRAY['A']), - (2, ARRAY['A']), - (3, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), (4, ARRAY['A']), - (5, ARRAY['_']) + (5, ARRAY['A']), + (6, ARRAY['A','B']), + (7, ARRAY['B']), + (8, ARRAY['A']) ) 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_skip_next +FROM test_reentry_consuming WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN (A+) + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,3} (A | B B){1,3} (A | B B){1,3}) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) ); --- SKIP difference verification -WITH test_skip_diff AS ( +-- Empty iteration followed by a consuming one, below min +-- A? is tried before B, so on row 1 the first two iterations go empty and the +-- third takes B, matching rows 1-2. The longer A B C match ranks lower: it +-- abandons A? in the first iteration (7.2.4 -- length breaks prefix ties only). +WITH test_empty_then_consume AS ( SELECT * FROM (VALUES - (1, ARRAY['A']), - (2, ARRAY['B']), - (3, ARRAY['A']), - (4, ARRAY['B']) + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) ) AS t(id, flags) ) -SELECT 'SKIP PAST' AS mode, id, flags, +SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end -FROM test_skip_diff +FROM test_empty_then_consume WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (A B) + PATTERN ((A? | B){3} C) DEFINE A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags) + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- The same pattern written out, with the copies renamed so that no rewrite +-- can fold them back into a loop. Must give the same match. +WITH test_empty_then_consume AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A','C']), + (3, ARRAY['C']) + ) AS t(id, flags) ) -UNION ALL -SELECT 'SKIP NEXT' AS mode, id, flags, +SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end -FROM test_skip_diff +FROM test_empty_then_consume WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN (A B) + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B) (D? | E) (F? | G) C) DEFINE A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags) -) -ORDER BY mode, id; + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'A' = ANY(flags), + E AS 'B' = ANY(flags), + F AS 'A' = ANY(flags), + G AS 'B' = ANY(flags) +); --- Reluctant SKIP comparison: A+? with SKIP PAST vs SKIP NEXT -WITH test_reluctant_skip AS ( +-- (A+)+ B with an overlap row: the inner A+ must take row 3 as A, leaving +-- row 4 for B. Nested unbounded quantifiers over a row that satisfies both +-- the quantified variable and its successor. +WITH test_nest_unbounded_overlap AS ( SELECT * FROM (VALUES (1, ARRAY['A']), (2, ARRAY['A']), - (3, ARRAY['A']), - (4, ARRAY['_']) + (3, ARRAY['A','B']), + (4, ARRAY['B']) ) AS t(id, flags) ) -SELECT 'SKIP PAST' AS mode, id, flags, +SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end -FROM test_reluctant_skip +FROM test_nest_unbounded_overlap WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP PAST LAST ROW - PATTERN (A+?) + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A+)+ B) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ((A+ B)+ C)+ D: three unbounded quantifiers at three depths, every row +-- shared with its successor. Iteration boundaries at each level can be +-- drawn several ways over the same rows. +WITH test_nest_three_levels AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B','C']), + (4, ARRAY['C','D']), + (5, ARRAY['D']) + ) AS t(id, flags) ) -UNION ALL -SELECT 'SKIP NEXT' AS mode, id, flags, +SELECT id, flags, first_value(id) OVER w AS match_start, last_value(id) OVER w AS match_end -FROM test_reluctant_skip +FROM test_nest_three_levels WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP TO NEXT ROW - PATTERN (A+?) + PATTERN (((A+ B)+ C)+ D) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + +-- ((A | B)+)+ C: alternation nested inside two unbounded quantifiers, with +-- rows satisfying both alternatives. +WITH test_nest_alt_unbounded AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','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_nest_alt_unbounded +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (((A | B)+)+ C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- ============================================================ +-- SKIP Options (Runtime) +-- ============================================================ + +-- SKIP PAST LAST ROW (non-overlapping matches) +WITH test_skip_past AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['A']), + (5, ARRAY['_']) + ) 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_skip_past +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+) + DEFINE + A AS 'A' = ANY(flags) +); + +-- SKIP TO NEXT ROW (overlapping matches) +WITH test_skip_next AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['A']), + (5, ARRAY['_']) + ) 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_skip_next +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (A+) + DEFINE + A AS 'A' = ANY(flags) +); + +-- SKIP difference verification +WITH test_skip_diff AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) AS t(id, flags) +) +SELECT 'SKIP PAST' AS mode, id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_skip_diff +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +) +UNION ALL +SELECT 'SKIP NEXT' AS mode, id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_skip_diff +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (A B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +) +ORDER BY mode, id; + +-- Reluctant SKIP comparison: A+? with SKIP PAST vs SKIP NEXT +WITH test_reluctant_skip AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['_']) + ) AS t(id, flags) +) +SELECT 'SKIP PAST' AS mode, id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_reluctant_skip +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+?) + DEFINE + A AS 'A' = ANY(flags) +) +UNION ALL +SELECT 'SKIP NEXT' AS mode, id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_reluctant_skip +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN (A+?) DEFINE A AS 'A' = ANY(flags) ) ORDER BY mode, id; +-- A* under SKIP PAST LAST ROW: row 1 matches empty, which consumes nothing +-- and so must not move the skip landing. Row 2 still starts its own match. +WITH test_skip_past_after_empty AS ( + SELECT * FROM (VALUES + (1, ARRAY['_']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['_']) + ) 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_skip_past_after_empty +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A*) + DEFINE + A AS 'A' = ANY(flags) +); + +-- (A B)* C: row 1 matches C alone with the group taken zero times, so the +-- landing is row 2 and the A B C match at rows 2-4 is still found. +WITH test_skip_past_zero_iterations AS ( + SELECT * FROM (VALUES + (1, ARRAY['C']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (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_skip_past_zero_iterations +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)* C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + -- ============================================================ -- INITIAL Mode (Runtime) -- ============================================================ @@ -3522,207 +3986,594 @@ WINDOW w AS ( B AS 'B' = ANY(flags) ); --- ============================================================ --- Standard Clause 7: Formal Pattern Matching Rules --- ISO/IEC 19075-5, Clause 7 --- ============================================================ - --- ------------------------------------------------------------ --- 7.2.2 Alternation: first alternative is preferred --- ------------------------------------------------------------ - --- (A | B): A preferred over B when both could match --- Row 1 has both A and B flags: A should be chosen (first alternative) -WITH test_alt_prefer AS ( +-- (A (B*?)+?)+ : a reluctant unbounded quantifier over a nullable group, +-- inside an outer quantifier. The empty iteration ends the inner loop. +WITH test_cycle_reluctant_nullable AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['B']), - (3, ARRAY['A']) + (1, ARRAY['A']), + (2, ARRAY['A']) ) 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_alt_prefer +FROM test_cycle_reluctant_nullable WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A | B)) + PATTERN ((A (B*?)+?)+) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); --- (A{1,2} | B{2,3}): all A-matches before all B-matches --- Standard example: preferment order is AA, A, BBB, BB --- Rows 1-2 have both A and B: greedy A{1,2} should match 1-2 -WITH test_alt_quantified AS ( +-- Same body under a bounded outer quantifier with lower bound zero. +WITH test_cycle_reluctant_bounded AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['A','B']), - (3, ARRAY['B']), - (4, ARRAY['B']), - (5, ARRAY['B']) + (1, ARRAY['A']), + (2, ARRAY['A']) ) 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_alt_quantified +FROM test_cycle_reluctant_bounded WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A{1,2} | B{2,3})) + PATTERN ((A (B*?)+?){0,2}) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); --- ------------------------------------------------------------ --- 7.2.3 Concatenation: lexicographic ordering --- ------------------------------------------------------------ - --- ((A | B) (C | D)): preferment order is AC, AD, BC, BD --- Row 1 matches A and B, Row 2 matches C and D --- Preferred match: A then C (first alternatives in both positions) -WITH test_concat_lex AS ( +-- Greedy inner over the same nullable group: the preferred path consumes a +-- row and parks in the frontier, so it cannot recurse through epsilon. +WITH test_cycle_greedy_nullable AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['C','D']) + (1, ARRAY['A']), + (2, ARRAY['A']) ) 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_concat_lex +FROM test_cycle_greedy_nullable WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP PAST LAST ROW - PATTERN ((A | B) (C | D)) + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+){2,}) DEFINE A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags), - C AS 'C' = ANY(flags), - D AS 'D' = ANY(flags) + B AS 'B' = ANY(flags) ); --- ((A | B) C): first alt (A) fails, second alt (B) succeeds --- Tests backtracking: row 1 has only B, row 2 has C -WITH test_concat_backtrack AS ( +-- Non-nullable inner body: every derivation consumes a row, so no empty +-- iteration exists and the guard has nothing to do. +WITH test_cycle_nonnullable_inner AS ( SELECT * FROM (VALUES - (1, ARRAY['B']), - (2, ARRAY['C']), + (1, ARRAY['A']), + (2, ARRAY['B']), (3, ARRAY['A']), - (4, ARRAY['C']) + (4, ARRAY['B']) ) 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_concat_backtrack +FROM test_cycle_nonnullable_inner WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A | B) C) + PATTERN ((A (B+)+?){2,}) DEFINE A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags), - C AS 'C' = ANY(flags) + B AS 'B' = ANY(flags) ); --- ------------------------------------------------------------ --- 7.2.4 Quantification: greedy/reluctant, lexicographic > length --- ------------------------------------------------------------ - --- V{2,4} greedy: longer match preferred -WITH test_quant_greedy AS ( +-- Reluctant unbounded quantifier over a nullable group, inside an outer +-- quantifier whose lower bound is above one. Below the bound the guard +-- must keep looping without unbounded epsilon recursion: each empty inner +-- iteration advances the count until the bound is met. Two iterations +-- (one A each, inner empty) satisfy min=2 and match rows 1-2. +WITH test_cycle_reluctant_below_min AS ( SELECT * FROM (VALUES (1, ARRAY['A']), - (2, ARRAY['A']), - (3, ARRAY['A']), - (4, ARRAY['B']) + (2, ARRAY['A']) ) 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_quant_greedy +FROM test_cycle_reluctant_below_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+?){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Same shape with a reluctant outer bound: stops at exactly two iterations +-- even though a third A row is available. +WITH test_cycle_reluctant_outer_min AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']) + ) 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_cycle_reluctant_outer_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+?){2,}?) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ============================================================ +-- Standard Clause 7: Formal Pattern Matching Rules +-- ISO/IEC 19075-5, Clause 7 +-- ============================================================ + +-- ------------------------------------------------------------ +-- 7.2.2 Alternation: first alternative is preferred +-- ------------------------------------------------------------ + +-- (A | B): A preferred over B when both could match +-- Row 1 has both A and B flags: A should be chosen (first alternative) +WITH test_alt_prefer AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_alt_prefer +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (A{1,2} | B{2,3}): all A-matches before all B-matches +-- Standard example: preferment order is AA, A, BBB, BB +-- Rows 1-2 have both A and B: greedy A{1,2} should match 1-2 +WITH test_alt_quantified AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['B']), + (5, ARRAY['B']) + ) 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_alt_quantified +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A{1,2} | B{2,3})) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (A | B B | C C C): three alternatives, all viable on every row. +-- Preferment order is A, BB, CCC: the first alternative wins even though +-- the later ones would match longer. +WITH test_alt_three_way AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B','C']), + (2, ARRAY['A','B','C']), + (3, ARRAY['A','B','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_alt_three_way +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B B | C C C)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- ((A | B | C)+): three alternatives ranked on every iteration, not just +-- once. Each row carries all three flags. +WITH test_alt_three_way_loop AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B','C']), + (2, ARRAY['A','B','C']), + (3, ARRAY['A','B','C']), + (4, ARRAY['_']) + ) 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_alt_three_way_loop +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B | C)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- (A B | A C): branches share the prefix A, so the choice is only decided +-- at row 2, which carries both B and C. The first alternative wins there. +WITH test_alt_shared_prefix AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B','C']), + (3, ARRAY['C']), + (4, ARRAY['_']) + ) 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_alt_shared_prefix +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A B | A C)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- (A B C | A B): the first alternative is the longer one and it fits, so +-- length and written order agree. Compare with the reverse below. +WITH test_alt_shared_prefix_long_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, ARRAY['_']) + ) 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_alt_shared_prefix_long_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A B C | A B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- ------------------------------------------------------------ +-- 7.2.3 Concatenation: lexicographic ordering +-- ------------------------------------------------------------ + +-- ((A | B) (C | D)): preferment order is AC, AD, BC, BD +-- Row 1 matches A and B, Row 2 matches C and D +-- Preferred match: A then C (first alternatives in both positions) +WITH test_concat_lex AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['C','D']) + ) 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_concat_lex +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B) (C | D)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + +-- ((A | B) C): first alt (A) fails, second alt (B) succeeds +-- Tests backtracking: row 1 has only B, row 2 has C +WITH test_concat_backtrack AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['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_concat_backtrack +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B) C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- ------------------------------------------------------------ +-- 7.2.4 Quantification: greedy/reluctant, lexicographic > length +-- ------------------------------------------------------------ + +-- V{2,4} greedy: longer match preferred +WITH test_quant_greedy AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) 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_quant_greedy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A{2,4}) + DEFINE + A AS 'A' = ANY(flags) +); + +-- V{2,4}? reluctant: shorter match preferred +WITH test_quant_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) 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_quant_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A{2,4}?) + DEFINE + A AS 'A' = ANY(flags) +); + +-- ((A|B){1,2}) greedy: lexicographic > length +-- Standard example: preferment AA, AB, A, BA, BB, B +-- Single A preferred over B-starting longer match +WITH test_quant_lex_greedy AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']) + ) 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_quant_lex_greedy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2})) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ((A|B){1,2}?) reluctant: lexicographic > length +-- Standard example: preferment A, AA, AB, B, BA, BB +-- Single A preferred over any B-starting match +WITH test_quant_lex_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']) + ) 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_quant_lex_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2}?)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- A+? B where every row is both A and B: stopping and continuing are both +-- viable at every step, so reluctance is actually contested. Without the +-- overlap the reluctant path is never tested against a live alternative. +WITH test_quant_reluctant_contested AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['_']) + ) 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_quant_reluctant_contested WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (A{2,4}) + PATTERN (A+? B) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) ); --- V{2,4}? reluctant: shorter match preferred -WITH test_quant_reluctant AS ( +-- A+ B over the same rows: greedy takes as many as it can while still +-- leaving a B behind. Contrast with the reluctant case above. +WITH test_quant_greedy_contested AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['_']) + ) 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_quant_greedy_contested +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (A+ B)+? C: the outer quantifier is reluctant, so it stops after one +-- iteration and takes the C available at row 3. Row 3 is also an A, which +-- would let a second iteration run; reluctance declines it. +WITH test_quant_reluctant_outer AS ( SELECT * FROM (VALUES (1, ARRAY['A']), - (2, ARRAY['A']), - (3, ARRAY['A']), - (4, ARRAY['B']) + (2, ARRAY['B']), + (3, ARRAY['A','C']), + (4, ARRAY['B']), + (5, 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_quant_reluctant +FROM test_quant_reluctant_outer WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (A{2,4}?) + PATTERN ((A+ B)+? C) DEFINE - A AS 'A' = ANY(flags) + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) ); --- ((A|B){1,2}) greedy: lexicographic > length --- Standard example: preferment AA, AB, A, BA, BB, B --- Single A preferred over B-starting longer match -WITH test_quant_lex_greedy AS ( +-- (A+ B)+ C over the same rows: outer greed takes the second iteration and +-- lands on the C at row 5 instead. Contrast with the reluctant outer above. +WITH test_quant_greedy_outer AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['B']) + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A','C']), + (4, ARRAY['B']), + (5, 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_quant_lex_greedy +FROM test_quant_greedy_outer WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (((A | B){1,2})) + PATTERN ((A+ B)+ C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- A{2}? B: an exact bound leaves no choice, so the reluctant mark must not +-- change anything. Overlap on rows 2-3 would expose a bound lowered to +-- {0,2}? or {1,2}?. +WITH test_quant_reluctant_exact AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['B']) + ) 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_quant_reluctant_exact +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A{2}? B) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); --- ((A|B){1,2}?) reluctant: lexicographic > length --- Standard example: preferment A, AA, AB, B, BA, BB --- Single A preferred over any B-starting match -WITH test_quant_lex_reluctant AS ( +-- A{2} B: the greedy spelling of the same bound, for contrast. +WITH test_quant_exact AS ( SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['B']) + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['A','B']), + (4, ARRAY['B']) ) 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_quant_lex_reluctant +FROM test_quant_exact WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW - PATTERN (((A | B){1,2}?)) + PATTERN (A{2} B) DEFINE A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) @@ -3876,6 +4727,58 @@ WINDOW w AS ( A AS 'A' = ANY(flags) ); +-- (A? | B){3}: an empty iteration below min fills the lower bound (STR06), +-- and it must outrank the later branch. Row 2 is B only, so A? derives empty +-- there; repeating that derivation fills the remaining iterations and the +-- match ends at row 1. Taking branch B instead would consume rows 2-3. +WITH test_728_empty_fills_min AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_empty_fills_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){3}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- The same pattern unrolled. Consecutive identical alternations are merged +-- into the rolled form above, so the two must agree. +WITH test_728_empty_fills_min_unrolled AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) 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_empty_fills_min_unrolled +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B) (C? | D) (E? | F)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'A' = ANY(flags), + D AS 'B' = ANY(flags), + E AS 'A' = ANY(flags), + F AS 'B' = ANY(flags) +); + -- (A? B?){2,3}: multi-element nullable body with real matches -- Body A? B? is nullable (both optional), but A and B DO match rows. -- Real (non-empty) iterations loop back normally; fast-forward only @@ -3958,6 +4861,211 @@ WINDOW w AS ( B AS 'B' = ANY(flags) ); + +-- The stopping rule also governs an alternation body. On A,B the greedy +-- (A? | B)* takes A in iteration 1; in iteration 2 the preferred branch A? +-- matches empty, so the quantifier stops and B never consumes row 2. +WITH test_empty_stop_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']) + ) 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_empty_stop_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- With min = max the group's own greed says nothing, so the body decides +-- whether the empty match is preferred: {n}? must equal {n}. A? prefers to +-- consume (both forms take two rows); A?? prefers empty (both match empty). +WITH test_fixed_quant_body_greed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + count(*) OVER g AS greedy_body, -- ((A?){2}) + count(*) OVER gr AS greedy_body_rel, -- ((A?){2}?) + count(*) OVER r AS rel_body, -- ((A??){2}) + count(*) OVER rr AS rel_body_rel -- ((A??){2}?) +FROM test_fixed_quant_body_greed +WINDOW g AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A?){2})) + DEFINE A AS 'A' = ANY(flags)), + gr AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A?){2}?)) + DEFINE A AS 'A' = ANY(flags)), + r AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A??){2})) + DEFINE A AS 'A' = ANY(flags)), + rr AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (((A??){2}?)) + DEFINE A AS 'A' = ANY(flags)) +ORDER BY id; +-- (A* | B)*: A* is the preferred alternative and matches empty at row 3, +-- which ends the loop by the lower-bound stopping rule. B is never tried, +-- so the match stops short of the B rows even though taking them would be +-- longer. Perl agrees: (a*|b)* against "aabb" matches "aa". +WITH test_728_nullable_alt_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A* | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (B | A*)*: same body, alternatives swapped. B is preferred and consumes, +-- so no empty iteration arises and the loop reaches the B rows. +WITH test_728_nullable_alt_second AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_second +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((B | A*)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (A+ | B)*: the first alternative is not nullable, so it cannot produce an +-- empty iteration and the loop reaches the B rows. Compare with (A* | B)*. +WITH test_728_nonnullable_alt_first AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nonnullable_alt_first +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A+ | B)*) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- (A? | B){2,3}: the stop rule binds at the lower bound even when the +-- upper bound could still admit more iterations. Iterations one and two +-- go empty via A?, which stops the loop at min; C then fails at row 1 and +-- backtracking REPLACES iteration two with B instead of extending, so the +-- match runs B, A, C = rows 1-3. Perl agrees: (?:a?|b){2,3}c backtracks +-- the same way. An engine that keeps iterating after the empty stop +-- returns rows 1-2 via the shorter empty-empty-B derivation instead. +WITH test_728_stop_binds_at_min 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_binds_at_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){2,3} 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. +WITH test_728_exact_below_min 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_exact_below_min +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){3} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- (A? | B){2,}: the stopping rule applies above the lower bound as well. +-- Two iterations consume the A rows and satisfy min=2; the third matches +-- empty via A? and ends the loop before any B is taken. +WITH test_728_nullable_alt_min2 AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['B']) + ) 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_nullable_alt_min2 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A? | B){2,}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + -- ------------------------------------------------------------ -- 7.3 Pattern matching in theory and practice -- ------------------------------------------------------------ -- 2.50.1 (Apple Git-155)