From cbf4da013b2cb0ffe2a1496e7f9467f1dc02997f Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Fri, 20 Feb 2026 09:18:21 +0900 Subject: [PATCH 03/10] Fix ALT lexical ordering via DFS early termination, remove altPriority --- src/backend/executor/nodeWindowAgg.c | 169 +++++++++------------- src/include/nodes/execnodes.h | 7 - src/test/regress/expected/rpr_base.out | 2 +- src/test/regress/expected/rpr_explain.out | 40 +++++ src/test/regress/expected/rpr_nfa.out | 92 ++++-------- src/test/regress/sql/rpr_explain.sql | 24 +++ src/test/regress/sql/rpr_nfa.sql | 70 +++------ 7 files changed, 186 insertions(+), 218 deletions(-) diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 9b2c4b6a1d7..96b2cd4b9c4 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -265,8 +265,7 @@ static RPRNFAState *nfa_state_alloc(WindowAggState *winstate); static void nfa_state_free(WindowAggState *winstate, RPRNFAState *state); static void nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list); static RPRNFAState *nfa_state_create(WindowAggState *winstate, int16 elemIdx, - int16 altPriority, int32 *counts, - bool sourceAbsorbable); + int32 *counts, bool sourceAbsorbable); static bool nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2); static bool nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, @@ -5188,14 +5187,14 @@ nfa_state_free_list(WindowAggState *winstate, RPRNFAState *list) /* * nfa_state_create * - * Create a new state with given elemIdx, altPriority and counts. + * Create a new state with given elemIdx and counts. * isAbsorbable is computed immediately: inherited AND new element's flag. * Monotonic property: once false, stays false through all transitions. * * Caller is responsible for linking the returned state. */ static RPRNFAState * -nfa_state_create(WindowAggState *winstate, int16 elemIdx, int16 altPriority, +nfa_state_create(WindowAggState *winstate, int16 elemIdx, int32 *counts, bool sourceAbsorbable) { RPRPattern *pattern = winstate->rpPattern; @@ -5204,7 +5203,6 @@ nfa_state_create(WindowAggState *winstate, int16 elemIdx, int16 altPriority, RPRPatternElement *elem = &pattern->elements[elemIdx]; state->elemIdx = elemIdx; - state->altPriority = altPriority; if (counts != NULL && maxDepth > 0) memcpy(state->counts, counts, sizeof(int32) * maxDepth); @@ -5249,7 +5247,7 @@ nfa_states_equal(WindowAggState *winstate, RPRNFAState *s1, RPRNFAState *s2) * * Add a state to ctx->states at the END, only if no duplicate exists. * Returns true if state was added, false if duplicate found (state is freed). - * Earlier states have lower altPriority (lexical order), so existing wins. + * Earlier states have better lexical order (DFS traversal order), so existing wins. */ static bool nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state) @@ -5286,96 +5284,42 @@ nfa_add_state_unique(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState * /* * nfa_add_matched_state * - * Record a matched state following SQL standard semantics. - * Lexical order (lower altPriority) wins first. Among same lexical order, - * longer match wins (greedy). + * Record a state that reached FIN, replacing any previous match. * - * FIXME: altPriority is a single value that only tracks the last ALT choice. - * For patterns with repeated or nested ALTs like (A|B)+, this cannot correctly - * implement SQL standard lexical order, which requires comparing the full path - * from left to right. For example: - * Pattern: (A | B)+ - * Path "A B A" vs "B A B" - * Current: compares last choice (A vs B) → altPriority 10 vs 20 - * Correct: should compare first choice (A < B) → "A B A" wins - * - * A classifier structure tracking the entire ALT path is required for correct - * implementation. Without it, patterns with repeated or nested ALTs will - * produce incorrect match selection. + * For SKIP PAST LAST ROW, also prune subsequent contexts whose start row + * falls within the match range, as they cannot produce output rows. */ static void nfa_add_matched_state(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *state, int64 matchEndRow) { - bool shouldUpdate = false; + if (ctx->matchedState != NULL) + nfa_state_free(winstate, ctx->matchedState); - if (ctx->matchedState == NULL) - shouldUpdate = true; - else if (state->altPriority < ctx->matchedState->altPriority) - shouldUpdate = true; /* Better lexical order wins */ - else if (state->altPriority == ctx->matchedState->altPriority && - matchEndRow > ctx->matchEndRow) - shouldUpdate = true; /* Same lexical order, longer wins */ + ctx->matchedState = state; + state->next = NULL; + ctx->matchEndRow = matchEndRow; - if (shouldUpdate) + /* Prune contexts that started within this match's range */ + if (winstate->rpSkipTo == ST_PAST_LAST_ROW) { - /* Free old matchedState if exists */ - if (ctx->matchedState != NULL) - nfa_state_free(winstate, ctx->matchedState); + RPRNFAContext *nextCtx; + int64 skippedLen; - /* Take ownership of the new state */ - ctx->matchedState = state; - state->next = NULL; - ctx->matchEndRow = matchEndRow; - - /*---------- - * SKIP PAST LAST ROW: eagerly prune contexts within match range. - * - * This function is called whenever a FIN state is reached, including - * during greedy matching when intermediate (shorter) matches are - * found. Each time we update matchEndRow (whether extending a greedy - * match or finding a new match), we can prune pending contexts that - * started within the current match range. - * - * SKIP PAST LAST ROW uses lexical order (matchStartRow). Therefore, - * any pending context that started at or before matchEndRow can never - * produce a valid output row - it would be skipped anyway per SQL - * standard. - * - * Example (greedy matching in progress): - * Pattern: START UP+ - * Rows: 1 2 3 4 5 - * Context A starts at row 1: - * - Matches START UP (rows 1-2) → matchEndRow=2 → prune Context B(row 2) - * - Matches START UP UP (rows 1-3) → matchEndRow=3 → prune Context C(row 3) - * - Continues greedy extension while pruning incrementally - *---------- - */ - if (winstate->rpSkipTo == ST_PAST_LAST_ROW) + while (ctx->next != NULL && + ctx->next->matchStartRow <= matchEndRow) { - RPRNFAContext *nextCtx; - int64 skippedLen; - - while (ctx->next != NULL && - ctx->next->matchStartRow <= matchEndRow) - { - nextCtx = ctx->next; - ctx->next = ctx->next->next; + nextCtx = ctx->next; + ctx->next = ctx->next->next; - Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); - skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; - nfa_record_context_skipped(winstate, skippedLen); + Assert(nextCtx->lastProcessedRow >= nextCtx->matchStartRow); + skippedLen = nextCtx->lastProcessedRow - nextCtx->matchStartRow + 1; + nfa_record_context_skipped(winstate, skippedLen); - nfa_context_free(winstate, nextCtx); - } - if (ctx->next == NULL) - winstate->nfaContextTail = ctx; + nfa_context_free(winstate, nextCtx); } - } - else - { - /* This state didn't win, free it */ - nfa_state_free(winstate, state); + if (ctx->next == NULL) + winstate->nfaContextTail = ctx; } } @@ -6124,8 +6068,7 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *skipState; skipState = nfa_state_create(winstate, nextElem->next, - state->altPriority, state->counts, - state->isAbsorbable); + state->counts, state->isAbsorbable); nfa_advance_state(winstate, ctx, skipState, currentPos, initialAdvance); } } @@ -6138,8 +6081,7 @@ nfa_route_to_elem(WindowAggState *winstate, RPRNFAContext *ctx, /* * nfa_advance_alt * - * Handle ALT element: expand all branches in lexical order (DFS). - * Sets altPriority to element index to preserve lexical order for match selection. + * Handle ALT element: expand all branches in lexical order via DFS. */ static void nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, @@ -6163,13 +6105,12 @@ nfa_advance_alt(WindowAggState *winstate, RPRNFAContext *ctx, if (first) { state->elemIdx = altIdx; - state->altPriority = altIdx; newState = state; first = false; } else { - newState = nfa_state_create(winstate, altIdx, altIdx, + newState = nfa_state_create(winstate, altIdx, state->counts, state->isAbsorbable); } @@ -6204,7 +6145,7 @@ nfa_advance_begin(WindowAggState *winstate, RPRNFAContext *ctx, /* Optional group: create skip path (but don't route yet) */ if (elem->min == 0) { - skipState = nfa_state_create(winstate, elem->jump, state->altPriority, + skipState = nfa_state_create(winstate, elem->jump, state->counts, state->isAbsorbable); } @@ -6286,21 +6227,15 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, * Between min and max (with at least one iteration) - can exit or * loop */ - RPRElemIdx exitAltPriority; RPRNFAState *exitState; RPRPatternElement *jumpElem; RPRPatternElement *nextElem; - /* Preserve altPriority for greedy extension */ - exitAltPriority = state->altPriority; - if (ctx->matchedState != NULL) - exitAltPriority = ctx->matchedState->altPriority; - /* * Create exit state first (need original counts before modifying * state) */ - exitState = nfa_state_create(winstate, elem->next, exitAltPriority, + exitState = nfa_state_create(winstate, elem->next, state->counts, state->isAbsorbable); exitState->counts[depth] = 0; nextElem = &elements[exitState->elemIdx]; @@ -6349,7 +6284,7 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, RPRNFAState *loopState; RPRPatternElement *nextElem; - loopState = nfa_state_create(winstate, state->elemIdx, state->altPriority, + loopState = nfa_state_create(winstate, state->elemIdx, state->counts, state->isAbsorbable); nfa_add_state_unique(winstate, ctx, loopState); @@ -6358,6 +6293,20 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, state->elemIdx = elem->next; nextElem = &elements[state->elemIdx]; + /* + * When a quantified VAR (e.g., A+) exits directly to an outer END, + * increment the END's iteration count. Simple VARs (min=max=1) + * handle this via inline advance in nfa_match, but quantified VARs + * bypass that path. Only increment when the VAR actually consumed + * rows (count > 0) to preserve cycle prevention for zero-progress + * loops. + */ + if (RPRElemIsEnd(nextElem) && count > 0) + { + if (state->counts[nextElem->depth] < RPR_COUNT_MAX) + state->counts[nextElem->depth]++; + } + nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos, initialAdvance); } else if (canLoop) @@ -6374,6 +6323,13 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, state->elemIdx = elem->next; nextElem = &elements[state->elemIdx]; + /* See comment above: increment outer END count for quantified VARs */ + if (RPRElemIsEnd(nextElem) && count > 0) + { + if (state->counts[nextElem->depth] < RPR_COUNT_MAX) + state->counts[nextElem->depth]++; + } + nfa_route_to_elem(winstate, ctx, state, nextElem, currentPos, initialAdvance); } } @@ -6382,9 +6338,7 @@ nfa_advance_var(WindowAggState *winstate, RPRNFAContext *ctx, * nfa_advance_state * * Recursively process a single state through epsilon transitions. - * Uses DFS traversal to maintain lexical order: lower altPriority paths - * are fully processed before higher altPriority paths, ensuring states - * are added to ctx->states in lexical order. + * DFS traversal ensures states are added to ctx->states in lexical order. */ static void nfa_advance_state(WindowAggState *winstate, RPRNFAContext *ctx, @@ -6443,13 +6397,26 @@ nfa_advance(WindowAggState *winstate, RPRNFAContext *ctx, int64 currentPos, ctx->states = NULL; /* Will rebuild */ - /* Process each state in order */ + /* Process each state in lexical order (DFS order from previous advance) */ while (states != NULL) { + RPRNFAState *savedMatchedState = ctx->matchedState; + state = states; states = states->next; state->next = NULL; nfa_advance_state(winstate, ctx, state, currentPos, initialAdvance); + + /* + * Early termination: if a FIN was newly reached in this advance, + * 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) + { + nfa_state_free_list(winstate, states); + break; + } } } diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index cd6f794f62b..9a1561fce7e 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2523,21 +2523,14 @@ typedef enum WindowAggStatus * RPRNFAState - single NFA state for pattern matching * * counts[] tracks repetition counts at each nesting depth. - * altPriority tracks lexical order for alternation (lower = earlier alternative). * * isAbsorbable tracks if state is in absorbable region (ABSORBABLE_BRANCH). * Monotonic property: once false, stays false (can't re-enter region). - * - * Absorption comparison uses elemIdx and counts[depth] directly because: - * - VAR elements consume a row, forcing states to wait for next row - * - END loop puts states at group start with iteration count preserved - * - At row end, comparable states are at the same position (elemIdx) */ typedef struct RPRNFAState { struct RPRNFAState *next; /* next state in linked list */ int16 elemIdx; /* current pattern element index */ - int16 altPriority; /* lexical order priority (lower = preferred) */ bool isAbsorbable; /* true if state is in absorbable region */ int32 counts[FLEXIBLE_ARRAY_MEMBER]; /* repetition counts by depth */ } RPRNFAState; diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index 1d42af15980..d317ec70c8d 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -3703,7 +3703,7 @@ WINDOW w AS ( ORDER BY id; id | val | cnt ----+-----+----- - 1 | 10 | 0 + 1 | 10 | 3 2 | 20 | 0 3 | 30 | 0 4 | 40 | 0 diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out index bfe4ee2ba7d..dacb8d6907f 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -676,6 +676,46 @@ WINDOW w AS ( -> Function Scan on generate_series s (actual rows=100.00 loops=1) (9 rows) +DROP VIEW rpr_v; +-- Early termination: first ALT branch (A) reaches FIN immediately, +-- pruning second branch (A B+) before it can accumulate B repetitions. +CREATE TEMP VIEW rpr_v AS +SELECT count(*) OVER w +FROM generate_series(1, 100) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | A B)+) + DEFINE A AS v = 1, B AS v > 1 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_v'), E'\n')) AS line WHERE line ~ 'PATTERN'; + line +------------------------- + PATTERN ((a | a b)+) +(1 row) + +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 100) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | A B)+) + DEFINE A AS v = 1, B AS v > 1 +);'); + rpr_explain_filter +----------------------------------------------------------------------- + WindowAgg (actual rows=100.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a | a b)+ + Storage: Memory Maximum Storage: NkB + NFA States: 5 peak, 204 total, 0 merged + NFA Contexts: 3 peak, 101 total, 99 pruned + NFA: 1 matched (len 1/1/1.0), 0 mismatched + -> Function Scan on generate_series s (actual rows=100.00 loops=1) +(8 rows) + DROP VIEW rpr_v; -- Nested quantifiers causing state growth CREATE TEMP VIEW rpr_v AS diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index 46a463c2597..7d38d62ac31 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -1514,6 +1514,34 @@ WINDOW w AS ( 4 | {_,_} | | (4 rows) +-- ALT lexical order takes priority over greedy (longer match). +-- Row 1 matches both A and B; A wins by lexical order (match 1-1). +WITH test_alt_lexical_order AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), -- A and B both match + (2, ARRAY['_','C']) -- only C matches (would continue 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_lexical_order +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,B} | 1 | 1 + 2 | {_,C} | | +(2 rows) + -- ============================================================ -- Deep Nested Groups -- ============================================================ @@ -2403,66 +2431,6 @@ WINDOW w AS ( -- ============================================================ -- FIXME Issues - Known Limitations -- ============================================================ --- FIXME 1 - altPriority lexical order -WITH test_alt_priority_repeated AS ( - SELECT * FROM (VALUES - (1, ARRAY['A','B']), -- Both A and B match - (2, ARRAY['A','B']), - (3, 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_alt_priority_repeated -WINDOW w AS ( - ORDER BY id - ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING - AFTER MATCH SKIP TO NEXT ROW - PATTERN ((A | B)+) - DEFINE - A AS 'A' = ANY(flags), - B AS 'B' = ANY(flags) -); - id | flags | match_start | match_end -----+-------+-------------+----------- - 1 | {A,B} | 1 | 3 - 2 | {A,B} | 2 | 3 - 3 | {A,B} | 3 | 3 -(3 rows) - --- FIXME 1 - Nested ALT lexical order -WITH test_alt_priority_nested AS ( - SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['C','D']), - (3, ARRAY['A','B']), - (4, 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_alt_priority_nested -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,B} | 1 | 4 - 2 | {C,D} | | - 3 | {A,B} | 3 | 4 - 4 | {C,D} | | -(4 rows) - -- FIXME 2 - Cycle prevention at count > 0 WITH test_cycle_nonzero AS ( SELECT * FROM (VALUES @@ -2516,8 +2484,8 @@ WINDOW w AS ( ); id | flags | match_start | match_end ----+-------+-------------+----------- - 1 | {A} | 1 | 2 - 2 | {B} | 2 | 2 + 1 | {A} | 1 | 3 + 2 | {B} | 2 | 3 3 | {A} | 3 | 3 4 | {C} | | (4 rows) diff --git a/src/test/regress/sql/rpr_explain.sql b/src/test/regress/sql/rpr_explain.sql index ea8c39b991e..d017a2292d2 100644 --- a/src/test/regress/sql/rpr_explain.sql +++ b/src/test/regress/sql/rpr_explain.sql @@ -451,6 +451,30 @@ WINDOW w AS ( );'); DROP VIEW rpr_v; +-- Early termination: first ALT branch (A) reaches FIN immediately, +-- pruning second branch (A B+) before it can accumulate B repetitions. +CREATE TEMP VIEW rpr_v AS +SELECT count(*) OVER w +FROM generate_series(1, 100) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | A B)+) + DEFINE A AS v = 1, B AS v > 1 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_v'), 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, 100) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | A B)+) + DEFINE A AS v = 1, B AS v > 1 +);'); +DROP VIEW rpr_v; + -- Nested quantifiers causing state growth CREATE TEMP VIEW rpr_v AS SELECT count(*) OVER w diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 9573d1dab3b..e9894cfa691 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -1079,6 +1079,29 @@ WINDOW w AS ( D AS 'D' = ANY(flags) ); +-- ALT lexical order takes priority over greedy (longer match). +-- Row 1 matches both A and B; A wins by lexical order (match 1-1). +WITH test_alt_lexical_order AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), -- A and B both match + (2, ARRAY['_','C']) -- only C matches (would continue 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_lexical_order +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) +); + -- ============================================================ -- Deep Nested Groups -- ============================================================ @@ -1772,53 +1795,6 @@ WINDOW w AS ( -- FIXME Issues - Known Limitations -- ============================================================ --- FIXME 1 - altPriority lexical order -WITH test_alt_priority_repeated AS ( - SELECT * FROM (VALUES - (1, ARRAY['A','B']), -- Both A and B match - (2, ARRAY['A','B']), - (3, 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_alt_priority_repeated -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) -); - --- FIXME 1 - Nested ALT lexical order -WITH test_alt_priority_nested AS ( - SELECT * FROM (VALUES - (1, ARRAY['A','B']), - (2, ARRAY['C','D']), - (3, ARRAY['A','B']), - (4, 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_alt_priority_nested -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) -); - -- FIXME 2 - Cycle prevention at count > 0 WITH test_cycle_nonzero AS ( SELECT * FROM (VALUES -- 2.50.1 (Apple Git-155)