From 7c26901a505ebebfe65d4dc22a3a1e5c53b72cd6 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 PATTERN tree rewrites kept the set of matchable lengths but changed which match is preferred, so the same query returned different rows with the optimization than without. Each can move a repetition's exit decision past a choice point inside the body, which leftmost-choice-first (ISO/IEC TR 19075-5 7.2) makes observable. Gate them on the body consuming a fixed number of rows (rprBodyHasUniformLength; equal-length alternatives count as fixed, and a count of RPR_QUANTITY_INF or more counts as varying, which no partition reaches and keeps the measurement in int64). mergeConsecutiveGroups and the suffix phase of mergeGroupPrefixSuffix fold a copy of the body into an adjacent group's quantifier, so over rows A, AB, B, A the pattern (A | B B)+ (A | B B)+ prefers all four where (A | B B){2,} takes two; the prefix phase reorders nothing and needs no gate. tryMultiplyQuantifiers also needs more than contiguous counts: over four rows (A{2,3}){1,2} prefers three where the flattened A{2,6} takes four. Three rpr_base tests pinned the wrongly folded pattern -- a{4,9}, a{4,12}, and (a b*){2,} -- and now show it as written; runtime tests fix the preferred match for each. README.rpr IV-3 records the conditions. --- src/backend/executor/README.rpr | 27 ++- src/backend/optimizer/plan/rpr.c | 137 +++++++++++++- 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 +++++++++++++++++++ 6 files changed, 609 insertions(+), 19 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 02beb50a066..7616676cfd6 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -202,7 +202,14 @@ IV-2. The 6 Phases of buildRPRPattern() IV-3. Phase 1: Parse Tree Optimization After copying the parser-generated parse tree, the following optimizations are -applied: +applied. + +A rewrite must keep not only the set of matchable lengths but also which +match is preferred. Several of them can move a repetition's exit decision +past a choice point inside the body, which leftmost-choice-first (7.2) makes +observable, so they are gated on the body consuming a fixed number of rows. +Alternatives of equal length count as fixed: they pick different variables, +never different rows. (a) SEQ flattening: Unwrap nested SEQ nodes SEQ(A, SEQ(B, C)) -> SEQ(A, B, C) @@ -212,24 +219,34 @@ applied: A A -> A{2} A{2,3} A{1,2} -> A{3,5} - (c) Consecutive group merging: Merge repeated identical groups + (c) Consecutive group merging: Merge repeated identical groups whose + body consumes a fixed number of rows (A B)+ (A B)+ -> (A B){2,INF} + (A | B B)+ (A | B B)+ stays as-is (how the iterations split between + the two groups is a choice the merged form does not have) (d) Consecutive ALT merging: Merge repeated identical ALT nodes (A | B) (A | B) (A | B) -> (A | B){3} - (e) Prefix/suffix merging: Merge identical sequences before/after - a group + (e) Prefix/suffix merging: Merge an identical sequence before or after + a group. A prefix copy is mandatory and comes before the group, so + it always merges; a suffix copy merges only when the body consumes a + fixed number of rows. A B (A B)+ -> (A B){2,INF} (f) ALT flattening and deduplication (A | (B | C)) -> (A | B | C) (A | B | A) -> (A | B) - (g) Quantifier multiplication: Collapse nested quantifiers when safe + (g) Quantifier multiplication: Collapse nested quantifiers when the + achievable counts are contiguous and the preferred match does not + move (A+)+ -> A+ (A{2,3}){5} -> A{10,15} (A{2,})* stays as-is (count 1 unreachable; A* would be wrong) + (A{2,3}){1,2} stays as-is (counts contiguous, but the nested form + settles the first iteration first and prefers three rows where + A{2,6} takes four) (h) Single-child unwrap SEQ(A) -> A, (A){1,1} -> A diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index ee64000bd74..bc58345b64b 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -48,6 +48,9 @@ /* 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 bool rprBodyHasUniformLength(List *children); static List *flattenSeqChildren(List *children); static List *mergeConsecutiveVars(List *children); static List *mergeConsecutiveGroups(List *children); @@ -150,6 +153,91 @@ 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; + + check_stack_depth(); + + 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) + return -1; + if (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; + + /* A count this large cannot arise from real rows anyway */ + if (total >= RPR_QUANTITY_INF) + return -1; + } + return total; +} + +/* + * rprBodyHasUniformLength + * Do the children always consume the same number of rows? + */ +static bool +rprBodyHasUniformLength(List *children) +{ + return rprBodyRowCount(children) >= 0; +} + /* * flattenSeqChildren * Recursively optimize children and flatten nested SEQ. @@ -269,6 +357,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 +386,7 @@ mergeConsecutiveGroups(List *children) */ if (prev != NULL && rprPatternChildrenEqual(prev->children, child->children) && + rprBodyHasUniformLength(child->children) && prev->min < RPR_QUANTITY_INF - child->min && (prev->max < RPR_QUANTITY_INF - child->max || prev->max == RPR_QUANTITY_INF || @@ -457,6 +553,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 +683,7 @@ mergeGroupPrefixSuffix(List *children) /* Compare with GROUP's children */ if (list_length(suffixElements) == groupChildCount && rprPatternChildrenEqual(suffixElements, groupContent) && + rprBodyHasUniformLength(groupContent) && child->min < RPR_QUANTITY_INF - 1 && (child->max == RPR_QUANTITY_INF || child->max < RPR_QUANTITY_INF - 1)) @@ -760,6 +865,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 +892,22 @@ 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. + * + * A VAR child has no body to measure, and its own quantifier already + * settles this, so the test applies to a GROUP child only. + */ + if (child->min != child->max && + child->nodeType == RPR_PATTERN_GROUP && + !rprBodyHasUniformLength(child->children)) + 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 +919,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 +940,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 b5e7de96813..aa762c9dd58 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 -- ============================================================ @@ -3585,6 +3720,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 d8bbd7d7f18..68a311a8706 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 -- ============================================================ @@ -2578,6 +2681,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) -- ============================================================