From ae2ca7bf67c4ca35ae95227c571d551cbf88b823 Mon Sep 17 00:00:00 2001 From: Tatsuo Ishii Date: Sun, 18 Jan 2026 21:01:37 +0900 Subject: [PATCH v40 4/8] Row pattern recognition patch (planner). --- src/backend/optimizer/plan/Makefile | 1 + src/backend/optimizer/plan/createplan.c | 62 +- src/backend/optimizer/plan/meson.build | 1 + src/backend/optimizer/plan/planner.c | 3 + src/backend/optimizer/plan/rpr.c | 1346 +++++++++++++++++++++ src/backend/optimizer/plan/setrefs.c | 27 +- src/backend/optimizer/prep/prepjointree.c | 9 + src/include/nodes/plannodes.h | 73 ++ src/include/optimizer/rpr.h | 47 + 9 files changed, 1551 insertions(+), 18 deletions(-) create mode 100644 src/backend/optimizer/plan/rpr.c create mode 100644 src/include/optimizer/rpr.h diff --git a/src/backend/optimizer/plan/Makefile b/src/backend/optimizer/plan/Makefile index 80ef162e484..7e0167789d8 100644 --- a/src/backend/optimizer/plan/Makefile +++ b/src/backend/optimizer/plan/Makefile @@ -19,6 +19,7 @@ OBJS = \ planagg.o \ planmain.o \ planner.o \ + rpr.o \ setrefs.o \ subselect.o diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index eb4806b084a..99180ba339e 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -35,6 +35,7 @@ #include "optimizer/prep.h" #include "optimizer/restrictinfo.h" #include "optimizer/subselect.h" +#include "optimizer/rpr.h" #include "optimizer/tlist.h" #include "parser/parse_clause.h" #include "parser/parsetree.h" @@ -287,7 +288,10 @@ static Memoize *make_memoize(Plan *lefttree, Oid *hashoperators, static WindowAgg *make_windowagg(List *tlist, WindowClause *wc, int partNumCols, AttrNumber *partColIdx, Oid *partOperators, Oid *partCollations, int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations, - List *runCondition, List *qual, bool topWindow, + List *runCondition, RPSkipTo rpSkipTo, + RPRPattern *compiledPattern, + List *defineClause, + List *qual, bool topWindow, Plan *lefttree); static Group *make_group(List *tlist, List *qual, int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations, @@ -2528,21 +2532,36 @@ create_windowagg_plan(PlannerInfo *root, WindowAggPath *best_path) ordNumCols++; } - /* And finally we can make the WindowAgg node */ - plan = make_windowagg(tlist, - wc, - partNumCols, - partColIdx, - partOperators, - partCollations, - ordNumCols, - ordColIdx, - ordOperators, - ordCollations, - best_path->runCondition, - best_path->qual, - best_path->topwindow, - subplan); + /* Build defineVariableList from defineClause for pattern compilation */ + { + List *defineVariableList = NIL; + + foreach(lc, wc->defineClause) + { + TargetEntry *te = (TargetEntry *) lfirst(lc); + defineVariableList = lappend(defineVariableList, + makeString(pstrdup(te->resname))); + } + + /* And finally we can make the WindowAgg node */ + plan = make_windowagg(tlist, + wc, + partNumCols, + partColIdx, + partOperators, + partCollations, + ordNumCols, + ordColIdx, + ordOperators, + ordCollations, + best_path->runCondition, + wc->rpSkipTo, + buildRPRPattern(wc->rpPattern, defineVariableList), + wc->defineClause, + best_path->qual, + best_path->topwindow, + subplan); + } copy_generic_path_info(&plan->plan, (Path *) best_path); @@ -6608,7 +6627,10 @@ static WindowAgg * make_windowagg(List *tlist, WindowClause *wc, int partNumCols, AttrNumber *partColIdx, Oid *partOperators, Oid *partCollations, int ordNumCols, AttrNumber *ordColIdx, Oid *ordOperators, Oid *ordCollations, - List *runCondition, List *qual, bool topWindow, Plan *lefttree) + List *runCondition, RPSkipTo rpSkipTo, + RPRPattern *compiledPattern, + List *defineClause, + List *qual, bool topWindow, Plan *lefttree) { WindowAgg *node = makeNode(WindowAgg); Plan *plan = &node->plan; @@ -6635,6 +6657,12 @@ make_windowagg(List *tlist, WindowClause *wc, node->inRangeAsc = wc->inRangeAsc; node->inRangeNullsFirst = wc->inRangeNullsFirst; node->topWindow = topWindow; + node->rpSkipTo = rpSkipTo; + + /* Store compiled pattern for NFA execution */ + node->rpPattern = compiledPattern; + + node->defineClause = defineClause; plan->targetlist = tlist; plan->lefttree = lefttree; diff --git a/src/backend/optimizer/plan/meson.build b/src/backend/optimizer/plan/meson.build index c565b2adbcc..5b2381cd774 100644 --- a/src/backend/optimizer/plan/meson.build +++ b/src/backend/optimizer/plan/meson.build @@ -7,6 +7,7 @@ backend_sources += files( 'planagg.c', 'planmain.c', 'planner.c', + 'rpr.c', 'setrefs.c', 'subselect.c', ) diff --git a/src/backend/optimizer/plan/planner.c b/src/backend/optimizer/plan/planner.c index 7a6b8b749f2..2a93feee25b 100644 --- a/src/backend/optimizer/plan/planner.c +++ b/src/backend/optimizer/plan/planner.c @@ -964,6 +964,9 @@ subquery_planner(PlannerGlobal *glob, Query *parse, char *plan_name, EXPRKIND_LIMIT); wc->endOffset = preprocess_expression(root, wc->endOffset, EXPRKIND_LIMIT); + wc->defineClause = (List *) preprocess_expression(root, + (Node *) wc->defineClause, + EXPRKIND_TARGET); } parse->limitOffset = preprocess_expression(root, parse->limitOffset, diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c new file mode 100644 index 00000000000..9b847c5e8b1 --- /dev/null +++ b/src/backend/optimizer/plan/rpr.c @@ -0,0 +1,1346 @@ +/*------------------------------------------------------------------------- + * + * rpr.c + * Row Pattern Recognition pattern compilation for planner + * + * This file contains functions for optimizing RPR pattern AST and + * compiling it to bytecode for execution by WindowAgg. + * + * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * + * IDENTIFICATION + * src/backend/optimizer/plan/rpr.c + * + *------------------------------------------------------------------------- + */ + +#include "postgres.h" + +#include "nodes/makefuncs.h" +#include "optimizer/rpr.h" + +/* Forward declarations - pattern comparison */ +static bool rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b); +static bool rprPatternChildrenEqual(List *a, List *b); + +/* Forward declarations - pattern optimization (shared) */ +static RPRPatternNode *tryUnwrapSingleChild(RPRPatternNode *pattern); + +/* Forward declarations - SEQ optimization */ +static List *flattenSeqChildren(List *children); +static List *mergeConsecutiveVars(List *children); +static List *mergeConsecutiveGroups(List *children); +static List *mergeGroupPrefixSuffix(List *children); +static RPRPatternNode *optimizeSeqPattern(RPRPatternNode *pattern); + +/* Forward declarations - ALT optimization */ +static List *flattenAltChildren(List *children); +static List *removeDuplicateAlternatives(List *children); +static RPRPatternNode *optimizeAltPattern(RPRPatternNode *pattern); + +/* Forward declarations - GROUP optimization */ +static RPRPatternNode *tryMultiplyQuantifiers(RPRPatternNode *pattern); +static RPRPatternNode *tryUnwrapGroup(RPRPatternNode *pattern); +static RPRPatternNode *optimizeGroupPattern(RPRPatternNode *pattern); + +/* Forward declarations - optimization dispatcher */ +static RPRPatternNode *optimizeRPRPattern(RPRPatternNode *pattern); + +/* Forward declarations - pattern compilation */ +static int collectDefineVariables(List *defineVariableList, char **varNames); +static void scanRPRPatternRecursive(RPRPatternNode *node, char **varNames, + int *numVars, int *numElements, + RPRDepth depth, RPRDepth *maxDepth); +static void scanRPRPattern(RPRPatternNode *node, char **varNames, int *numVars, + int *numElements, RPRDepth *maxDepth); +static RPRPattern *allocateRPRPattern(int numVars, int numElements, + RPRDepth maxDepth, char **varNamesStack); +static RPRVarId getVarIdFromPattern(RPRPattern *pat, const char *varName); +static void fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static void fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static void fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static void fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static void finalizeRPRPattern(RPRPattern *result); + +/* Forward declarations - context absorption */ +static bool isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx); +static void computeAbsorbability(RPRPattern *pattern); + +/* + * rprPatternEqual + * Compare two RPRPatternNode trees for equality. + * + * Returns true if the trees are structurally identical. + */ +static bool +rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b) +{ + if (a == NULL && b == NULL) + return true; + if (a == NULL || b == NULL) + return false; + + /* Must have same node type and quantifiers */ + if (a->nodeType != b->nodeType) + return false; + if (a->min != b->min || a->max != b->max) + return false; + if (a->reluctant != b->reluctant) + return false; + + switch (a->nodeType) + { + case RPR_PATTERN_VAR: + return strcmp(a->varName, b->varName) == 0; + + case RPR_PATTERN_SEQ: + case RPR_PATTERN_ALT: + case RPR_PATTERN_GROUP: + return rprPatternChildrenEqual(a->children, b->children); + } + + return false; /* keep compiler quiet */ +} + +/* + * rprPatternChildrenEqual + * Compare children lists of two pattern nodes for equality. + * + * Returns true if the children lists are structurally identical. + */ +static bool +rprPatternChildrenEqual(List *a, List *b) +{ + ListCell *lca, + *lcb; + + if (list_length(a) != list_length(b)) + return false; + + forboth(lca, a, lcb, b) + { + if (!rprPatternEqual((RPRPatternNode *) lfirst(lca), + (RPRPatternNode *) lfirst(lcb))) + return false; + } + + return true; +} + +/* + * tryUnwrapSingleChild + * Try to unwrap pattern node with single child. + * + * Examples (internal node representation): + * SEQ[A] -> A (single-element sequence becomes the element) + * ALT[A] -> A (single-alternative becomes the alternative) + * + * If pattern has exactly one child, return the child directly. + * Otherwise returns the pattern unchanged. + * Used by both SEQ and ALT optimization. + */ +static RPRPatternNode * +tryUnwrapSingleChild(RPRPatternNode *pattern) +{ + if (list_length(pattern->children) == 1) + return (RPRPatternNode *) linitial(pattern->children); + + return pattern; +} + +/* + * flattenSeqChildren + * Recursively optimize children and flatten nested SEQ/GROUP{1,1}. + * + * Examples: + * A ((B) (C)) -> A B C (flatten nested GROUP{1,1}) + * A (B) -> A B (flatten GROUP{1,1}) + * + * Returns a new list with optimized children, with nested SEQ and + * GROUP{1,1} children flattened into the parent list. + */ +static List * +flattenSeqChildren(List *children) +{ + ListCell *lc; + List *newChildren = NIL; + + foreach(lc, children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + RPRPatternNode *opt = optimizeRPRPattern(child); + + /* Flatten GROUP{1,1} or nested SEQ */ + if ((opt->nodeType == RPR_PATTERN_GROUP && + opt->min == 1 && opt->max == 1 && !opt->reluctant) || + opt->nodeType == RPR_PATTERN_SEQ) + { + newChildren = list_concat(newChildren, + list_copy(opt->children)); + } + else + { + newChildren = lappend(newChildren, opt); + } + } + + return newChildren; +} + +/* + * mergeConsecutiveVars + * Merge consecutive identical VAR nodes. + * + * A{m1,M1} A{m2,M2} -> A{m1+m2, M1+M2} where INF + x = INF. + * Only merges non-reluctant VAR nodes with the same variable name. + */ +static List * +mergeConsecutiveVars(List *children) +{ + ListCell *lc; + List *mergedChildren = NIL; + RPRPatternNode *prev = NULL; + + foreach(lc, children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + + if (child->nodeType == RPR_PATTERN_VAR && !child->reluctant) + { + if (prev != NULL && + prev->nodeType == RPR_PATTERN_VAR && + strcmp(prev->varName, child->varName) == 0 && + !prev->reluctant && + prev->min <= RPR_QUANTITY_INF - child->min && + (prev->max == RPR_QUANTITY_INF || + child->max == RPR_QUANTITY_INF || + prev->max <= RPR_QUANTITY_INF - child->max)) + { + /* + * Merge: accumulate min/max into prev. + */ + prev->min += child->min; + + 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; + } + } + 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); + + return mergedChildren; +} + +/* + * mergeConsecutiveGroups + * Merge consecutive identical GROUP nodes. + * + * Example: + * (A B)+ (A B)+ -> (A B){2,} + * + * Only merges non-reluctant GROUP nodes with identical children. + */ +static List * +mergeConsecutiveGroups(List *children) +{ + ListCell *lc; + List *mergedChildren = NIL; + RPRPatternNode *prev = NULL; + + foreach(lc, children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + + if (child->nodeType == RPR_PATTERN_GROUP && !child->reluctant) + { + if (prev != NULL && + prev->nodeType == RPR_PATTERN_GROUP && + !prev->reluctant && + rprPatternChildrenEqual(prev->children, child->children) && + prev->min <= RPR_QUANTITY_INF - child->min && + (prev->max == RPR_QUANTITY_INF || + child->max == RPR_QUANTITY_INF || + prev->max <= RPR_QUANTITY_INF - child->max)) + { + /* + * Merge: accumulate min/max into prev. + */ + prev->min += child->min; + + 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; + } + } + 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); + + return mergedChildren; +} + +/* + * mergeGroupPrefixSuffix + * Merge sequence prefix/suffix into GROUP with matching children. + * + * Examples: + * A B (A B)+ -> (A B){2,} + * (A B)+ A B -> (A B){2,} + * A B (A B)+ A B -> (A B){3,} + */ +static List * +mergeGroupPrefixSuffix(List *children) +{ + List *result = NIL; + int numChildren = list_length(children); + int i; + int skipUntil = -1; /* skip suffix elements already absorbed */ + + for (i = 0; i < numChildren; i++) + { + RPRPatternNode *child = (RPRPatternNode *) list_nth(children, i); + + /* Skip elements that were absorbed as suffix */ + if (i < skipUntil) + continue; + + /* + * 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) + { + List *groupContent = child->children; + int groupChildCount; + int prefixLen = list_length(result); + + /* + * 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); + + if (inner->nodeType == RPR_PATTERN_SEQ) + groupContent = inner->children; + } + + groupChildCount = list_length(groupContent); + + /* + * PREFIX MERGE: Check if preceding elements match. + * Keep absorbing 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) + { + /* + * Match! Merge by incrementing GROUP's min. + * Remove the prefix elements from output. + */ + child->min += 1; + + /* Rebuild result without matched prefix */ + { + List *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; + } + + list_free(prefixElements); + } + + /* + * SUFFIX MERGE: Check if following elements match. + * Keep absorbing as long as we have matching suffixes. + */ + while (i + groupChildCount < numChildren && groupChildCount > 0) + { + List *suffixElements = NIL; + int j; + int suffixStart = i + 1; + + /* Adjust for already absorbed elements */ + if (skipUntil > suffixStart) + break; + + /* Extract next groupChildCount elements as suffix */ + for (j = 0; j < groupChildCount; j++) + { + int idx = suffixStart + j; + + if (idx >= numChildren) + break; + suffixElements = lappend(suffixElements, + list_nth(children, idx)); + } + + /* Compare with GROUP's children */ + if (list_length(suffixElements) == groupChildCount && + rprPatternChildrenEqual(suffixElements, groupContent) && + child->min < RPR_QUANTITY_INF) + { + /* + * Match! Absorb suffix by incrementing min and skipping. + */ + child->min += 1; + skipUntil = suffixStart + groupChildCount; + /* Update i to continue suffix check after absorbed elements */ + i = skipUntil - 1; + } + else + { + list_free(suffixElements); + break; + } + + list_free(suffixElements); + } + } + + result = lappend(result, child); + } + + return result; +} + +/* + * optimizeSeqPattern + * Optimize SEQ pattern node. + * + * Optimizations: + * 1. Flatten nested SEQ and GROUP{1,1} + * 2. Merge consecutive identical VAR nodes + * 3. Merge consecutive identical GROUP nodes + * 4. Merge prefix/suffix into GROUP with matching children + * 5. Unwrap single-item SEQ + */ +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 prefix/suffix into GROUP with matching children */ + pattern->children = mergeGroupPrefixSuffix(pattern->children); + + /* Unwrap single-item SEQ */ + return tryUnwrapSingleChild(pattern); +} + +/* + * flattenAltChildren + * Recursively optimize children and flatten nested ALT nodes. + * + * Example: + * (A | (B | C)) -> (A | B | C) + * + * Returns a new list with optimized children, with nested ALT children + * flattened into the parent list. + */ +static List * +flattenAltChildren(List *children) +{ + ListCell *lc; + List *newChildren = NIL; + + foreach(lc, children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + RPRPatternNode *opt = optimizeRPRPattern(child); + + if (opt->nodeType == RPR_PATTERN_ALT) + newChildren = list_concat(newChildren, list_copy(opt->children)); + else + newChildren = lappend(newChildren, opt); + } + + return newChildren; +} + +/* + * removeDuplicateAlternatives + * Remove duplicate alternatives from a list. + * + * Returns a new list with only unique children (first occurrence kept). + */ +static List * +removeDuplicateAlternatives(List *children) +{ + ListCell *lc; + ListCell *lc2; + List *uniqueChildren = NIL; + + foreach(lc, children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + bool isDuplicate = false; + + foreach(lc2, uniqueChildren) + { + if (rprPatternEqual((RPRPatternNode *) lfirst(lc2), child)) + { + isDuplicate = true; + break; + } + } + + if (!isDuplicate) + uniqueChildren = lappend(uniqueChildren, child); + } + + return uniqueChildren; +} + +/* + * optimizeAltPattern + * Optimize ALT pattern node. + * + * Optimizations: + * 1. Flatten nested ALT + * 2. Remove duplicate alternatives + * 3. Unwrap single-item ALT + */ +static RPRPatternNode * +optimizeAltPattern(RPRPatternNode *pattern) +{ + /* Recursively optimize children and flatten nested ALT */ + pattern->children = flattenAltChildren(pattern->children); + + /* Remove duplicate alternatives */ + pattern->children = removeDuplicateAlternatives(pattern->children); + + /* Unwrap single-item ALT */ + return tryUnwrapSingleChild(pattern); +} + +/* + * tryMultiplyQuantifiers + * Try to multiply quantifiers: (A{m}){n} -> A{m*n} + * + * Returns the child node with multiplied quantifiers if successful, + * otherwise returns the original pattern unchanged. + */ +static RPRPatternNode * +tryMultiplyQuantifiers(RPRPatternNode *pattern) +{ + RPRPatternNode *child; + int64 new_min_64; + int new_max; + + if (list_length(pattern->children) != 1 || pattern->reluctant) + return pattern; + + child = (RPRPatternNode *) linitial(pattern->children); + + if (child->nodeType != RPR_PATTERN_VAR || child->reluctant) + return pattern; + + /* Can't multiply if child has infinite max */ + if (child->max == RPR_QUANTITY_INF) + return pattern; + + /* Calculate new min (must not overflow) */ + new_min_64 = (int64) pattern->min * child->min; + if (new_min_64 >= RPR_QUANTITY_INF) + return pattern; + + /* Calculate new max */ + if (pattern->max == RPR_QUANTITY_INF) + { + new_max = RPR_QUANTITY_INF; + } + else + { + int64 new_max_64 = (int64) pattern->max * child->max; + + if (new_max_64 >= RPR_QUANTITY_INF) + return pattern; + new_max = (int) new_max_64; + } + + child->min = (int) new_min_64; + child->max = new_max; + return child; +} + +/* + * tryUnwrapGroup + * Try to unwrap GROUP{1,1} node. + * + * Examples: + * (A){1,1} -> A + * (A B){1,1} -> A B (converts to SEQ internally) + * + * If GROUP has min=1, max=1, and is not reluctant: + * - Single child: return the child directly + * - Multiple children: convert GROUP to SEQ + * Otherwise returns the pattern unchanged. + */ +static RPRPatternNode * +tryUnwrapGroup(RPRPatternNode *pattern) +{ + if (pattern->min != 1 || pattern->max != 1 || pattern->reluctant) + return pattern; + + if (list_length(pattern->children) == 1) + return (RPRPatternNode *) linitial(pattern->children); + + /* Multiple children: convert to SEQ */ + pattern->nodeType = RPR_PATTERN_SEQ; + return pattern; +} + +/* + * optimizeGroupPattern + * Optimize GROUP pattern node. + * + * Optimizations: + * 1. Quantifier multiplication: (A{m}){n} -> A{m*n} + * 2. Unwrap GROUP{1,1} + */ +static RPRPatternNode * +optimizeGroupPattern(RPRPatternNode *pattern) +{ + ListCell *lc; + List *newChildren; + RPRPatternNode *result; + + /* Recursively optimize children */ + newChildren = NIL; + foreach(lc, pattern->children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + + newChildren = lappend(newChildren, optimizeRPRPattern(child)); + } + pattern->children = newChildren; + + /* Try quantifier multiplication */ + result = tryMultiplyQuantifiers(pattern); + if (result != pattern) + return result; + + /* Try unwrapping GROUP{1,1} */ + result = tryUnwrapGroup(pattern); + + /* If converted to SEQ (not just unwrapped child), optimize as SEQ */ + if (result == pattern && result->nodeType == RPR_PATTERN_SEQ) + return optimizeSeqPattern(result); + + return result; +} + +/* + * optimizeRPRPattern + * Optimize RPRPatternNode tree (dispatcher). + * + * Dispatches to type-specific optimization functions. + * Returns the optimized pattern (may be a different node). + */ +static RPRPatternNode * +optimizeRPRPattern(RPRPatternNode *pattern) +{ + if (pattern == NULL) + return NULL; + + switch (pattern->nodeType) + { + case RPR_PATTERN_VAR: + return pattern; + case RPR_PATTERN_SEQ: + return optimizeSeqPattern(pattern); + case RPR_PATTERN_ALT: + return optimizeAltPattern(pattern); + case RPR_PATTERN_GROUP: + return optimizeGroupPattern(pattern); + } + + return pattern; /* keep compiler quiet */ +} + +/* + * collectDefineVariables + * Collect variable names from DEFINE clause. + * + * Populates varNames array with variable names in DEFINE order. + * This ensures varId == defineIdx, eliminating runtime mapping. + * Returns the number of variables collected. + */ +static int +collectDefineVariables(List *defineVariableList, char **varNames) +{ + ListCell *lc; + int numVars = 0; + + foreach(lc, defineVariableList) + { + if (numVars >= RPR_VARID_MAX) + ereport(ERROR, + (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), + errmsg("too many pattern variables"), + errdetail("Maximum is %d.", RPR_VARID_MAX))); + + varNames[numVars++] = strVal(lfirst(lc)); + } + + return numVars; +} + +/* + * scanRPRPatternRecursive + * Recursively scan pattern AST (pass 1 internal). + * + * Collects unique variable names and counts elements while tracking depth. + * Variables from DEFINE clause are already in varNames; this adds any + * additional variables found in the pattern. + */ +static void +scanRPRPatternRecursive(RPRPatternNode *node, char **varNames, int *numVars, + int *numElements, RPRDepth depth, RPRDepth *maxDepth) +{ + ListCell *lc; + int i; + + if (node == NULL) + return; + + /* Track maximum depth */ + if (depth > *maxDepth) + *maxDepth = depth; + + switch (node->nodeType) + { + case RPR_PATTERN_VAR: + /* Count element */ + (*numElements)++; + + /* Collect variable name if not already present */ + for (i = 0; i < *numVars; i++) + { + if (strcmp(varNames[i], node->varName) == 0) + return; /* Already have this variable */ + } + + /* New variable */ + if (*numVars >= RPR_VARID_MAX) + ereport(ERROR, + (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), + errmsg("too many pattern variables"), + errdetail("Maximum is %d.", RPR_VARID_MAX))); + + varNames[*numVars] = node->varName; + (*numVars)++; + break; + + case RPR_PATTERN_SEQ: + /* Sequence: just recurse into children */ + foreach(lc, node->children) + { + scanRPRPatternRecursive((RPRPatternNode *) lfirst(lc), varNames, + numVars, numElements, depth, maxDepth); + } + break; + + case RPR_PATTERN_GROUP: + /* Recurse into children at increased depth */ + foreach(lc, node->children) + { + scanRPRPatternRecursive((RPRPatternNode *) lfirst(lc), varNames, + numVars, numElements, depth + 1, maxDepth); + } + + /* Add END element if group has non-trivial quantifier */ + if (node->min != 1 || node->max != 1) + (*numElements)++; + break; + + case RPR_PATTERN_ALT: + /* Count ALT start element */ + (*numElements)++; + + /* Recurse into children at increased depth */ + foreach(lc, node->children) + { + scanRPRPatternRecursive((RPRPatternNode *) lfirst(lc), varNames, + numVars, numElements, depth + 1, maxDepth); + } + break; + } +} + +/* + * scanRPRPattern + * Scan pattern AST (pass 1 entry point). + * + * Collects unique variable names (appending to those from DEFINE clause), + * counts total elements (including FIN marker), and tracks maximum depth. + * Reports error if element count exceeds RPR_ELEMIDX_MAX. + */ +static void +scanRPRPattern(RPRPatternNode *node, char **varNames, int *numVars, + int *numElements, RPRDepth *maxDepth) +{ + *numElements = 0; + *maxDepth = 0; + + scanRPRPatternRecursive(node, varNames, numVars, numElements, 0, maxDepth); + + (*numElements)++; /* +1 for FIN marker */ + + if (*numElements > RPR_ELEMIDX_MAX) + ereport(ERROR, + (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), + errmsg("pattern too complex"), + errdetail("Pattern has %d elements, maximum is %d.", + *numElements, RPR_ELEMIDX_MAX))); +} + +/* + * allocateRPRPattern + * Allocate and initialize RPRPattern structure. + * + * Creates the pattern structure, copies variable names, and allocates + * the elements array. The elements array is zero-initialized. + */ +static RPRPattern * +allocateRPRPattern(int numVars, int numElements, RPRDepth maxDepth, + char **varNamesStack) +{ + RPRPattern *result; + int i; + + result = makeNode(RPRPattern); + result->numVars = numVars; + result->maxDepth = maxDepth + 1; /* +1: depth is 0-based */ + result->numElements = numElements; + + /* Copy varNames */ + if (numVars > 0) + { + result->varNames = palloc(numVars * sizeof(char *)); + for (i = 0; i < numVars; i++) + result->varNames[i] = pstrdup(varNamesStack[i]); + } + else + { + result->varNames = NULL; + } + + /* Allocate elements array (zero-init for reserved fields) */ + result->elements = palloc0(numElements * sizeof(RPRPatternElement)); + + return result; +} + +/* + * getVarIdFromPattern + * Get variable ID for a variable name from RPRPattern. + * + * Returns the index of the variable in the varNames array. + */ +static RPRVarId +getVarIdFromPattern(RPRPattern *pat, const char *varName) +{ + for (int i = 0; i < pat->numVars; i++) + { + if (strcmp(pat->varNames[i], varName) == 0) + return (RPRVarId) i; + } + + /* Should not happen - variable should already be collected */ + elog(ERROR, "pattern variable \"%s\" not found", varName); + pg_unreachable(); +} + +/* + * fillRPRPatternVar + * Fill a VAR pattern element. + */ +static void +fillRPRPatternVar(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) +{ + RPRPatternElement *elem = &pat->elements[*idx]; + + memset(elem, 0, sizeof(RPRPatternElement)); + elem->varId = getVarIdFromPattern(pat, node->varName); + elem->depth = depth; + elem->min = node->min; + elem->max = (node->max == INT_MAX) ? RPR_QUANTITY_INF : node->max; + elem->next = RPR_ELEMIDX_INVALID; + elem->jump = RPR_ELEMIDX_INVALID; + if (node->reluctant) + elem->flags |= RPR_ELEM_RELUCTANT; + (*idx)++; +} + +/* + * fillRPRPatternGroup + * Fill a GROUP pattern and its children. + * + * Creates elements for group content at increased depth, plus an END marker + * if the group has a non-trivial quantifier. + */ +static void +fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) +{ + ListCell *lc; + int groupStartIdx = *idx; + bool altOnlyChild; + RPRDepth childDepth; + + /* + * Fill group content at increased depth. + * Exception: if the only child is ALT, don't increase depth + * since GROUP's parens already provide visual grouping. + * This avoids output like "((a | b))+" instead of "(a | b)+". + */ + altOnlyChild = (list_length(node->children) == 1 && + ((RPRPatternNode *) linitial(node->children))->nodeType == RPR_PATTERN_ALT); + childDepth = altOnlyChild ? depth : depth + 1; + + foreach(lc, node->children) + { + fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, childDepth); + } + + /* Add group end marker if group has non-trivial quantifier */ + if (node->min != 1 || node->max != 1) + { + RPRPatternElement *elem = &pat->elements[*idx]; + + memset(elem, 0, sizeof(RPRPatternElement)); + elem->varId = RPR_VARID_END; + elem->depth = depth; + elem->min = node->min; + elem->max = (node->max == INT_MAX) ? RPR_QUANTITY_INF : node->max; + elem->next = RPR_ELEMIDX_INVALID; + elem->jump = groupStartIdx; + if (node->reluctant) + elem->flags |= RPR_ELEM_RELUCTANT; + (*idx)++; + } +} + +/* + * fillRPRPatternAlt + * Fill an ALT pattern and its alternatives. + * + * Creates ALT_START marker, fills each alternative at increased depth, + * and sets up jump pointers between alternatives. + */ +static void +fillRPRPatternAlt(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) +{ + ListCell *lc; + RPRPatternElement *elem; + int altStartIdx = *idx; + List *altBranchStarts = NIL; + List *altEndPositions = NIL; + + /* Add alternation start marker */ + elem = &pat->elements[*idx]; + memset(elem, 0, sizeof(RPRPatternElement)); + elem->varId = RPR_VARID_ALT; + elem->depth = depth; + elem->min = 1; + elem->max = 1; + elem->next = RPR_ELEMIDX_INVALID; + elem->jump = RPR_ELEMIDX_INVALID; + (*idx)++; + + /* Fill each alternative */ + foreach(lc, node->children) + { + RPRPatternNode *alt = (RPRPatternNode *) lfirst(lc); + int branchStart = *idx; + + altBranchStarts = lappend_int(altBranchStarts, branchStart); + fillRPRPattern(alt, pat, idx, depth + 1); + + if (*idx > branchStart) + altEndPositions = lappend_int(altEndPositions, *idx - 1); + } + + /* Set ALT_START.next to first alternative */ + if (list_length(altBranchStarts) > 0) + pat->elements[altStartIdx].next = linitial_int(altBranchStarts); + + /* Set jump on first element of each alternative to next alternative */ + foreach(lc, altBranchStarts) + { + int firstElemIdx = lfirst_int(lc); + + if (lnext(altBranchStarts, lc) != NULL) + pat->elements[firstElemIdx].jump = lfirst_int(lnext(altBranchStarts, lc)); + } + + /* Set next on last element of each alternative to after the alternation */ + { + int afterAltIdx = *idx; + + foreach(lc, altEndPositions) + { + int endPos = lfirst_int(lc); + + if (pat->elements[endPos].next == RPR_ELEMIDX_INVALID) + pat->elements[endPos].next = afterAltIdx; + } + } + + list_free(altBranchStarts); + list_free(altEndPositions); +} + +/* + * fillRPRPattern + * Fill pattern elements array from AST (pass 2). + * + * Recursively traverses AST and populates pre-allocated elements array. + * Dispatches to type-specific fill functions. + */ +static void +fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) +{ + ListCell *lc; + + if (node == NULL) + return; + + switch (node->nodeType) + { + case RPR_PATTERN_SEQ: + foreach(lc, node->children) + { + fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth); + } + break; + + case RPR_PATTERN_VAR: + fillRPRPatternVar(node, pat, idx, depth); + break; + + case RPR_PATTERN_GROUP: + fillRPRPatternGroup(node, pat, idx, depth); + break; + + case RPR_PATTERN_ALT: + fillRPRPatternAlt(node, pat, idx, depth); + break; + } +} + +/* + * finalizeRPRPattern + * Finalize pattern structure after filling elements. + * + * This performs: + * 1. Set up next pointers for sequential flow + * 2. Add FIN marker at the end + */ +static void +finalizeRPRPattern(RPRPattern *result) +{ + int finIdx = result->numElements - 1; + int i; + RPRPatternElement *finElem; + + /* Set up next pointers for elements that don't have one yet */ + for (i = 0; i < finIdx; i++) + { + if (result->elements[i].next == RPR_ELEMIDX_INVALID) + { + /* Point to next element, or to FIN if this is the last */ + result->elements[i].next = (i < finIdx - 1) ? i + 1 : finIdx; + } + } + + /* Add FIN marker at the end */ + finElem = &result->elements[finIdx]; + memset(finElem, 0, sizeof(RPRPatternElement)); + finElem->varId = RPR_VARID_FIN; + finElem->depth = 0; + finElem->min = 1; + finElem->max = 1; + finElem->next = RPR_ELEMIDX_INVALID; + finElem->jump = RPR_ELEMIDX_INVALID; +} + +/* + * isUnboundedStart + * Check if the element at idx starts an unbounded sequence. + * + * For context absorption to work, the sequence starting at idx must be + * unbounded (max = infinity) so that we can "shift" by decrementing count. + * + * Two cases are handled: + * 1. Simple var: A+ B C - first element A has max=INF + * 2. Group: (A B){2,} C - group END has max=INF, and all elements + * inside the group must be simple {1,1} vars (no nested complexity) + * + * Returns false for patterns where absorption cannot work: + * - A B+ (unbounded not at start) + * - (A | B){2,} (ALT inside group) + * - (A B+){2,} (unbounded element inside group) + * - ((A B){2,} C){3,} (nested groups) + */ +static bool +isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx) +{ + RPRPatternElement *elem = &pattern->elements[idx]; + RPRDepth startDepth = elem->depth; + RPRPatternElement *lastElem = NULL; + bool allSimpleInside = true; + + /* Traverse elements until we exit the current scope */ + for (RPRElemIdx i = idx; ; i++) + { + RPRPatternElement *e; + + Assert(i >= 0 && i < pattern->numElements); + e = &pattern->elements[i]; + + /* Exit when depth drops (left the group) or reached FIN */ + if (e->depth < startDepth || e->varId == RPR_VARID_FIN) + { + lastElem = e; + break; + } + + /* Track whether all elements at this depth are simple {1,1} vars */ + if (e->depth == startDepth) + { + if (!RPRElemIsVar(e) || e->min != 1 || e->max != 1) + allSimpleInside = false; + } + else + { + /* Any nested structure disqualifies */ + allSimpleInside = false; + } + } + + Assert(lastElem != NULL); + + /* Case 2: Unbounded group - END element points back to idx */ + if (lastElem->varId == RPR_VARID_END && + lastElem->jump == idx && + lastElem->max == RPR_QUANTITY_INF) + { + /* + * Check for outer nesting: if there's another END at a lower depth + * before FIN, we're inside a nested structure that doesn't support + * simple absorption. For example, ((A B){2,} C){3,} has an inner + * END at depth=1 and an outer END at depth=0. + */ + RPRElemIdx lastIdx = (RPRElemIdx) (lastElem - pattern->elements); + RPRElemIdx j; + + for (j = lastIdx + 1; j < pattern->numElements; j++) + { + RPRPatternElement *e = &pattern->elements[j]; + + if (e->varId == RPR_VARID_FIN) + break; /* Reached end, no outer nesting */ + if (e->varId == RPR_VARID_END && e->depth < lastElem->depth) + return false; /* Found outer END, nested structure */ + } + + return allSimpleInside; + } + + /* Case 1: Simple unbounded var at start */ + return RPRElemIsVar(elem) && elem->max == RPR_QUANTITY_INF; +} + +/* + * computeAbsorbability + * Determine if pattern supports context absorption optimization. + * + * Context absorption allows the executor to reuse NFA match states from + * previous row positions. When a match at position P can be "shifted" to + * position P+1 by decrementing the count of the first unbounded element, + * we avoid re-running the NFA from scratch. + * + * This function sets RPR_ELEM_ABSORBABLE on elements that can be shifted, + * and pattern->isAbsorbable if any element is absorbable. + * + * Examples: + * A+ B C - absorbable (unbounded var at start) + * (A B){2,} C - absorbable (unbounded group) + * A B+ - NOT absorbable (unbounded not at start) + * A+ | B+ C - both branches absorbable (checked independently) + * A+ B | C D - first branch only + */ +static void +computeAbsorbability(RPRPattern *pattern) +{ + RPRPatternElement *first = &pattern->elements[0]; + + pattern->isAbsorbable = false; + + if (pattern->numElements < 2) /* At minimum: one element + FIN */ + return; + + if (first->varId == RPR_VARID_ALT) + { + /* ALT: check each branch */ + RPRElemIdx branchIdx = first->next; + + while (branchIdx != RPR_ELEMIDX_INVALID && + branchIdx < pattern->numElements - 1) + { + RPRPatternElement *branchFirst = &pattern->elements[branchIdx]; + + if (isUnboundedStart(pattern, branchIdx)) + { + branchFirst->flags |= RPR_ELEM_ABSORBABLE; + pattern->isAbsorbable = true; + } + + branchIdx = branchFirst->jump; + } + } + else + { + /* Non-ALT: check first element */ + if (isUnboundedStart(pattern, 0)) + { + first->flags |= RPR_ELEM_ABSORBABLE; + pattern->isAbsorbable = true; + } + } +} + +/* + * buildRPRPattern + * Compile pattern AST to flat bytecode array. + * + * Compilation phases: + * 1. Optimize AST (flatten, merge, deduplicate) + * 2. Scan: collect variables, count elements (pass 1) + * 3. Allocate result structure + * 4. Fill elements from AST (pass 2) + * 5. Finalize: set up next pointers, add FIN marker + * 6. Compute context absorption eligibility + * + * Called from createplan.c during plan creation. + * Returns NULL if pattern is NULL. + */ +RPRPattern * +buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList) +{ + RPRPattern *result; + RPRPatternNode *optimized; + char *varNamesStack[RPR_VARID_MAX + 1]; + int numVars; + int numElements; + RPRDepth maxDepth; + int idx; + + if (pattern == NULL) + return NULL; + + /* Optimize the pattern tree (planner phase) */ + optimized = optimizeRPRPattern(pattern); + + /* Collect variable names from DEFINE clause */ + numVars = collectDefineVariables(defineVariableList, varNamesStack); + + /* Scan pattern: collect variables, count elements, validate limits */ + scanRPRPattern(optimized, varNamesStack, &numVars, &numElements, &maxDepth); + + /* Allocate result structure */ + result = allocateRPRPattern(numVars, numElements, maxDepth, varNamesStack); + + /* Fill elements (pass 2) */ + idx = 0; + fillRPRPattern(optimized, result, &idx, 0); + + /* Finalize: set up next pointers and add FIN marker */ + finalizeRPRPattern(result); + + /* Compute context absorption eligibility */ + computeAbsorbability(result); + + return result; +} diff --git a/src/backend/optimizer/plan/setrefs.c b/src/backend/optimizer/plan/setrefs.c index 16d200cfb46..2efeec22102 100644 --- a/src/backend/optimizer/plan/setrefs.c +++ b/src/backend/optimizer/plan/setrefs.c @@ -211,7 +211,6 @@ static List *set_windowagg_runcondition_references(PlannerInfo *root, List *runcondition, Plan *plan); - /***************************************************************************** * * SUBPLAN REFERENCES @@ -2576,6 +2575,32 @@ set_upper_references(PlannerInfo *root, Plan *plan, int rtoffset) NRM_EQUAL, NUM_EXEC_QUAL(plan)); + /* + * Modifies an expression tree in each DEFINE clause so that all Var + * nodes's varno refers to OUTER_VAR. + */ + if (IsA(plan, WindowAgg)) + { + WindowAgg *wplan = (WindowAgg *) plan; + + if (wplan->defineClause != NIL) + { + foreach(l, wplan->defineClause) + { + TargetEntry *tle = (TargetEntry *) lfirst(l); + + tle->expr = (Expr *) + fix_upper_expr(root, + (Node *) tle->expr, + subplan_itlist, + OUTER_VAR, + rtoffset, + NRM_EQUAL, + NUM_EXEC_QUAL(plan)); + } + } + } + pfree(subplan_itlist); } diff --git a/src/backend/optimizer/prep/prepjointree.c b/src/backend/optimizer/prep/prepjointree.c index c80bfc88d82..63d872b029d 100644 --- a/src/backend/optimizer/prep/prepjointree.c +++ b/src/backend/optimizer/prep/prepjointree.c @@ -2510,6 +2510,15 @@ perform_pullup_replace_vars(PlannerInfo *root, parse->returningList = (List *) pullup_replace_vars((Node *) parse->returningList, rvcontext); + foreach(lc, parse->windowClause) + { + WindowClause *wc = lfirst_node(WindowClause, lc); + + if (wc->defineClause != NIL) + wc->defineClause = (List *) + pullup_replace_vars((Node *) wc->defineClause, rvcontext); + } + if (parse->onConflict) { parse->onConflict->onConflictSet = (List *) diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index 4bc6fb5670e..a76abda3440 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -20,6 +20,7 @@ #include "lib/stringinfo.h" #include "nodes/bitmapset.h" #include "nodes/lockoptions.h" +#include "nodes/parsenodes.h" #include "nodes/primnodes.h" @@ -1223,6 +1224,69 @@ typedef struct Agg List *chain; } Agg; +/* ---------------- + * Row Pattern Recognition compiled pattern types + * ---------------- + */ + +/* Type definitions for RPR pattern elements */ +typedef uint8 RPRVarId; /* pattern variable ID */ +typedef uint8 RPRElemFlags; /* element flags */ +typedef uint8 RPRDepth; /* group nesting depth */ +typedef int32 RPRQuantity; /* quantifier min/max */ +typedef int16 RPRElemIdx; /* element array index */ + +/* + * RPRPatternElement - flat element for NFA pattern matching (16 bytes) + * + * Layout optimized for alignment (no padding holes): + * varId(1) + depth(1) + flags(1) + reserved(1) + min(4) + max(4) + next(2) + jump(2) + */ +typedef struct RPRPatternElement +{ + RPRVarId varId; /* variable ID, or special value for control */ + RPRDepth depth; /* group nesting depth */ + RPRElemFlags flags; /* flags (reluctant, etc.) */ + uint8 reserved; /* reserved padding byte */ + RPRQuantity min; /* quantifier minimum */ + RPRQuantity max; /* quantifier maximum */ + RPRElemIdx next; /* next element index */ + RPRElemIdx jump; /* jump target (for ALT/GROUP) */ +} RPRPatternElement; + +/* + * RPRPattern - compiled pattern for NFA execution + * + * Requires custom copy/out/read functions due to elements array. + */ +typedef struct RPRPattern +{ + pg_node_attr(custom_copy_equal, custom_read_write) + + NodeTag type; /* T_RPRPattern */ + int numVars; /* number of pattern variables */ + char **varNames; /* array of variable names (DEFINE order first) */ + RPRDepth maxDepth; /* maximum group nesting depth */ + int numElements; /* number of elements */ + RPRPatternElement *elements; /* array of pattern elements */ + + /* + * Context absorption optimization. + * + * Absorption is only safe when later matches are guaranteed to be + * suffixes of earlier matches. This requires simple pattern structure: + * + * Case 1: No ALT, single unbounded element (A+, (A B)+) + * Case 2: Top-level ALT with each branch being single unbounded (A+ | B+) + * + * Complex patterns like A B (A B)+ could theoretically be transformed to + * (A B){2,} for absorption, but this changes lexical order and is not + * implemented. Similarly, (A|B)+ cannot be absorbed because different + * start positions produce different match contents (not suffix relation). + */ + bool isAbsorbable; /* true if pattern supports context absorption */ +} RPRPattern; + /* ---------------- * window aggregate node * ---------------- @@ -1293,6 +1357,15 @@ typedef struct WindowAgg /* nulls sort first for in_range tests? */ bool inRangeNullsFirst; + /* Row Pattern Recognition AFTER MATCH SKIP clause */ + RPSkipTo rpSkipTo; /* Row Pattern Skip To type */ + + /* Compiled Row Pattern for NFA execution */ + struct RPRPattern *rpPattern; + + /* Row Pattern DEFINE clause (list of TargetEntry) */ + List *defineClause; + /* * false for all apart from the WindowAgg that's closest to the root of * the plan diff --git a/src/include/optimizer/rpr.h b/src/include/optimizer/rpr.h new file mode 100644 index 00000000000..4846ad6f2b7 --- /dev/null +++ b/src/include/optimizer/rpr.h @@ -0,0 +1,47 @@ +/*------------------------------------------------------------------------- + * + * rpr.h + * Row Pattern Recognition pattern compilation for planner + * + * Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group + * Portions Copyright (c) 1994, Regents of the University of California + * + * src/include/optimizer/rpr.h + * + *------------------------------------------------------------------------- + */ +#ifndef OPTIMIZER_RPR_H +#define OPTIMIZER_RPR_H + +#include "nodes/parsenodes.h" +#include "nodes/plannodes.h" + +/* Limits and special values */ +#define RPR_VARID_MAX 252 /* max pattern variables: 252 */ +#define RPR_DEPTH_MAX UINT8_MAX /* max nesting depth: 255 */ +#define RPR_QUANTITY_INF INT32_MAX /* unbounded quantifier */ +#define RPR_COUNT_MAX INT32_MAX /* max runtime count (NFA state) */ +#define RPR_ELEMIDX_MAX INT16_MAX /* max pattern elements */ +#define RPR_ELEMIDX_INVALID ((RPRElemIdx) -1) /* invalid index */ + +/* Special varId values for control elements (253-255) */ +#define RPR_VARID_ALT ((RPRVarId) 253) /* alternation start */ +#define RPR_VARID_END ((RPRVarId) 254) /* group end */ +#define RPR_VARID_FIN ((RPRVarId) 255) /* pattern finish */ + +/* Element flags */ +#define RPR_ELEM_RELUCTANT 0x01 /* reluctant (non-greedy) quantifier */ +#define RPR_ELEM_ABSORBABLE 0x02 /* branch supports context absorption */ + +/* Accessor macros for RPRPatternElement */ +#define RPRElemIsReluctant(e) ((e)->flags & RPR_ELEM_RELUCTANT) +#define RPRElemIsAbsorbable(e) ((e)->flags & RPR_ELEM_ABSORBABLE) +#define RPRElemIsVar(e) ((e)->varId <= RPR_VARID_MAX) +#define RPRElemIsAlt(e) ((e)->varId == RPR_VARID_ALT) +#define RPRElemIsEnd(e) ((e)->varId == RPR_VARID_END) +#define RPRElemIsFin(e) ((e)->varId == RPR_VARID_FIN) +#define RPRElemCanSkip(e) ((e)->min == 0) + +extern RPRPattern *buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList); + +#endif /* OPTIMIZER_RPR_H */ -- 2.43.0