From 9b745d7ecff073a77346689a1fea17da4a9d589b Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Thu, 9 Jul 2026 10:42:52 +0900 Subject: [PATCH] Fix row pattern recognition alternation branch-walk overload A compiled alternation linked each alternative to the next through the jump field of the branch's first element. A group's BEGIN uses that same field for its skip-past-END path, so when an alternative began with a quantified group the two meanings collided: the branch walk followed the group skip and treated the following group as another alternative. PATTERN (A | (B C)+ (D E)+) thus behaved like A | (B C)+ | (D E)+ and matched rows it should not; absorbability analysis over-marked the trailing group as well. Terminate every alternative with a dedicated SEP (branch separator) control element that carries the branch link, so jump means only a group skip or loop-back. The match walk, absorbability analysis and EXPLAIN deparse now enumerate branches through the SEP chain, removing the depth-based and relative-position guards they previously needed. Add regression tests covering alternations whose branch ends in a plain, optional, or reluctant group, and update README.rpr. --- src/backend/commands/explain.c | 90 +++++------ src/backend/executor/README.rpr | 173 +++++++++++++++------- src/backend/executor/execRPR.c | 55 ++++--- src/backend/optimizer/plan/rpr.c | 137 ++++++++++++----- src/include/nodes/plannodes.h | 3 +- src/include/optimizer/rpr.h | 11 +- src/test/regress/expected/rpr_base.out | 17 +++ src/test/regress/expected/rpr_explain.out | 48 +++++- src/test/regress/expected/rpr_nfa.out | 165 +++++++++++++++++++++ src/test/regress/sql/rpr_base.sql | 7 + src/test/regress/sql/rpr_explain.sql | 24 +++ src/test/regress/sql/rpr_nfa.sql | 129 ++++++++++++++++ 12 files changed, 684 insertions(+), 175 deletions(-) diff --git a/src/backend/commands/explain.c b/src/backend/commands/explain.c index a5d272b6323..1ee7d351c24 100644 --- a/src/backend/commands/explain.c +++ b/src/backend/commands/explain.c @@ -128,7 +128,6 @@ static int deparse_rpr_node(RPRPattern *pattern, int idx, int limit, StringInfo buf); static int rpr_match_end(RPRPattern *pattern, int beginIdx); static int rpr_alt_scope_end(RPRPattern *pattern, int idx); -static int rpr_next_branch(RPRPattern *pattern, int bno, int altEnd); static void show_storage_info(char *maxStorageType, int64 maxSpaceUsed, ExplainState *es); static void show_tablesample(TableSampleClause *tsc, PlanState *planstate, @@ -2955,17 +2954,17 @@ append_rpr_quantifier(StringInfo buf, RPRPatternElement *elem) * passes the boundary down, so each construct's extent is fixed by its caller. * Three signals drive the walk: * - * - scope ends (where an ALT or GROUP body finishes) come from depth, via - * rpr_alt_scope_end() and rpr_match_end(). - * - branch boundaries (where a "|" goes) come from a branch-start jump, - * confirmed by the relative test elem[j-1].next != j, via - * rpr_next_branch(). + * - a GROUP body's end comes from depth, via rpr_match_end(); an ALT's + * scope end comes from its SEP chain, via rpr_alt_scope_end(). + * - branch boundaries (where a "|" goes) come from the ALT's SEP chain: each + * branch is terminated by a SEP whose jump links to the next branch's SEP + * (-1 on the last), so a branch runs from its content start up to its SEP. * - parentheses come from structure (a BEGIN group, an ALT) plus a one-step * lookahead for a group that wraps a lone ALT. * - * depth and the relative next test are stable across the next/jump values the - * compiler assigns to branch tails and nested alternations, which is what makes - * them suitable to anchor scope and branch boundaries. + * depth and the SEP chain are stable across the next/jump values the compiler + * assigns to branch tails and nested alternations, which is what makes them + * suitable to anchor scope and branch boundaries. * * EXPLAIN parenthesizes every ALT on its own, so a top-level "A | B" deparses * as "(a | b)". This self-consistent EXPLAIN form is the correctness oracle @@ -3021,9 +3020,9 @@ deparse_rpr_seq(RPRPattern *pattern, int start, int limit, StringInfo buf) * matching END (rpr_match_end); when the group's sole child is an ALT that * runs to the END, the ALT supplies the parentheses and the group only adds * the quantifier, otherwise the group body is wrapped in its own "( )". An - * ALT runs to its depth-determined scope end (capped by the inherited limit) - * and emits "( b1 | b2 | ... )", each branch deparsed within the boundary - * handed down by rpr_next_branch. + * ALT runs to its SEP-chain scope end (capped by the inherited limit) and + * emits "( b1 | b2 | ... )", each branch deparsed within the boundary handed + * down by its SEP chain. */ static int deparse_rpr_node(RPRPattern *pattern, int idx, int limit, StringInfo buf) @@ -3067,22 +3066,30 @@ deparse_rpr_node(RPRPattern *pattern, int idx, int limit, StringInfo buf) { int altEnd = rpr_alt_scope_end(pattern, idx); int b; + int sepIdx; bool first = true; - /* an alternation's depth-derived scope end never exceeds the limit */ + /* an alternation's SEP-chain scope end never exceeds the limit */ Assert(altEnd <= limit); appendStringInfoChar(buf, '('); - b = idx + 1; - while (b < altEnd) + b = elem->next; /* first branch's content */ + sepIdx = elem->jump; /* first branch's terminating SEP */ + for (;;) { - int nb = rpr_next_branch(pattern, b, altEnd); + RPRPatternElement *sep = &pattern->elements[sepIdx]; + /* The branch runs up to its terminating SEP */ + Assert(RPRElemIsSep(sep)); if (!first) appendStringInfoString(buf, " | "); first = false; - (void) deparse_rpr_seq(pattern, b, nb, buf); - b = nb; + (void) deparse_rpr_seq(pattern, b, sepIdx, buf); + + if (sep->jump == RPR_ELEMIDX_INVALID) + break; + b = sep->next; + sepIdx = sep->jump; } appendStringInfoChar(buf, ')'); return altEnd; @@ -3110,44 +3117,27 @@ rpr_match_end(RPRPattern *pattern, int beginIdx) } /* - * Scope end of the construct at index idx: the first following element whose - * depth is no greater than idx's own. For an ALT marker this is the index - * just past its last branch, since depth stays constant across branch - * boundaries. FIN sits at depth 0, so a top-level ALT stops there. + * Scope end of the alternation marker at idx: the element just past its last + * branch. Walk the SEP chain from ALT.jump to the last SEP (jump invalid); + * the element right after that SEP is the post-ALT element. Only ever called + * on an ALT. + * + * Use "last SEP index + 1", not the SEP's next: for a nested ALT the last + * SEP's next is redirected past the *enclosing* alternation by the branch-exit + * fixup in fillRPRPatternAlt, whereas SEPs are laid out contiguously, so the + * index after the last SEP is always this ALT's own post-ALT element. */ static int rpr_alt_scope_end(RPRPattern *pattern, int idx) { - RPRDepth d = pattern->elements[idx].depth; - int i; - - for (i = idx + 1; i < pattern->numElements; i++) - { - if (pattern->elements[i].depth <= d) - return i; - } - return pattern->numElements; -} + int sepIdx; -/* - * Boundary of the alternation branch starting at bno (i.e. the start of the - * next branch, or altEnd if bno is the last branch). - * - * The branch-start element's jump points at the next branch when this is not - * the last branch. jump is overloaded (a group BEGIN also uses it for its - * skip path), so confirm a real branch boundary with the relative test - * elem[j-1].next != j: at a true boundary the preceding branch's tail has its - * next redirected past the alternation, so it does not point at j. - */ -static int -rpr_next_branch(RPRPattern *pattern, int bno, int altEnd) -{ - int j = pattern->elements[bno].jump; + Assert(RPRElemIsAlt(&pattern->elements[idx])); - if (j != RPR_ELEMIDX_INVALID && j < altEnd && - pattern->elements[j - 1].next != j) - return j; - return altEnd; + sepIdx = pattern->elements[idx].jump; + while (pattern->elements[sepIdx].jump != RPR_ELEMIDX_INVALID) + sepIdx = pattern->elements[sepIdx].jump; + return sepIdx + 1; } /* diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 956d69b7549..4ad8dee0bf7 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -243,25 +243,26 @@ RPRPatternElement struct (16 bytes): Field Size Description --------------------------------------------------------- - varId 1B Variable ID (0-0xEF) or control code (0xFC-0xFF) + varId 1B Variable ID (0-0xEF) or control code (0xFB-0xFF) depth 1B Group nesting depth flags 1B Bit flags (see below) reserved 1B Padding min 4B Quantifier lower bound max 4B Quantifier upper bound next 2B Next element index (sequential flow) - jump 2B Branch target index (for ALT/GROUP) + jump 2B Branch link (ALT/SEP), group skip/loop-back (BEGIN/END) Pattern variables occupy varId 0 to RPR_VARID_MAX (0xEF) inclusive, giving 240 distinct variables. Any varId with the high nibble set -(0xF0-0xFF) is reserved for control elements; 0xF0-0xFB are currently +(0xF0-0xFF) is reserved for control elements; 0xF0-0xFA are currently spare. Control codes: - RPR_VARID_BEGIN (0xFC) Group start marker - RPR_VARID_END (0xFD) Group end marker - RPR_VARID_ALT (0xFE) Alternation start marker + RPR_VARID_BEGIN (0xFB) Group start marker + RPR_VARID_END (0xFC) Group end marker + RPR_VARID_ALT (0xFD) Alternation start marker + RPR_VARID_SEP (0xFE) Alternation branch separator RPR_VARID_FIN (0xFF) Pattern completion marker Element flags (1 byte, bitmask): @@ -296,39 +297,24 @@ Element flags (1 byte, bitmask): RPRElemIsAbsorbableBranch(e) (e)->flags & 0x04 RPRElemIsAbsorbable(e) (e)->flags & 0x08 -Example: PATTERN (A+ B | C) - - Parse tree: ALT(SEQ(VAR(A,1,INF), VAR(B,1,1)), VAR(C,1,1)) - - Compilation result: - - idx varId depth min max next jump Description - ------------------------------------------------------------ - 0 ALT 0 1 1 1 -1 Alternation start - 1 A(0) 1 1 INF 2 3 Branch 1: A+ - 2 B(1) 1 1 1 4 -1 Branch 1: B -> FIN - 3 C(2) 1 1 1 4 -1 Branch 2: C -> FIN - 4 FIN 0 1 1 -1 -1 Pattern completion - - - idx 0: ALT marker. next(=1) is the start of the first branch - - idx 1: Variable A. next(=2) is B, jump(=3) is the start of the second - branch - - idx 2: Variable B. next(=4) is FIN - - idx 3: Variable C. next(=4) is FIN - - idx 4: FIN marker. Match completion signal - Roles of next and jump: - next: The next element to move to "after consuming" the current element. For VAR, the next position after a successful match. For BEGIN/END, the next position inside/outside the group. + For ALT, the first branch's content; for SEP, the next branch's + content (post-ALT on the last SEP). - jump: The element to "skip to." - In ALT, a jump from one branch to the next branch. + In ALT, the first branch's terminating SEP. + In SEP, the branch link to the next branch's SEP (-1 on the last). In BEGIN, a skip path to END+1 (for groups with min=0). In END, a loop-back to the start of the group body. -Example: PATTERN ((A B)+) +The examples below build up in order: a GROUP, then an ALT (which introduces +the SEP branch-separator markers), then the two combined. + +Example: PATTERN ((A B)+) -- GROUP idx varId depth min max next jump Description -------------------------------------------------------------- @@ -343,6 +329,68 @@ Example: PATTERN ((A B)+) - idx 3: END. next(=4) exits the group. jump(=1) loops back to the start of the group body. +Example: PATTERN (A+ B | C) -- ALT + + Parse tree: ALT(SEQ(VAR(A,1,INF), VAR(B,1,1)), VAR(C,1,1)) + + Compilation result: + + idx varId depth min max next jump Description + ------------------------------------------------------------ + 0 ALT 0 1 1 1 3 Alternation start + 1 A(0) 1 1 INF 2 -1 Branch 1: A+ + 2 B(1) 1 1 1 6 -1 Branch 1: B -> FIN + 3 SEP 1 1 1 4 5 Branch 1 terminator + 4 C(2) 1 1 1 6 -1 Branch 2: C -> FIN + 5 SEP 1 1 1 6 -1 Branch 2 terminator (last) + 6 FIN 0 1 1 -1 -1 Pattern completion + + - idx 0: ALT marker. next(=1) enters branch 1's content, jump(=3) is + branch 1's terminating SEP + - idx 1: Variable A. next(=2) is B + - idx 2: Variable B. next(=6) is FIN (branch tail redirected past the ALT) + - idx 3: SEP. next(=4) enters branch 2's content, jump(=5) links to the + next branch's SEP + - idx 4: Variable C. next(=6) is FIN + - idx 5: SEP. jump(=-1) marks the last branch; next(=6) is post-ALT + - idx 6: FIN marker. Match completion signal + + Each branch is bounded by a trailing SEP, so even the last branch's extent + is known without consulting depth. The branch link lives on the SEP + markers, not on the branch content. That keeps it clear of a branch that + ends with a quantified group, whose BEGIN.jump is the group's own + skip-past-END path (redirected past the ALT so it never lands on a SEP). + +Example: PATTERN ((B C)* | A) -- GROUP + ALT combined + + idx varId depth min max next jump Description + -------------------------------------------------------------- + 0 ALT 0 1 1 1 5 Alternation start + 1 BEGIN 1 0 INF 2 8 Branch 1: (B C)* -- skip + 2 B(1) 2 1 1 3 -1 redirected from SEP(5) + 3 C(2) 2 1 1 4 -1 to post-ALT(8) + 4 END 1 0 INF 8 2 Branch 1 tail -> post-ALT + 5 SEP 1 1 1 6 7 Branch 1 terminator + 6 A(0) 1 1 1 8 -1 Branch 2: A -> post-ALT + 7 SEP 1 1 1 8 -1 Branch 2 terminator (last) + 8 FIN 0 1 1 -1 -1 Pattern completion + + A branch-terminal optional group's skip path: + + A group's BEGIN skip-past-END jump (taken when an optional group matches + zero times) is set to "the element after END". Here that element is the + branch's own SEP terminator (idx 5), so a naive skip would land on a SEP + marker. A SEP is a compile-time boundary, never a runtime state; landing + there would (via the default VAR switch arm) mis-treat the SEP's varId as an + always-true variable and consume a spurious row, or fall through SEP.next + into the next branch. + + fillRPRPatternAlt therefore redirects any branch-terminal BEGIN.jump that + points at the branch's SEP to the post-ALT element (so idx 1's jump is 8, + not 5), and the zero-match skip ends the branch -- an empty match, exactly + as it would outside an alternation. The same redirect covers the + last-branch case, where the element after END is the final SEP. + IV-4a. Reluctant Flag (RPR_ELEM_RELUCTANT) The reluctant flag is set during Phase 4 (fillRPRPattern) when the parse @@ -956,12 +1004,15 @@ IX-4. Per-Element advance Behavior (a) ALT (nfa_advance_alt) - Upon encountering an ALT element, all branches are expanded in order. - The first element of each branch is connected via a jump pointer. + Upon encountering an ALT element, all branches are expanded in order via the + SEP branch-separator chain. ALT.next is the first branch's content and + ALT.jump is that branch's terminating SEP; each SEP.jump links to the next + branch's SEP (-1 on the last) and each SEP.next is the next branch's content. - idx=0 (ALT) -> branch 1 start (next) -> branch 2 start (jump) -> ... + ALT.next -> branch 1 content; ALT.jump -> SEP1 -> SEP2 -> ... (jump chain) + SEP_i.next -> branch (i+1) content - nfa_advance_state() is recursively called for each branch. + nfa_advance_state() is recursively called at each branch's content. (b) BEGIN (nfa_advance_begin) @@ -1593,11 +1644,18 @@ C-3. PATTERN (A | B | C) idx varId depth min max next jump ---------------------------------------- - 0 ALT 0 1 1 1 -1 alternation start - 1 A 1 1 1 4 2 branch 1 -> FIN, jump -> branch 2 - 2 B 1 1 1 4 3 branch 2 -> FIN, jump -> branch 3 - 3 C 1 1 1 4 -1 branch 3 -> FIN - 4 FIN 0 1 1 -1 -1 + 0 ALT 0 1 1 1 2 next -> branch 1, jump -> SEP1 + 1 A 1 1 1 7 -1 branch 1 -> post-ALT + 2 SEP 1 1 1 3 4 branch 1 term.; next -> B, jump -> SEP2 + 3 B 1 1 1 7 -1 branch 2 -> post-ALT + 4 SEP 1 1 1 5 6 branch 2 term.; next -> C, jump -> SEP3 + 5 C 1 1 1 7 -1 branch 3 -> post-ALT + 6 SEP 1 1 1 7 -1 branch 3 terminator (last) + 7 FIN 0 1 1 -1 -1 + + Each branch is terminated by a SEP. ALT.jump enters the SEP chain, each + SEP.jump links to the next branch's SEP (-1 on the last), and each SEP.next + enters the next branch's content; the branch tails are redirected to FIN. C-4. PATTERN ((A B)+ C) @@ -1617,13 +1675,18 @@ C-5. PATTERN ((A | B)+? C) idx varId depth min max next jump flags ------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 5 RELUCTANT, group start - 1 ALT 1 1 1 2 -1 alternation start - 2 A 2 1 1 4 3 branch 1 - 3 B 2 1 1 4 -1 branch 2 - 4 END 0 1 INF 5 1 RELUCTANT, group end - 5 C 0 1 1 6 -1 - 6 FIN 0 1 1 -1 -1 + 0 BEGIN 0 1 INF 1 7 RELUCTANT, group start + 1 ALT 1 1 1 2 3 next -> branch 1, jump -> SEP1 + 2 A 2 1 1 6 -1 branch 1 -> END + 3 SEP 2 1 1 4 5 branch 1 term.; jump -> SEP2 + 4 B 2 1 1 6 -1 branch 2 -> END + 5 SEP 2 1 1 6 -1 branch 2 terminator (last) + 6 END 0 1 INF 7 1 RELUCTANT, group end + 7 C 0 1 1 8 -1 + 8 FIN 0 1 1 -1 -1 + + The ALT lives inside a group, so its branch tails are redirected to the + post-ALT element (here the group's END at idx 6), not out of the group. C-6. PATTERN ((A+ B)+ C) -- Absorbability flag example @@ -1645,14 +1708,16 @@ C-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT idx varId depth min max next jump flags --------------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 6 ABSORBABLE_BRANCH - 1 ALT 1 1 1 2 -1 ABSORBABLE_BRANCH - 2 A 2 1 INF 3 4 ABSORBABLE | ABSORBABLE_BRANCH - 3 B 2 1 1 5 -1 - 4 C 2 0 INF 5 -1 ABSORBABLE | ABSORBABLE_BRANCH - 5 END 0 1 INF 6 1 EMPTY_LOOP - 6 D 0 1 1 7 -1 - 7 FIN 0 1 1 -1 -1 + 0 BEGIN 0 1 INF 1 8 ABSORBABLE_BRANCH + 1 ALT 1 1 1 2 4 ABSORBABLE_BRANCH; jump -> SEP1 + 2 A 2 1 INF 3 -1 ABSORBABLE | ABSORBABLE_BRANCH + 3 B 2 1 1 7 -1 branch 1 -> END + 4 SEP 2 1 1 5 6 branch 1 term.; jump -> SEP2 + 5 C 2 0 INF 7 -1 ABSORBABLE | ABSORBABLE_BRANCH + 6 SEP 2 1 1 7 -1 branch 2 terminator (last) + 7 END 0 1 INF 8 1 EMPTY_LOOP + 8 D 0 1 1 9 -1 + 9 FIN 0 1 1 -1 -1 ALT branches are checked independently for absorbability. Branch 1: A+ matches Case 1 -> A gets ABSORBABLE. B has no flag. @@ -1662,6 +1727,8 @@ C-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT END has EMPTY_LOOP: branch 2 (C*) is nullable, making the group body nullable. BEGIN and ALT get ABSORBABLE_BRANCH (on the path to absorbable elements). + The SEP branch-separator markers carry no flags: computeAbsorbabilityRecursive + walks the SEP chain but marks only branch content. References: diff --git a/src/backend/executor/execRPR.c b/src/backend/executor/execRPR.c index 043d5a18f5b..fd366dc79bf 100644 --- a/src/backend/executor/execRPR.c +++ b/src/backend/executor/execRPR.c @@ -1019,6 +1019,12 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, * nfa_advance_alt * * Handle ALT element: expand all branches in lexical order via DFS. + * + * ALT.next is the first branch's content and ALT.jump is that branch's + * terminating SEP. Each SEP.jump links to the next branch's SEP (-1 on the + * last) and each SEP.next is the next branch's content. The branch link lives + * on SEP alone, so it never collides with a branch content BEGIN's + * skip-past-END path. */ static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, @@ -1027,37 +1033,29 @@ nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, { RPRPattern *pattern = winstate->rpPattern; RPRPatternElement *elements = pattern->elements; - RPRElemIdx altIdx = elem->next; + RPRElemIdx brStart = elem->next; + RPRElemIdx sepIdx = elem->jump; - while (altIdx >= 0) + for (;;) { - RPRPatternElement *altElem; + RPRPatternElement *sepElem; RPRNFAState *newState; - /* Branch jump/next links are always -1 or a valid index */ - Assert(altIdx < pattern->numElements); - altElem = &elements[altIdx]; - - /* - * Stop if element is outside ALT scope (not a branch). The check - * fires when the last branch is a quantified group whose BEGIN.jump - * (set by fillRPRPatternGroup) is preserved -- not overridden by - * fillRPRPatternAlt, which only links non-last branch heads -- and - * leads to a post-ALT element. Other branch shapes terminate the - * walk earlier via altIdx = RPR_ELEMIDX_INVALID. Use <=, not <: the - * post-ALT element may sit at the same depth as the ALT when the ALT - * has a sibling at that level. - */ - if (altElem->depth <= elem->depth) - break; - - /* Create independent state for each branch */ - newState = nfa_state_clone(winstate, altIdx, + /* Create independent state at this branch's content */ + newState = nfa_state_clone(winstate, brStart, state->counts, state->isAbsorbable); - /* Recursively process this branch before next */ + /* Recursively process this branch before the next */ nfa_advance_state(winstate, ctx, newState, currentPos); - altIdx = altElem->jump; + + /* The walk never lands on -1: the last SEP breaks the loop below */ + Assert(sepIdx >= 0 && sepIdx < pattern->numElements); + sepElem = &elements[sepIdx]; + Assert(RPRElemIsSep(sepElem)); + if (sepElem->jump == RPR_ELEMIDX_INVALID) + break; + brStart = sepElem->next; + sepIdx = sepElem->jump; } nfa_state_free(winstate, state); @@ -1500,6 +1498,15 @@ nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, if (!RPRElemIsVar(elem)) nfa_mark_visited(winstate, state->elemIdx); + /* + * A SEP is a compile-time branch boundary only: fillRPRPatternAlt routes + * every branch exit and group skip past the alternation, so no state is + * ever positioned on one. Guard the invariant here -- otherwise a SEP + * would fall through to the VAR arm and be mis-treated as an always-true + * variable (varId > RPR_VARID_MAX) rather than tripping an assertion. + */ + Assert(!RPRElemIsSep(elem)); + switch (elem->varId) { case RPR_VARID_FIN: diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index da918a908a7..91f88b0ce88 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -1039,6 +1039,8 @@ scanRPRPatternRecursive(RPRPatternNode *node, char **varNames, int *numVars, /* Recurse into children at increased depth */ foreach_node(RPRPatternNode, child, node->children) { + /* Each branch is terminated by a SEP branch-separator marker */ + (*numElements)++; scanRPRPatternRecursive(child, varNames, numVars, numElements, depth + 1, maxDepth); } @@ -1250,8 +1252,21 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de * fillRPRPatternAlt * Fill an ALT pattern and its alternatives. * - * Creates the ALT marker, fills each alternative at increased depth, - * sets jump pointers for backtracking, and next pointers for successful paths. + * Creates the ALT marker and fills each alternative at increased depth, + * terminating every alternative (including the last) with a SEP + * branch-separator marker. The branch link lives on the SEP markers, so it + * never collides with a branch content BEGIN's skip-past-END path, and each + * alternative's extent is bounded by its own trailing SEP without consulting + * depth. + * + * ALT.next -> first branch content SEP.next -> next branch content + * ALT.jump -> first SEP (post-ALT on the last) + * SEP.jump -> next SEP (-1 on the last) + * + * A branch's tail (and a branch-terminal group's BEGIN skip path, whose jump + * would otherwise point at the branch's SEP) is redirected to the post-ALT + * element, so SEP markers are compile-time boundaries only and are never a + * runtime state position. * * Returns true if any branch is nullable (OR semantics: one nullable * branch suffices for the alternation to produce an empty match). @@ -1261,9 +1276,12 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept { ListCell *lc; ListCell *lc2; + ListCell *lc3; RPRPatternElement *elem; + int altIdx = *idx; List *altBranchStarts = NIL; List *altEndPositions = NIL; + List *altSepIdxs = NIL; int afterAltIdx; bool anyNullable = false; @@ -1274,47 +1292,78 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept elem->depth = depth; elem->min = 1; elem->max = 1; - elem->next = RPR_ELEMIDX_INVALID; - elem->jump = RPR_ELEMIDX_INVALID; + elem->next = RPR_ELEMIDX_INVALID; /* set to first branch content below */ + elem->jump = RPR_ELEMIDX_INVALID; /* set to first SEP below */ (*idx)++; - /* Fill each alternative */ + /* ALT enters the first branch's content (the contiguous next element) */ + pat->elements[altIdx].next = *idx; + + /* Fill each alternative, terminated by a SEP branch-separator marker */ foreach_node(RPRPatternNode, alt, node->children) { int branchStart = *idx; + int sepIdx; + RPRPatternElement *sep; altBranchStarts = lappend_int(altBranchStarts, branchStart); if (fillRPRPattern(alt, pat, idx, depth + 1)) anyNullable = true; altEndPositions = lappend_int(altEndPositions, *idx - 1); - } - - /* Set jump on first element of each alternative to next alternative */ - foreach(lc, altBranchStarts) - { - int firstElemIdx = lfirst_int(lc); - if (lnext(altBranchStarts, lc) != NULL) - pat->elements[firstElemIdx].jump = lfirst_int(lnext(altBranchStarts, lc)); + /* SEP terminates this branch */ + sepIdx = *idx; + sep = &pat->elements[sepIdx]; + memset(sep, 0, sizeof(RPRPatternElement)); + sep->varId = RPR_VARID_SEP; + sep->depth = depth + 1; + sep->min = 1; + sep->max = 1; + sep->next = RPR_ELEMIDX_INVALID; /* set below */ + sep->jump = RPR_ELEMIDX_INVALID; /* branch link, set below */ + altSepIdxs = lappend_int(altSepIdxs, sepIdx); + (*idx)++; } - /* Set next on last element of each alternative to after the alternation */ afterAltIdx = *idx; - forboth(lc, altEndPositions, lc2, altBranchStarts) + /* ALT reaches the first branch's terminating SEP */ + pat->elements[altIdx].jump = linitial_int(altSepIdxs); + + /* + * Wire the SEP chain, and redirect each branch's exits past the + * alternation. + */ + forthree(lc, altSepIdxs, lc2, altBranchStarts, lc3, altEndPositions) { - int endPos = lfirst_int(lc); + int sepIdx = lfirst_int(lc); int branchStart = lfirst_int(lc2); + int endPos = lfirst_int(lc3); + ListCell *nextSep = lnext(altSepIdxs, lc); + int j; + + /* SEP.jump -> next SEP; SEP.next -> next branch content */ + if (nextSep != NULL) + { + pat->elements[sepIdx].jump = lfirst_int(nextSep); + pat->elements[sepIdx].next = lfirst_int(lnext(altBranchStarts, lc2)); + } + else + { + pat->elements[sepIdx].jump = RPR_ELEMIDX_INVALID; + pat->elements[sepIdx].next = afterAltIdx; + } + /* + * Redirect the branch's fall-through exit to after the alternation. + * The natural exit is the element past the branch content, which is + * now this branch's SEP; a simple tail leaves next unset (finalize + * would fall it through to the SEP), while an inner ALT already set + * next to that position. + */ if (pat->elements[endPos].next != RPR_ELEMIDX_INVALID) { - /* - * An inner ALT already set next on this element. Redirect all - * elements in this branch that share the same target to point to - * after this ALT instead. - */ int oldTarget = pat->elements[endPos].next; - int j; for (j = branchStart; j <= endPos; j++) { @@ -1326,8 +1375,20 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept { pat->elements[endPos].next = afterAltIdx; } + + /* + * A branch-terminal group's BEGIN skip-past-END path points at the + * element following the group, which is this branch's SEP; redirect + * it past the alternation too so the skip never lands on a SEP. + */ + for (j = branchStart; j <= endPos; j++) + { + if (pat->elements[j].jump == sepIdx) + pat->elements[j].jump = afterAltIdx; + } } + list_free(altSepIdxs); list_free(altBranchStarts); list_free(altEndPositions); @@ -1669,30 +1730,28 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, if (RPRElemIsAlt(elem)) { - /* ALT: recursively check each branch */ - RPRElemIdx branchIdx = elem->next; - RPRPatternElement *branchFirst; + /* ALT: recursively check each branch via the SEP chain */ + RPRElemIdx brStart = elem->next; + RPRElemIdx sepIdx = elem->jump; + RPRPatternElement *sepElem; bool branchAbsorbable; - while (branchIdx != RPR_ELEMIDX_INVALID) + for (;;) { branchAbsorbable = false; - Assert(branchIdx < pattern->numElements); - branchFirst = &pattern->elements[branchIdx]; - - /* Stop if element is outside ALT scope (not a branch) */ - if (branchFirst->depth <= elem->depth) - break; - - /* Recursively check this branch */ - computeAbsorbabilityRecursive(pattern, branchIdx, &branchAbsorbable); + /* Recursively check this branch's content */ + computeAbsorbabilityRecursive(pattern, brStart, &branchAbsorbable); if (branchAbsorbable) - { *hasAbsorbable = true; - } - branchIdx = branchFirst->jump; + Assert(sepIdx >= 0 && sepIdx < pattern->numElements); + sepElem = &pattern->elements[sepIdx]; + Assert(RPRElemIsSep(sepElem)); + if (sepElem->jump == RPR_ELEMIDX_INVALID) + break; + brStart = sepElem->next; + sepIdx = sepElem->jump; } /* Mark ALT element if any branch is absorbable */ @@ -1728,9 +1787,7 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, /* Non-ALT, non-BEGIN: check if unbounded start */ if (isUnboundedStart(pattern, startIdx)) - { *hasAbsorbable = true; - } } } diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index dc58209d9aa..e124ffc02ee 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -1274,7 +1274,8 @@ typedef struct RPRPatternElement RPRQuantity min; /* quantifier minimum */ RPRQuantity max; /* quantifier maximum */ RPRElemIdx next; /* next element index */ - RPRElemIdx jump; /* jump target (for ALT/GROUP) */ + RPRElemIdx jump; /* ALT/SEP branch link, or GROUP + * skip/loop-back */ } RPRPatternElement; /* diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h index d73f8c8e693..47a7467e2f9 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -41,10 +41,12 @@ #define RPR_DEPTH_MAX (PG_UINT8_MAX - 1) /* max pattern nesting depth: * 254 */ -/* Reserved control-element varIds (high nibble 0xF; 0xF0-0xFB spare) */ -#define RPR_VARID_BEGIN ((RPRVarId) 0xFC) /* group begin */ -#define RPR_VARID_END ((RPRVarId) 0xFD) /* group end */ -#define RPR_VARID_ALT ((RPRVarId) 0xFE) /* alternation start */ +/* Reserved control-element varIds (high nibble 0xF; 0xF0-0xFA spare) */ +#define RPR_VARID_BEGIN ((RPRVarId) 0xFB) /* group begin */ +#define RPR_VARID_END ((RPRVarId) 0xFC) /* group end */ +#define RPR_VARID_ALT ((RPRVarId) 0xFD) /* alternation start */ +#define RPR_VARID_SEP ((RPRVarId) 0xFE) /* alternation branch + * separator */ #define RPR_VARID_FIN ((RPRVarId) 0xFF) /* pattern finish */ /* Element flags */ @@ -70,6 +72,7 @@ #define RPRElemIsBegin(e) ((e)->varId == RPR_VARID_BEGIN) #define RPRElemIsEnd(e) ((e)->varId == RPR_VARID_END) #define RPRElemIsAlt(e) ((e)->varId == RPR_VARID_ALT) +#define RPRElemIsSep(e) ((e)->varId == RPR_VARID_SEP) #define RPRElemIsFin(e) ((e)->varId == RPR_VARID_FIN) #define RPRElemCanSkip(e) ((e)->min == 0) diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index 85a1ad8727d..b5da8de0965 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -5610,6 +5610,23 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING -> Seq Scan on rpr_plan (7 rows) +-- ALT branch tail not over-marked: A | (B C)+ (D E)+ -> (a | (b' c')+" (d e)+) +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_plan +WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (A | (B C)+ (D E)+) + DEFINE A AS val <= 20, B AS val <= 40, C AS val <= 60, D AS val <= 80, E AS val > 80); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a | (b' c')+" (d e)+) + Nav Mark Lookback: 0 + -> Sort + Sort Key: id + -> Seq Scan on rpr_plan +(7 rows) + -- Nested unbounded: (A+ | B)+ -> (a+" | b)+ (first iteration absorbable) EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out index 11fad2b80ba..a2c52588361 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -307,6 +307,48 @@ WINDOW w AS ( -> Function Scan on generate_series s (actual rows=30.00 loops=1) (9 rows) +-- Regression test: ALT branch whose tail is a group +-- (A | (B C)+ (D E)+) means A | ((B C)+ (D E)+) by precedence, so the two +-- trailing groups must deparse inside one branch, not as separate branches. +CREATE VIEW rpr_ev_basic_deparse_alttail AS +SELECT count(*) OVER w +FROM generate_series(1, 30) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A | (B C)+ (D E)+) + DEFINE A AS v % 6 = 1, B AS v % 6 = 2, C AS v % 6 = 3, D AS v % 6 = 4, E AS v % 6 = 5 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_basic_deparse_alttail'), E'\n')) AS line WHERE line ~ 'PATTERN'; + line +-------------------------------- + PATTERN (a | (b c)+ (d e)+) +(1 row) + +-- The viewdef above deparses the parse tree; this one deparses the compiled +-- element array, which enumerates ALT branches via the SEP terminators. +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 30) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A | (B C)+ (D E)+) + DEFINE A AS v % 6 = 1, B AS v % 6 = 2, C AS v % 6 = 3, D AS v % 6 = 4, E AS v % 6 = 5 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=30.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a | (b' c')+" (d e)+) + Nav Mark Lookback: 0 + Storage: Memory Maximum Storage: NkB + NFA States: 5 peak, 103 total, 0 merged + NFA Contexts: 3 peak, 31 total, 15 pruned + NFA: 10 matched (len 1/4/2.5), 0 mismatched + NFA: 0 absorbed, 5 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=30.00 loops=1) +(10 rows) + -- Regression test: Quoted identifiers in EXPLAIN pattern deparse -- Mixed case names must be quoted to preserve round-trip safety SELECT rpr_explain_filter(' @@ -4486,9 +4528,9 @@ WINDOW w AS ( Pattern: (c | (a' b')+" d) Nav Mark Lookback: 0 Storage: Memory Maximum Storage: NkB - NFA States: 6 peak, 88 total, 0 merged - NFA Contexts: 3 peak, 21 total, 6 pruned - NFA: 10 matched (len 1/1/1.0), 4 mismatched (len 3/3/3.0) + NFA States: 5 peak, 67 total, 0 merged + NFA Contexts: 3 peak, 21 total, 11 pruned + NFA: 5 matched (len 1/1/1.0), 4 mismatched (len 3/3/3.0) -> Function Scan on generate_series s (actual rows=20.00 loops=1) (9 rows) diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index 22d244707c6..f807c70f80c 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -3188,6 +3188,171 @@ WINDOW w AS ( 5 | {X} | | (5 rows) +-- (A | (B C)+ (D E)+): the last branch is (B C)+ (D E)+, so with no A/B/C the +-- rows D E D E match nothing -- the trailing (D E)+ is not its own branch. +WITH test_alt_concat_groups AS ( + SELECT * FROM (VALUES + (1, ARRAY['D']), + (2, ARRAY['E']), + (3, ARRAY['D']), + (4, ARRAY['E']) + ) 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_concat_groups +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)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags), + E AS 'E' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {D} | | + 2 | {E} | | + 3 | {D} | | + 4 | {E} | | +(4 rows) + +-- (A | (B C)*): optional group as the last ALT branch. When (B C)* matches +-- zero the branch ends with an empty match (NULL bounds), consuming no row. +WITH test_alt_tail_optgroup AS ( + SELECT * FROM (VALUES + (1, ARRAY['_']), + (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_tail_optgroup +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 | {_} | | + 2 | {B} | 2 | 3 + 3 | {C} | | + 4 | {_} | | +(4 rows) + +-- ((B C)* | A): optional group as a non-last branch; a zero-match (B C)* must +-- not spill into the following A branch. +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 | 4 +(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 ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['C']), + (3, ARRAY['D']), + (4, ARRAY['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_optgroup_then_elem +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((B C)* | A) 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 | {B} | 1 | 3 + 2 | {C} | | + 3 | {D} | | + 4 | {D} | 4 | 4 + 5 | {_} | | +(5 rows) + +-- ((B C)*? | A): a reluctant optional group as a branch prefers zero +-- iterations, giving an empty match where no A is present. +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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | | + 2 | {C} | | + 3 | {A} | 3 | 3 + 4 | {_} | | +(4 rows) + -- ============================================================ -- Deep Nested Groups -- ============================================================ diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index 3de44c509e8..eed5ea958a0 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -3324,6 +3324,13 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING AFTER MATCH SKIP PAST LAST ROW PATTERN (((A+ B) | C) D | A B C) DEFINE A AS val <= 30, B AS val <= 60, C AS val <= 80, D AS val > 80); +-- ALT branch tail not over-marked: A | (B C)+ (D E)+ -> (a | (b' c')+" (d e)+) +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_plan +WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW PATTERN (A | (B C)+ (D E)+) + DEFINE A AS val <= 20, B AS val <= 40, C AS val <= 60, D AS val <= 80, E AS val > 80); + -- Nested unbounded: (A+ | B)+ -> (a+" | b)+ (first iteration absorbable) EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan diff --git a/src/test/regress/sql/rpr_explain.sql b/src/test/regress/sql/rpr_explain.sql index d300530216a..2515c4cbec9 100644 --- a/src/test/regress/sql/rpr_explain.sql +++ b/src/test/regress/sql/rpr_explain.sql @@ -227,6 +227,30 @@ WINDOW w AS ( DEFINE A AS v % 5 = 1, B AS v % 5 = 2, C AS v % 5 = 3, D AS v % 5 = 4, E AS v % 5 = 0 );'); +-- Regression test: ALT branch whose tail is a group +-- (A | (B C)+ (D E)+) means A | ((B C)+ (D E)+) by precedence, so the two +-- trailing groups must deparse inside one branch, not as separate branches. +CREATE VIEW rpr_ev_basic_deparse_alttail AS +SELECT count(*) OVER w +FROM generate_series(1, 30) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A | (B C)+ (D E)+) + DEFINE A AS v % 6 = 1, B AS v % 6 = 2, C AS v % 6 = 3, D AS v % 6 = 4, E AS v % 6 = 5 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_basic_deparse_alttail'), E'\n')) AS line WHERE line ~ 'PATTERN'; +-- The viewdef above deparses the parse tree; this one deparses the compiled +-- element array, which enumerates ALT branches via the SEP terminators. +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 30) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A | (B C)+ (D E)+) + DEFINE A AS v % 6 = 1, B AS v % 6 = 2, C AS v % 6 = 3, D AS v % 6 = 4, E AS v % 6 = 5 +);'); + -- Regression test: Quoted identifiers in EXPLAIN pattern deparse -- Mixed case names must be quoted to preserve round-trip safety SELECT rpr_explain_filter(' diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 79f99922870..3d8d3bf4a8a 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -2278,6 +2278,135 @@ WINDOW w AS ( C AS 'C' = ANY(flags) ); +-- (A | (B C)+ (D E)+): the last branch is (B C)+ (D E)+, so with no A/B/C the +-- rows D E D E match nothing -- the trailing (D E)+ is not its own branch. +WITH test_alt_concat_groups AS ( + SELECT * FROM (VALUES + (1, ARRAY['D']), + (2, ARRAY['E']), + (3, ARRAY['D']), + (4, ARRAY['E']) + ) 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_concat_groups +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)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags), + E AS 'E' = ANY(flags) +); + +-- (A | (B C)*): optional group as the last ALT branch. When (B C)* matches +-- zero the branch ends with an empty match (NULL bounds), consuming no row. +WITH test_alt_tail_optgroup AS ( + SELECT * FROM (VALUES + (1, ARRAY['_']), + (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_tail_optgroup +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) +); + +-- ((B C)* | A): optional group as a non-last branch; a zero-match (B C)* must +-- not spill into the following A branch. +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 ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['C']), + (3, ARRAY['D']), + (4, ARRAY['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_optgroup_then_elem +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((B C)* | A) D) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + +-- ((B C)*? | A): a reluctant optional group as a branch prefers zero +-- iterations, giving an empty match where no A is present. +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) +); + -- ============================================================ -- Deep Nested Groups -- ============================================================