From 6f5534fd2d981cec6967e5c84ddbfa2cd287ff84 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Tue, 11 Aug 2026 19:46:56 +0900 Subject: [PATCH] Stop RPR absorption at a reluctant group's BEGIN computeAbsorbability() documents that reluctant quantifiers are excluded, but isUnboundedStart() tests only the quantifier it is handed, so the greedy A+ in PATTERN ((A+ B)+? C) became an absorption comparison point. Absorption assumes an earlier context subsumes a later one, which a reluctant group inverts. Return at such a BEGIN: the group's quantifier sits on its BEGIN as well as its END, so that element answers for the whole subtree. The change only withholds flags, so the matcher keeps contexts it used to discard and never the reverse. The new rpr_explain cases are a discriminating pair -- same body, DEFINE and rows -- where the greedy (A+ B)+ C reports the absorption marker on a+ and a nonzero absorbed count, and the reluctant (A+ B)+? C twin reports neither. --- src/backend/executor/README.rpr | 5 ++ src/backend/optimizer/plan/rpr.c | 29 ++++++-- src/test/regress/expected/rpr_explain.out | 82 +++++++++++++++++++++++ src/test/regress/sql/rpr_explain.sql | 48 +++++++++++++ 4 files changed, 158 insertions(+), 6 deletions(-) diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 69277701744..3a965fc01f8 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -514,6 +514,11 @@ Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive): ABSORBABLE | ABSORBABLE_BRANCH set on A. B and END get no flags -> absorption stops once past A. +A reluctant group disqualifies its whole subtree. computeAbsorbability- +Recursive() returns at such a BEGIN, so (A+ B)+? gets no flags at all +even though A+ itself is greedy: the group prefers its shorter +alternative, which is the opposite of the ordering absorption relies on. + Absorbability is determined per-element, not per-pattern. Absorption comparison is performed only when a state resides at an element with the RPR_ELEM_ABSORBABLE flag. Once a state leaves the diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index a77bfb45fd8..bbcf6734967 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -1807,10 +1807,15 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth) * * Returns false for patterns where absorption cannot work: * - A B+ (unbounded not at start) - * - A+? B (reluctant quantifier) + * - A+? B (the unbounded quantifier itself is reluctant) * - (A | B)+ (ALT inside group) * - (A B+)+ (variable-length element inside group) * - (A B{2,5})+ (min != max inside group) + * + * The reluctance test covers only the quantifier examined here. A + * reluctant quantifier on an enclosing group -- (A+)??, where A+ itself + * is greedy -- is rejected at that group's BEGIN by + * computeAbsorbabilityRecursive(), before this function is reached. */ static bool isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) @@ -1868,11 +1873,15 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) * computeAbsorbabilityRecursive * Recursively check absorbability starting from given index. * - * If the element at startIdx is ALT, recursively checks each branch independently. - * Each branch gets its own absorbability status, and if any branch is absorbable, - * the ALT element itself is marked with RPR_ELEM_ABSORBABLE_BRANCH. + * If the element at startIdx is ALT, recursively checks each branch + * independently. Each branch gets its own absorbability status, and if + * any branch is absorbable, the ALT element itself is marked with + * RPR_ELEM_ABSORBABLE_BRANCH. * - * If BEGIN, skips to first child. + * If BEGIN, skips to first child -- but only when the group's own + * quantifier is greedy. Absorption assumes an earlier context subsumes a + * later one, which a reluctant group inverts; isUnboundedStart() sees only + * the quantifier it is handed, so the greedy A+ in (A+)?? needs this check. * * Otherwise (VAR), checks if the element starts an unbounded sequence via * isUnboundedStart. @@ -1917,6 +1926,13 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, } else if (RPRElemIsBegin(elem)) { + /* + * Not an absorbable region. The group's quantifier sits on its BEGIN + * as well as its END, so this element answers for the group. + */ + if (RPRElemIsReluctant(elem)) + return; + /* * BEGIN: first try to treat this BEGIN's children as an unbounded * group directly (handles nested fixed-length groups like ((A{2} @@ -1958,7 +1974,8 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx, * * Only greedy unbounded quantifiers at pattern start can be absorbable. * Reluctant quantifiers are excluded because they don't maintain monotonic - * decrease property required for safe absorption. + * decrease property required for safe absorption -- both the unbounded + * quantifier itself and any group quantifier enclosing it. * * This function sets two flags: * RPR_ELEM_ABSORBABLE: Absorption comparison point diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out index 19f23cef2e1..112e483d55b 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -1428,6 +1428,88 @@ WINDOW w AS ( -> Function Scan on generate_series s (actual rows=50.00 loops=1) (10 rows) +-- Variable-length group body absorption: (A+ B)+ C +-- Body is not fixed-length, so the leading A+ is the comparison point +-- (Case 3); the group's own END gets no flag. +CREATE VIEW rpr_ev_ctx_absorb_group_greedy AS +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+ C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_ctx_absorb_group_greedy'), E'\n')) AS line WHERE line ~ 'PATTERN'; + line +------------------------ + PATTERN ((a+ b)+ c) +(1 row) + +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+ C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=50.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a+" b)+ c + Storage: Memory Maximum Storage: NkB + NFA States: 3 peak, 96 total, 0 merged + NFA Contexts: 3 peak, 51 total, 5 pruned + NFA: 5 matched (len 10/10/10.0), 0 mismatched + NFA: 35 absorbed (len 1/1/1.0), 5 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=50.00 loops=1) +(9 rows) + +-- No absorption when the enclosing group is reluctant: (A+ B)+? C +-- Same body, DEFINE and rows as above; only the group quantifier differs. +-- Compare: absorbed count 0 and no marker on a+, vs >0 and a+# above. +CREATE VIEW rpr_ev_ctx_no_absorb_reluctant_group AS +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+? C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_ctx_no_absorb_reluctant_group'), E'\n')) AS line WHERE line ~ 'PATTERN'; + line +------------------------- + PATTERN ((a+ b)+? c) +(1 row) + +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+? C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=50.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a+ b)+? c + Storage: Memory Maximum Storage: NkB + NFA States: 17 peak, 271 total, 0 merged + NFA Contexts: 10 peak, 51 total, 5 pruned + NFA: 5 matched (len 10/10/10.0), 0 mismatched + NFA: 0 absorbed, 40 skipped (len 1/9/5.4) + -> Function Scan on generate_series s (actual rows=50.00 loops=1) +(9 rows) + -- Alternation, non-absorbable branch match survives absorption: A+ B | C -- The dominating A+ run absorbs redundant contexts, but the recorded C matches -- are not absorbable, so they survive (2 matched, not 0) diff --git a/src/test/regress/sql/rpr_explain.sql b/src/test/regress/sql/rpr_explain.sql index 4246c559d35..f28c0cdacb1 100644 --- a/src/test/regress/sql/rpr_explain.sql +++ b/src/test/regress/sql/rpr_explain.sql @@ -892,6 +892,54 @@ WINDOW w AS ( DEFINE A AS v % 5 <> 0, B AS v % 5 = 0 AND PREV(FIRST(v), 1) IS NOT NULL );'); +-- Variable-length group body absorption: (A+ B)+ C +-- Body is not fixed-length, so the leading A+ is the comparison point +-- (Case 3); the group's own END gets no flag. +CREATE VIEW rpr_ev_ctx_absorb_group_greedy AS +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+ C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_ctx_absorb_group_greedy'), E'\n')) AS line WHERE line ~ 'PATTERN'; +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+ C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +);'); + +-- No absorption when the enclosing group is reluctant: (A+ B)+? C +-- Same body, DEFINE and rows as above; only the group quantifier differs. +-- Compare: absorbed count 0 and no marker on a+, vs >0 and a+# above. +CREATE VIEW rpr_ev_ctx_no_absorb_reluctant_group AS +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+? C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +); +SELECT line FROM unnest(string_to_array(pg_get_viewdef('rpr_ev_ctx_no_absorb_reluctant_group'), E'\n')) AS line WHERE line ~ 'PATTERN'; +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 50) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A+ B)+? C) + DEFINE A AS v % 10 NOT IN (0, 9), B AS v % 10 = 9, C AS v % 10 = 0 +);'); + -- Alternation, non-absorbable branch match survives absorption: A+ B | C -- The dominating A+ run absorbs redundant contexts, but the recorded C matches -- are not absorbable, so they survive (2 matched, not 0)