v50-0001-refactor-absorbability-helper-functions.nocfbot
application/octet-stream
Filename: v50-0001-refactor-absorbability-helper-functions.nocfbot
Type: application/octet-stream
Part: 0
Message:
Re: Row pattern recognition
From 751ef8c94f08d64f01e49045b58bdd72c3fdf042 Mon Sep 17 00:00:00 2001
From: jian he <jian.universality@gmail.com>
Date: Wed, 24 Jun 2026 09:54:29 +0800
Subject: [PATCH v50 1/1] refactor absorbability helper functions
Rename isUnboundedStart() to start_with_unbounded_quantifier() and
isFixedLengthChildren() to isFixedQuantifier() for clarity.
Rework start_with_unbounded_quantifier() to accept an RPRPatternElement *
directly instead of an index, and restructure its body as an explicit
if/else chain over element kinds (VAR, BEGIN, ALT/FIN, END) rather than
two loosely-coupled early-return checks.
Fix subgroup traversal in isFixedQuantifier() to use elem->jump - 1 to
locate the matching END element directly, replacing the previous loop
that walked next pointers.
Move isAbsorbable initialization from finalizeRPRPattern() into
makeRPRPattern(), and guard the computeAbsorbabilityRecursive() call in
computeAbsorbability() so it is only entered when the first element is
an ALT or has an unbounded quantifier.
Use palloc_array/palloc0_array in makeRPRPattern(). Remove the redundant
"T_RPRPattern" comment on the NodeTag field. Update README.rpr and
in-code comments to reflect the new function names.
---
src/backend/executor/README.rpr | 4 +-
src/backend/optimizer/plan/rpr.c | 179 +++++++++++++++++--------------
src/include/nodes/plannodes.h | 8 +-
3 files changed, 106 insertions(+), 85 deletions(-)
diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr
index 9275e265d4..f25abd78fe 100644
--- a/src/backend/executor/README.rpr
+++ b/src/backend/executor/README.rpr
@@ -415,10 +415,10 @@ absorption optimization and sets flags on the relevant elements:
Eligibility conditions:
- (1) SKIP PAST LAST ROW (not NEXT ROW)
+ (1) SKIP PAST LAST ROW (not SKIP TO NEXT ROW)
(2) Frame end is UNBOUNDED FOLLOWING
-Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive):
+Structural conditions (start_with_unbounded_quantifier + computeAbsorbabilityRecursive):
Case 1: Simple VAR+ (e.g., A+)
-> ABSORBABLE | ABSORBABLE_BRANCH set on the VAR
diff --git a/src/backend/optimizer/plan/rpr.c b/src/backend/optimizer/plan/rpr.c
index fac3d7bcf3..657798aa37 100644
--- a/src/backend/optimizer/plan/rpr.c
+++ b/src/backend/optimizer/plan/rpr.c
@@ -23,7 +23,7 @@
* - RPR_ELEM_ABSORBABLE_BRANCH: marks the absorbable region
*
* See computeAbsorbability() and the detailed comments before
- * isUnboundedStart() for the full design explanation.
+ * start_with_unbounded_quantifier() for the full design explanation.
*
* Portions Copyright (c) 1996-2026, PostgreSQL Global Development Group
* Portions Copyright (c) 1994, Regents of the University of California
@@ -82,9 +82,10 @@ static bool fillRPRPattern(RPRPatternNode *node, RPRPattern *pat,
int *idx, RPRDepth depth);
static void finalizeRPRPattern(RPRPattern *result);
-static bool isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx,
- RPRDepth scopeDepth);
-static bool isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx);
+static bool isFixedQuantifier(RPRPattern *pattern, RPRElemIdx idx,
+ RPRDepth scopeDepth);
+static bool start_with_unbounded_quantifier(RPRPattern *pattern,
+ RPRPatternElement *elem);
static void computeAbsorbabilityRecursive(RPRPattern *pattern,
RPRElemIdx startIdx,
bool *hasAbsorbable);
@@ -1097,13 +1098,17 @@ makeRPRPattern(int numVars, int numElements, RPRDepth maxDepth,
/* Copy varNames (pattern must have at least one variable) */
Assert(numVars > 0);
- result->varNames = palloc(numVars * sizeof(char *));
+ result->varNames = palloc_array(char *, numVars);
+
for (i = 0; i < numVars; i++)
result->varNames[i] = pstrdup(varNamesStack[i]);
/* Allocate elements array (zero-init for reserved fields) */
Assert(numElements >= 2);
- result->elements = palloc0(numElements * sizeof(RPRPatternElement));
+ result->elements = palloc0_array(RPRPatternElement, numElements);
+
+ /* Initialize absorption flag */
+ result->isAbsorbable = false;
return result;
}
@@ -1214,7 +1219,7 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de
/* Add group end marker if group has non-trivial quantifier (not {1,1}) */
if (node->min != 1 || node->max != 1)
{
- RPRPatternElement *beginElem = &pat->elements[beginIdx];
+ RPRPatternElement *elem = &pat->elements[beginIdx];
RPRPatternElement *endElem = &pat->elements[*idx];
memset(endElem, 0, sizeof(RPRPatternElement));
@@ -1240,7 +1245,7 @@ fillRPRPatternGroup(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth de
(*idx)++;
/* Set BEGIN skip pointer (next is set by finalize) */
- beginElem->jump = *idx; /* skip: go to after END */
+ elem->jump = *idx; /* skip: go to after END */
}
return (node->min == 0 || bodyNullable);
@@ -1381,12 +1386,10 @@ fillRPRPattern(RPRPatternNode *node, RPRPattern *pat, int *idx, RPRDepth depth)
/*
* finalizeRPRPattern
- * Finalize pattern structure after filling elements.
+ * Finalize RPRPattern node after filling elements.
*
- * This performs:
- * 1. Initialize absorption flag to false
- * 2. Set up next pointers for sequential flow
- * 3. Add FIN marker at the end
+ * 1. Set up next pointers for sequential flow
+ * 2. Add FIN marker at the end
*/
static void
finalizeRPRPattern(RPRPattern *result)
@@ -1395,9 +1398,6 @@ finalizeRPRPattern(RPRPattern *result)
int i;
RPRPatternElement *finElem;
- /* Initialize absorption flag */
- result->isAbsorbable = false;
-
/* Set up next pointers for elements that don't have one */
for (i = 0; i < finIdx; i++)
{
@@ -1504,8 +1504,8 @@ finalizeRPRPattern(RPRPattern *result)
*/
/*
- * isFixedLengthChildren
- * Check if all children at scopeDepth have fixed-length quantifiers
+ * isFixedQuantifier
+ * Check if all children at scopeDepth have fixed quantifiers
* (min == max), recursively for nested subgroups.
*
* A fixed-length group is semantically equivalent to unrolling each child
@@ -1519,11 +1519,11 @@ finalizeRPRPattern(RPRPattern *result)
* ALT elements are rejected (alternation inside absorbable group is
* not supported).
*
- * Returns true if all children are fixed-length, stopping at the END
+ * Returns true if all children quantifier are fixed, stopping at the END
* element at scopeDepth - 1.
*/
static bool
-isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth)
+isFixedQuantifier(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth)
{
RPRPatternElement *e = &pattern->elements[idx];
@@ -1541,13 +1541,11 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth)
RPRElemIdx childIdx = e->next;
/* Recurse into subgroup children at scopeDepth + 1 */
- if (!isFixedLengthChildren(pattern, childIdx, scopeDepth + 1))
+ if (!isFixedQuantifier(pattern, childIdx, scopeDepth + 1))
return false;
/* Advance past the subgroup to its END element */
- e = &pattern->elements[e->next];
- while (e->depth > scopeDepth)
- e = &pattern->elements[e->next];
+ e = &pattern->elements[e->jump - 1];
/* e is now the END at scopeDepth; check its quantifier */
Assert(RPRElemIsEnd(e) && e->depth == scopeDepth);
@@ -1568,11 +1566,11 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth)
}
/*
- * isUnboundedStart
+ * start_with_unbounded_quantifier
* Check if the element at idx starts an unbounded greedy sequence.
*
* For context absorption to work, the sequence starting at idx must be:
- * - Unbounded (max = infinity)
+ * - Unbounded (max = RPR_QUANTITY_INF)
* - Greedy (not reluctant)
* - At the start of current scope
*
@@ -1600,50 +1598,73 @@ isFixedLengthChildren(RPRPattern *pattern, RPRElemIdx idx, RPRDepth scopeDepth)
* - (A B{2,5})+ (min != max inside group)
*/
static bool
-isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
+start_with_unbounded_quantifier(RPRPattern *pattern, RPRPatternElement *elem)
{
- RPRPatternElement *elem = &pattern->elements[idx];
- RPRDepth startDepth = elem->depth;
+ RPRDepth startDepth;
RPRPatternElement *e;
+ RPRElemIdx idx;
- /* Case 1: Simple unbounded VAR at start (greedy only) */
- if (RPRElemIsVar(elem) && elem->max == RPR_QUANTITY_INF &&
- !RPRElemIsReluctant(elem))
+ if (RPRElemIsAlt(elem) || RPRElemIsFin(elem))
+ return false;
+ else if (RPRElemIsVar(elem))
{
- /* Set both flags on first element */
- elem->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE;
- return true;
+ /* Case 1: Simple unbounded VAR at start (greedy only) */
+ if (elem->max == RPR_QUANTITY_INF && !RPRElemIsReluctant(elem))
+ {
+ /* Set both flags on first element */
+ elem->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE;
+
+ return true;
+ }
+ else
+ return false;
}
+ else if (RPRElemIsBegin(elem))
+ {
+ idx = elem->next;
- /*
- * Case 2: Unbounded GROUP with fixed-length children. Each child must
- * have min == max (recursively for nested subgroups), ensuring a fixed
- * step size per iteration so that count-dominance holds.
- */
- if (!isFixedLengthChildren(pattern, idx, startDepth))
- return false;
+ startDepth = (&pattern->elements[idx])->depth;
- /* Find the END element at startDepth - 1 */
- e = &pattern->elements[idx];
- while (e->depth >= startDepth)
- e = &pattern->elements[e->next];
+ /*
+ * Case 2: Unbounded GROUP with children that each have a fixed
+ * quantifier. Each child must have min == max (recursively for nested
+ * subgroups), ensuring a fixed step size per iteration so that
+ * count-dominance holds.
+ */
+ if (!isFixedQuantifier(pattern, idx, startDepth))
+ return false;
- /* END must be unbounded greedy */
- if (e->depth == startDepth - 1 &&
- RPRElemIsEnd(e) && e->max == RPR_QUANTITY_INF &&
- !RPRElemIsReluctant(e))
- {
- Assert(e->jump == idx); /* END points back to first child */
-
- /* Set ABSORBABLE_BRANCH on all children, ABSORBABLE on END only */
- for (e = elem; !RPRElemIsEnd(e) || e->depth >= startDepth;
- e = &pattern->elements[e->next])
- e->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
- e->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE;
- return true;
+ /* Find the END element at startDepth - 1 */
+ e = &pattern->elements[elem->jump - 1];
+
+ /* END must be unbounded greedy */
+ if (e->depth == startDepth - 1 &&
+ RPRElemIsEnd(e) && e->max == RPR_QUANTITY_INF &&
+ !RPRElemIsReluctant(e))
+ {
+ Assert(e->jump == idx); /* END points back to first child */
+
+ /* Set ABSORBABLE_BRANCH on all children, ABSORBABLE on END only */
+ for (e = elem; !RPRElemIsEnd(e) || e->depth >= startDepth;
+ e = &pattern->elements[e->next])
+ e->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
+
+ e->flags |= RPR_ELEM_ABSORBABLE_BRANCH | RPR_ELEM_ABSORBABLE;
+
+ /* set BEGIN flag also */
+ elem->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
+
+ return true;
+ }
+ else
+ return false;
}
+ else
+ {
+ elog(ERROR, "END element should not reached in start_with_unbounded_quantifier");
- return false;
+ return false;
+ }
}
/*
@@ -1657,7 +1678,7 @@ isUnboundedStart(RPRPattern *pattern, RPRElemIdx idx)
* If BEGIN, skips to first child.
*
* Otherwise (VAR), checks if the element starts an unbounded sequence via
- * isUnboundedStart.
+ * start_with_unbounded_quantifier.
*/
static void
computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
@@ -1671,7 +1692,7 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
{
/* ALT: recursively check each branch */
RPRElemIdx branchIdx = elem->next;
- RPRPatternElement *branchFirst;
+ RPRPatternElement *branchElement;
bool branchAbsorbable;
while (branchIdx != RPR_ELEMIDX_INVALID)
@@ -1679,10 +1700,10 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
branchAbsorbable = false;
Assert(branchIdx < pattern->numElements);
- branchFirst = &pattern->elements[branchIdx];
+ branchElement = &pattern->elements[branchIdx];
/* Stop if element is outside ALT scope (not a branch) */
- if (branchFirst->depth <= elem->depth)
+ if (branchElement->depth <= elem->depth)
break;
/* Recursively check this branch */
@@ -1692,7 +1713,7 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
*hasAbsorbable = true;
}
- branchIdx = branchFirst->jump;
+ branchIdx = branchElement->jump;
}
/* Mark ALT element if any branch is absorbable */
@@ -1707,11 +1728,8 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
* B{3}){2})+). If that fails, skip to first child and recurse as
* before.
*/
- if (isUnboundedStart(pattern, elem->next))
- {
+ if (start_with_unbounded_quantifier(pattern, elem))
*hasAbsorbable = true;
- elem->flags |= RPR_ELEM_ABSORBABLE_BRANCH;
- }
else
{
computeAbsorbabilityRecursive(pattern, elem->next, hasAbsorbable);
@@ -1726,11 +1744,8 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
/* Should never reach END - structural invariant of pattern parse tree */
Assert(!RPRElemIsEnd(elem));
- /* Non-ALT, non-BEGIN: check if unbounded start */
- if (isUnboundedStart(pattern, startIdx))
- {
+ if (start_with_unbounded_quantifier(pattern, elem))
*hasAbsorbable = true;
- }
}
}
@@ -1755,9 +1770,9 @@ computeAbsorbabilityRecursive(RPRPattern *pattern, RPRElemIdx startIdx,
*
* Examples:
* A+ B C - absorbable (A gets both flags)
- * (A B)+ C - absorbable (A,B,END get BRANCH, END gets ABSORBABLE)
- * A B+ - NOT absorbable (unbounded not at start)
- * A+? B C - NOT absorbable (reluctant quantifier)
+ * (A B)+ C - absorbable (A,B, END marked as RPR_ELEM_ABSORBABLE_BRANCH, END also marked as RPR_ELEM_ABSORBABLE)
+ * A B+ - not absorbable (unbounded not at start)
+ * A+? B C - not absorbable (reluctant quantifier)
* (A+ B+)+ - only first A+ on first iteration (nested unbounded not supported)
* A+ | B+ - both branches absorbable independently
* A+ | C D - only A+ branch absorbable (C D branch not absorbable)
@@ -1772,8 +1787,14 @@ computeAbsorbability(RPRPattern *pattern)
Assert(pattern->numElements >= 2);
/* Start recursion from first element */
- computeAbsorbabilityRecursive(pattern, 0, &hasAbsorbable);
- pattern->isAbsorbable = hasAbsorbable;
+ if (RPRElemIsAlt(&pattern->elements[0]) ||
+ pattern->elements[0].max == RPR_QUANTITY_INF)
+ {
+ computeAbsorbabilityRecursive(pattern, 0,
+ &hasAbsorbable);
+
+ pattern->isAbsorbable = hasAbsorbable;
+ }
}
/*
@@ -1914,7 +1935,7 @@ buildRPRPattern(WindowClause *wc, bool hasMatchStartDependent)
idx = 0;
fillRPRPattern(optimized, result, &idx, 0);
- /* Finalize: set up next pointers, flags, and add FIN marker */
+ /* Finalize: set up next pointers and add FIN marker */
finalizeRPRPattern(result);
/*
diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h
index 2b37c8f226..cd6092ff96 100644
--- a/src/include/nodes/plannodes.h
+++ b/src/include/nodes/plannodes.h
@@ -1291,7 +1291,7 @@ typedef struct RPRPattern
*/
pg_node_attr(custom_copy_equal, custom_read_write, no_equal)
- NodeTag type; /* T_RPRPattern */
+ NodeTag type;
int numVars; /* number of pattern variables */
char **varNames; /* array of variable names (DEFINE order
* first) */
@@ -1309,18 +1309,18 @@ typedef struct RPRPattern
* pattern toward that form first -- so e.g. A B (A B)+ is merged to
* (A B){2,} and then judged absorbable.
*
- * computeAbsorbability() marks the absorbable cases (see isUnboundedStart):
+ * computeAbsorbability() marks the absorbable cases (see
+ * computeAbsorbabilityRecursive and subroutines):
* - simple unbounded VAR at the start: A+ B C
* - unbounded GROUP with fixed-length children: (A B)+, (A B{2})+
* - top-level ALT with independently absorbable branches: A+ | B+
- * (handled in computeAbsorbabilityRecursive)
*
* Not absorbable: an unbounded element not at the start (A B+), a
* reluctant quantifier (A+?), or an ALT inside a group ((A|B)+) -- there
* different start positions yield different match contents, so later
* matches are not suffixes of earlier ones.
*/
- bool isAbsorbable; /* true if pattern supports context absorption */
+ bool isAbsorbable;
} RPRPattern;
/* ----------------
--
2.34.1