From a8481774babb51b4d5527fab6c134987f9bb49c9 Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Sat, 4 Apr 2026 11:49:32 +0900 Subject: [PATCH] Add tuplestore trim optimization for RPR PREV navigation Advance the tuplestore mark pointer based on the maximum PREV offset found in DEFINE clause expressions, allowing tuplestore_trim() to free rows that PREV can no longer reach. The planner walks DEFINE expressions to find the maximum PREV offset. If all offsets are constants, navMaxOffset is set directly. If any offset is non-constant (parameter or expression), the planner sets RPR_NAV_OFFSET_NEEDS_EVAL and the executor evaluates all PREV offsets at init time. The executor then advances the mark to (currentpos - navMaxOffset) each row. NEXT offsets are ignored since they look forward and do not affect trim. RPR_NAV_OFFSET_RETAIN_ALL is reserved for future navigation functions (FIRST/LAST) that require the entire partition. --- src/backend/executor/nodeWindowAgg.c | 136 ++++++++++++++++++++++-- src/backend/optimizer/plan/createplan.c | 101 ++++++++++++++++++ src/include/nodes/execnodes.h | 1 + src/include/nodes/plannodes.h | 9 ++ src/include/optimizer/rpr.h | 9 ++ 5 files changed, 246 insertions(+), 10 deletions(-) diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c index d2fffe0fce6..186029df1d9 100644 --- a/src/backend/executor/nodeWindowAgg.c +++ b/src/backend/executor/nodeWindowAgg.c @@ -244,6 +244,10 @@ static void update_reduced_frame(WindowObject winobj, int64 pos); /* Forward declarations - NFA row evaluation */ static bool nfa_evaluate_row(WindowObject winobj, int64 pos, bool *varMatched); +/* Forward declarations - navigation offset evaluation */ +static bool collect_prev_offset_walker(Node *node, List **offsets); +static void eval_nav_max_offset(WindowAggState *winstate, List *defineClause); + /* * Not null info bit array consists of 2-bit items */ @@ -934,12 +938,18 @@ eval_windowaggregates(WindowAggState *winstate) if (rpr_is_defined(winstate)) { /* - * If RPR is used, it is possible PREV wants to look at the - * previous row. So the mark pos should be frameheadpos - 1 - * unless it is below 0. + * If RPR is used, PREV may need to look at rows before the frame + * head. Adjust mark by navMaxOffset if known, otherwise retain + * from position 0. */ - markpos -= 1; - if (markpos < 0) + if (winstate->navMaxOffset >= 0) + { + if (markpos > winstate->navMaxOffset) + markpos -= winstate->navMaxOffset; + else + markpos = 0; + } + else markpos = 0; } WinSetMarkPosition(agg_winobj, markpos); @@ -1269,12 +1279,15 @@ prepare_tuplestore(WindowAggState *winstate) if (winstate->nav_winobj) { /* - * Allocate a mark pointer pinned at position 0 so that the tuplestore - * never truncates rows that a PREV(expr, N) might need. + * Allocate mark and read pointers for PREV/NEXT navigation. + * + * If navMaxOffset >= 0, we advance the mark to (currentpos - + * navMaxOffset) as rows are processed, allowing tuplestore_trim() to + * free rows that are no longer reachable. * - * XXX This retains the entire partition in the tuplestore. If the - * DEFINE clause only uses PREV/NEXT with small constant offsets, we - * could advance the mark to (currentpos - max_offset) instead. + * If navMaxOffset < 0 (RPR_NAV_OFFSET_NEEDS_EVAL or + * RPR_NAV_OFFSET_RETAIN_ALL), the mark stays at 0, retaining the + * entire partition in the tuplestore. */ winstate->nav_winobj->markptr = tuplestore_alloc_read_pointer(winstate->buffer, 0); @@ -2512,6 +2525,24 @@ ExecWindowAgg(PlanState *pstate) if (winstate->grouptail_ptr >= 0) update_grouptailpos(winstate); + /* + * Advance RPR navigation mark pointer if possible, so that + * tuplestore_trim() can free rows no longer reachable by PREV. + */ + if (winstate->nav_winobj && + winstate->rpPattern != NULL && + winstate->navMaxOffset >= 0) + { + int64 navmarkpos; + + if (winstate->currentpos > winstate->navMaxOffset) + navmarkpos = winstate->currentpos - winstate->navMaxOffset; + else + navmarkpos = 0; + if (navmarkpos > winstate->nav_winobj->markpos) + WinSetMarkPosition(winstate->nav_winobj, navmarkpos); + } + /* * Truncate any no-longer-needed rows from the tuplestore. */ @@ -2960,6 +2991,10 @@ ExecInitWindowAgg(WindowAgg *node, EState *estate, int eflags) winstate->rpSkipTo = node->rpSkipTo; /* Set up row pattern recognition PATTERN clause (compiled NFA) */ winstate->rpPattern = node->rpPattern; + /* Set up max PREV offset for tuplestore trim */ + winstate->navMaxOffset = node->navMaxOffset; + if (winstate->navMaxOffset == RPR_NAV_OFFSET_NEEDS_EVAL) + eval_nav_max_offset(winstate, node->defineClause); /* Calculate NFA state size and allocate cycle detection bitmap */ if (node->rpPattern != NULL) @@ -3872,6 +3907,87 @@ put_notnull_info(WindowObject winobj, int64 pos, int argno, bool isnull) mbp[bpos] = mb; } +/* + * collect_prev_offset_walker + * Walk expression tree to collect PREV offset_arg expressions. + */ +static bool +collect_prev_offset_walker(Node *node, List **offsets) +{ + if (node == NULL) + return false; + + if (IsA(node, RPRNavExpr)) + { + RPRNavExpr *nav = (RPRNavExpr *) node; + + if (nav->kind == RPR_NAV_PREV && nav->offset_arg != NULL) + *offsets = lappend(*offsets, nav->offset_arg); + + /* Don't walk into RPRNavExpr children */ + return false; + } + + return expression_tree_walker(node, collect_prev_offset_walker, offsets); +} + +/* + * eval_nav_max_offset + * Evaluate non-constant PREV offsets at executor init time. + * + * Called when the planner set navMaxOffset to RPR_NAV_OFFSET_NEEDS_EVAL + * because some PREV offset contains a parameter or non-foldable expression. + * Walks the original defineClause expression trees, compiles and evaluates + * each PREV offset_arg, and stores the maximum in winstate->navMaxOffset. + */ +static void +eval_nav_max_offset(WindowAggState *winstate, List *defineClause) +{ + ExprContext *econtext = winstate->ss.ps.ps_ExprContext; + List *offsets = NIL; + ListCell *lc; + int64 maxOffset = 0; + + /* Collect all PREV offset expressions from DEFINE clause */ + foreach(lc, defineClause) + { + TargetEntry *te = (TargetEntry *) lfirst(lc); + + collect_prev_offset_walker((Node *) te->expr, &offsets); + } + + /* Evaluate each offset and find maximum */ + foreach(lc, offsets) + { + Expr *offset_expr = (Expr *) lfirst(lc); + ExprState *estate; + Datum val; + bool isnull; + int64 offset; + + estate = ExecInitExpr(offset_expr, (PlanState *) winstate); + val = ExecEvalExprSwitchContext(estate, econtext, &isnull); + + /* + * NULL or negative offsets will cause a runtime error when PREV is + * actually evaluated. For trim purposes, treat them as 0. + */ + if (isnull) + continue; + + offset = DatumGetInt64(val); + if (offset < 0) + continue; + + if (offset > maxOffset) + maxOffset = offset; + } + + winstate->navMaxOffset = maxOffset; + + list_free(offsets); +} + /* * rpr_is_defined * return true if Row pattern recognition is defined. diff --git a/src/backend/optimizer/plan/createplan.c b/src/backend/optimizer/plan/createplan.c index 9ac24cc222d..ee2d53b5924 100644 --- a/src/backend/optimizer/plan/createplan.c +++ b/src/backend/optimizer/plan/createplan.c @@ -2461,6 +2461,104 @@ create_minmaxagg_plan(PlannerInfo *root, MinMaxAggPath *best_path) return plan; } +/* + * nav_max_offset_walker + * Walk expression tree to find the maximum PREV offset. + * + * Only PREV is relevant for tuplestore trim since it looks backward; + * NEXT looks forward and never references already-trimmed rows. + * + * Returns true (to stop walking) if a non-constant PREV offset is found, + * in which case *maxOffset is set to -1. Otherwise accumulates the + * maximum constant offset value. + */ +static bool +nav_max_offset_walker(Node *node, int64 *maxOffset) +{ + if (node == NULL) + return false; + + if (IsA(node, RPRNavExpr)) + { + RPRNavExpr *nav = (RPRNavExpr *) node; + + /* Only PREV looks backward; NEXT is irrelevant for trim */ + if (nav->kind == RPR_NAV_PREV) + { + int64 offset; + + if (nav->offset_arg == NULL) + { + /* 1-arg form: implicit offset of 1 */ + offset = 1; + } + else if (IsA(nav->offset_arg, Const)) + { + Const *c = (Const *) nav->offset_arg; + + if (c->constisnull) + { + /* + * NULL offset causes a runtime error, so this path is + * never actually reached during execution. Use 0 as a + * safe placeholder for planning purposes. + */ + offset = 0; + } + else + { + offset = DatumGetInt64(c->constvalue); + if (offset < 0) + offset = 0; /* negative offset causes runtime error */ + } + } + else + { + /* + * Non-constant offset (Param, stable function, etc.). The + * parser guarantees offset is a runtime constant, so it can + * be evaluated at executor init time. + */ + *maxOffset = RPR_NAV_OFFSET_NEEDS_EVAL; + return true; /* stop walking */ + } + + if (offset > *maxOffset) + *maxOffset = offset; + } + + /* Don't walk into RPRNavExpr children - offset_arg already handled */ + return false; + } + + return expression_tree_walker(node, nav_max_offset_walker, maxOffset); +} + +/* + * compute_nav_max_offset + * Compute the maximum PREV offset from DEFINE clause expressions. + * + * Returns the maximum constant offset found, or -1 if any PREV offset + * cannot be determined statically. NEXT offsets are ignored since they + * look forward and don't affect tuplestore trim. + */ +static int64 +compute_nav_max_offset(List *defineClause) +{ + int64 maxOffset = 0; + ListCell *lc; + + foreach(lc, defineClause) + { + TargetEntry *te = (TargetEntry *) lfirst(lc); + + if (nav_max_offset_walker((Node *) te->expr, &maxOffset)) + return RPR_NAV_OFFSET_NEEDS_EVAL; + } + + return maxOffset; +} + /* * create_windowagg_plan * @@ -6678,6 +6776,9 @@ make_windowagg(List *tlist, WindowClause *wc, node->defineClause = defineClause; + /* Compute max PREV offset for tuplestore trim optimization */ + node->navMaxOffset = compute_nav_max_offset(defineClause); + plan->targetlist = tlist; plan->lefttree = lefttree; plan->righttree = NULL; diff --git a/src/include/nodes/execnodes.h b/src/include/nodes/execnodes.h index 74a6b682132..ff6d7d70a60 100644 --- a/src/include/nodes/execnodes.h +++ b/src/include/nodes/execnodes.h @@ -2692,6 +2692,7 @@ typedef struct WindowAggState TupleTableSlot *temp_slot_2; /* RPR navigation */ + int64 navMaxOffset; /* max PREV offset; see RPR_NAV_OFFSET_* */ struct WindowObjectData *nav_winobj; /* winobj for RPR nav fetch */ int64 nav_slot_pos; /* position cached in nav_slot, or -1 */ TupleTableSlot *nav_slot; /* slot for PREV/NEXT target row */ diff --git a/src/include/nodes/plannodes.h b/src/include/nodes/plannodes.h index ceaab4d97b0..27a2e7b48c7 100644 --- a/src/include/nodes/plannodes.h +++ b/src/include/nodes/plannodes.h @@ -1386,6 +1386,15 @@ typedef struct WindowAgg /* Row Pattern DEFINE clause (list of TargetEntry) */ List *defineClause; + /* + * Maximum PREV offset for tuplestore mark optimization. >= 0: statically + * determined max offset (mark = currentpos - offset). + * RPR_NAV_OFFSET_NEEDS_EVAL: has non-constant offset; evaluate at + * executor init. RPR_NAV_OFFSET_RETAIN_ALL: must retain entire partition + * (no trim possible). + */ + int64 navMaxOffset; + /* * 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 index e78092678bb..91148f6c574 100644 --- a/src/include/optimizer/rpr.h +++ b/src/include/optimizer/rpr.h @@ -55,6 +55,15 @@ #define RPRElemIsFin(e) ((e)->varId == RPR_VARID_FIN) #define RPRElemCanSkip(e) ((e)->min == 0) +/* + * navMaxOffset sentinel values. + * Non-negative values represent a statically determined maximum PREV offset. + */ +#define RPR_NAV_OFFSET_NEEDS_EVAL (-1) /* has non-constant PREV offset; + * evaluate at executor init */ +#define RPR_NAV_OFFSET_RETAIN_ALL (-2) /* must retain entire partition + * (e.g., future FIRST/LAST) */ + extern List *collectPatternVariables(RPRPatternNode *pattern); extern void buildDefineVariableList(List *defineClause, List **defineVariableList); -- 2.50.1 (Apple Git-155)