From c5d93a33c73b68dd1332e2c98bfe0ad72d902f66 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Wed, 15 Jul 2026 08:08:10 +0900 Subject: [PATCH] Preserve row pattern preferment in three PATTERN optimizations Three of the PATTERN tree rewrites kept the set of matchable lengths but changed which match is preferred, so a plain query returned a different match with the optimization than without it. Each is bounded by the same idea: the rewrite may reorder a repetition's exit decision relative to a choice point inside the body, which the standard's leftmost-choice-first rule (ISO/IEC TR 19075-5 7.2) makes observable. tryMultiplyQuantifiers flattened (A{2,3}){1,2} into A{2,6}. The per-iteration counts [2,3] (one iteration) and [4,6] (two) are contiguous, but the nested form settles the first iteration's count before deciding whether to iterate again, so on four A rows it prefers three where A{2,6} takes four. A contiguous count set is necessary but not sufficient. Flatten only when the child cannot reorder its exit decision: its lower bound is reachable in a single iteration (child->min <= 1) or it never has to stop (child->max unbounded); and, when the child repeats a variable number of times (child->min != child->max), only if its body consumes a fixed number of rows (rprBodyRowCount), since a variable-length body defers the stop the same way. A brute force over p,q,m,n confirms this blocks exactly the offending class and nothing safe. mergeConsecutiveGroups and the suffix phase of mergeGroupPrefixSuffix both fold a copy of the body into an adjacent group's quantifier. That is safe only when the body consumes a fixed number of rows; otherwise the merged form defers the group's stop decision past choices the separate copy made first -- (A | B B)+ (A | B B)+ prefers a four-row match where the merged (A | B B){2,} takes two. Add rprNodeRowCount to recognize a fixed-length body (equal-length alternatives included) and gate both merges on it. The prefix phase needs no such gate: a leading copy is mandatory and merges without reordering anything, which a differential fuzz confirms. Three rpr_base tests pinned the wrongly folded pattern in their EXPLAIN output -- a{4,9}, a{4,12}, and (a b*){2,} -- and now show the pattern left as written; runtime tests, including a variable-length nested body case, fix the preferred match for each. --- src/backend/optimizer/plan/rpr.c | 115 +++++++++++- src/test/regress/expected/rpr_base.out | 22 ++- src/test/regress/expected/rpr_nfa.out | 241 +++++++++++++++++++++++++ src/test/regress/sql/rpr_base.sql | 16 +- src/test/regress/sql/rpr_nfa.sql | 185 +++++++++++++++++++ 5 files changed, 565 insertions(+), 14 deletions(-) diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 61cafff4191..9f481e0daab 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -48,6 +48,8 @@ /* Forward declarations */ static bool rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b); static bool rprPatternChildrenEqual(List *a, List *b); +static int64 rprNodeRowCount(RPRPatternNode *node); +static int64 rprBodyRowCount(List *children); static List *flattenSeqChildren(List *children); static List *mergeConsecutiveVars(List *children); static List *mergeConsecutiveGroups(List *children); @@ -150,6 +152,73 @@ rprPatternChildrenEqual(List *a, List *b) return true; } +/* + * rprNodeRowCount + * Rows the node always consumes, or -1 if that varies. + * + * Alternatives of equal length count as fixed: they may pick different + * variables, but never different rows. + */ +static int64 +rprNodeRowCount(RPRPatternNode *node) +{ + int64 len; + + switch (node->nodeType) + { + case RPR_PATTERN_VAR: + if (node->min != node->max) + return -1; + return node->min; + + case RPR_PATTERN_ALT: + len = -1; + foreach_node(RPRPatternNode, branch, node->children) + { + int64 branchLen = rprNodeRowCount(branch); + + if (branchLen < 0 || (len >= 0 && branchLen != len)) + return -1; + len = branchLen; + } + return len; + + case RPR_PATTERN_SEQ: + case RPR_PATTERN_GROUP: + len = rprBodyRowCount(node->children); + if (len < 0 || node->nodeType == RPR_PATTERN_SEQ) + return len; + if (node->min != node->max) + return -1; + len *= node->min; + /* A count this large cannot arise from real rows anyway */ + if (len >= RPR_QUANTITY_INF) + return -1; + return len; + } + return -1; +} + +/* + * rprBodyRowCount + * Rows the children always consume in sequence, or -1 if that varies. + */ +static int64 +rprBodyRowCount(List *children) +{ + int64 total = 0; + + foreach_node(RPRPatternNode, child, children) + { + int64 len = rprNodeRowCount(child); + + if (len < 0) + return -1; + total += len; + } + return total; +} + /* * flattenSeqChildren * Recursively optimize children and flatten nested SEQ. @@ -269,6 +338,13 @@ mergeConsecutiveVars(List *children) * (A B)+ (A B)+ -> (A B){2,} * * Only merges non-reluctant GROUP nodes with identical children. + * + * The body must consume a fixed number of rows. Otherwise the merge changes + * which match is preferred: the two groups split the iterations between them, + * and that split is a choice point the merged form does not have. With a + * fixed body, rows consumed rise in step with the iteration count, so both + * forms reach the same rows in the same order; without one, they need not -- + * (A | B B)+ (A | B B)+ prefers a four-row match where (A | B B){2,} takes two. */ static List * mergeConsecutiveGroups(List *children) @@ -291,6 +367,7 @@ mergeConsecutiveGroups(List *children) */ if (prev != NULL && rprPatternChildrenEqual(prev->children, child->children) && + rprBodyRowCount(child->children) >= 0 && prev->min < RPR_QUANTITY_INF - child->min && (prev->max < RPR_QUANTITY_INF - child->max || prev->max == RPR_QUANTITY_INF || @@ -457,6 +534,14 @@ mergeConsecutiveAlts(List *children) * A B (A B)+ -> (A B){2,} * (A B)+ A B -> (A B){2,} * A B (A B)+ A B -> (A B){3,} + * + * The two phases are not equally safe. A prefix copy is mandatory and comes + * before the group, exactly like the leading mandatory iterations it becomes, + * so the decision trees stay isomorphic for any content. A suffix copy comes + * after the group has already decided to stop, which the merged form defers + * until after the last iteration's own choices. Merge a suffix only when the + * content consumes a fixed number of rows, which leaves it nothing to decide; + * see mergeConsecutiveGroups for why that condition is the right one. */ static List * mergeGroupPrefixSuffix(List *children) @@ -579,6 +664,7 @@ mergeGroupPrefixSuffix(List *children) /* Compare with GROUP's children */ if (list_length(suffixElements) == groupChildCount && rprPatternChildrenEqual(suffixElements, groupContent) && + rprBodyRowCount(groupContent) >= 0 && child->min < RPR_QUANTITY_INF - 1 && (child->max == RPR_QUANTITY_INF || child->max < RPR_QUANTITY_INF - 1)) @@ -760,6 +846,9 @@ optimizeAltPattern(RPRPatternNode *pattern) * yields {4,6} (not 4..6), and (A{2,})* yields {0} UNION [2,INF) (not * [0,INF), so A* would wrongly admit a single A). * + * Contiguity settles the set of counts, not which count is preferred, so a + * further condition is needed; see the comment on safe below. + * * Returns the child node with multiplied quantifiers if successful, * otherwise returns the original pattern unchanged. */ @@ -784,6 +873,19 @@ tryMultiplyQuantifiers(RPRPatternNode *pattern) child->reluctant) return pattern; + /* + * Flattening erases the outer block boundaries, so how the child's + * iterations split across blocks must not matter. A fixed-length body + * ensures that -- splits with the same total span the same rows -- as + * does an exact child quantifier, which admits only one split. Otherwise + * preferment shifts: ((A | B B){1,2}){2} would become (A | B B){2,4}, + * which stops at two A's where the nested form prefers A (B B) A A. + */ + if (child->min != child->max && + child->nodeType == RPR_PATTERN_GROUP && + rprBodyRowCount(child->children) < 0) + return pattern; + /* * Decide whether the achievable counts form one contiguous interval. The * child quantifier is {child->min, child->max} and the outer one is @@ -795,6 +897,7 @@ tryMultiplyQuantifiers(RPRPatternNode *pattern) { bool touch; bool zero_ok; + bool order_ok; /* * Consecutive intervals [t*min, t*max] and [(t+1)*min, (t+1)*max] @@ -815,7 +918,17 @@ tryMultiplyQuantifiers(RPRPatternNode *pattern) */ zero_ok = (pattern->min >= 1 || child->min <= 1); - safe = touch && zero_ok; + /* + * Contiguity is necessary but not sufficient: the flattened form must + * prefer the same match too. The nested form settles the first + * iteration's count before iterating again, so it stops early when + * the tail cannot reach the child's lower bound -- (A{2,3}){1,2} + * prefers three rows where the flattened A{2,6} takes four. Only a + * bounded lower bound >= 2 can be undershot. + */ + order_ok = (child->min <= 1 || child->max == RPR_QUANTITY_INF); + + safe = touch && zero_ok && order_ok; } if (!safe) diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index b5da8de0965..af78ae737fe 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -4711,8 +4711,10 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING -> Seq Scan on rpr_plan (7 rows) --- Quantifier multiply: (A{2,3}){2,3} -> a{4,9} --- outer range, child range: counts [4,6] U [6,9] = [4,9] are contiguous, so it folds +-- Quantifier multiply refused: (A{2,3}){2,3} stays nested. +-- The counts [4,6] U [6,9] = [4,9] are contiguous, but a bounded child with a +-- lower bound to fall short of makes the nested form prefer a shorter match +-- than a{4,9} would. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING @@ -4721,7 +4723,7 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING ------------------------------------------------------------------------------- WindowAgg Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) - Pattern: a{4,9} + Pattern: (a{2,3}){2,3} Nav Mark Lookback: 0 -> Sort Sort Key: id @@ -4843,8 +4845,8 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING -> Seq Scan on rpr_plan (7 rows) --- (A{2,3}){2,4} -> a{4,12} (outer range x child range, contiguous: --- [4,6] U [6,9] U [8,12] = [4,12]) +-- (A{2,3}){2,4} stays nested for the same reason, even though the counts +-- [4,6] U [6,9] U [8,12] = [4,12] are contiguous. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING @@ -4853,7 +4855,7 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING ------------------------------------------------------------------------------- WindowAgg Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) - Pattern: a{4,12} + Pattern: (a{2,3}){2,4} Nav Mark Lookback: 0 -> Sort Sort Key: id @@ -5148,7 +5150,11 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING -> Seq Scan on rpr_plan (7 rows) --- SUFFIX merge with quantifiers: (A B*)+ A B* -> (a b*){2,} +-- SUFFIX merge refused: (A B*)+ A B* stays as written. The body A B* has no +-- fixed row count, so folding the trailing copy into the group would move the +-- group's stop decision ahead of that copy's own choices. The PREFIX merge +-- just above keeps working on the same kind of body -- a leading copy is +-- mandatory, so it merges without reordering anything. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING @@ -5158,7 +5164,7 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING ------------------------------------------------------------------------------- WindowAgg Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) - Pattern: (a b*){2,} + Pattern: (a b*)+ a b* Nav Mark Lookback: 0 -> Sort Sort Key: id diff --git a/src/test/regress/expected/rpr_nfa.out b/src/test/regress/expected/rpr_nfa.out index f807c70f80c..79679a076b6 100644 --- a/src/test/regress/expected/rpr_nfa.out +++ b/src/test/regress/expected/rpr_nfa.out @@ -2640,6 +2640,141 @@ WINDOW w AS ( 4 | {_} | | (4 rows) +-- Consecutive groups are merged only when the body has a fixed row count. +-- (A | B B)+ (A | B B)+ keeps both groups: the merged (A | B B){2,} would +-- stop after two rows, because two iterations already meet its lower bound, +-- while the second group here still demands an iteration of its own. +WITH test_group_merge_uneven_alt AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A', 'B']), + (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_group_merge_uneven_alt +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B)+ (A | B B)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | +(4 rows) + +-- Same guard, reached through a reluctant quantifier in the body: B A+? has no +-- fixed row count either, so (B A+?)+ (B A+?)+ is left alone. +WITH test_group_merge_reluctant_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']), + (6, ARRAY['B']), + (7, 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_group_merge_reluctant_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((B A+?)+ (B A+?)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {B} | 1 | 7 + 2 | {A} | | + 3 | {B} | | + 4 | {A} | | + 5 | {A} | | + 6 | {B} | | + 7 | {A} | | +(7 rows) + +-- The trailing copy in (A | B B){1,2} (A | B B) is not folded into the group +-- for the same reason. A leading copy would be, since it is mandatory. +WITH test_suffix_merge_uneven_alt AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A', 'B']), + (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_suffix_merge_uneven_alt +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,2} (A | B B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 4 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | +(4 rows) + +-- Nested bounded quantifiers ((A{2,3}){1,2}) are not flattened into A{2,6}: +-- the first iteration's count is settled before the group decides whether to +-- iterate again, so with four A rows it takes three and leaves the group +-- rather than taking two and two. A{2,6} would take all four. +WITH test_nested_bounded_quantifier AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['A']), + (5, ARRAY['_']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_bounded_quantifier +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A{2,3}){1,2}) + DEFINE + A AS 'A' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 3 + 2 | {A} | | + 3 | {A} | | + 4 | {A} | | + 5 | {_} | | +(5 rows) + -- ============================================================ -- Alternation Runtime Behavior -- ============================================================ @@ -3613,6 +3748,112 @@ WINDOW w AS ( 3 | {B} | | (3 rows) +-- Exact outer quantifier over a variable-length body +-- ((A | B B){1,2}){2} is by definition (A | B B){1,2} (A | B B){1,2}, so the +-- two must prefer the same match. The optimizer must not collapse the nested +-- form to (A | B B){2,4}: the alternation branches consume a different number +-- of rows, so moving an iteration across the outer block boundary changes +-- which rows are matched. The collapsed form stops at A A (rows 1-2), while +-- the nested form, whose second block must still take an iteration, prefers +-- A (B B) A A (rows 1-5). +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B B){1,2}){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 5 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | + 5 | {A} | | +(5 rows) + +-- The same pattern written out. Must give the same match as the nested form. +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,2} (A | B B){1,2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 5 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | | + 5 | {A} | | +(5 rows) + +-- The collapsed form, written by hand. It admits the same iteration counts as +-- the two above, but it is a different pattern and prefers a different match: +-- with no block boundary to force a second iteration it stops at rows 1-2. +-- That difference is why the two above must not be rewritten into this one. +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){2,4}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + id | flags | match_start | match_end +----+-------+-------------+----------- + 1 | {A} | 1 | 2 + 2 | {A,B} | | + 3 | {B} | | + 4 | {A} | 4 | 5 + 5 | {A} | | +(5 rows) + -- ============================================================ -- SKIP Options (Runtime) -- ============================================================ diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index eed5ea958a0..571300d0d40 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -2957,8 +2957,10 @@ SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN ((A{2}){3,5}) DEFINE A AS val > 0); --- Quantifier multiply: (A{2,3}){2,3} -> a{4,9} --- outer range, child range: counts [4,6] U [6,9] = [4,9] are contiguous, so it folds +-- Quantifier multiply refused: (A{2,3}){2,3} stays nested. +-- The counts [4,6] U [6,9] = [4,9] are contiguous, but a bounded child with a +-- lower bound to fall short of makes the nested form prefer a shorter match +-- than a{4,9} would. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING @@ -3009,8 +3011,8 @@ SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN ((A+){2,4}) DEFINE A AS val > 0); --- (A{2,3}){2,4} -> a{4,12} (outer range x child range, contiguous: --- [4,6] U [6,9] U [8,12] = [4,12]) +-- (A{2,3}){2,4} stays nested for the same reason, even though the counts +-- [4,6] U [6,9] U [8,12] = [4,12] are contiguous. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING @@ -3134,7 +3136,11 @@ WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A+ B* C? (A+ B* C?)+) DEFINE A AS val <= 30, B AS val > 30 AND val <= 60, C AS val > 60); --- SUFFIX merge with quantifiers: (A B*)+ A B* -> (a b*){2,} +-- SUFFIX merge refused: (A B*)+ A B* stays as written. The body A B* has no +-- fixed row count, so folding the trailing copy into the group would move the +-- group's stop decision ahead of that copy's own choices. The PREFIX merge +-- just above keeps working on the same kind of body -- a leading copy is +-- mandatory, so it merges without reordering anything. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_plan WINDOW w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING diff --git a/src/test/regress/sql/rpr_nfa.sql b/src/test/regress/sql/rpr_nfa.sql index 3d8d3bf4a8a..279958678b3 100644 --- a/src/test/regress/sql/rpr_nfa.sql +++ b/src/test/regress/sql/rpr_nfa.sql @@ -1864,6 +1864,109 @@ WINDOW w AS ( B AS 'B' = ANY(flags) ); +-- Consecutive groups are merged only when the body has a fixed row count. +-- (A | B B)+ (A | B B)+ keeps both groups: the merged (A | B B){2,} would +-- stop after two rows, because two iterations already meet its lower bound, +-- while the second group here still demands an iteration of its own. +WITH test_group_merge_uneven_alt AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A', 'B']), + (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_group_merge_uneven_alt +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B)+ (A | B B)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Same guard, reached through a reluctant quantifier in the body: B A+? has no +-- fixed row count either, so (B A+?)+ (B A+?)+ is left alone. +WITH test_group_merge_reluctant_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['B']), + (2, ARRAY['A']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']), + (6, ARRAY['B']), + (7, 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_group_merge_reluctant_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((B A+?)+ (B A+?)+) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- The trailing copy in (A | B B){1,2} (A | B B) is not folded into the group +-- for the same reason. A leading copy would be, since it is mandatory. +WITH test_suffix_merge_uneven_alt AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A', 'B']), + (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_suffix_merge_uneven_alt +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,2} (A | B B)) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- Nested bounded quantifiers ((A{2,3}){1,2}) are not flattened into A{2,6}: +-- the first iteration's count is settled before the group decides whether to +-- iterate again, so with four A rows it takes three and leaves the group +-- rather than taking two and two. A{2,6} would take all four. +WITH test_nested_bounded_quantifier AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A']), + (3, ARRAY['A']), + (4, ARRAY['A']), + (5, ARRAY['_']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_bounded_quantifier +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A{2,3}){1,2}) + DEFINE + A AS 'A' = ANY(flags) +); + -- ============================================================ -- Alternation Runtime Behavior -- ============================================================ @@ -2600,6 +2703,88 @@ WINDOW w AS ( A AS 'A' = ANY(flags) ); +-- Exact outer quantifier over a variable-length body +-- ((A | B B){1,2}){2} is by definition (A | B B){1,2} (A | B B){1,2}, so the +-- two must prefer the same match. The optimizer must not collapse the nested +-- form to (A | B B){2,4}: the alternation branches consume a different number +-- of rows, so moving an iteration across the outer block boundary changes +-- which rows are matched. The collapsed form stops at A A (rows 1-2), while +-- the nested form, whose second block must still take an iteration, prefers +-- A (B B) A A (rows 1-5). +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (((A | B B){1,2}){2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- The same pattern written out. Must give the same match as the nested form. +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){1,2} (A | B B){1,2}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + +-- The collapsed form, written by hand. It admits the same iteration counts as +-- the two above, but it is a different pattern and prefers a different match: +-- with no block boundary to force a second iteration it stops at rows 1-2. +-- That difference is why the two above must not be rewritten into this one. +WITH test_nested_alt_body AS ( + SELECT * FROM (VALUES + (1, ARRAY['A']), + (2, ARRAY['A','B']), + (3, ARRAY['B']), + (4, ARRAY['A']), + (5, ARRAY['A']) + ) AS t(id, flags) +) +SELECT id, flags, + first_value(id) OVER w AS match_start, + last_value(id) OVER w AS match_end +FROM test_nested_alt_body +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A | B B){2,4}) + DEFINE + A AS 'A' = ANY(flags), + B AS 'B' = ANY(flags) +); + -- ============================================================ -- SKIP Options (Runtime) -- ============================================================ -- 2.50.1 (Apple Git-155)