From 259ce0040203f0e81aaa3ac625c7f9f9b4998ed8 Mon Sep 17 00:00:00 2001 From: Tatsuo Ishii Date: Thu, 15 Jan 2026 13:26:44 +0900 Subject: [PATCH v38 4/8] Row pattern recognition patch (planner). --- src/backend/optimizer/plan/Makefile | 1 + src/backend/optimizer/plan/createplan.c | 64 +- src/backend/optimizer/plan/meson.build | 1 + src/backend/optimizer/plan/planner.c | 3 + src/backend/optimizer/plan/rpr.c | 1024 +++++++++++++++++++++ src/backend/optimizer/plan/setrefs.c | 27 +- src/backend/optimizer/prep/prepjointree.c | 9 + src/include/nodes/plannodes.h | 76 ++ src/include/optimizer/rpr.h | 46 + 9 files changed, 1233 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 af41ca69929..51334f80a5c 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -37,6 +37,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" @@ -289,7 +290,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 *defineInitial, + List *qual, bool topWindow, Plan *lefttree); static Group *make_group(List *tlist, List *qual, int numGroupCols, AttrNumber *grpColIdx, Oid *grpOperators, Oid *grpCollations, @@ -2530,21 +2534,37 @@ 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, + wc->defineInitial, + best_path->qual, + best_path->topwindow, + subplan); + } copy_generic_path_info(&plan->plan, (Path *) best_path); @@ -6610,7 +6630,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 *defineInitial, + List *qual, bool topWindow, Plan *lefttree) { WindowAgg *node = makeNode(WindowAgg); Plan *plan = &node->plan; @@ -6637,6 +6660,13 @@ 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; + node->defineInitial = defineInitial; 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..0eed6b865ae --- /dev/null +++ b/src/backend/optimizer/plan/rpr.c @@ -0,0 +1,1024 @@ +/*------------------------------------------------------------------------- + * + * 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-2025, 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 */ +static bool rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b); +static RPRPatternNode *optimizeRPRPattern(RPRPatternNode *pattern); +static void scanRPRPattern(RPRPatternNode *node, char **varNames, int *numVars, + int *numElements, RPRDepth depth, RPRDepth *maxDepth); +static void fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, + int *idx, RPRDepth depth); +static RPRVarId getVarIdFromPattern(RPRPattern *pat, const char *varName); +static void computeAbsorbability(RPRPattern *pattern); + +/* + * rprPatternChildrenEqual + * Compare children of two GROUP nodes for equality. + * + * Returns true if the children lists are structurally identical. + * Used for GROUP merge optimization where we ignore outer quantifiers. + */ +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; +} + +/* + * rprPatternEqual + * Compare two RPRPatternNode trees for equality. + * + * Returns true if the trees are structurally identical. + */ +static bool +rprPatternEqual(RPRPatternNode *a, RPRPatternNode *b) +{ + ListCell *lca, + *lcb; + + 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: + /* Must have same number of children */ + if (list_length(a->children) != list_length(b->children)) + return false; + + /* Compare each child */ + forboth(lca, a->children, lcb, b->children) + { + if (!rprPatternEqual((RPRPatternNode *) lfirst(lca), + (RPRPatternNode *) lfirst(lcb))) + return false; + } + return true; + } + + return false; /* keep compiler quiet */ +} + +/* + * optimizeRPRPattern + * Optimize RPRPatternNode tree in a single pass. + * + * Optimizations applied (bottom-up, in order per node): + * 1. Flatten nested SEQ: (A (B C)) -> (A B C) + * 2. Flatten nested ALT: (A | (B | C)) -> (A | B | C) + * 3. Unwrap GROUP{1,1}: ((A)) -> A, (A B){1,1} -> A B + * 4. Quantifier multiplication: (A{2}){3} -> A{6} + * 5. Remove duplicate alternatives: (A | B | A) -> (A | B) + * 6. Merge consecutive vars: A A A -> A{3,3} + * 7. Remove single-item SEQ/ALT wrappers + */ +static RPRPatternNode * +optimizeRPRPattern(RPRPatternNode *pattern) +{ + ListCell *lc; + List *newChildren; + + if (pattern == NULL) + return NULL; + + switch (pattern->nodeType) + { + case RPR_PATTERN_VAR: + /* Leaf node - nothing to optimize */ + return pattern; + + case RPR_PATTERN_SEQ: + { + RPRPatternNode *prev = NULL; + + /* Recursively optimize children, flatten SEQ/GROUP{1,1} */ + newChildren = NIL; + foreach(lc, pattern->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); + } + } + + /* + * Merge consecutive identical VAR nodes with any quantifier. + * A{m1,M1} A{m2,M2} -> A{m1+m2, M1+M2} + * where INF + x = INF + */ + { + List *mergedChildren = NIL; + + foreach(lc, newChildren) + { + 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) + { + /* + * Merge: accumulate min/max into prev. + * INF + anything = INF + */ + 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); + + newChildren = mergedChildren; + } + + /* + * Merge sequence prefix/suffix into GROUP with matching children. + * A B (A B)+ -> (A B){2,} + * (A B)+ A B -> (A B){2,} + * A B (A B)+ A B -> (A B){3,} + */ + { + List *groupMergedChildren = NIL; + int numChildren = list_length(newChildren); + int i; + bool merged = false; + int skipUntil = -1; /* skip suffix elements already absorbed */ + + for (i = 0; i < numChildren; i++) + { + RPRPatternNode *child = (RPRPatternNode *) list_nth(newChildren, 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(groupMergedChildren); + + /* + * If GROUP has single SEQ child, compare with SEQ's children. + * e.g., (A B)+ is GROUP[SEQ[A,B]], we want to compare [A,B]. + */ + 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(groupMergedChildren, j)); + } + + /* Compare with GROUP's (possibly unwrapped) children */ + if (rprPatternChildrenEqual(prefixElements, groupContent)) + { + /* + * Match! Merge by incrementing GROUP's min. + * Remove the prefix elements from output. + */ + child->min += 1; + + /* Rebuild groupMergedChildren without matched prefix */ + { + List *trimmed = NIL; + + for (j = 0; j < prefixLen - groupChildCount; j++) + { + trimmed = lappend(trimmed, + list_nth(groupMergedChildren, j)); + } + groupMergedChildren = trimmed; + prefixLen = list_length(groupMergedChildren); + } + merged = true; + } + 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(newChildren, idx)); + } + + /* Compare with GROUP's children */ + if (list_length(suffixElements) == groupChildCount && + rprPatternChildrenEqual(suffixElements, groupContent)) + { + /* + * Match! Absorb suffix by incrementing min and skipping. + */ + child->min += 1; + skipUntil = suffixStart + groupChildCount; + merged = true; + /* Update i to continue suffix check after absorbed elements */ + i = skipUntil - 1; + } + else + { + list_free(suffixElements); + break; + } + + list_free(suffixElements); + } + } + + groupMergedChildren = lappend(groupMergedChildren, child); + } + + if (merged) + newChildren = groupMergedChildren; + } + + pattern->children = newChildren; + + /* Unwrap single-item SEQ */ + if (list_length(pattern->children) == 1) + return (RPRPatternNode *) linitial(pattern->children); + + return pattern; + } + + case RPR_PATTERN_ALT: + { + ListCell *lc2; + + /* Recursively optimize children, flatten nested ALT */ + newChildren = NIL; + foreach(lc, pattern->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); + } + } + + /* Remove duplicate alternatives */ + { + List *uniqueChildren = NIL; + + foreach(lc, newChildren) + { + 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); + } + + pattern->children = uniqueChildren; + } + + /* Unwrap single-item ALT */ + if (list_length(pattern->children) == 1) + return (RPRPatternNode *) linitial(pattern->children); + + return pattern; + } + + case RPR_PATTERN_GROUP: + /* Recursively optimize children */ + newChildren = NIL; + foreach(lc, pattern->children) + { + RPRPatternNode *child = (RPRPatternNode *) lfirst(lc); + + newChildren = lappend(newChildren, optimizeRPRPattern(child)); + } + pattern->children = newChildren; + + /* Quantifier multiplication: (A{m}){n} -> A{m*n} */ + if (list_length(pattern->children) == 1 && !pattern->reluctant) + { + RPRPatternNode *child = (RPRPatternNode *) linitial(pattern->children); + + if (child->nodeType == RPR_PATTERN_VAR && !child->reluctant) + { + if (pattern->max != RPR_QUANTITY_INF && child->max != RPR_QUANTITY_INF) + { + int64 new_min_64 = (int64) pattern->min * child->min; + int64 new_max_64 = (int64) pattern->max * child->max; + + if (new_min_64 < RPR_QUANTITY_INF && new_max_64 < RPR_QUANTITY_INF) + { + child->min = (int) new_min_64; + child->max = (int) new_max_64; + return child; + } + } + } + } + + /* Unwrap GROUP{1,1} */ + if (pattern->min == 1 && pattern->max == 1 && !pattern->reluctant) + { + if (list_length(pattern->children) == 1) + return (RPRPatternNode *) linitial(pattern->children); + + /* Multiple children: convert to SEQ */ + pattern->nodeType = RPR_PATTERN_SEQ; + } + + return pattern; + } + + return pattern; /* keep compiler quiet */ +} + +/* + * scanRPRPattern + * Single-pass scan: collect variable names and count elements. + * + * Collects unique variable names in pattern encounter order (max RPR_VARID_MAX). + * Also counts elements and tracks maximum nesting depth. + */ +static void +scanRPRPattern(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) + { + scanRPRPattern((RPRPatternNode *) lfirst(lc), varNames, numVars, + numElements, depth, maxDepth); + } + break; + + case RPR_PATTERN_GROUP: + /* Recurse into children at increased depth */ + foreach(lc, node->children) + { + scanRPRPattern((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) + { + scanRPRPattern((RPRPatternNode *) lfirst(lc), varNames, numVars, + numElements, depth + 1, maxDepth); + } + break; + } +} + +/* + * 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(); +} + +/* + * fillRPRPattern + * Fill the pattern elements array (second pass). + * + * This traverses the AST and fills in the pre-allocated elements array. + * The idx pointer tracks the current position in the array. + */ +static void +fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth) +{ + ListCell *lc; + RPRPatternElement *elem; + int groupStartIdx; + int altStartIdx; + List *altBranchStarts; + List *altEndPositions; + + if (node == NULL) + return; + + switch (node->nodeType) + { + case RPR_PATTERN_SEQ: + /* Sequence: fill each child in order */ + foreach(lc, node->children) + { + fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth); + } + break; + + case RPR_PATTERN_VAR: + /* Variable: create element with varId */ + 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)++; + break; + + case RPR_PATTERN_GROUP: + groupStartIdx = *idx; + + /* Fill group content at increased depth */ + foreach(lc, node->children) + { + fillRPRPattern((RPRPatternNode *) lfirst(lc), pat, idx, depth + 1); + } + + /* Add group end marker if group has non-trivial quantifier */ + if (node->min != 1 || node->max != 1) + { + elem = &pat->elements[*idx]; + memset(elem, 0, sizeof(RPRPatternElement)); + elem->varId = RPR_VARID_END; + elem->depth = depth; /* parent depth for iteration count */ + elem->min = node->min; + elem->max = (node->max == INT_MAX) ? RPR_QUANTITY_INF : node->max; + elem->next = RPR_ELEMIDX_INVALID; + elem->jump = groupStartIdx; /* jump back to group start */ + if (node->reluctant) + elem->flags |= RPR_ELEM_RELUCTANT; + (*idx)++; + } + break; + + case RPR_PATTERN_ALT: + /* Add alternation start marker */ + altStartIdx = *idx; + 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)++; + + altBranchStarts = NIL; + altEndPositions = NIL; + + /* 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); + + /* Record end position if any elements were added */ + 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) + { + int nextAltStart = lfirst_int(lnext(altBranchStarts, lc)); + + pat->elements[firstElemIdx].jump = nextAltStart; + } + /* Last alternative's jump stays as -1 (default) */ + } + + /* 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); + break; + } +} + +/* + * buildRPRPattern + * Build flat pattern element array from AST. + * + * Optimizes the pattern tree, then uses 2-pass: count elements, allocate and fill. + * Returns NULL if pattern is NULL. + * + * This function is called from createplan.c during plan creation. + */ +RPRPattern * +buildRPRPattern(RPRPatternNode *pattern, List *defineVariableList) +{ + RPRPattern *result; + RPRPatternNode *optimized; + char *varNamesStack[RPR_VARID_MAX + 1]; /* stack array for collection */ + int numVars = 0; + int numElements = 0; + RPRDepth maxDepth = 0; + int idx; + int finIdx; + int i; + RPRPatternElement *finElem; + ListCell *lc; + + if (pattern == NULL) + return NULL; + + /* Optimize the pattern tree (planner phase) */ + optimized = optimizeRPRPattern(pattern); + + /* + * First, populate varNames from defineVariableList in order. + * This ensures varId == defineIdx for all defined variables, + * eliminating the need for varIdToDefineIdx mapping. + */ + foreach(lc, defineVariableList) + { + char *varName = strVal(lfirst(lc)); + + if (numVars >= RPR_VARID_MAX) + ereport(ERROR, + (errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED), + errmsg("too many pattern variables"), + errdetail("Maximum is %d.", RPR_VARID_MAX))); + + varNamesStack[numVars] = varName; + numVars++; + } + + /* + * Pass 1: Single scan to collect variable names and count elements. + * Variables already in varNamesStack (from DEFINE) are skipped. + * Also counts elements and tracks max depth in one traversal. + */ + scanRPRPattern(optimized, varNamesStack, &numVars, + &numElements, 0, &maxDepth); + numElements++; /* +1 for FIN marker */ + + /* Check element count limit */ + 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))); + + /* + * Allocate result structure with makeNode for proper NodeTag. + */ + result = makeNode(RPRPattern); + result->numVars = numVars; + result->maxDepth = maxDepth + 1; /* +1: depth is 0-based, need counts[0..maxDepth] */ + result->numElements = numElements; + + /* Build varNames as char** array */ + 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 separately (zero-init for reserved field) */ + result->elements = palloc0(numElements * sizeof(RPRPatternElement)); + + /* + * Pass 2: Fill elements directly into pre-allocated array. + */ + idx = 0; + fillRPRPattern(optimized, result, &idx, 0); + + /* Set up next pointers for elements that don't have one yet */ + finIdx = numElements - 1; /* FIN marker is at the last position */ + 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; + + /* Compute context absorption eligibility */ + computeAbsorbability(result); + + return result; +} + +/* + * computeAbsorbability + * Determine if pattern supports context absorption optimization. + * + * Context absorption is safe when later matches are guaranteed to be + * suffixes of earlier matches (both row positions AND content). + * + * Sets RPR_ELEM_ABSORBABLE flag on the first element of each absorbable + * branch. A branch is absorbable if: + * - It starts with an unbounded element (greedy-first) + * - It has exactly one unbounded element + * - It's not inside an unbounded GROUP (GREEDY(ALT) case) + * + * pattern->isAbsorbable is set true if ANY branch is absorbable. + */ +static void +computeAbsorbability(RPRPattern *pattern) +{ + int i; + int maxAltDepth = -1; + RPRDepth minUnboundedGroupDepth = UINT8_MAX; + bool hasTopLevelAlt = false; + + pattern->isAbsorbable = false; + + if (pattern->numElements < 2) /* At minimum: one element + FIN */ + return; + + /* + * Scan elements to find ALT structure and unbounded GROUP depth. + */ + for (i = 0; i < pattern->numElements - 1; i++) + { + RPRPatternElement *elem = &pattern->elements[i]; + + if (elem->varId == RPR_VARID_ALT) + { + if (elem->depth > maxAltDepth) + maxAltDepth = elem->depth; + if (i == 0) + hasTopLevelAlt = true; + } + else if (elem->varId == RPR_VARID_END) + { + if (elem->max == INT32_MAX && elem->depth < minUnboundedGroupDepth) + minUnboundedGroupDepth = elem->depth; + } + } + + /* + * Check for GREEDY(ALT) pattern: ALT inside unbounded GROUP. + * In this case, no branch can be absorbable. + */ + if (maxAltDepth >= 0 && maxAltDepth > minUnboundedGroupDepth) + return; + + /* + * For top-level ALT patterns, check each branch separately. + * Set ABSORBABLE flag on branches that qualify. + */ + if (hasTopLevelAlt) + { + int branchStart = 1; /* after ALT marker */ + int patternEnd = pattern->numElements - 1; + + while (branchStart < patternEnd) + { + RPRPatternElement *branchFirst = &pattern->elements[branchStart]; + int branchEnd; + int branchUnbounded = 0; + int j; + bool branchAbsorbable = true; + + /* Find branch end */ + if (branchFirst->jump != RPR_ELEMIDX_INVALID) + branchEnd = branchFirst->jump; + else + branchEnd = patternEnd; + + /* First element of branch must be unbounded */ + if (branchFirst->max != INT32_MAX) + branchAbsorbable = false; + + /* Count unbounded in this branch - must be exactly 1 */ + if (branchAbsorbable) + { + for (j = branchStart; j < branchEnd; j++) + { + RPRPatternElement *elem = &pattern->elements[j]; + + if (elem->varId == RPR_VARID_END) + { + if (elem->max == INT32_MAX) + branchUnbounded++; + } + else if (elem->varId != RPR_VARID_ALT) + { + if (elem->max == INT32_MAX) + branchUnbounded++; + } + } + + if (branchUnbounded != 1) + branchAbsorbable = false; + } + + /* Set flag on branch's first element if absorbable */ + if (branchAbsorbable) + { + branchFirst->flags |= RPR_ELEM_ABSORBABLE; + pattern->isAbsorbable = true; + } + + branchStart = branchEnd; + } + return; + } + + /* + * Non-ALT pattern: check for absorbability. + * + * Case 1: First element is unbounded (A+ B, etc.) + * Case 2: Top-level unbounded GROUP (A B){2,} - GROUP END at depth 0 + * + * In both cases, must have exactly one unbounded element/group. + */ + { + RPRPatternElement *first = &pattern->elements[0]; + int numUnbounded = 0; + bool hasTopLevelUnboundedGroup = false; + RPRElemIdx topLevelGroupEnd = RPR_ELEMIDX_INVALID; + + /* Count unbounded elements and find top-level unbounded GROUP */ + for (i = 0; i < pattern->numElements - 1; i++) + { + RPRPatternElement *elem = &pattern->elements[i]; + + if (elem->varId == RPR_VARID_END) + { + if (elem->max == INT32_MAX) + { + numUnbounded++; + /* Check if this is a top-level GROUP (depth 0) */ + if (elem->depth == 0) + { + hasTopLevelUnboundedGroup = true; + topLevelGroupEnd = i; + } + } + } + else if (elem->varId != RPR_VARID_ALT) + { + if (elem->max == INT32_MAX) + numUnbounded++; + } + } + + /* Must have exactly one unbounded element/group */ + if (numUnbounded != 1) + return; + + /* + * Case 1: First element is unbounded (e.g., A+ B) + */ + if (first->max == INT32_MAX) + { + first->flags |= RPR_ELEM_ABSORBABLE; + pattern->isAbsorbable = true; + return; + } + + /* + * Case 2: Top-level unbounded GROUP that spans entire pattern. + * e.g., (A B){2,} where GROUP END is at the last position before FIN. + * The entire pattern content is inside this unbounded group. + */ + if (hasTopLevelUnboundedGroup && + topLevelGroupEnd == pattern->numElements - 2) + { + first->flags |= RPR_ELEM_ABSORBABLE; + pattern->isAbsorbable = true; + } + } +} 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..8d9097a8f4e 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,18 @@ 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; + + /* Row Pattern DEFINE variable initial names (list of String) */ + List *defineInitial; + /* * 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..95324e7a343 --- /dev/null +++ b/src/include/optimizer/rpr.h @@ -0,0 +1,46 @@ +/*------------------------------------------------------------------------- + * + * rpr.h + * Row Pattern Recognition pattern compilation for planner + * + * Portions Copyright (c) 1996-2025, 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_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