From 9cde391843d2dd9d73b3c18a42c9557fbf51ffe4 Mon Sep 17 00:00:00 2001 From: jian he Date: Mon, 10 Aug 2026 15:58:20 +0900 Subject: [PATCH] Rewrite RPR pattern list optimizations to compact lists in place mergeConsecutiveVars, mergeConsecutiveGroups, mergeConsecutiveAlts, removeDuplicateAlternatives and mergeGroupPrefixSuffix only ever drop elements. All five now walk the children with a read and a write cursor, storing each survivor at the write cursor and truncating once at the end, rather than appending to a second list. The write cursor never passes the read cursor, so a store cannot overwrite a cell still to be read, and list_truncate() neither moves cells nor reallocates. The orderings the rebuilt lists produced are kept: the GROUP wrapping a run of identical ALTs replaces the run where it stood. The cursors say what the old code needed extra state to say. In mergeGroupPrefixSuffix a prefix copy is one of the survivors already stored, so folding it is a step back of the write cursor rather than a rebuild of the result list, and a suffix copy is still unread, so folding it is a step forward of the read cursor rather than a skipUntil bookkeeping index. Its comparisons no longer manufacture a List per attempt either; rprChildrenMatchAt compares a run of cells against a group's content in place, and rprGroupContent unwraps that content once for both phases. Because the passes still hand the list back, they are marked pg_nodiscard, the way the List API marks lappend and list_truncate. Dropping the result loses a pass silently -- the pattern still compiles and still matches, only less well -- and the compiler now says so. flattenAltChildren can end up longer than what it started with, the way flattenSeqChildren can, so it stays a rebuild -- but only when there is something to splice. It optimizes the children through the cells it has and returns the same list when no child became an ALT, which is the common case. Drop the reluctance tests in the ALT merge. A quantifier only ever attaches to a pattern primary, which the grammar makes a VAR or a GROUP, and the one place that hands the flag down to a child requires that child to be a VAR, so nothing could set the flag they read. The GROUP wrapping a run no longer copies the ALT it wraps either, since the cell it replaces held the only reference to it. Quantifier arithmetic goes through pg_add_s32_overflow for sums and pg_mul_s32_overflow for products. Both operands and the result are the int32 the pattern node stores, so no narrowing cast is left behind and either check can fire: without the product check, ((A{46341,}){46341,}) wraps to a negative minimum that passes the RPR_QUANTITY_INF gate. An overflow declines the rewrite, the same as the gate beside it, rather than raising an error no query can reach. Consecutive same-variable VARs merge only when the following one is greedy: a greedy quantifier followed by a reluctant one settles the first count before the second decides, which leftmost-choice-first makes observable, so the merged form would prefer a different match. mergeGroupPrefixSuffix also stops interleaving its two phases. It now folds every prefix copy in one pass over the children and every suffix copy in a second, rather than doing both for each group as it reaches it. A copy between two GROUPs is a suffix of the one before it and a prefix of the one after, and this order hands it to the second, which is the safer of the two rules: a mandatory copy before a group already sits where the leading iterations it becomes would sit, so folding it as a prefix holds for any content, while folding one as a suffix needs a fixed-length body. One optimization is added rather than moved. Two identical GROUPs can end up next to each other with nothing having put them side by side: the ALT merge wraps a run into a GROUP that may land beside an identical one, and folding a copy away can close the gap between two. mergeConsecutiveGroups therefore gets a second look after mergeGroupPrefixSuffix has run. Once is enough: that pass only drops elements and raises quantifiers, so it creates no copy for the prefix and suffix fold to take in turn. (A B)+ A B (A B)+ A B had been leaving (A B){2,} (A B){2,} behind, and three groups with two copies between them left three pieces where one belongs. This also settles which group claims a copy between two of them: either attribution reaches the same merged quantifier, so splitting the two phases moves nothing that survives to the plan. Only the pattern the planner builds changes; the rows matched and their order do not, since the two forms carry the same iteration totals. The gain is in the NFA: on 2000 rows the three-group shape drops from 11 peak states and 5985 total to 4 and 2996, and the 995 states the runtime had been merging away stop being created. Measured on a 122-shape battery covering every pass -- the overflow boundary on both the sum and the product, reluctant quantifiers on either side, alternations nested three deep, group bodies of variable length, copies shared between two and three groups, and runs that match only in part. Every shape but the five the new pass collects deparses to what the rebuilt lists produced. Those five were checked for match equivalence over every A and B string of length 1 through 12, 90114 rows in all, and the output is identical. rpr_explain gains four cases, and each of them fails without the second GROUP merge. --- src/backend/optimizer/plan/rpr.c | 731 +++++++++++----------- src/test/regress/expected/rpr_base.out | 279 +++++++++ src/test/regress/expected/rpr_explain.out | 103 +++ src/test/regress/sql/rpr_base.sql | 135 ++++ src/test/regress/sql/rpr_explain.sql | 55 ++ 5 files changed, 935 insertions(+), 368 deletions(-) diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c index 8b26bd95ff7..26d0bea6ad7 100644 --- a/src/backend/optimizer/plan/rpr.c +++ b/src/backend/optimizer/plan/rpr.c @@ -37,6 +37,7 @@ #include "postgres.h" +#include "common/int.h" #include "miscadmin.h" #include "optimizer/rpr.h" @@ -46,15 +47,18 @@ 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); -static List *mergeConsecutiveAlts(List *children); -static List *mergeGroupPrefixSuffix(List *children); +static bool rprChildrenMatchAt(List *children, int start, List *content); +static List *rprGroupContent(RPRPatternNode *group); +static bool rprTryAddIteration(RPRPatternNode *group); +static pg_nodiscard List *flattenSeqChildren(List *children); +static pg_nodiscard List *mergeConsecutiveVars(List *children); +static pg_nodiscard List *mergeConsecutiveGroups(List *children); +static pg_nodiscard List *mergeConsecutiveAlts(List *children); +static pg_nodiscard List *mergeGroupPrefixSuffix(List *children); static RPRPatternNode *optimizeSeqPattern(RPRPatternNode *pattern); -static List *flattenAltChildren(List *children); -static List *removeDuplicateAlternatives(List *children); +static pg_nodiscard List *flattenAltChildren(List *children); +static pg_nodiscard List *removeDuplicateAlternatives(List *children); static RPRPatternNode *optimizeAltPattern(RPRPatternNode *pattern); static RPRPatternNode *tryMultiplyQuantifiers(RPRPatternNode *pattern); @@ -233,6 +237,84 @@ rprBodyHasUniformLength(List *children) return rprBodyRowCount(children) >= 0; } +/* + * rprChildrenMatchAt + * Do the cells of children at [start, start + list_length(content)) + * match content element for element? + * + * Returns false when that range does not lie inside children, so a caller + * walking towards either end of the list can just ask. + */ +static bool +rprChildrenMatchAt(List *children, int start, List *content) +{ + int offset = 0; + + if (start < 0 || start + list_length(content) > list_length(children)) + return false; + + foreach_node(RPRPatternNode, want, content) + { + RPRPatternNode *have; + + have = list_nth_node(RPRPatternNode, children, start + offset); + if (!rprPatternEqual(have, want)) + return false; + offset++; + } + + return true; +} + +/* + * rprGroupContent + * The elements a GROUP stands for, as they appear in a sequence. + * + * A GROUP holds a single child, and a multi-element body arrives wrapped in a + * SEQ, so unwrap that to compare against elements of the enclosing sequence: + * (A B)+ holds the sequence A B. + */ +static List * +rprGroupContent(RPRPatternNode *group) +{ + List *content = group->children; + + if (list_length(content) == 1) + { + RPRPatternNode *inner = linitial_node(RPRPatternNode, content); + + if (inner->nodeType == RPR_PATTERN_SEQ) + content = inner->children; + } + + Assert(list_length(content) > 0); + return content; +} + +/* + * rprTryAddIteration + * Raise a GROUP's quantifier by one iteration, if that is representable. + * + * An unbounded max stands for "no limit", not a count, so it is left alone and + * nothing can overflow. A finite bound has to stay below RPR_QUANTITY_INF: + * one landing on the marker would read as unbounded. Returns false without + * touching the node when either bound has no room. + */ +static bool +rprTryAddIteration(RPRPatternNode *group) +{ + if (group->min >= RPR_QUANTITY_INF - 1) + return false; + if (group->max != RPR_QUANTITY_INF && + group->max >= RPR_QUANTITY_INF - 1) + return false; + + group->min += 1; + if (group->max != RPR_QUANTITY_INF) + group->max += 1; + return true; +} + /* * flattenSeqChildren * Recursively optimize children and flatten nested SEQ. @@ -241,7 +323,11 @@ rprBodyHasUniformLength(List *children) * SEQ(A, SEQ(B, C)) -> SEQ(A, B, C) * * Returns a new list with optimized children, with nested SEQ children - * flattened into the parent list. + * flattened into the parent list. The helpers in this file follow two + * conventions -- this one and flattenAltChildren() build a new list, since + * either can end up longer than what it started with, while the rest compact + * the cells they already have -- so a caller must always assign the return + * value. */ static List * flattenSeqChildren(List *children) @@ -285,66 +371,73 @@ flattenSeqChildren(List *children) static List * mergeConsecutiveVars(List *children) { - List *mergedChildren = NIL; - RPRPatternNode *prev = NULL; + int writepos = 0; + int readpos = 0; - foreach_node(RPRPatternNode, child, children) + while (readpos < list_length(children)) { - if (child->nodeType == RPR_PATTERN_VAR && child->reluctant == false) + RPRPatternNode *node = list_nth_node(RPRPatternNode, children, readpos); + int runlen = 1; + + if (node->nodeType == RPR_PATTERN_VAR && !node->reluctant) { - /* ---------------------- - * Can merge consecutive VAR nodes if: - * 1. Same variable name - * 2. No min overflow: prev->min + child->min < INF - * 3. No max overflow: prev->max + child->max < INF (or either is INF) - * - * Strict <: a sum equal to INF would alias the unbounded sentinel - * (min must stay finite; a finite max must not become INF). - */ - if (prev != NULL && - strcmp(prev->varName, child->varName) == 0 && - prev->min < RPR_QUANTITY_INF - child->min && - (prev->max < RPR_QUANTITY_INF - child->max || - prev->max == RPR_QUANTITY_INF || - child->max == RPR_QUANTITY_INF)) + /* Fold the VARs that follow into node while they fit */ + while (readpos + runlen < list_length(children)) { + RPRPatternNode *other; + int newmin; + int newmax; + + other = list_nth_node(RPRPatternNode, children, readpos + runlen); + + if (other->nodeType != RPR_PATTERN_VAR) + break; + /* - * Merge: accumulate min/max into prev. prev is guaranteed to - * be a non-reluctant VAR by the outer condition. + * A greedy quantifier followed by a reluctant one over the + * same variable is not expressible as a single quantifier: + * the pair settles the first quantifier's count before the + * second one decides, which the standard's + * leftmost-choice-first rule (ISO/IEC TR 19075-5 7.2) makes + * observable. Merging them would change the preferred match, + * so stop here. */ - Assert(prev->nodeType == RPR_PATTERN_VAR && prev->reluctant == false); + if (other->reluctant) + break; - prev->min += child->min; + if (strcmp(node->varName, other->varName) != 0) + break; - if (prev->max == RPR_QUANTITY_INF || - child->max == RPR_QUANTITY_INF) - prev->max = RPR_QUANTITY_INF; - else - prev->max += child->max; - } - else - { - /* Flush previous and start new */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); - prev = child; + /* + * RPR_QUANTITY_INF means unbounded, not a count: a finite sum + * landing on it is representable, so reject it separately. + */ + if (node->max == RPR_QUANTITY_INF || + other->max == RPR_QUANTITY_INF) + newmax = RPR_QUANTITY_INF; + else if (pg_add_s32_overflow(node->max, other->max, &newmax) || + newmax >= RPR_QUANTITY_INF) + break; /* fallback: leave the pair unmerged */ + + if (pg_add_s32_overflow(node->min, other->min, &newmin) || + newmin >= RPR_QUANTITY_INF) + break; /* fallback: leave the pair unmerged */ + + node->min = newmin; + node->max = newmax; + runlen++; } } - else - { - /* Non-mergeable - flush previous */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); - mergedChildren = lappend(mergedChildren, child); - prev = NULL; - } - } - /* Flush remaining */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); + /* + * Survivors are compacted towards the front. writepos never passes + * readpos, so this cannot overwrite a cell still to be read. + */ + lfirst(list_nth_cell(children, writepos++)) = node; + readpos += runlen; + } - return mergedChildren; + return list_truncate(children, writepos); } /* @@ -366,67 +459,65 @@ mergeConsecutiveVars(List *children) static List * mergeConsecutiveGroups(List *children) { - List *mergedChildren = NIL; - RPRPatternNode *prev = NULL; + int writepos = 0; + int readpos = 0; - foreach_node(RPRPatternNode, child, children) + while (readpos < list_length(children)) { - if (child->nodeType == RPR_PATTERN_GROUP && child->reluctant == false) + RPRPatternNode *node = list_nth_node(RPRPatternNode, children, readpos); + int runlen = 1; + + if (node->nodeType == RPR_PATTERN_GROUP && !node->reluctant) { - /* ---------------------- - * Can merge consecutive GROUP nodes if: - * 1. Identical children - * 2. No min overflow: prev->min + child->min < INF - * 3. No max overflow: prev->max + child->max < INF (or either is INF) - * - * Strict <: a sum equal to INF would alias the unbounded sentinel - * (min must stay finite; a finite max must not become INF). - */ - 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 || - child->max == RPR_QUANTITY_INF)) + /* Fold the GROUPs that follow into node while they fit */ + while (readpos + runlen < list_length(children)) { - /* - * Merge: accumulate min/max into prev. prev is guaranteed to - * be a non-reluctant GROUP by the outer condition. - */ - Assert(prev->nodeType == RPR_PATTERN_GROUP && prev->reluctant == false); + RPRPatternNode *other; + int newmin; + int newmax; - prev->min += child->min; + other = list_nth_node(RPRPatternNode, children, readpos + runlen); - if (prev->max == RPR_QUANTITY_INF || - child->max == RPR_QUANTITY_INF) - prev->max = RPR_QUANTITY_INF; - else - prev->max += child->max; - } - else - { - /* Flush previous and start new */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); - prev = child; + if (other->nodeType != RPR_PATTERN_GROUP || other->reluctant) + break; + + if (!rprPatternChildrenEqual(node->children, other->children)) + break; + + /* The body must consume a fixed number of rows; see above */ + if (!rprBodyHasUniformLength(node->children)) + break; + + /* + * RPR_QUANTITY_INF means unbounded, not a count: a finite sum + * landing on it is representable, so reject it separately. + */ + if (node->max == RPR_QUANTITY_INF || + other->max == RPR_QUANTITY_INF) + newmax = RPR_QUANTITY_INF; + else if (pg_add_s32_overflow(node->max, other->max, &newmax) || + newmax >= RPR_QUANTITY_INF) + break; /* fallback: leave the pair unmerged */ + + if (pg_add_s32_overflow(node->min, other->min, &newmin) || + newmin >= RPR_QUANTITY_INF) + break; /* fallback: leave the pair unmerged */ + + node->min = newmin; + node->max = newmax; + runlen++; } } - else - { - /* Non-mergeable - flush previous */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); - mergedChildren = lappend(mergedChildren, child); - prev = NULL; - } - } - /* Flush remaining */ - if (prev != NULL) - mergedChildren = lappend(mergedChildren, prev); + /* + * Survivors are compacted towards the front. writepos never passes + * readpos, so this cannot overwrite a cell still to be read. + */ + lfirst(list_nth_cell(children, writepos++)) = node; + readpos += runlen; + } - return mergedChildren; + return list_truncate(children, writepos); } /* @@ -443,91 +534,54 @@ mergeConsecutiveGroups(List *children) static List * mergeConsecutiveAlts(List *children) { - List *mergedChildren = NIL; - RPRPatternNode *prev = NULL; - int count = 0; + int writepos = 0; + int readpos = 0; - foreach_node(RPRPatternNode, child, children) + while (readpos < list_length(children)) { - if (child->nodeType == RPR_PATTERN_ALT && child->reluctant == false) + RPRPatternNode *node = list_nth_node(RPRPatternNode, children, readpos); + int count = 1; + + /* A quantifier never lands on an ALT, so none of these is reluctant */ + if (node->nodeType == RPR_PATTERN_ALT) { - if (prev != NULL && - rprPatternChildrenEqual(prev->children, child->children)) + /* Count the run of ALTs identical to this one */ + while (readpos + count < list_length(children)) { - /* Same ALT as prev - accumulate */ + RPRPatternNode *other; + + other = list_nth_node(RPRPatternNode, children, readpos + count); + + if (!rprPatternEqual(node, other)) + break; + count++; } - else - { - /* Different ALT or first ALT - flush previous */ - if (prev != NULL) - { - if (count > 1) - { - /* Wrap in GROUP{count,count}(ALT) */ - RPRPatternNode *group = makeNode(RPRPatternNode); - - group->nodeType = RPR_PATTERN_GROUP; - group->min = count; - group->max = count; - group->reluctant = false; - group->location = -1; - group->children = list_make1(prev); - mergedChildren = lappend(mergedChildren, group); - } - else - mergedChildren = lappend(mergedChildren, prev); - } - prev = child; - count = 1; - } - } - else - { - /* Non-ALT - flush previous */ - if (prev != NULL) + + if (count > 1) { - if (count > 1) - { - RPRPatternNode *group = makeNode(RPRPatternNode); - - group->nodeType = RPR_PATTERN_GROUP; - group->min = count; - group->max = count; - group->reluctant = false; - group->location = -1; - group->children = list_make1(prev); - mergedChildren = lappend(mergedChildren, group); - } - else - mergedChildren = lappend(mergedChildren, prev); + /* Wrap the run into GROUP{count,count}(ALT) */ + RPRPatternNode *group = makeNode(RPRPatternNode); + + group->nodeType = RPR_PATTERN_GROUP; + group->min = count; + group->max = count; + group->reluctant = false; + group->location = -1; + group->children = list_make1(node); + node = group; } - mergedChildren = lappend(mergedChildren, child); - prev = NULL; - count = 0; } - } - /* Flush remaining */ - if (prev != NULL) - { - if (count > 1) - { - RPRPatternNode *group = makeNode(RPRPatternNode); - - group->nodeType = RPR_PATTERN_GROUP; - group->min = count; - group->max = count; - group->reluctant = false; - group->location = -1; - group->children = list_make1(prev); - mergedChildren = lappend(mergedChildren, group); - } - else - mergedChildren = lappend(mergedChildren, prev); + /* + * Survivors are compacted towards the front. writepos never passes + * readpos, so this cannot overwrite a cell still to be read. + */ + lfirst(list_nth_cell(children, writepos++)) = node; + readpos += count; } - return mergedChildren; + return list_truncate(children, writepos); } /* @@ -540,12 +594,12 @@ mergeConsecutiveAlts(List *children) * * Algorithm: * For each GROUP encountered in the sequence: - * 1. PREFIX phase: compare the last N elements already in the result - * list against the GROUP's children. On match, remove them from - * result and increment the GROUP's min/max. Repeat until no match. - * 2. SUFFIX phase: compare the next N elements in the input against - * the GROUP's children. On match, skip them (via skipUntil) and - * increment min/max. Repeat until no match. + * 1. PREFIX phase: compare the last N survivors kept so far against the + * GROUP's children. On match, drop them and increment the GROUP's + * min/max. Repeat until no match. + * 2. SUFFIX phase: compare the next N elements not yet read against the + * GROUP's children. On match, skip them and increment min/max. + * Repeat until no match. * * Examples: * A B (A B)+ -> (A B){2,} @@ -563,189 +617,121 @@ mergeConsecutiveAlts(List *children) static List * mergeGroupPrefixSuffix(List *children) { - List *result = NIL; - int numChildren = list_length(children); - int i; - int skipUntil = -1; /* skip suffix elements already merged */ + int numChildren; + int writepos; + int readpos; - for (i = 0; i < numChildren; i++) - { - RPRPatternNode *child = (RPRPatternNode *) list_nth(children, i); + /* + * PREFIX phase. Every copy that sits immediately before a GROUP is + * folded into it, over the whole sequence, before any suffix is + * considered. A copy between two GROUPs is a suffix of the one before it + * and a prefix of the one after, and this order hands it to the second, + * which is the safer of the two rules: a mandatory copy before a group + * already sits where the leading iterations it becomes would sit, so + * folding it as a prefix holds for any content, while folding one as a + * suffix needs a fixed-length body. + * + * A prefix copy is one of the survivors already stored, so folding it is + * a step back of the write cursor. + */ + writepos = 0; + numChildren = list_length(children); - /* - * The suffix merge logic below adjusts i to skip merged elements, - * ensuring we never revisit them. Verify this invariant. - */ - Assert(i >= skipUntil); + for (readpos = 0; readpos < numChildren; readpos++) + { + RPRPatternNode *child = list_nth_node(RPRPatternNode, children, readpos); - /* - * If this is a GROUP, see if preceding/following elements match its - * children. GROUP's content may be wrapped in a SEQ - unwrap for - * comparison. - */ - if (child->nodeType == RPR_PATTERN_GROUP && child->reluctant == false) + if (child->nodeType == RPR_PATTERN_GROUP && !child->reluctant) { - List *groupContent = child->children; - int groupChildCount; - int prefixLen = list_length(result); - List *trimmed; + List *content = rprGroupContent(child); + int content_len = list_length(content); - /* - * If GROUP has single SEQ child, compare with SEQ's children. - * e.g., (A B)+ internally contains sequence A B; compare against - * that. - */ - if (list_length(groupContent) == 1) - { - RPRPatternNode *inner = (RPRPatternNode *) linitial(groupContent); + while (rprChildrenMatchAt(children, writepos - content_len, content) && + rprTryAddIteration(child)) + writepos -= content_len; + } - if (inner->nodeType == RPR_PATTERN_SEQ) - groupContent = inner->children; - } + /* + * Survivors are compacted towards the front. writepos never passes + * readpos, so this cannot overwrite a cell still to be read. + */ + lfirst(list_nth_cell(children, writepos++)) = child; + } - groupChildCount = list_length(groupContent); + children = list_truncate(children, writepos); - /* - * PREFIX MERGE: Check if preceding elements match. Keep merging - * as long as we have matching prefixes. - */ - while (prefixLen >= groupChildCount && groupChildCount > 0) - { - List *prefixElements = NIL; - int j; - - /* Extract last groupChildCount elements from prefix */ - for (j = prefixLen - groupChildCount; j < prefixLen; j++) - { - prefixElements = lappend(prefixElements, - list_nth(result, j)); - } - - /* Compare with GROUP's (possibly unwrapped) children */ - if (rprPatternChildrenEqual(prefixElements, groupContent) && - child->min < RPR_QUANTITY_INF - 1 && - (child->max == RPR_QUANTITY_INF || - child->max < RPR_QUANTITY_INF - 1)) - { - /* - * Match! Merge by incrementing GROUP's quantifier. Remove - * the prefix elements from output. - */ - child->min += 1; - if (child->max != RPR_QUANTITY_INF) - child->max += 1; - - /* Rebuild result without matched prefix */ - trimmed = NIL; - for (j = 0; j < prefixLen - groupChildCount; j++) - { - trimmed = lappend(trimmed, - list_nth(result, j)); - } - result = trimmed; - prefixLen = list_length(result); - } - else - { - list_free(prefixElements); - break; - } + /* + * SUFFIX phase. 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, so the body must consume a fixed number of rows; see + * above. + * + * Such a copy is still unread, so folding it is a step forward of the + * read cursor. + */ + writepos = 0; + readpos = 0; + numChildren = list_length(children); - list_free(prefixElements); - } + while (readpos < numChildren) + { + RPRPatternNode *child = list_nth_node(RPRPatternNode, children, readpos); + int runlen = 1; - /* - * SUFFIX MERGE: Check if following elements match. Keep merging - * as long as we have matching suffixes. - */ - while (i + groupChildCount < numChildren && groupChildCount > 0) - { - List *suffixElements = NIL; - int j; - int suffixStart = i + 1; - - /* suffixStart always >= skipUntil after i adjustment */ - Assert(skipUntil <= suffixStart); - - /* Extract next groupChildCount elements as suffix */ - for (j = 0; j < groupChildCount; j++) - { - int idx = suffixStart + j; - - /* while condition guarantees idx < numChildren */ - Assert(idx < numChildren); - suffixElements = lappend(suffixElements, - list_nth(children, idx)); - } - - /* 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)) - { - /* - * Match! Merge suffix by incrementing quantifier and - * skipping. - */ - child->min += 1; - if (child->max != RPR_QUANTITY_INF) - child->max += 1; - skipUntil = suffixStart + groupChildCount; - - /* - * Update i to continue suffix check after merged elements - */ - i = skipUntil - 1; - } - else - { - list_free(suffixElements); - break; - } + if (child->nodeType == RPR_PATTERN_GROUP && !child->reluctant) + { + List *content = rprGroupContent(child); + int content_len = list_length(content); - list_free(suffixElements); - } + while (rprBodyHasUniformLength(content) && + rprChildrenMatchAt(children, readpos + runlen, content) && + rprTryAddIteration(child)) + runlen += content_len; } - result = lappend(result, child); + lfirst(list_nth_cell(children, writepos++)) = child; + readpos += runlen; } - return result; + return list_truncate(children, writepos); } /* * optimizeSeqPattern * Optimize SEQ pattern node. * - * Optimizations: - * 1. Flatten nested SEQ and GROUP{1,1} + * Optimizations, in the order they run: + * 1. Recursively optimize the children and flatten nested SEQ * 2. Merge consecutive identical VAR nodes * 3. Merge consecutive identical GROUP nodes * 4. Merge consecutive identical ALT nodes into GROUP * 5. Merge prefix/suffix into GROUP with matching children - * 6. Unwrap single-item SEQ + * 6. Merge consecutive identical GROUP nodes once more + * 7. Unwrap single-item SEQ + * + * That order carries meaning: 1 is what optimizes the children, so every pass + * after it sees a flat list of finished nodes, and 6 runs for the reason + * given there. */ static RPRPatternNode * optimizeSeqPattern(RPRPatternNode *pattern) { - /* Recursively optimize children and flatten nested SEQ/GROUP{1,1} */ pattern->children = flattenSeqChildren(pattern->children); - - /* Merge consecutive identical VAR nodes */ pattern->children = mergeConsecutiveVars(pattern->children); - - /* Merge consecutive identical GROUP nodes */ pattern->children = mergeConsecutiveGroups(pattern->children); - - /* Merge consecutive identical ALT nodes into GROUP */ pattern->children = mergeConsecutiveAlts(pattern->children); - - /* Merge prefix/suffix into GROUP with matching children */ pattern->children = mergeGroupPrefixSuffix(pattern->children); + /* + * Two identical GROUPs can end up next to each other with nothing having + * put them side by side: the ALT merge wraps a run into a GROUP that may + * land beside an identical one, and folding a prefix or a suffix away can + * close the gap between two. So the GROUP merge gets a second look. One + * is enough: it only drops elements and raises quantifiers, so it creates + * no copy for the prefix/suffix pass to fold in turn. + */ + pattern->children = mergeConsecutiveGroups(pattern->children); + /* Unwrap single-item SEQ: SEQ[A] -> A */ if (list_length(pattern->children) == 1) return (RPRPatternNode *) linitial(pattern->children); @@ -760,25 +746,28 @@ optimizeSeqPattern(RPRPatternNode *pattern) * Example: * (A | (B | C)) -> (A | B | C) * - * Returns a new list with optimized children, with nested ALT children - * flattened into the parent list. + * Splices each nested ALT's children into the parent list at the position the + * ALT occupied, so the flattened alternatives keep their place. Like + * flattenSeqChildren(), this pass can end up longer than what it started + * with, so it builds a new list rather than compacting the cells it has; the + * caller must assign the result. */ static List * flattenAltChildren(List *children) { - List *newChildren = NIL; + List *flattened = NIL; foreach_node(RPRPatternNode, child, children) { - RPRPatternNode *opt = optimizeRPRPattern(child); + RPRPatternNode *optimized = optimizeRPRPattern(child); - if (opt->nodeType == RPR_PATTERN_ALT) - newChildren = list_concat(newChildren, list_copy(opt->children)); + if (optimized->nodeType == RPR_PATTERN_ALT) + flattened = list_concat(flattened, optimized->children); else - newChildren = lappend(newChildren, opt); + flattened = lappend(flattened, optimized); } - return newChildren; + return flattened; } /* @@ -794,15 +783,22 @@ flattenAltChildren(List *children) static List * removeDuplicateAlternatives(List *children) { - List *uniqueChildren = NIL; + int writepos = 0; - foreach_node(RPRPatternNode, child, children) + for (int readpos = 0; readpos < list_length(children); readpos++) { + RPRPatternNode *node = list_nth_node(RPRPatternNode, children, readpos); bool isDuplicate = false; - foreach_node(RPRPatternNode, uchild, uniqueChildren) + /* + * Survivors are compacted towards the front, so those already kept + * are the cells below writepos. writepos never passes readpos, so + * the store below cannot overwrite a cell still to be read. + */ + for (int keptpos = 0; keptpos < writepos; keptpos++) { - if (rprPatternEqual(uchild, child)) + if (rprPatternEqual(list_nth_node(RPRPatternNode, children, keptpos), + node)) { isDuplicate = true; break; @@ -810,10 +806,10 @@ removeDuplicateAlternatives(List *children) } if (!isDuplicate) - uniqueChildren = lappend(uniqueChildren, child); + lfirst(list_nth_cell(children, writepos++)) = node; } - return uniqueChildren; + return list_truncate(children, writepos); } /* @@ -874,8 +870,8 @@ tryMultiplyQuantifiers(RPRPatternNode *pattern) { RPRPatternNode *child; bool safe; - int64 new_min_64; - int64 new_max_64; + int32 newmin; + int32 newmax; /* Parser always creates GROUP with exactly one child */ Assert(list_length(pattern->children) == 1); @@ -954,22 +950,23 @@ tryMultiplyQuantifiers(RPRPatternNode *pattern) if (!safe) return pattern; - /* Flatten the child quantifier, guarding against overflow. */ - new_min_64 = (int64) pattern->min * child->min; - if (new_min_64 >= RPR_QUANTITY_INF) - return pattern; /* overflow, skip optimization */ + /* Flatten the child quantifier, declining the rewrite if it does not fit */ + if (pg_mul_s32_overflow(pattern->min, child->min, &newmin) || + newmin >= RPR_QUANTITY_INF) + return pattern; + /* + * RPR_QUANTITY_INF means unbounded, not a count: a finite product landing + * on it is representable, so reject it separately. + */ if (pattern->max == RPR_QUANTITY_INF || child->max == RPR_QUANTITY_INF) - new_max_64 = RPR_QUANTITY_INF; - else - { - new_max_64 = (int64) pattern->max * child->max; - if (new_max_64 >= RPR_QUANTITY_INF) - return pattern; - } + newmax = RPR_QUANTITY_INF; + else if (pg_mul_s32_overflow(pattern->max, child->max, &newmax) || + newmax >= RPR_QUANTITY_INF) + return pattern; - child->min = (int) new_min_64; - child->max = (int) new_max_64; + child->min = newmin; + child->max = newmax; return child; } @@ -1031,16 +1028,14 @@ tryUnwrapGroup(RPRPatternNode *pattern) static RPRPatternNode * optimizeGroupPattern(RPRPatternNode *pattern) { - List *newChildren; + ListCell *lc; RPRPatternNode *result; /* Recursively optimize children */ - newChildren = NIL; - foreach_node(RPRPatternNode, child, pattern->children) + foreach(lc, pattern->children) { - newChildren = lappend(newChildren, optimizeRPRPattern(child)); + lfirst(lc) = optimizeRPRPattern((RPRPatternNode *) lfirst(lc)); } - pattern->children = newChildren; /* Try quantifier multiplication */ result = tryMultiplyQuantifiers(pattern); diff --git a/src/test/regress/expected/rpr_base.out b/src/test/regress/expected/rpr_base.out index 2bc272298d0..dce0e9447e2 100644 --- a/src/test/regress/expected/rpr_base.out +++ b/src/test/regress/expected/rpr_base.out @@ -1231,6 +1231,38 @@ DROP TABLE rpr_quant; -- Reluctant quantifiers CREATE TABLE rpr_reluctant (id INT, val INT); INSERT INTO rpr_reluctant VALUES (1, 10), (2, 20), (3, 30); +-- A greedy quantifier followed by a reluctant one over the same variable must +-- not be merged: the merged spellings A{2,3} and A{1,4} match all three rows +-- where these stop at two, so merging would change the preferred match. +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A{2} A??) DEFINE A AS TRUE); + id | count +----+------- + 1 | 2 + 2 | 0 + 3 | 0 +(3 rows) + +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A{1,2} A{0,2}?) DEFINE A AS TRUE); + id | count +----+------- + 1 | 2 + 2 | 0 + 3 | 1 +(3 rows) + +-- cascade: the reluctant middle VAR must stop the merge on both sides, where +-- the merged A{1,3} would match all three rows +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A? A?? A) DEFINE A AS TRUE); + id | count +----+------- + 1 | 2 + 2 | 0 + 3 | 1 +(3 rows) + -- *? (zero or more, reluctant) -- Reluctant quantifier: prefer shortest match SELECT COUNT(*) OVER w @@ -6979,6 +7011,103 @@ WINDOW w AS ( (6 rows) -- Expected: Fallback - VARs not merged (min sum 2147483647 == INF) +-- Test: one more than that sum does not fit in int32. The fallback looks the +-- same as the case above; this one reaches the overflow check instead of the +-- >= INF comparison. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1073741825,} A{1073741823,}) + DEFINE A AS val > 0 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a{1073741825,}" a{1073741823,} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: VAR merge falls back when the max sum lands exactly on INF. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741823} A{1,1073741824}) + DEFINE A AS val > 0 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a{1,1073741823} a{1,1073741824} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: one below that sum is the largest max the merge may keep. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741822} A{1,1073741824}) + DEFINE A AS val > 0 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a{2,2147483646} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: one above that does not fit in int32; the overflow check rejects it. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741824} A{1,1073741824}) + DEFINE A AS val > 0 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a{1,1073741824} a{1,1073741824} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: an operand that is already unbounded still merges. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741823} A{1,}) + DEFINE A AS val > 0 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a{2,}" + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + -- Test: consecutive GROUP merge whose min sum is exactly INF causes fallback. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_fallback @@ -6999,6 +7128,156 @@ WINDOW w AS ( (6 rows) -- Expected: Fallback - GROUPs not merged (min sum 2147483647 == INF) +-- Test: consecutive GROUP merge whose max sum is exactly INF causes fallback, +-- where one less merges. Without the guard the merged max would alias INF and +-- a bounded pattern would become unbounded. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){1,1073741823} (A B){1,1073741824}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a b){1,1073741823} (a b){1,1073741824} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){1,1073741822} (A B){1,1073741824}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a b){2,2147483646} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: the prefix merge adds one iteration, so it declines a min already at +-- INF - 1 and a max already at INF - 1; one less than either merges. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){2147483646,}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a b (a b){2147483646,} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){2147483645,}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){2147483646,}" + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){1,2147483646}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: a b (a b){1,2147483646} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){1,2147483645}) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a b){2,2147483646} + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +-- Test: the suffix merge has the same boundary as the prefix merge. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){2147483646,} A B) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){2147483646,}" a b + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){2147483645,} A B) + DEFINE A AS val > 0, B AS val > 5 +); + QUERY PLAN +------------------------------------------------------------------------------- + WindowAgg + Window: w AS (ORDER BY id ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){2147483646,}" + -> Sort + Sort Key: id + -> Seq Scan on rpr_fallback +(6 rows) + DROP TABLE rpr_fallback; -- ============================================================ -- Planner Integration Tests diff --git a/src/test/regress/expected/rpr_explain.out b/src/test/regress/expected/rpr_explain.out index 3d03351daa0..60b121aa245 100644 --- a/src/test/regress/expected/rpr_explain.out +++ b/src/test/regress/expected/rpr_explain.out @@ -690,6 +690,109 @@ WINDOW w AS ( -> Function Scan on generate_series s (actual rows=40.00 loops=1) (9 rows) +-- Folding a copy that sits between two GROUPs leaves those GROUPs +-- adjacent, which nothing had put side by side before, so the GROUP +-- merge runs once more to collect them. The copy reaches the fold as +-- a suffix of the GROUP before it. +-- (A B)+ A B (A B)+ A B -> (A B){4,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)+ A B (A B)+ A B) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=40.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){4,}" + Storage: Memory Maximum Storage: NkB + NFA States: 4 peak, 58 total, 0 merged + NFA Contexts: 3 peak, 41 total, 3 pruned + NFA: 1 matched (len 40/40/40.0), 0 mismatched + NFA: 19 absorbed (len 2/2/2.0), 17 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=40.00 loops=1) +(9 rows) + +-- A leading copy reaches the fold as a prefix instead +-- A B (A B)+ A B (A B)+ -> (A B){4,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A B (A B)+ A B (A B)+) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=40.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){4,}" + Storage: Memory Maximum Storage: NkB + NFA States: 4 peak, 58 total, 0 merged + NFA Contexts: 3 peak, 41 total, 3 pruned + NFA: 1 matched (len 40/40/40.0), 0 mismatched + NFA: 19 absorbed (len 2/2/2.0), 17 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=40.00 loops=1) +(9 rows) + +-- The same with bounded quantifiers +-- (A B){2} A B (A B){2} -> (A B){5} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B){2} A B (A B){2}) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=40.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a b){5} + Storage: Memory Maximum Storage: NkB + NFA States: 6 peak, 41 total, 0 merged + NFA Contexts: 6 peak, 41 total, 16 pruned + NFA: 4 matched (len 10/10/10.0), 0 mismatched + NFA: 0 absorbed, 20 skipped (len 1/8/4.2) + -> Function Scan on generate_series s (actual rows=40.00 loops=1) +(9 rows) + +-- Three GROUPs and two copies between them +-- (A B)+ A B (A B)+ A B (A B)+ -> (A B){5,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)+ A B (A B)+ A B (A B)+) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + rpr_explain_filter +---------------------------------------------------------------------- + WindowAgg (actual rows=40.00 loops=1) + Window: w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING) + Pattern: (a' b'){5,}" + Storage: Memory Maximum Storage: NkB + NFA States: 4 peak, 57 total, 0 merged + NFA Contexts: 3 peak, 41 total, 4 pruned + NFA: 1 matched (len 40/40/40.0), 0 mismatched + NFA: 19 absorbed (len 2/2/2.0), 16 skipped (len 1/1/1.0) + -> Function Scan on generate_series s (actual rows=40.00 loops=1) +(9 rows) + -- High state count - alternation with plus quantifier CREATE VIEW rpr_ev_state_alt_plus AS SELECT count(*) OVER w diff --git a/src/test/regress/sql/rpr_base.sql b/src/test/regress/sql/rpr_base.sql index 5a90ab38d4f..49a9e41f117 100644 --- a/src/test/regress/sql/rpr_base.sql +++ b/src/test/regress/sql/rpr_base.sql @@ -885,6 +885,20 @@ DROP TABLE rpr_quant; CREATE TABLE rpr_reluctant (id INT, val INT); INSERT INTO rpr_reluctant VALUES (1, 10), (2, 20), (3, 30); +-- A greedy quantifier followed by a reluctant one over the same variable must +-- not be merged: the merged spellings A{2,3} and A{1,4} match all three rows +-- where these stop at two, so merging would change the preferred match. +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A{2} A??) DEFINE A AS TRUE); + +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A{1,2} A{0,2}?) DEFINE A AS TRUE); + +-- cascade: the reluctant middle VAR must stop the merge on both sides, where +-- the merged A{1,3} would match all three rows +SELECT id, count(*) OVER w FROM rpr_reluctant +WINDOW w AS (ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING PATTERN (A? A?? A) DEFINE A AS TRUE); + -- *? (zero or more, reluctant) -- Reluctant quantifier: prefer shortest match SELECT COUNT(*) OVER w @@ -4165,6 +4179,54 @@ WINDOW w AS ( ); -- Expected: Fallback - VARs not merged (min sum 2147483647 == INF) +-- Test: one more than that sum does not fit in int32. The fallback looks the +-- same as the case above; this one reaches the overflow check instead of the +-- >= INF comparison. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1073741825,} A{1073741823,}) + DEFINE A AS val > 0 +); + +-- Test: VAR merge falls back when the max sum lands exactly on INF. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741823} A{1,1073741824}) + DEFINE A AS val > 0 +); +-- Test: one below that sum is the largest max the merge may keep. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741822} A{1,1073741824}) + DEFINE A AS val > 0 +); +-- Test: one above that does not fit in int32; the overflow check rejects it. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741824} A{1,1073741824}) + DEFINE A AS val > 0 +); +-- Test: an operand that is already unbounded still merges. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A{1,1073741823} A{1,}) + DEFINE A AS val > 0 +); -- Test: consecutive GROUP merge whose min sum is exactly INF causes fallback. EXPLAIN (COSTS OFF) SELECT COUNT(*) OVER w FROM rpr_fallback @@ -4176,6 +4238,79 @@ WINDOW w AS ( ); -- Expected: Fallback - GROUPs not merged (min sum 2147483647 == INF) +-- Test: consecutive GROUP merge whose max sum is exactly INF causes fallback, +-- where one less merges. Without the guard the merged max would alias INF and +-- a bounded pattern would become unbounded. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){1,1073741823} (A B){1,1073741824}) + DEFINE A AS val > 0, B AS val > 5 +); +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){1,1073741822} (A B){1,1073741824}) + DEFINE A AS val > 0, B AS val > 5 +); + +-- Test: the prefix merge adds one iteration, so it declines a min already at +-- INF - 1 and a max already at INF - 1; one less than either merges. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){2147483646,}) + DEFINE A AS val > 0, B AS val > 5 +); +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){2147483645,}) + DEFINE A AS val > 0, B AS val > 5 +); +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){1,2147483646}) + DEFINE A AS val > 0, B AS val > 5 +); +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN (A B (A B){1,2147483645}) + DEFINE A AS val > 0, B AS val > 5 +); + +-- Test: the suffix merge has the same boundary as the prefix merge. +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){2147483646,} A B) + DEFINE A AS val > 0, B AS val > 5 +); +EXPLAIN (COSTS OFF) +SELECT COUNT(*) OVER w FROM rpr_fallback +WINDOW w AS ( + ORDER BY id + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + PATTERN ((A B){2147483645,} A B) + DEFINE A AS val > 0, B AS val > 5 +); + DROP TABLE rpr_fallback; -- ============================================================ diff --git a/src/test/regress/sql/rpr_explain.sql b/src/test/regress/sql/rpr_explain.sql index b4712029a88..da11881e06c 100644 --- a/src/test/regress/sql/rpr_explain.sql +++ b/src/test/regress/sql/rpr_explain.sql @@ -456,6 +456,61 @@ WINDOW w AS ( DEFINE A AS v % 2 = 0, B AS v % 2 = 1 );'); +-- Folding a copy that sits between two GROUPs leaves those GROUPs +-- adjacent, which nothing had put side by side before, so the GROUP +-- merge runs once more to collect them. The copy reaches the fold as +-- a suffix of the GROUP before it. +-- (A B)+ A B (A B)+ A B -> (A B){4,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)+ A B (A B)+ A B) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + +-- A leading copy reaches the fold as a prefix instead +-- A B (A B)+ A B (A B)+ -> (A B){4,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN (A B (A B)+ A B (A B)+) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + +-- The same with bounded quantifiers +-- (A B){2} A B (A B){2} -> (A B){5} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B){2} A B (A B){2}) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + +-- Three GROUPs and two copies between them +-- (A B)+ A B (A B)+ A B (A B)+ -> (A B){5,} +SELECT rpr_explain_filter(' +EXPLAIN (ANALYZE, BUFFERS OFF, COSTS OFF, TIMING OFF, SUMMARY OFF) +SELECT count(*) OVER w +FROM generate_series(1, 40) AS s(v) +WINDOW w AS ( + ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + AFTER MATCH SKIP PAST LAST ROW + PATTERN ((A B)+ A B (A B)+ A B (A B)+) + DEFINE A AS v % 2 = 1, B AS v % 2 = 0 +);'); + -- High state count - alternation with plus quantifier CREATE VIEW rpr_ev_state_alt_plus AS SELECT count(*) OVER w