From 5524dccf54e5bcd92f396c0e690a743bd3356bba 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. Leave the group there rather than discarding the state, which demoted "stop here" below the remaining alternatives and let a less-preferred branch consume rows. Below the bound the quantifier cannot exit, so fall through to the normal loop-back, which keeps reachable the derivation that goes empty first and consumes later -- the preferred one. 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. A skip path landing directly on an outer END did not count the iteration, so the group failed its min check although it had run often enough. Count it, as the exit path in nfa_advance_var does; the guard's below-min fall-through reaches the bound on those same increments. Narrowing the guard to nullable ENDs stops FIN being marked, so one expansion can reach it more than once, and the later arrival is the less preferred one: an END that has met its lower bound explores the loop first and its own exit afterwards, and both run to FIN. The paths that cut less-preferred alternatives each saved ctx->matchedState and compared it after their sub-expansion, which only sees what that one call did -- a match recorded before the save is invisible, so the exit ran and overwrote the preferred match with its own. Record the fact in the context instead. nfa_advance() clears matchUpdated when it starts and nfa_add_matched_state() sets it, so every frame that is unwinding sees a match made anywhere in the advance, not only in the call it made itself. The saved copies go away with it, and with them the assumption that an address identifies a state: nfa_state_free() puts freed states on a LIFO list, so a later allocation can return the same address. Three paths were then found to have no such test at all, all of them the greedy half of a pair whose reluctant half had one: entering a group before skipping it in nfa_advance_begin(), and looping before either the fast-forward or the exit in nfa_advance_end(). Each explores its first choice, which outranks the second, and then explored the second anyway -- so the second reached FIN and overwrote the preferred match with its own. Test there too, and free the state prepared for the path not taken. Nothing in the expected output moved, because the two matches cover the same rows: an advance records at the row it is on, so both spans start and end alike and only the state behind them differs. What the second record does change is what stays in ctx->states, and a state parked after a match can complete on a later row and replace it -- the mechanism this commit already narrows in nfa_advance_alt(). Assert in nfa_add_matched_state() that an advance records once, and in nfa_add_state_unique() that nothing is parked after it has. The three paths above were found by those assertions and by nothing else, no output having moved either way, so rpr_nfa drives each of them from a query of its own: removing any one of the three fails that file in a cassert build. nfa_advance_alt() explored every branch even after one had matched. A later branch could replace the preferred match either by reaching FIN in the same DFS or by parking states that complete on a later row; the second is the one that shows in output, as (A* | B) matching empty on a row where B would have consumed one. Stop the walk, and say in the comment which of the two the break is really for. 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 -- duplicated at every exit path. Fold it into nfa_exit_to() so the convention has one definition. An empty match was classified as a failure in the NFA statistics rather than the length-0 success it is. README.rpr's flag table listed the two absorption flags at 0x04 and 0x08, which RPR_ELEM_EMPTY_PREFERRED displaces to 0x08 and 0x10, and did not mention the new flag at all. IV-4b covered only RPR_ELEM_EMPTY_LOOP, and IX-4(c) said the fast-forward exists without saying what orders it against the loop-back. The below-min fall-through advances the count one empty iteration at a time and each step is a recursion, so its cost follows the lower bound, which the grammar caps only at RPR_QUANTITY_INF. IX-6 records that, and why the steps cannot be collapsed by setting the count to the bound: the intermediate counts are the enumeration order, and ((A? | B){4} C) needs the loop-back at count 3 specifically. A test under a reduced max_stack_depth pins the depth. Narrowing the marks takes the deferred marking out of nfa_add_state_unique() too, so what reaches its duplicate check changes -- and nothing observed that count. Every NFA States line in the expected output read 0 merged, because the DEFINE sets in that section of rpr_explain are mutually exclusive and two branches never arrive at the same state. A case with overlapping DEFINEs records 14 merges. 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 | 167 +- src/backend/executor/execRPR.c | 410 +++-- src/backend/executor/nodeWindowAgg.c | 4 +- src/backend/optimizer/plan/rpr.c | 121 +- src/include/nodes/execnodes.h | 8 +- src/include/optimizer/rpr.h | 7 +- src/test/regress/expected/rpr_base.out | 15 +- src/test/regress/expected/rpr_explain.out | 66 +- src/test/regress/expected/rpr_nfa.out | 1967 +++++++++++++++++++-- src/test/regress/sql/rpr_base.sql | 11 +- src/test/regress/sql/rpr_explain.sql | 24 + src/test/regress/sql/rpr_nfa.sql | 1567 ++++++++++++++-- 12 files changed, 3824 insertions(+), 543 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 7616676cfd6..5b64e0b96a5 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -295,14 +295,19 @@ Element flags (1 byte, bitmask): loop-back so cycle detection doesn't kill legitimate matches. (IV-4b) - 0x04 RPR_ELEM_ABSORBABLE_BRANCH (VAR, BEGIN, END, ALT) + 0x04 RPR_ELEM_EMPTY_PREFERRED (END) + Group body prefers the empty match over a consuming one. + Orders the fast-forward ahead of the loop-back below min, + where the group's own greed says nothing. (IV-4b) + + 0x08 RPR_ELEM_ABSORBABLE_BRANCH (VAR, BEGIN, END, ALT) Element lies within an absorbable region. Used at runtime to track whether the current NFA state is in an absorbable context. See "IV-5. Absorbability Analysis" and "VIII-2. Solution: Context Absorption" for more details about absorption. - 0x08 RPR_ELEM_ABSORBABLE (VAR, END) + 0x10 RPR_ELEM_ABSORBABLE (VAR, END) Absorption comparison point. Where to compare consecutive iterations for absorption. - Simple unbounded VAR (A+): set on the VAR itself @@ -311,8 +316,9 @@ Element flags (1 byte, bitmask): Accessor macros: RPRElemIsReluctant(e) (e)->flags & 0x01 RPRElemCanEmptyLoop(e) (e)->flags & 0x02 - RPRElemIsAbsorbableBranch(e) (e)->flags & 0x04 - RPRElemIsAbsorbable(e) (e)->flags & 0x08 + RPRElemIsEmptyPreferred(e) (e)->flags & 0x04 + RPRElemIsAbsorbableBranch(e) (e)->flags & 0x08 + RPRElemIsAbsorbable(e) (e)->flags & 0x10 Roles of next and jump: @@ -440,31 +446,36 @@ At runtime (nfa_advance), the flag controls Depth-First Search The absorption optimization requires greedy quantifiers. Reluctant quantifiers are excluded from absorbability analysis (see IV-5). -IV-4b. Empty Loop Flag (RPR_ELEM_EMPTY_LOOP) +IV-4b. Empty Match Flags (RPR_ELEM_EMPTY_LOOP, RPR_ELEM_EMPTY_PREFERRED) -The empty-loop flag is set during Phase 4 (fillRPRPatternGroup) on the END -element when the group body is nullable -- i.e., every path through the -body can match zero rows (all children are nullable). +Both flags are set during Phase 4 (fillRPRPatternGroup) on the END element +and describe the group's body, not the group itself. fillRPRPattern* +returns them for every node and the END inherits the body's pair: a +concatenation carries a bit only when every child does (AND), an +alternation is nullable when any branch is (OR) but takes its preference +from the first branch alone, since leftmost-choice-first makes that the +preferred one. -Example patterns that trigger this flag: +RPR_ELEM_EMPTY_LOOP -- the body is nullable, i.e. every path through it +can match zero rows: (A?)* A is nullable (min=0), so group body is nullable -> END gets flag (A? B?)+ Both children nullable -> body nullable -> END gets flag (A | B*) B* is nullable, making the ALT nullable -> END gets flag -The flag works in conjunction with the empty match cycle detection -(elemIdx visited bitmap). Without this flag, cycle detection alone would -cause legitimate matches to fail. - -Problem example: (A*){2,3} - - Iteration 1: A* consumes all available rows -> count=1, END reached - - Loop-back for iteration 2: A* matches zero rows -> END reached again - - Cycle detection sees the same elemIdx on the same row -> state killed - - count never reaches min(2) -> match fails (incorrect) - -With the RPR_ELEM_EMPTY_LOOP flag, nfa_advance_end creates two paths: -the normal loop-back (which cycle detection will eventually kill) and -a fast-forward exit clone that bypasses the loop entirely. +It marks the END for the cycle detection of IX-6, which only ever tests a +nullable END, and it lets nfa_advance_end offer a fast-forward exit beside +the loop-back below min. Without it, (A*){2,3} could not reach its lower +bound: iteration 1 consumes every available row, iteration 2 derives an +empty match, and nothing would carry the count to min(2). + +RPR_ELEM_EMPTY_PREFERRED -- the body's preferred derivation is the empty +one, which is what orders those two paths. A bare variable consumes a +row; only a reluctant quantifier that may take zero repetitions prefers to +skip it. The group's own greed cannot decide this: in ((A?){2}?) min +equals max, so the group has no choice of iteration count left to be +greedy or reluctant about, while the body A? still prefers to consume a +row. The flag is what distinguishes ((A?){2}?) from ((A??){2}). (See IX-4(c) for detailed runtime behavior.) IV-5. Absorbability Analysis (RPR_ELEM_ABSORBABLE) @@ -589,7 +600,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 @@ -663,8 +674,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() @@ -1001,9 +1020,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) @@ -1036,8 +1061,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: @@ -1061,6 +1091,11 @@ IX-4. Per-Element advance Behavior and exits via next (treating the remaining required iterations as empty matches). + The body decides which of the two comes first, not the group's own + greed: the fast-forward is explored first exactly when + RPR_ELEM_EMPTY_PREFERRED is set (IV-4b). If it then reaches FIN, + the loop-back is dropped, as in the min <= count < max arm below. + min <= count < max: Greedy: loop-back first, exit second Reluctant: exit first, loop-back second @@ -1117,7 +1152,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. @@ -1136,22 +1171,58 @@ 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, and it is the preferred + one: ((A? | B){3} C) over rows {B},{A,C},{C} matches rows 1-2 by + going empty twice and taking B on the third iteration, not rows 1-3 + by taking B on the first. 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. + + The count advances one empty iteration at a time, and each step is a + recursion, so the cost follows the lower bound -- which the grammar + caps only at RPR_QUANTITY_INF. The steps cannot be collapsed by + setting the count to the bound directly: the intermediate counts are + the enumeration order, and each one parks the body's consuming + branches at a rank of its own. ((A? | B){4} C) over rows + {B},{A},{A,C},{C} matches rows 1-3, which needs the loop-back at + count 3 specifically. + + That bound is on the count, not on the expansion. Within one + expansion only a nullable END is marked, so ALT and BEGIN may be + re-entered any number of times; where several alternations in a row + have nullable branches, the expansion enumerates paths instead of + states and costs 2^k for k such alternations. See the XXX at the + marking site in nfa_advance_state(). + + Marks are never cleared during a DFS. Clearing the body's marks on a + below-min loop-back would disarm the guard for any nested reluctant + unbounded quantifier inside the body, whose empty iterations then + recurse without bound: (A (B*?)+?){2,} on a single matching row. The + outer count does not advance while the inner one spins, so "the count + stops at min" is not on its own a termination argument. Chapter X Match Result Processing ============================================================================ @@ -1486,8 +1557,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 @@ -1615,7 +1686,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 f119f4545d3..e2468fee047 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 * @@ -353,12 +389,11 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState * 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. + * Nothing is parked once this advance has recorded: a state kept here + * survives to the next row, where it could complete and replace the match + * that outranks it. */ - nfa_mark_visited(winstate, state->elemIdx); + Assert(!ctx->matchUpdated); /* Check for duplicate and find tail */ for (s = ctx->states; s != NULL; s = s->next) @@ -398,6 +433,13 @@ static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, int64 matchEndRow) { + /* + * One advance records at most one match. The guards below stop every + * less-preferred path once matchUpdated is set, so arriving here twice + * would mean a path that can reach FIN is not reading it. + */ + Assert(!ctx->matchUpdated); + if (ctx->matchedState != NULL) nfa_state_free(winstate, ctx->matchedState); @@ -405,6 +447,14 @@ nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, state->next = NULL; ctx->matchEndRow = matchEndRow; + /* + * Tell the frames that are unwinding. FIN is not marked visited, so an + * expansion can reach it more than once, and the later arrival is the + * less preferred one: the paths that cut less-preferred alternatives read + * this and stop rather than record again. + */ + ctx->matchUpdated = true; + /* Prune contexts that started within this match's range */ if (winstate->rpSkipTo == ST_PAST_LAST_ROW) { @@ -415,6 +465,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 +504,7 @@ nfa_context_make(WindowAggState *winstate) ctx->matchEndRow = -1; ctx->lastProcessedRow = -1; ctx->matchedState = NULL; + ctx->matchUpdated = false; /* Initialize two-flag absorption design based on pattern */ ctx->hasAbsorbableState = winstate->rpPattern->isAbsorbable; @@ -797,7 +850,10 @@ 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. An unbounded VAR + * never reaches the test: Case 1 of isUnboundedStart() gives a simple + * unbounded VAR both absorption flags, and Case 2 marks only fixed-length + * children, so the flag pair the test sits behind excludes it. * - Chains through END elements while count >= max (must-exit path) * * Non-VAR elements (ALT, END, FIN) are kept as-is for advance phase. @@ -976,13 +1032,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: + * a skipped iteration still ran, and that count is what the + * group's min check and the cycle guard's below-min fall-through + * both read. + */ + landElem = &winstate->rpPattern->elements[skipState->elemIdx]; + if (RPRElemIsEnd(landElem) && + skipState->counts[landElem->depth] < RPR_COUNT_INF) + skipState->counts[landElem->depth]++; + } + if (skipState != NULL && RPRElemIsReluctant(nextElem)) { - RPRNFAState *savedMatch = ctx->matchedState; - /* * Reluctant optional VAR: prefer skipping. Explore the skip path * first so it outranks the enter (match) path; if it reaches FIN @@ -992,7 +1062,7 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, */ nfa_advance_state(winstate, ctx, skipState, currentPos); - if (ctx->matchedState != savedMatch) + if (ctx->matchUpdated) { nfa_state_free(winstate, state); return; @@ -1047,6 +1117,25 @@ 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: a + * later branch would either reach FIN in this same DFS and replace + * the preferred match, or park states that complete on a later row + * and replace it then. Same technique as the reluctant paths in + * nfa_route_to_elem and nfa_advance_begin. + * + * PATTERN (A* | B) on a row where A is false and B is true: the A* + * branch is explored first, its skip path runs straight to FIN, and + * the empty match is recorded here. Breaking leaves that match + * standing, which is what the preference order asks for. Without the + * break, B would be expanded too, would match the row, and its + * one-row match would replace the empty one, as if the pattern were + * written (B | A*). + */ + if (ctx->matchUpdated) + break; + Assert(sepIdx >= 0 && sepIdx < pattern->numElements); sepElem = &elements[sepIdx]; Assert(RPRElemIsSep(sepElem)); @@ -1087,23 +1176,29 @@ 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; - /* Reluctant: skip first (prefer fewer iterations), enter second */ nfa_route_to_elem(winstate, ctx, skipState, &elements[elem->jump], currentPos); - /* - * If skip path reached FIN, shortest match is found. Skip group entry - * to prevent longer matches. - */ - if (ctx->matchedState != savedMatch) + /* The skip matched: do not enter the group over it */ + if (ctx->matchUpdated) { nfa_state_free(winstate, state); return; @@ -1125,6 +1220,14 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, nfa_route_to_elem(winstate, ctx, state, &elements[state->elemIdx], currentPos); + /* Entering matched: do not take the skip over it */ + if (ctx->matchUpdated) + { + if (skipState != NULL) + nfa_state_free(winstate, skipState); + return; + } + if (skipState != NULL) { nfa_route_to_elem(winstate, ctx, skipState, @@ -1167,11 +1270,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; see the cycle guard in nfa_advance_state. + */ state->elemIdx = elem->jump; jumpElem = &elements[state->elemIdx]; - if (ffState != NULL && RPRElemIsReluctant(elem)) + if (ffState != NULL && RPRElemIsEmptyPreferred(elem)) { - RPRNFAState *savedMatch = ctx->matchedState; - - /* 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); - /* - * 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) + /* The fast-forward matched: do not loop back over it */ + if (ctx->matchUpdated) { nfa_state_free(winstate, state); return; @@ -1228,6 +1320,15 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, /* Greedy (or non-nullable): loop-back first, fast-forward second */ nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos); + + /* The loop-back matched: do not fast-forward over it */ + if (ctx->matchUpdated) + { + if (ffState != NULL) + nfa_state_free(winstate, ffState); + return; + } + if (ffState != NULL) nfa_route_to_elem(winstate, ctx, ffState, nextElem, currentPos); @@ -1238,18 +1339,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); } @@ -1270,13 +1360,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; @@ -1284,17 +1368,12 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, if (RPRElemIsReluctant(elem)) { - RPRNFAState *savedMatch = ctx->matchedState; - /* Exit first (preferred for reluctant) */ nfa_route_to_elem(winstate, ctx, exitState, nextElem, currentPos); - /* - * If exit path reached FIN, shortest match is found. Skip loop to - * prevent longer matches from replacing it. - */ - if (ctx->matchedState != savedMatch) + /* The exit matched: do not loop over it */ + if (ctx->matchUpdated) { nfa_state_free(winstate, state); return; @@ -1309,6 +1388,14 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, /* Loop first (preferred for greedy) */ nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos); + + /* The loop matched: do not exit over it */ + if (ctx->matchUpdated) + { + nfa_state_free(winstate, exitState); + return; + } + /* Exit second */ nfa_route_to_elem(winstate, ctx, exitState, nextElem, currentPos); @@ -1328,7 +1415,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); @@ -1356,31 +1442,17 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, */ if (reluctant) { - RPRNFAState *savedMatch = ctx->matchedState; - /* 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, currentPos); - /* - * If exit path reached FIN, the shortest match is found. Skip - * loop state to prevent longer matches from replacing it. - */ - if (ctx->matchedState != savedMatch) + /* The exit matched: do not loop over it */ + if (ctx->matchUpdated) { nfa_state_free(winstate, state); return; @@ -1398,28 +1470,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); @@ -1436,24 +1488,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); } @@ -1477,23 +1512,71 @@ 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 any other loop-back has consumed a row. Dropping one + * loses the match outright -- ((A | B B){1,3}){3} then finds nothing. + */ + 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. + * Only a nullable END is ever tested; see the guard above. + * + * XXX this bounds the cycle, not the cost. Leaving ALT and BEGIN + * unmarked lets them be re-entered any number of times within one + * expansion, so a run of alternations whose branches are all nullable + * enumerates paths rather than states: nfa_advance_alt() recurses once + * per branch and fillRPRPatternAlt() converges every branch tail on the + * same element, making k such alternations cost 2^k. (A?|B?){30} takes + * over half an hour, and the recursion depth stays at k, so + * check_stack_depth() never fires. Bounding the cost needs a revisit key + * of (elemIdx, counts); this bitmap identifies elemIdx alone. */ - if (!RPRElemIsVar(elem)) + if (RPRElemCanEmptyLoop(elem)) nfa_mark_visited(winstate, state->elemIdx); switch (elem->varId) @@ -1537,15 +1620,14 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos) { RPRNFAState *states = ctx->states; RPRNFAState *state; - RPRNFAState *savedMatchedState; ctx->states = NULL; /* Will rebuild */ + ctx->matchUpdated = false; /* Process each state in lexical order (DFS order from previous advance) */ while (states != NULL) { CHECK_FOR_INTERRUPTS(); - savedMatchedState = ctx->matchedState; /* * Clear visited bitmap before each state's DFS expansion. Only the @@ -1557,7 +1639,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)); @@ -1585,7 +1667,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->matchUpdated && states != NULL) { nfa_state_free_list(winstate, states); break; @@ -1680,11 +1762,13 @@ ExecRPRStartContext(WindowAggState *winstate, int64 startPos) /* * Add to tail of active context list (doubly-linked, oldest-first). - * matchStartRow is nondecreasing along the list, so the head holds the - * smallest -- an ordering other code relies on. + * matchStartRow increases along the list, so the head holds the smallest + * -- an ordering other code relies on. At most one context starts at a + * row: the on-demand path in update_reduced_frame creates one only where + * none exists. */ Assert(winstate->nfaContextTail == NULL || - startPos >= winstate->nfaContextTail->matchStartRow); + startPos > winstate->nfaContextTail->matchStartRow); ctx->prev = winstate->nfaContextTail; ctx->next = NULL; if (winstate->nfaContextTail != NULL) @@ -1699,8 +1783,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); @@ -1857,7 +1941,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); @@ -1936,8 +2027,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; /* @@ -1974,10 +2070,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. @@ -1994,6 +2092,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 d5d96ca7a77..e9d2c86305a 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -3054,8 +3054,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 bc58345b64b..1f7a9b4b6df 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -75,14 +75,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, @@ -1269,12 +1269,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); @@ -1289,7 +1293,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; } /* @@ -1310,16 +1321,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) @@ -1342,11 +1357,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) @@ -1366,13 +1379,8 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de if (node->reluctant) 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. - */ - if (bodyNullable) - endElem->flags |= RPR_ELEM_EMPTY_LOOP; + /* The END carries the body's bits, not the group's; see README IV-4b */ + endElem->flags |= bodyFlags; (*idx)++; @@ -1380,7 +1388,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; } /* @@ -1400,10 +1416,13 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de * SEP is a marker, never a state: a branch's tail and a branch-terminal * group's BEGIN skip are redirected past the alternation. * - * 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; @@ -1413,7 +1432,10 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept List *altBranchStarts = NIL; List *altEndPositions = 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]; @@ -1434,10 +1456,18 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept { int branchStart = *idx; 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, so it sits at branch end + 1 */ @@ -1518,7 +1548,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); } /* @@ -1529,14 +1559,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); @@ -1545,12 +1575,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); @@ -1563,7 +1594,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 63204795977..2f85c325f31 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2569,7 +2569,9 @@ typedef struct RPRNFAContext int64 matchStartRow; /* row where match started */ 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) */ + RPRNFAState *matchedState; /* this context's match candidate, or NULL */ + bool matchUpdated; /* matchedState was set or replaced during the + * advance now running */ /* Two-flag absorption optimization */ bool hasAbsorbableState; /* can absorb others (>=1 absorbable @@ -2668,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 5ef73003405..800f547cbb1 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 56b252c2078..8e8093380ef 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -859,12 +859,54 @@ 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) +-- Overlapping DEFINEs let two branches reach the same state, so this is the +-- only case here with a nonzero merged count; the alt_merge names above mean +-- the optimizer's merge of consecutive ALTs, not this counter. +CREATE VIEW rpr_ev_state_dedup AS +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B){2,4}) + DEFINE A AS v % 2 = 1, B AS v % 3 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_state_dedup'), E'\n')) AS line WHERE line ~ 'PATTERN'; + line +--------------------------- + PATTERN ((a | b){2,4}) +(1 row) + +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B){2,4}) + DEFINE A AS v % 2 = 1, B AS v % 3 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=40.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a | b){2,4} + Nav Mark Lookback: 0 + Storage: Memory Maximum Storage: NkB + NFA States: 6 peak, 201 total, 14 merged + NFA Contexts: 3 peak, 41 total, 14 pruned + NFA: 6 matched (len 3/3/3.0), 8 mismatched (len 2/2/2.0) + NFA: 0 absorbed, 12 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=40.00 loops=1) +(10 rows) + -- ============================================================ -- Context Statistics Tests (peak, total, pruned + absorbed/skipped) -- ============================================================ @@ -2531,8 +2573,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 +2611,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 +5216,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 +5253,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 aa762c9dd58..f49d7e4963a 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 -- ============================================================ @@ -2931,6 +3060,64 @@ WINDOW w AS ( 2 | {_,C} | | (2 rows) +-- Preference beats length even when the preferred branch matches empty: the +-- A* branch reaches FIN with no rows consumed and nfa_advance_alt stops there, +-- so B is never expanded on a row where it would have matched. +WITH test_alt_empty_pref AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['_', 'B']), + (3, ARRAY['A', 'B']), + (4, ARRAY['_', 'B']) + ) AS t(id, flags) +) +SELECT id, flags, count(*) OVER w AS n +FROM test_alt_empty_pref +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 | n +----+-------+--- + 1 | {A,B} | 1 + 2 | {_,B} | 0 + 3 | {A,B} | 1 + 4 | {_,B} | 0 +(4 rows) + +-- Swapping the branches makes B preferred, so every row matches one row. +WITH test_alt_empty_pref AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['_', 'B']), + (3, ARRAY['A', 'B']), + (4, ARRAY['_', 'B']) + ) AS t(id, flags) +) +SELECT id, flags, count(*) OVER w AS n +FROM test_alt_empty_pref +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 | n +----+-------+--- + 1 | {A,B} | 1 + 2 | {_,B} | 1 + 3 | {A,B} | 1 + 4 | {_,B} | 1 +(4 rows) + -- ALT with reluctant: (A+? | B+) - A branch is reluctant, B is greedy. -- Row 1 matches both A and B. A+? exits immediately (match 1-1). WITH test_alt_reluctant AS ( @@ -2962,7 +3149,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 +3173,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 +3201,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 +3229,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,6 +3577,39 @@ WINDOW w AS ( 4 | {_} | | (4 rows) +-- ((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['_']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, 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_nonlast_optgroup +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((B C)* | A) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {_} | | + 2 | {B} | 2 | 3 + 3 | {C} | | + 4 | {A} | | +(4 rows) + -- (((B C)* | A) D): the ALT is followed by D, so a zero-match (B C)* must -- continue into D. Row 4 (a lone D) exercises that; row 1 is the B C D match. WITH test_alt_optgroup_then_elem AS ( @@ -3460,129 +3681,323 @@ WINDOW w AS ( 5 | {_} | | (5 rows) --- ============================================================ --- Deep Nested Groups --- ============================================================ --- Three-level nesting ((((A B)+)+)+) -WITH test_deep_nesting AS ( +-- ((B C)*? | A): a reluctant optional group as a branch prefers zero +-- 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['A']), - (2, ARRAY['B']), + (1, ARRAY['B']), + (2, ARRAY['C']), (3, ARRAY['A']), - (4, ARRAY['B']), - (5, ARRAY['A']), - (6, ARRAY['B']), - (7, ARRAY['_']) + (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_deep_nesting +FROM test_alt_reluctant_optgroup 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 ((B C)*? | A) DEFINE A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags) + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 6 - 2 | {B} | | - 3 | {A} | 3 | 6 - 4 | {B} | | - 5 | {A} | 5 | 6 - 6 | {B} | | - 7 | {_} | | -(7 rows) + 1 | {B} | | + 2 | {C} | | + 3 | {A} | | + 4 | {_} | | +(4 rows) --- Multiple groups in nesting (((A B) (C D))+) -WITH test_nested_sequential AS ( +-- 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['B']), - (3, ARRAY['C']), - (4, ARRAY['D']), - (5, ARRAY['A']), - (6, ARRAY['B']), - (7, ARRAY['C']), - (8, ARRAY['D']), - (9, ARRAY['_']) + (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_nested_sequential +FROM test_alt_quant_reentry WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN (((A B) (C D))+) + AFTER MATCH SKIP PAST LAST ROW + INITIAL + 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) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 8 - 2 | {B} | | - 3 | {C} | | - 4 | {D} | | - 5 | {A} | 5 | 8 - 6 | {B} | | - 7 | {C} | | - 8 | {D} | | - 9 | {_} | | -(9 rows) + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | +(3 rows) --- Nested END->END max reached --- Inner group (A B){2} reaches max=2 -> exits to outer END -WITH test_end_nested_max AS ( +-- 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['B']), - (3, ARRAY['A']), - (4, ARRAY['B']), - (5, ARRAY['A']), - (6, ARRAY['B']), - (7, ARRAY['A']), - (8, ARRAY['B']), - (9, ARRAY['_']) + (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_end_nested_max +FROM test_alt_quant_reentry_order WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN (((A B){2})+) + 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 | 8 - 2 | {B} | | - 3 | {A} | 3 | 6 - 4 | {B} | | - 5 | {A} | 5 | 8 - 6 | {B} | | - 7 | {A} | | - 8 | {B} | | - 9 | {_} | | -(9 rows) + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | +(3 rows) --- Nested END->END between min/max +-- 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 +-- ============================================================ +-- Three-level nesting ((((A B)+)+)+) +WITH test_deep_nesting AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']), + (5, ARRAY['A']), + (6, ARRAY['B']), + (7, 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_deep_nesting +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 | 6 + 2 | {B} | | + 3 | {A} | 3 | 6 + 4 | {B} | | + 5 | {A} | 5 | 6 + 6 | {B} | | + 7 | {_} | | +(7 rows) + +-- Multiple groups in nesting (((A B) (C D))+) +WITH test_nested_sequential AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, ARRAY['D']), + (5, ARRAY['A']), + (6, ARRAY['B']), + (7, ARRAY['C']), + (8, ARRAY['D']), + (9, 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_nested_sequential +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 | 8 + 2 | {B} | | + 3 | {C} | | + 4 | {D} | | + 5 | {A} | 5 | 8 + 6 | {B} | | + 7 | {C} | | + 8 | {D} | | + 9 | {_} | | +(9 rows) + +-- Nested END->END max reached +-- Inner group (A B){2} reaches max=2 -> exits to outer END +WITH test_end_nested_max AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']), + (5, ARRAY['A']), + (6, ARRAY['B']), + (7, ARRAY['A']), + (8, ARRAY['B']), + (9, 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_end_nested_max +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 | 8 + 2 | {B} | | + 3 | {A} | 3 | 6 + 4 | {B} | | + 5 | {A} | 5 | 8 + 6 | {B} | | + 7 | {A} | | + 8 | {B} | | + 9 | {_} | | +(9 rows) + +-- Nested END->END between min/max -- Inner group (A B){1,3} exits between min/max -> outer END count++ WITH test_end_nested_mid AS ( SELECT * FROM (VALUES @@ -3721,13 +4136,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']), @@ -3791,9 +4203,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 @@ -3826,76 +4237,382 @@ 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']), - (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) ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 4 - 2 | {A} | 2 | 4 - 3 | {A} | 3 | 4 - 4 | {A} | 4 | 4 - 5 | {_} | | -(5 rows) + 1 | {A} | 1 | 8 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | + 5 | {A} | | + 6 | {A,B} | | + 7 | {B} | | + 8 | {A} | | +(8 rows) --- 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']), + (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) + +-- Bound above the empty-then-consume cases above. The rows are the same at +-- every bound from 2 up while the derivation shifts, so a shortcut through +-- the below-min counts first shows here, where they are not adjacent. +WITH test_empty_then_consume_bound AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A']), + (3, ARRAY['A','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_empty_then_consume_bound +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){4} 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} | | + 3 | {A,C} | | + 4 | {C} | 4 | 4 +(4 rows) + +-- Recursion depth of the same below-min path: the fall-through advances the +-- count by one empty iteration at a time, so the depth follows the bound. +-- Reduced stack so the limit is reached quickly. +SET max_stack_depth = '100kB'; +WITH test_below_min_depth 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_below_min_depth +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){10000} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); +ERROR: stack depth limit exceeded +HINT: Increase the configuration parameter "max_stack_depth" (currently 100kB), after ensuring the platform's stack depth limit is adequate. +RESET max_stack_depth; +-- (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']), + (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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A} | 2 | 4 + 3 | {A} | 3 | 4 + 4 | {A} | 4 | 4 + 5 | {_} | | +(5 rows) + +-- 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) @@ -3987,6 +4704,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) -- ============================================================ @@ -4774,6 +5553,264 @@ WINDOW w AS ( 4 | {C} | | (4 rows) +-- (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']), + (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_nullable +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 +(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) + +-- ------------------------------------------------------------ +-- Preferment guards: the path explored second must not record +-- over a match the first one already made +-- ------------------------------------------------------------ +-- +-- Where two paths leave the same element the first is the preferred one, so +-- once it has recorded a match the second must not run. Both derivations +-- cover the same rows below, so the output is the same either way; what +-- fails when a guard is removed is an assertion, in a cassert build. +-- Entering a group before skipping it. +WITH test_guard_begin_enter 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_guard_begin_enter +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)*){1,3}) + 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) + +-- Below the lower bound, looping back before the fast-forward. +WITH test_guard_end_below_min 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_guard_end_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,4}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {B} | 2 | 2 +(2 rows) + +-- Between the bounds, looping before the exit. Here the second path parks +-- a state instead of reaching FIN. +WITH test_guard_end_loop_exit 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_guard_end_loop_exit +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+){2,3}) + 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) + -- ============================================================ -- Standard Clause 7: Formal Pattern Matching Rules -- ISO/IEC 19075-5, Clause 7 @@ -4844,6 +5881,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 -- ------------------------------------------------------------ @@ -4982,49 +6146,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) @@ -5207,6 +6565,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 @@ -5312,6 +6734,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_explain.sql b/src/test/regress/sql/rpr_explain.sql index ab8811d4024..ee80d4090e4 100644 --- a/src/test/regress/sql/rpr_explain.sql +++ b/src/test/regress/sql/rpr_explain.sql @@ -546,6 +546,30 @@ WINDOW w AS ( DEFINE A AS v % 3 <> 0 );'); +-- Overlapping DEFINEs let two branches reach the same state, so this is the +-- only case here with a nonzero merged count; the alt_merge names above mean +-- the optimizer's merge of consecutive ALTs, not this counter. +CREATE VIEW rpr_ev_state_dedup AS +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B){2,4}) + DEFINE A AS v % 2 = 1, B AS v % 3 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_state_dedup'), E'\n')) AS line WHERE line ~ 'PATTERN'; +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B){2,4}) + DEFINE A AS v % 2 = 1, B AS v % 3 = 0 +);'); + -- ============================================================ -- Context Statistics Tests (peak, total, pruned + absorbed/skipped) -- ============================================================ diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 68a311a8706..936e7f86d4b 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 -- ============================================================ @@ -2085,6 +2186,50 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- Preference beats length even when the preferred branch matches empty: the +-- A* branch reaches FIN with no rows consumed and nfa_advance_alt stops there, +-- so B is never expanded on a row where it would have matched. +WITH test_alt_empty_pref AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['_', 'B']), + (3, ARRAY['A', 'B']), + (4, ARRAY['_', 'B']) + ) AS t(id, flags) +) +SELECT id, flags, count(*) OVER w AS n +FROM test_alt_empty_pref +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) +); + +-- Swapping the branches makes B preferred, so every row matches one row. +WITH test_alt_empty_pref AS ( + SELECT * FROM (VALUES + (1, ARRAY['A', 'B']), + (2, ARRAY['_', 'B']), + (3, ARRAY['A', 'B']), + (4, ARRAY['_', 'B']) + ) AS t(id, flags) +) +SELECT id, flags, count(*) OVER w AS n +FROM test_alt_empty_pref +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) +); + -- ALT with reluctant: (A+? | B+) - A branch is reluctant, B is greedy. -- Row 1 matches both A and B. A+? exits immediately (match 1-1). WITH test_alt_reluctant AS ( @@ -2110,7 +2255,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,6 +2579,32 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- ((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['_']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, 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_nonlast_optgroup +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((B C)* | A) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + -- (((B C)* | A) D): the ALT is followed by D, so a zero-match (B C)* must -- continue into D. Row 4 (a lone D) exercises that; row 1 is the B C D match. WITH test_alt_optgroup_then_elem AS ( @@ -2488,6 +2660,159 @@ WINDOW w AS ( D AS 'D' = ANY(flags) ); +-- ((B C)*? | A): a reluctant optional group as a branch prefers zero +-- 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']), + (2, ARRAY['C']), + (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_alt_reluctant_optgroup +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((B C)*? | A) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + 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 -- ============================================================ @@ -2682,13 +3007,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']), @@ -2736,9 +3058,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 @@ -2763,52 +3084,294 @@ 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), + B AS 'B' = ANY(flags) +); + +-- 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) +); + +-- 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) +); + +-- Bound above the empty-then-consume cases above. The rows are the same at +-- every bound from 2 up while the derivation shifts, so a shortcut through +-- the below-min counts first shows here, where they are not adjacent. +WITH test_empty_then_consume_bound AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A']), + (3, ARRAY['A','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_empty_then_consume_bound +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){4} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- Recursion depth of the same below-min path: the fall-through advances the +-- count by one empty iteration at a time, so the depth follows the bound. +-- Reduced stack so the limit is reached quickly. +SET max_stack_depth = '100kB'; +WITH test_below_min_depth 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_below_min_depth +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A? | B){10000} C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); +RESET max_stack_depth; + +-- (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) +); + +-- ((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) +); + +-- ((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) ); @@ -2887,6 +3450,54 @@ WINDOW w AS ( ) 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) -- ============================================================ @@ -3500,207 +4111,668 @@ 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 +-- 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) +); + +-- 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) +); + +-- 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) +); + +-- 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) +); + +-- ------------------------------------------------------------ +-- Preferment guards: the path explored second must not record +-- over a match the first one already made +-- ------------------------------------------------------------ +-- +-- Where two paths leave the same element the first is the preferred one, so +-- once it has recorded a match the second must not run. Both derivations +-- cover the same rows below, so the output is the same either way; what +-- fails when a guard is removed is an assertion, in a cassert build. + +-- Entering a group before skipping it. +WITH test_guard_begin_enter 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_guard_begin_enter +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)*){1,3}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Below the lower bound, looping back before the fast-forward. +WITH test_guard_end_below_min 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_guard_end_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,4}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Between the bounds, looping before the exit. Here the second path parks +-- a state instead of reaching FIN. +WITH test_guard_end_loop_exit 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_guard_end_loop_exit +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A (B*?)+){2,3}) + 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']) + (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_concat_lex +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) (C | D)) + PATTERN (A+? B) 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 ( +-- 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['B']), - (2, ARRAY['C']), - (3, ARRAY['A']), - (4, ARRAY['C']) + (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_concat_backtrack +FROM test_quant_greedy_contested WINDOW w AS ( ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A | B) C) + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A+ B) 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 ( +-- (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_greedy +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) ); --- V{2,4}? reluctant: shorter match preferred -WITH test_quant_reluctant 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']), - (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_greedy_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{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','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_greedy +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) ); --- ((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) @@ -3854,6 +4926,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 @@ -3936,6 +5060,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 -- ------------------------------------------------------------