From 946696e81de973b64af9c88ab5404beee815a2f5 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Wed, 25 Feb 2026 19:58:59 +0900 Subject: [PATCH 08/10] Fix empty-match iteration for nullable group bodies --- src/backend/executor/nodeWindowAgg.c | 35 +- src/backend/optimizer/plan/rpr.c | 68 ++- src/include/optimizer/rpr.h | 7 +- src/test/regress/expected/rpr_nfa.out | 575 ++++++++++++++++++++++++++ src/test/regress/sql/rpr_nfa.sql | 468 +++++++++++++++++++++ 5 files changed, 1131 insertions(+), 22 deletions(-) diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index 98546fb17f7..0aa5df3e153 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -6212,15 +6212,46 @@ nfa_advance_end(WindowAggState *winstate, RPRNFAContext *ctx, if (count < elem->min) { - /* Must loop back */ RPRPatternElement *jumpElem; + RPRNFAState *ffState = NULL; + /* Snapshot state for ff path before modifying for loop-back */ + if (RPRElemCanEmptyLoop(elem)) + ffState = nfa_state_create(winstate, state->elemIdx, + state->counts, state->isAbsorbable); + + /* Loop back for real matches (primary path) */ for (int d = depth + 1; d < pattern->maxDepth; d++) state->counts[d] = 0; state->elemIdx = elem->jump; jumpElem = &elements[state->elemIdx]; + nfa_route_to_elem(winstate, ctx, state, jumpElem, + currentPos, initialAdvance); + + /* + * Fast-forward fallback for nullable bodies. E.g. (A?){2,3} when + * A doesn't match: the loop-back produces empty iterations that + * cycle detection would kill. Instead, exit directly treating all + * remaining required iterations as empty. Route to elem->next + * (not nfa_advance_end) to avoid creating competing greedy/reluctant + * loop states. + */ + if (ffState != NULL) + { + RPRPatternElement *nextElem; - nfa_route_to_elem(winstate, ctx, state, jumpElem, currentPos, initialAdvance); + ffState->counts[depth] = 0; + ffState->elemIdx = elem->next; + nextElem = &elements[ffState->elemIdx]; + + /* END->END: increment outer END's count */ + if (RPRElemIsEnd(nextElem) && + ffState->counts[nextElem->depth] < RPR_COUNT_MAX) + ffState->counts[nextElem->depth]++; + + nfa_route_to_elem(winstate, ctx, ffState, nextElem, + currentPos, initialAdvance); + } } else if (elem->max != RPR_QUANTITY_INF && count >= elem->max) { diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 4414b71b5ec..8792d8174fa 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -78,13 +78,13 @@ static void scanRPRPattern(RPRPatternNode *node, char **varNames, int *numVars, static RPRPattern *allocateRPRPattern(int numVars, int numElements, RPRDepth maxDepth, char **varNamesStack); static RPRVarId getVarIdFromPattern(RPRPattern *pat, const char *varName); -static void fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, +static bool fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth); -static void fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, +static bool fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth); -static void fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, +static bool fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth); -static void fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, +static bool fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth); static void finalizeRPRPattern(RPRPattern *result); @@ -1135,8 +1135,10 @@ getVarIdFromPattern(RPRPattern *pat, const char *varName) /* * fillRPRPatternVar * Fill a VAR pattern element. + * + * Returns true if this VAR is nullable (can match zero rows). */ -static void +static bool fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { RPRPatternElement *elem = &pat->elements[*idx]; @@ -1151,6 +1153,8 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept if (node->reluctant >= 0) elem->flags |= RPR_ELEM_RELUCTANT; (*idx)++; + + return (node->min == 0); } /* @@ -1159,13 +1163,18 @@ fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * * Creates elements for group content at increased depth, plus an END marker * if the group has a non-trivial quantifier. + * + * 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). */ -static void +static bool fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { ListCell *lc; int groupStartIdx = *idx; int beginIdx = -1; + bool bodyNullable = true; /* Add BEGIN marker if group has non-trivial quantifier */ if (node->min != 1 || node->max != 1) @@ -1188,7 +1197,8 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de foreach(lc, node->children) { - fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth + 1); + if (!fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth + 1)) + bodyNullable = false; } /* Add group end marker if group has non-trivial quantifier */ @@ -1206,11 +1216,22 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de endElem->jump = groupStartIdx; /* loop to first child */ if (node->reluctant >= 0) endElem->flags |= RPR_ELEM_RELUCTANT; + + /* + * If the group body is nullable (all paths can match empty), 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; + (*idx)++; /* Set BEGIN skip pointer (next is set by finalize) */ beginElem->jump = *idx; /* skip: go to after END */ } + + return (node->min == 0 || bodyNullable); } /* @@ -1219,8 +1240,11 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de * * Creates ALT_START marker, fills each alternative at increased depth, * sets jump pointers for backtracking, and next pointers for successful paths. + * + * Returns true if any branch is nullable (OR semantics: one nullable + * branch suffices for the alternation to produce an empty match). */ -static void +static bool fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { ListCell *lc; @@ -1229,6 +1253,7 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept List *altBranchStarts = NIL; List *altEndPositions = NIL; int afterAltIdx; + bool anyNullable = false; /* Add alternation start marker */ elem = &pat->elements[*idx]; @@ -1248,7 +1273,8 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept int branchStart = *idx; altBranchStarts = lappend_int(altBranchStarts, branchStart); - fillRPRPattern(alt, pat, idx, depth + 1); + if (fillRPRPattern(alt, pat, idx, depth + 1)) + anyNullable = true; altEndPositions = lappend_int(altEndPositions, *idx - 1); } @@ -1296,6 +1322,8 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept list_free(altBranchStarts); list_free(altEndPositions); + + return anyNullable; } /* @@ -1304,11 +1332,15 @@ fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth dept * * Recursively traverses AST and populates pre-allocated elements 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). */ -static void +static bool fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) { ListCell *lc; + bool allNullable = true; /* Pattern nodes from parser are never NULL */ Assert(node != NULL); @@ -1318,22 +1350,22 @@ fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) case RPR_PATTERN_SEQ: foreach(lc, node->children) { - fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth); + if (!fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth)) + allNullable = false; } - break; + return allNullable; case RPR_PATTERN_VAR: - fillRPRPatternVar(node, pat, idx, depth); - break; + return fillRPRPatternVar(node, pat, idx, depth); case RPR_PATTERN_GROUP: - fillRPRPatternGroup(node, pat, idx, depth); - break; + return fillRPRPatternGroup(node, pat, idx, depth); case RPR_PATTERN_ALT: - fillRPRPatternAlt(node, pat, idx, depth); - break; + return fillRPRPatternAlt(node, pat, idx, depth); } + + return false; /* unreachable */ } /* diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h index 7a8938dbebd..fa2d075925c 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -34,11 +34,14 @@ /* Element flags */ #define RPR_ELEM_RELUCTANT 0x01 /* reluctant (non-greedy) * quantifier */ -#define RPR_ELEM_ABSORBABLE_BRANCH 0x02 /* element in absorbable region */ -#define RPR_ELEM_ABSORBABLE 0x04 /* absorption judgment point */ +#define RPR_ELEM_EMPTY_LOOP 0x02 /* END: group body can produce + * empty match */ +#define RPR_ELEM_ABSORBABLE_BRANCH 0x04 /* element in absorbable region */ +#define RPR_ELEM_ABSORBABLE 0x08 /* absorption judgment point */ /* Accessor macros for RPRPatternElement */ #define RPRElemIsReluctant(e) ((e)->flags & RPR_ELEM_RELUCTANT) +#define RPRElemCanEmptyLoop(e) ((e)->flags & RPR_ELEM_EMPTY_LOOP) #define RPRElemIsAbsorbableBranch(e) ((e)->flags & RPR_ELEM_ABSORBABLE_BRANCH) #define RPRElemIsAbsorbable(e) ((e)->flags & RPR_ELEM_ABSORBABLE) #define RPRElemIsVar(e) ((e)->varId <= RPR_VARID_MAX) diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index 8ac375cfe86..2ace2df13ca 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -3006,3 +3006,578 @@ WINDOW w AS ( 4 | {C} | | (4 rows) +-- ============================================================ +-- Standard Clause 7: Formal Pattern Matching Rules +-- ISO/IEC 19075-5:2021, Clause 7 +-- ============================================================ +-- ------------------------------------------------------------ +-- 7.2.2 Alternation: first alternative is preferred +-- ------------------------------------------------------------ +-- (A | B): A preferred over B when both could match +-- Row 1 has both A and B flags: A should be chosen (first alternative) +WITH test_alt_prefer AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']), + (3, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_alt_prefer +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 1 + 2 | {B} | 2 | 2 + 3 | {A} | 3 | 3 +(3 rows) + +-- (A{1,2} | B{2,3}): all A-matches before all B-matches +-- Standard example: preferment order is AA, A, BBB, BB +-- 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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 2 + 2 | {A,B} | 2 | 2 + 3 | {B} | 3 | 5 + 4 | {B} | 4 | 5 + 5 | {B} | | +(5 rows) + +-- ------------------------------------------------------------ +-- 7.2.3 Concatenation: lexicographic ordering +-- ------------------------------------------------------------ +-- ((A | B) (C | D)): preferment order is AC, AD, BC, BD +-- Row 1 matches A and B, Row 2 matches C and D +-- Preferred match: A then C (first alternatives in both positions) +WITH test_concat_lex AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['C','D']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_concat_lex +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B) (C | D)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A,B} | 1 | 2 + 2 | {C,D} | | +(2 rows) + +-- ((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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 2 + 2 | {C} | | + 3 | {A} | 3 | 4 + 4 | {C} | | +(4 rows) + +-- ------------------------------------------------------------ +-- 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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | + 4 | {B} | | +(4 rows) + +-- 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) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | | + 3 | {A} | | + 4 | {B} | | +(4 rows) + +-- ((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) +); + 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) + +-- ------------------------------------------------------------ +-- 7.2.6 Anchors (not yet implemented - syntax error expected) +-- ------------------------------------------------------------ +-- ^ anchor: not yet supported +SELECT count(*) OVER w FROM (SELECT 1 AS v) t +WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (^ A) DEFINE A AS TRUE); +ERROR: syntax error at or near "^" +LINE 3: PATTERN (^ A) DEFINE A AS TRUE); + ^ +-- $ anchor: not yet supported +SELECT count(*) OVER w FROM (SELECT 1 AS v) t +WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A $) DEFINE A AS TRUE); +ERROR: syntax error at or near "$" +LINE 3: PATTERN (A $) DEFINE A AS TRUE); + ^ +-- ------------------------------------------------------------ +-- 7.2.8 Infinite repetitions of empty matches +-- (Perl lower-bound stopping rule) +-- ------------------------------------------------------------ +-- Standard examples from 7.2.8: +-- (A?){0,3}: allowed strings include STR00=(), STR01=(A), STR02=(empty), +-- STR03=(AA), STR04=(A,empty), STR07=(AAA), STR08=(AA,empty) +-- (A?){1,3}: same as {0,3} but STR00 excluded (min=1 not met) +-- (A?){2,3}: STR03-06 (len 2) and STR07,08,11,12 (len 3) are valid +-- STR06=(STRE,STRE) IS valid because non-final STRE at +-- position 1 fills the lower bound +-- (A??)*B: Standard 7.2.8 introductory example +-- "matched against a sequence of rows for which the only feasible +-- matching is: B" +-- A?? is reluctant, prefers empty. * is greedy but Perl rule stops +-- after empty match with min(=0) satisfied. +-- Expected: each B row matches alone (A?? empty, * stops, B matches) +WITH test_empty_reluctant_star AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (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_reluctant_star +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 | {B} | 1 | 1 + 2 | {B} | 2 | 2 + 3 | {C} | | +(3 rows) + +-- (A?){0,3}: min=0, nullable inner. +-- A never matches. A? matches empty, min=0 satisfied immediately. +-- Expected: empty match (match_start = match_end) for every row +WITH test_728_min0 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min0 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){0,3}) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | | + 2 | {B} | | + 3 | {B} | | +(3 rows) + +-- (A?){1,3}: min=1, nullable inner. +-- A never matches. Need 1 empty iteration to satisfy min=1. +-- Expected: empty match for every row +WITH test_728_min1 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min1 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){1,3}) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | | + 2 | {B} | | + 3 | {B} | | +(3 rows) + +-- (A?){2,3}: min=2, nullable inner. +-- A never matches. Need 2 empty iterations to satisfy min=2. +-- Per standard: STR06=(STRE STRE) is valid for min=2. +-- Expected: empty match for every row +-- BUG: visited bitmap blocks second empty iteration → match failure +WITH test_728_min2 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min2 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){2,3}) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | | + 2 | {B} | | + 3 | {B} | | +(3 rows) + +-- (A?){2,3} mixed: some rows match A, some don't +-- Rows 1-2: A matches, greedy takes 2 → min satisfied +-- Row 3: A doesn't match, needs 2 empty iterations for min=2 +-- Expected: all rows produce matches +WITH test_728_min2_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (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_728_min2_mixed +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){2,3}) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A} | 2 | 2 + 3 | {B} | | + 4 | {A} | 4 | 4 +(4 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 +-- fires as a parallel exit path (EXIT ONLY, no greedy/reluctant loop). +-- Data: alternating A, B rows (6 rows) +-- Greedy: each row gets the longest match from its starting position. +-- Row 1: 3 iters (A@1,B@2)(A@3,B@4)(A@5,B@6) → 1-6 +-- Row 5: 1 real iter + 1 ff empty exit → 5-6 +WITH test_728_multi_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']), + (5, ARRAY['A']), + (6, 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_multi_body +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 | 6 + 2 | {B} | 2 | 6 + 3 | {A} | 3 | 6 + 4 | {B} | 4 | 6 + 5 | {A} | 5 | 6 + 6 | {B} | 6 | 6 +(6 rows) + +-- (A? B?){2,3}: pure empty body (nothing matches) +-- All NULL: same known bug as test_728_min2 (initialAdvance blocks FIN +-- for zero-length matches at context start) +WITH test_728_multi_empty AS ( + SELECT * FROM (VALUES + (1, ARRAY['C']), + (2, ARRAY['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_multi_empty +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 | {C} | | + 2 | {C} | | + 3 | {C} | | +(3 rows) + +-- (A? B?){2,3}: mixed real and empty iterations +-- Row 1: iter1 real (A@1,B@2), iter2 at row 3 empty → ff exit, match 1-2 +-- Row 3: C doesn't match A or B → NULL +-- Row 4: iter1 real (A@4,B@5), iter2 at end empty → ff exit, match 4-5 +WITH test_728_multi_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, ARRAY['A']), + (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_728_multi_mixed +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 | {B} | 2 | 2 + 3 | {C} | | + 4 | {A} | 4 | 5 + 5 | {B} | 5 | 5 +(5 rows) + +-- ------------------------------------------------------------ +-- 7.3 Pattern matching in theory and practice +-- ------------------------------------------------------------ +-- Standard's worked example: A? B+ with specific data +-- Preferment order: (A)(BBB), (A)(BB), (A)(B), ()(BBB), ()(BB), ()(B) +-- Row 1: A condition (price>100) is false → A fails +-- Backtrack: empty A?, then B+ from row 1 +-- Expected: rows 1-3 match as B (A? takes empty match) +WITH test_73_example AS ( + SELECT * FROM (VALUES + (1, 60), + (2, 70), + (3, 40) + ) 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_73_example +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 price > 100, + B AS TRUE +); + id | price | match_start | match_end +----+-------+-------------+----------- + 1 | 60 | 1 | 3 + 2 | 70 | | + 3 | 40 | | +(3 rows) + diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index be78ab760a9..27426b1ac4f 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -2237,3 +2237,471 @@ WINDOW w AS ( A AS 'A' = ANY(flags), B AS 'B' = ANY(flags) ); + +-- ============================================================ +-- Standard Clause 7: Formal Pattern Matching Rules +-- ISO/IEC 19075-5:2021, 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) +); + +-- ------------------------------------------------------------ +-- 7.2.3 Concatenation: lexicographic ordering +-- ------------------------------------------------------------ + +-- ((A | B) (C | D)): preferment order is AC, AD, BC, BD +-- Row 1 matches A and B, Row 2 matches C and D +-- Preferred match: A then C (first alternatives in both positions) +WITH test_concat_lex AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['C','D']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_concat_lex +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B) (C | D)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags), + D AS 'D' = ANY(flags) +); + +-- ((A | B) C): first alt (A) fails, second alt (B) succeeds +-- Tests backtracking: row 1 has only B, row 2 has C +WITH test_concat_backtrack AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['C']), + (3, ARRAY['A']), + (4, ARRAY['C']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_concat_backtrack +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A | B) C) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags), + C AS 'C' = ANY(flags) +); + +-- ------------------------------------------------------------ +-- 7.2.4 Quantification: greedy/reluctant, lexicographic > length +-- ------------------------------------------------------------ + +-- V{2,4} greedy: longer match preferred +WITH test_quant_greedy AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_quant_greedy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A{2,4}) + DEFINE + A AS 'A' = ANY(flags) +); + +-- V{2,4}? reluctant: shorter match preferred +WITH test_quant_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['B']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_quant_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A{2,4}?) + DEFINE + A AS 'A' = ANY(flags) +); + +-- ((A|B){1,2}) greedy: lexicographic > length +-- Standard example: preferment AA, AB, A, BA, BB, B +-- Single A preferred over B-starting longer match +WITH test_quant_lex_greedy AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_quant_lex_greedy +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2})) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ((A|B){1,2}?) reluctant: lexicographic > length +-- Standard example: preferment A, AA, AB, B, BA, BB +-- Single A preferred over any B-starting match +WITH test_quant_lex_reluctant AS ( + SELECT * FROM (VALUES + (1, ARRAY['A','B']), + (2, ARRAY['B']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_quant_lex_reluctant +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B){1,2}?)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- ------------------------------------------------------------ +-- 7.2.6 Anchors (not yet implemented - syntax error expected) +-- ------------------------------------------------------------ + +-- ^ anchor: not yet supported +SELECT count(*) OVER w FROM (SELECT 1 AS v) t +WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (^ A) DEFINE A AS TRUE); + +-- $ anchor: not yet supported +SELECT count(*) OVER w FROM (SELECT 1 AS v) t +WINDOW w AS (ORDER BY v ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A $) DEFINE A AS TRUE); + +-- ------------------------------------------------------------ +-- 7.2.8 Infinite repetitions of empty matches +-- (Perl lower-bound stopping rule) +-- ------------------------------------------------------------ +-- Standard examples from 7.2.8: +-- (A?){0,3}: allowed strings include STR00=(), STR01=(A), STR02=(empty), +-- STR03=(AA), STR04=(A,empty), STR07=(AAA), STR08=(AA,empty) +-- (A?){1,3}: same as {0,3} but STR00 excluded (min=1 not met) +-- (A?){2,3}: STR03-06 (len 2) and STR07,08,11,12 (len 3) are valid +-- STR06=(STRE,STRE) IS valid because non-final STRE at +-- position 1 fills the lower bound + +-- (A??)*B: Standard 7.2.8 introductory example +-- "matched against a sequence of rows for which the only feasible +-- matching is: B" +-- A?? is reluctant, prefers empty. * is greedy but Perl rule stops +-- after empty match with min(=0) satisfied. +-- Expected: each B row matches alone (A?? empty, * stops, B matches) +WITH test_empty_reluctant_star AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (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_reluctant_star +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?){0,3}: min=0, nullable inner. +-- A never matches. A? matches empty, min=0 satisfied immediately. +-- Expected: empty match (match_start = match_end) for every row +WITH test_728_min0 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min0 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){0,3}) + DEFINE + A AS 'A' = ANY(flags) +); + +-- (A?){1,3}: min=1, nullable inner. +-- A never matches. Need 1 empty iteration to satisfy min=1. +-- Expected: empty match for every row +WITH test_728_min1 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min1 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){1,3}) + DEFINE + A AS 'A' = ANY(flags) +); + +-- (A?){2,3}: min=2, nullable inner. +-- A never matches. Need 2 empty iterations to satisfy min=2. +-- Per standard: STR06=(STRE STRE) is valid for min=2. +-- Expected: empty match for every row +-- BUG: visited bitmap blocks second empty iteration → match failure +WITH test_728_min2 AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['B']), + (3, 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_min2 +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){2,3}) + DEFINE + A AS 'A' = ANY(flags) +); + +-- (A?){2,3} mixed: some rows match A, some don't +-- Rows 1-2: A matches, greedy takes 2 → min satisfied +-- Row 3: A doesn't match, needs 2 empty iterations for min=2 +-- Expected: all rows produce matches +WITH test_728_min2_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (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_728_min2_mixed +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP TO NEXT ROW + PATTERN ((A?){2,3}) + DEFINE + A AS 'A' = 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 +-- fires as a parallel exit path (EXIT ONLY, no greedy/reluctant loop). +-- Data: alternating A, B rows (6 rows) +-- Greedy: each row gets the longest match from its starting position. +-- Row 1: 3 iters (A@1,B@2)(A@3,B@4)(A@5,B@6) → 1-6 +-- Row 5: 1 real iter + 1 ff empty exit → 5-6 +WITH test_728_multi_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['A']), + (4, ARRAY['B']), + (5, ARRAY['A']), + (6, 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_multi_body +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) +); + +-- (A? B?){2,3}: pure empty body (nothing matches) +-- All NULL: same known bug as test_728_min2 (initialAdvance blocks FIN +-- for zero-length matches at context start) +WITH test_728_multi_empty AS ( + SELECT * FROM (VALUES + (1, ARRAY['C']), + (2, ARRAY['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_multi_empty +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) +); + +-- (A? B?){2,3}: mixed real and empty iterations +-- Row 1: iter1 real (A@1,B@2), iter2 at row 3 empty → ff exit, match 1-2 +-- Row 3: C doesn't match A or B → NULL +-- Row 4: iter1 real (A@4,B@5), iter2 at end empty → ff exit, match 4-5 +WITH test_728_multi_mixed AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['B']), + (3, ARRAY['C']), + (4, ARRAY['A']), + (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_728_multi_mixed +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) +); + +-- ------------------------------------------------------------ +-- 7.3 Pattern matching in theory and practice +-- ------------------------------------------------------------ + +-- Standard's worked example: A? B+ with specific data +-- Preferment order: (A)(BBB), (A)(BB), (A)(B), ()(BBB), ()(BB), ()(B) +-- Row 1: A condition (price>100) is false → A fails +-- Backtrack: empty A?, then B+ from row 1 +-- Expected: rows 1-3 match as B (A? takes empty match) +WITH test_73_example AS ( + SELECT * FROM (VALUES + (1, 60), + (2, 70), + (3, 40) + ) 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_73_example +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 price > 100, + B AS TRUE +); -- 2.50.1 (Apple Git-155)