From e9270fcff5fd66c0cfcbe43402d7c12ac7be571c Mon Sep 17 00:00:00 2001 From: Henson Choi Date: Mon, 28 Sep 2026 15:53:22 +0900 Subject: [PATCH 09/10] Bring the row pattern recognition documentation up to date Documentation only; no code changes. 1. SGML documentation SELECT reference. - row_pattern_common_syntax was listed inside both forms of the frame_clause synopsis. The grammar places it beside the frame clause in the window specification, not within it, so move it to the window_definition synopsis, which did not mention it at all. - The note on the limit of 240 pattern variables also said that exceeding it raises an error, while the nesting depth limit in the next sentence raises one too and did not say so, inviting the reader to conclude that it does not. Drop the sentence. - Add a paragraph saying that a window using row pattern recognition gets neither of two prosupport-driven optimizations: a filter on a monotonic window function is not pushed down as a run condition, and the support functions are not allowed to replace the frame options. A reader comparing EXPLAIN output with and without PATTERN otherwise has no way to tell why the Run Condition is missing. Query results are not affected, only the cost of evaluating the window. - State the restrictions and behavior the page did not: duplicate DEFINE names, the pattern element limit and outer references. Tutorial (advanced.sgml). Strip the trailing space from the heading line of the row pattern example output. It was the only line under doc/src/sgml with trailing whitespace, so git diff --check flagged the patch; the rendered output is unchanged. Also say that GROUPING() is not allowed in DEFINE and what the empty frame of an empty match is. Window functions (func-window.sgml). Add the NULL rules of compound navigation, the shape it requires and the column reference a navigation argument needs. EXPLAIN (perform.sgml). Add the resolved bound under ANALYZE and the cases that print no absorption markers. 2. README.rpr: statements that no longer matched the code README.rpr, read back from the code, had a number of statements that no longer matched it. - A group's END loops back to the group's first child, not to its BEGIN; BEGIN.jump names the group's own END, and the zero-match skip leaves through END.next, so the element tables and the paragraph about redirecting a branch-terminal skip past the alternation are rewritten, and IX-6 now says that entering a group through its BEGIN marks that END visited. - Skipped contexts are pruned by nfa_prune_skipped_contexts() from ExecRPRProcessRow(), not on reaching FIN. A context is judged matched by matchedState rather than by comparing matchEndRow with matchStartRow. - The reduced frame is driven once per row from ExecWindowAgg() through ensure_reduced_frame(), and ExecRPRProcessRow() derives the frame bound itself. - Parse analysis no longer adds the columns a DEFINE clause reads to the targetlist; the planner asks for them, as it does for havingQual. - The count-dominance cover test, the Phase 1 rewrite list and the appendix diagram are corrected too, and nfa_add_state_unique() and nfa_reevaluate_dependent_vars() are cited by their current names, nfa_append_state_unique() and nfa_invalidate_dependent_vars(). - Statements the code changes of this series left stale are corrected: XIV-5 describes mark_define_columns(), which runs before set_using_names(); the remaining BEGIN.jump descriptions and the Appendix B element tables give the group's own END; III-4 counts the whole-row forms among what is decided before name resolution; V-2 and Chapter VII match matchedState, matchEndRow and nfa_match(); IX-6 is re-wrapped; XIII-1, XIII-4 and XIV-7 name grouping_planner(), the join-alias flattening copy of the navigation argument rule, and collapse_define_join_vars(); and the "Related code" list gains initsplan.c and var.c. - Every statement was then checked against the code, and the text is corrected where it disagreed: the match phase evaluates a DEFINE lazily (VII), the pattern array is copied rather than serialized with memcpy (XII-1), a zero frame end offset is rejected only at execution (III-1, X-4), the worked example creates each context where the code does (XI-4), the element flag rationales follow the cycle detection as it now works (IV-4, IV-4b), pull-up and join alias expansion wrap a navigation argument by different rules (XIII-4), GROUP Vars come from parse analysis (XIV-7), and duplicated paragraphs in XIII-4 and XIV-7 are merged. XIII-5 is replaced by a section on how a DEFINE condition is preprocessed and evaluated as a qual, which now also holds the volatility rule and says where that check runs. Chapter II shows the DEFINE and PATTERN halves of the planner side by side. - The R020 summary no longer says it supports ALL ROWS PER MATCH only: the window form has no ROWS PER MATCH clause, and its output corresponds to ONE ROW PER MATCH WITH UNMATCHED ROWS. The qual section also says why a volatile expression the DEFINE clause shares with GROUP BY passes the volatility check: the pattern match reads the grouping step's output. 3. README.rpr: what it was missing - The chapters that already existed gain the range checks on braced quantifiers, how "A*|B" lexes as one operator token and is split back into an alternation, the cursor locations of the frame diagnostics, why the DEFINE restrictions key on p_rpr_define rather than on p_expr_kind, and where and why WITH RECURSIVE rejects row pattern recognition. - New sections cover the rules for column references in a DEFINE condition (III-4), how PREV, NEXT, FIRST and LAST are bound before any catalog lookup (III-5), query jumbling of DEFINE variable names (III-6), how the navigation slot swap is handled by the interpreter and by JIT (VI-4), and why window aggregates are restarted on every row (X-5). Adding VI-4 renumbers the former VI-4 through VI-6 as VI-5 through VI-7, and the references inside the file follow. - Paragraphs added to existing sections cover the agreement between Phases 2 and 4 on the element count, how the rewrites avoid the RPR_QUANTITY_INF sentinel, count saturation, finalization at partition end, the DEFINE evaluation context, navigation offset defaults and navno numbering, nav_winobj, how the frame accessors clip to the reduced frame, the AFTER MATCH SKIP default, and the run-time check on a zero frame end offset. The syntax sketch shows the offset FOLLOWING frame end alongside UNBOUNDED FOLLOWING. - Mechanisms the code has and the file did not describe are added: the nesting rule for depth, the absorbability walk over alternations, the context list order, the non-reentrant navigation slot swap and the compound navigation rewrite it relies on, the arrival increment on a skip that lands on an outer END, the matchUpdated cut within one DFS, how an empty match reaches the frame accessors, the per-scan nav offset state, how pull-up reaches a DEFINE clause, the general column naming rules the DEFINE name reservation rests on, the scope of making '|' a self token, and the EXPLAIN ANALYZE counters (XIV-9). - The title spells out RPR, the audience paragraph is shortened, and the "Related code" list is grouped by the phase each file serves. 4. README.rpr: two new chapters - Chapter XIII collects the contracts row pattern recognition places on the rest of the planner: who owns the DEFINE expression tree and must empty it when a window will not run, why subquery output removal needs no protection for a DEFINE-only column, grouping, navigation arguments under subquery pull-up, the volatility restriction, the optimizations the SGML paragraph above describes, and Var fixup, parameter sets and costing. - Chapter XIV covers the two printers, pg_get_viewdef() and EXPLAIN, which spell a pattern differently on purpose, and what each must do for its output to be correct: the absorption markers, quoting of a pattern variable named permute, reluctance on a fixed count, keeping the unqualified column names in DEFINE resolvable on re-parse, qualifying user functions named like a navigation operation, GROUP Vars in DEFINE, and the Nav Mark lines. Note on section numbers: the numbers in this message are those of README.rpr before the next commit, "Reorder README.rpr by processing order", renumbers its chapters. The three source comments that cite README.rpr by section (execRPR.c, rpr.c and rpr.h) were corrected earlier in the series and already use the numbers the next commit gives, so until then they point ahead of the file. Author: Henson Choi Author: jian he --- doc/src/sgml/advanced.sgml | 50 +- doc/src/sgml/func/func-window.sgml | 25 +- doc/src/sgml/perform.sgml | 10 + doc/src/sgml/ref/select.sgml | 71 +- src/backend/executor/README.rpr | 1554 +++++++++++++++++++++++----- 5 files changed, 1429 insertions(+), 281 deletions(-) diff --git a/doc/src/sgml/advanced.sgml b/doc/src/sgml/advanced.sgml index 8c0e2f384a6..224bac63525 100644 --- a/doc/src/sgml/advanced.sgml +++ b/doc/src/sgml/advanced.sgml @@ -559,14 +559,15 @@ WHERE pos < 3; AFTER MATCH SKIP, INITIAL or SEEK, PATTERN and DEFINE. The first two are optional, and the - complete example at the end of this section uses both. + complete example below uses both. DEFINE defines row pattern variables along with an expression. The expression must be a logical expression, which means it must return TRUE, FALSE or NULL. The expression may comprise column references and non-volatile functions. Window functions, aggregate functions, - set-returning functions, whole-row references and subqueries are not - allowed. An example of DEFINE is as follows. + grouping operations, set-returning functions, whole-row references and + subqueries are not allowed. An example of DEFINE is + as follows. DEFINE @@ -588,26 +589,31 @@ DEFINE Once DEFINE exists, PATTERN can be used. PATTERN defines a sequence of rows that satisfies conditions defined in the DEFINE clause. For example - the following PATTERN defines a sequence of rows starting - with a row satisfying "LOWPRICE", then one or more rows satisfying + the following PATTERN defines a sequence of rows + starting with a row satisfying "LOWPRICE", then one or more rows satisfying "UP" and finally one or more rows satisfying "DOWN". Pattern variables can be followed by quantifiers: "+" means one or more matches, "*" means zero - or more matches, "?" means zero or one match, "{n}" (n > 0) means exactly - n matches, "{n,}" (n >= 0) means at least n matches, "{,m}" (m > 0) means - at most m matches, and "{n,m}" (0 <= n <= m, 0 < m) means between n and m - matches. Patterns can be grouped using parentheses and combined using - alternation (the vertical bar "|" for OR). For example, "(UP DOWN)+" - matches one or more repetitions of UP followed by DOWN. If a sequence of - rows which satisfies the PATTERN is found, in the starting row all columns - or functions are shown in the target list. Note that aggregations only - look into the matched rows, rather than the whole frame. On the second or - subsequent rows the window functions that read the frame, such - as first_value(), are shown as NULL, while functions - that do not depend on the frame, such - as row_number(), are unaffected. Aggregates on - non-starting rows return their initial value: for example, - count() returns 0 and sum() - returns NULL. Rows that do not match the PATTERN behave the same way. + or more matches, "?" means zero or one match, "{n}" (n > 0) means + exactly n matches, "{n,}" (n >= 0) means at least n matches, + "{,m}" (m > 0) means at most m matches, and + "{n,m}" (0 <= n <= m, 0 < m) means between n and m matches. + Patterns can be grouped using parentheses and combined using alternation + (the vertical bar "|" for OR). For example, "(UP DOWN)+" matches one or + more repetitions of UP followed by DOWN. If a sequence of rows which + satisfies the PATTERN is found, in the starting row all columns or + functions are shown in the target list. Note that aggregations only look + into the matched rows, rather than the whole frame. On the second or + subsequent rows the window functions that read the frame, such as + first_value(), are shown as NULL, while functions that + do not depend on the frame, such as row_number(), are + unaffected. Aggregates on non-starting rows return their initial value: + for example, count() returns 0 and + sum() returns NULL. Rows that do not match the + PATTERN behave the same way. + So do rows at which the PATTERN finds an empty match, which can happen + when the pattern as a whole can match zero rows (for + example A* or A?): such a match + contains no rows, so the frame is empty. Example of a SELECT using the DEFINE and PATTERN clause is as follows. @@ -632,7 +638,7 @@ FROM stock ); - company | tdate | price | first_value | max | count + company | tdate | price | first_value | max | count ----------+------------+-------+-------------+-----+------- company1 | 2023-07-01 | 100 | 100 | 200 | 4 company1 | 2023-07-02 | 200 | | | 0 diff --git a/doc/src/sgml/func/func-window.sgml b/doc/src/sgml/func/func-window.sgml index 1079b6abb6e..823923ac1da 100644 --- a/doc/src/sgml/func/func-window.sgml +++ b/doc/src/sgml/func/func-window.sgml @@ -357,8 +357,8 @@ IGNORE NULLS Returns value evaluated at the row that is offset rows after the match start row; returns NULL if the target row is beyond the current row. - offset defaults to 0 if omitted, referring to the - match start row itself. + offset defaults to 0 if omitted, referring to + the match start row itself. offset must be a non-negative integer. offset must not be NULL. Can only be used in a DEFINE clause. @@ -378,8 +378,8 @@ IGNORE NULLS offset rows before the current row within the match; returns NULL if the target row is before the match start row. - offset defaults to 0 if omitted, referring to the - current row itself. + offset defaults to 0 if omitted, referring to + the current row itself. offset must be a non-negative integer. offset must not be NULL. Can only be used in a DEFINE clause. @@ -396,6 +396,14 @@ IGNORE NULLS navigation. For example, PREV(FIRST(val, 2), 3) fetches the value at 3 rows before the row that is 2 rows after the match start. + The inner FIRST or LAST is + checked first, as it would be on its own: if the inner + FIRST row is beyond the current row, or the inner + LAST row is before the match start row, the result + is NULL, even when the outer offset would lead back into range. The + outer PREV or NEXT may then + reach rows outside the match, and returns NULL only if the target row + is outside the partition. The reverse nesting (FIRST/LAST wrapping PREV/NEXT) is not permitted. Same-category nesting (e.g., @@ -403,6 +411,15 @@ IGNORE NULLS prohibited. The offset argument must be a run-time constant: it cannot reference columns or contain a navigation operation. + In a compound navigation the inner FIRST or + LAST call must be the whole first argument of + PREV or NEXT; an argument + that merely contains one, such as PREV(FIRST(val) + 1), + is rejected. + The value argument, on the other hand, must + include at least one column reference; an argument made only of + constants or parameters, such as PREV(1), is + rejected. diff --git a/doc/src/sgml/perform.sgml b/doc/src/sgml/perform.sgml index 7d0bc9b8fbe..767fb1a0170 100644 --- a/doc/src/sgml/perform.sgml +++ b/doc/src/sgml/perform.sgml @@ -764,6 +764,10 @@ WINDOW w AS ( computed and every row of the frame has to be kept; and Nav Mark Lookahead reports runtime or infinite. + Under ANALYZE, a node that was executed shows the + bound resolved for its last scan instead of runtime: + a row count, retain all or + infinite. @@ -782,6 +786,12 @@ WINDOW w AS ( same pattern prints with the # and ~ markers in that mode and without them in the others. + The markers are also left out when the frame ends at + offset FOLLOWING rather + than UNBOUNDED FOLLOWING, or when a + DEFINE condition uses FIRST, or + LAST with an offset of its own, whether alone or + inside PREV or NEXT. diff --git a/doc/src/sgml/ref/select.sgml b/doc/src/sgml/ref/select.sgml index 2ef862e54a1..e970f18349d 100644 --- a/doc/src/sgml/ref/select.sgml +++ b/doc/src/sgml/ref/select.sgml @@ -929,6 +929,7 @@ WINDOW window_name AS ( expression [, ...] ] [ ORDER BY expression [ ASC | DESC | USING operator ] [ NULLS { FIRST | LAST } ] [, ...] ] [ frame_clause ] +[ row_pattern_common_syntax ] @@ -971,8 +972,8 @@ WINDOW window_name AS ( frame_clause can be one of -{ RANGE | ROWS | GROUPS } frame_start [ frame_exclusion ] [ row_pattern_common_syntax ] -{ RANGE | ROWS | GROUPS } BETWEEN frame_start AND frame_end [ frame_exclusion ] [ row_pattern_common_syntax ] +{ RANGE | ROWS | GROUPS } frame_start [ frame_exclusion ] +{ RANGE | ROWS | GROUPS } BETWEEN frame_start AND frame_end [ frame_exclusion ] where frame_start @@ -1081,10 +1082,11 @@ EXCLUDE NO OTHERS The - optional row_pattern_common_syntax + optional + row_pattern_common_syntax defines the Row Pattern Recognition condition for - this - window. row_pattern_common_syntax + this window. + row_pattern_common_syntax includes the following subclauses. @@ -1096,11 +1098,11 @@ DEFINE definition_variable_name AS AFTER MATCH SKIP PAST LAST ROW or AFTER MATCH SKIP TO NEXT ROW controls how to proceed to the next row position after a match is found. With AFTER MATCH SKIP PAST LAST - ROW (the default) the next row position is next to the last row of - the previous match. On the other hand, with AFTER MATCH SKIP TO NEXT - ROW the next row position is next to the first row of the previous - match. INITIAL or SEEK specifies from - which row in the frame pattern matching begins. + ROW (the default) the next row position is next to the last row + of the previous match. On the other hand, with AFTER MATCH SKIP TO + NEXT ROW the next row position is next to the first row of the + previous match. INITIAL or SEEK + specifies from which row in the frame pattern matching begins. If INITIAL is specified, the match must start from the first row in the frame. If SEEK is specified, the set of matching rows does not necessarily start from the first row. The @@ -1109,19 +1111,24 @@ DEFINE definition_variable_name AS defines definition variables along with a boolean expression. PATTERN defines a sequence of rows that satisfies certain conditions using variables defined - in the DEFINE clause (an empty PATTERN() - is not accepted by the syntax). Each pattern variable can be followed - by a quantifier to specify how many times it should match: - * (zero or more), + in the DEFINE clause (an empty + PATTERN() is not accepted by the syntax). Each pattern + variable can be followed by a quantifier to specify how many times it + should match: * (zero or more), + (one or more), ? (zero or one), - {n} (exactly n times, n > 0), - {n,} (at least n times, n >= 0), - {,m} (at most m times, m > 0), or + {n} + (exactly n times, n > 0), + {n,} + (at least n times, n >= 0), + {,m} + (at most m times, m > 0), or {n,m} - (between n and m times, 0 <= n <= m, 0 < m). + (between n and m + times, 0 <= n <= m, 0 < m). Reluctant quantifiers (e.g., *?, +?, - ??, {n,m}?) + ??, + {n,m}?) are supported. The exclusion ({- and -}) is not accepted by the syntax, and the permutation @@ -1149,6 +1156,9 @@ DEFINE definition_variable_name AS with an error. The DEFINE clause itself is not optional: leaving it out is a syntax error, even where every pattern variable would evaluate as TRUE. + A variable may be defined only once in the DEFINE + clause; a second definition of the same name is rejected with an + error. @@ -1167,7 +1177,6 @@ DEFINE definition_variable_name AS Note that the maximum number of unique pattern variables used in the PATTERN clause is 240. - If this limit is exceeded, an error will be raised. Additionally, the maximum nesting depth of pattern groups (parentheses) is 254 levels. An alternation costs a level of its own, so a pattern that nests alternations reaches the limit at about half @@ -1175,6 +1184,12 @@ DEFINE definition_variable_name AS However, pattern optimizations such as flattening nested sequences and simplifying nested quantifiers may reduce the effective depth, so this limit is rarely reached in practice. + The pattern is also limited to 32767 elements, counted after these + optimizations: one for each occurrence of a pattern variable, two for + each group with a quantifier other than {1}, one + for each alternation plus one for each of its alternatives, and one + more for the pattern as a whole. A larger pattern is rejected with + an error. @@ -1194,7 +1209,9 @@ DEFINE definition_variable_name AS whole FROM clause, and an ambiguous name is rejected. Where the name is not unique, rename the column in the FROM clause, for example with a column alias on - a subquery. + a subquery. A column of an outer query cannot be referenced from + a DEFINE condition, qualified or not; such a + reference is rejected as not supported. @@ -1222,6 +1239,18 @@ DEFINE definition_variable_name AS . + + Two planner optimizations are not applied to a window that uses row + pattern recognition. A filter on the result of a monotonic window + function, such as rn <= 3 on + a row_number() computed in a subquery, is not + pushed down into the window as a run condition, so the window is + evaluated to the end of the partition instead of stopping early. And + the frame clause is not replaced with a cheaper one, even when the + window functions using it do not depend on the frame. Query results + are not affected, only the cost of evaluating the window. + + The purpose of a WINDOW clause is to specify the behavior of window functions appearing in the query's diff --git a/src/backend/executor/README.rpr b/src/backend/executor/README.rpr index 05bbcd76240..f66dd5ddb03 100644 --- a/src/backend/executor/README.rpr +++ b/src/backend/executor/README.rpr @@ -1,27 +1,68 @@ ============================================================================ - PostgreSQL Row Pattern Recognition: Flat-Array Stream NFA Guide + PostgreSQL Row Pattern Recognition (RPR): Flat-Array Stream NFA Guide ============================================================================ - This README's target audience is developers with a basic - understanding of the PostgreSQL executor and planner architecture. - Also it would be better for them to understand the specification of - the row pattern recognition in the SQL standard [1][2]. If you do - not have access to the SQL standard, Oracle's manual or Trino's - manual can be alternatives for them. + Readers should understand the specification of row pattern + recognition in the SQL standard [1][2]. If you do not have access + to the SQL standard, Oracle's manual or Trino's manual can be + alternatives. This README's scope is the entire process from PATTERN/DEFINE clause - parsing to NFA runtime execution. - - Related code: - - src/backend/parser/parse_rpr.c (parser phase) - - src/backend/optimizer/plan/rpr.c (optimizer phase) - - src/backend/executor/nodeWindowAgg.c (executor phase, window agg) - - src/backend/executor/execRPR.c (executor phase, NFA engine) - - src/include/executor/execRPR.h (NFA public API) - - src/include/nodes/plannodes.h (plan node definitions) - - src/include/nodes/execnodes.h (execution state definitions) - - src/include/optimizer/rpr.h (types and constants) - - src/backend/optimizer/plan/createplan.c (match_start dependency metadata) + parsing to NFA runtime execution, together with the contracts the + feature places on the rest of the planner (Chapter XIII) and on the + two printers that display it (Chapter XIV). + + Related code, by the phase each file serves. A file appears once, + under the phase where its row pattern work belongs: + + Parser + - src/backend/parser/gram.y (grammar and keywords) + - src/backend/parser/parse_rpr.c (PATTERN/DEFINE analysis) + - src/include/parser/parse_rpr.h (parser entry points) + - src/include/parser/parse_node.h (DEFINE parse state) + - src/backend/parser/parse_clause.c (transformRPR() call site) + - src/backend/parser/parse_func.c (navigation name binding) + - src/backend/parser/parse_expr.c (DEFINE column restrictions) + - src/backend/parser/parse_target.c (DEFINE star expansion) + - src/backend/parser/parse_cte.c (WITH RECURSIVE rejection) + - src/backend/parser/parse_agg.c (grouping participation) + + Planner + - src/backend/optimizer/plan/rpr.c (rewrites and compilation) + - src/include/optimizer/rpr.h (types and constants) + - src/backend/optimizer/plan/createplan.c (match_start dependencies) + - src/backend/optimizer/plan/initsplan.c (DEFINE columns needed) + - src/backend/optimizer/plan/planner.c (window clause handling) + - src/backend/optimizer/plan/setrefs.c (DEFINE Vars to OUTER_VAR) + - src/backend/optimizer/plan/subselect.c (DEFINE param sets) + - src/backend/optimizer/path/allpaths.c (keeping DEFINE columns) + - src/backend/optimizer/path/costsize.c (DEFINE evaluation cost) + - src/backend/optimizer/prep/prepjointree.c (PlaceHolderVar wrapping) + - src/backend/optimizer/util/var.c (join alias expansion) + - src/backend/rewrite/rewriteManip.c (marking navigation args) + + Executor + - src/backend/executor/nodeWindowAgg.c (reduced frame and nav trim) + - src/backend/executor/execRPR.c (NFA engine) + - src/include/executor/execRPR.h (NFA public API) + - src/backend/executor/execExpr.c (navigation opcode compile) + - src/backend/executor/execExprInterp.c (navigation opcode eval) + - src/backend/jit/llvm/llvmjit_expr.c (JIT path for those opcodes) + + Node support + - src/include/nodes/parsenodes.h (parse node definitions) + - src/include/nodes/primnodes.h (RPRNavExpr) + - src/include/nodes/plannodes.h (plan node definitions) + - src/include/nodes/execnodes.h (execution state) + - src/backend/nodes/nodeFuncs.c (expression tree walking) + - src/backend/nodes/copyfuncs.c (RPRPattern copy support) + - src/backend/nodes/outfuncs.c (RPRPattern out support) + - src/backend/nodes/readfuncs.c (RPRPattern read support) + - src/backend/nodes/queryjumblefuncs.c (DEFINE clause jumble) + + Output + - src/backend/utils/adt/ruleutils.c (deparse for pg_get_viewdef) + - src/backend/commands/explain.c (EXPLAIN output) ============================================================================ @@ -49,8 +90,8 @@ base refer to that document. Where Chapters 4 (FROM clause) and 6 (WINDOW clause) describe parallel material, this implementation cites the Chapter 6 subclause first because it targets Feature R020. -Row Pattern Recognition (hereafter RPR) is a feature introduced in SQL:2016 -that matches regex-based patterns against ordered row sets. +RPR is a feature introduced in SQL:2016 that matches regex-based +patterns against ordered row sets. The SQL standard defines two forms: @@ -61,7 +102,11 @@ The SQL standard defines two forms: Feature R020: RPR in a window (WINDOW clause) - Integrated into the existing window function framework - - Supports ALL ROWS PER MATCH only + - No ROWS PER MATCH clause: every input row is returned once, and + only its reduced window frame depends on the match. In R010 + terms this corresponds to ONE ROW PER MATCH WITH UNMATCHED ROWS: + a match is reported on its starting row, and a row skipped inside + a match or matched by none gets an empty frame - No MATCH_NUMBER() This implementation targets Feature R020. @@ -72,13 +117,16 @@ The basic syntax is as follows: OVER ( PARTITION BY ... ORDER BY ... - ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING + ROWS BETWEEN CURRENT ROW AND [UNBOUNDED | offset] FOLLOWING AFTER MATCH SKIP TO NEXT ROW | SKIP PAST LAST ROW - [INITIAL | SEEK] -- SEEK is defined in the standard but not implemented + [INITIAL | SEEK] PATTERN ( ) DEFINE AS , ... ) +SEEK is defined in the standard but not implemented. The offset in +the frame's end boundary must not be zero or a negative value. + The PATTERN clause is a regular expression over row pattern variables. The DEFINE clause specifies boolean conditions that determine whether each variable evaluates to true for the current row. @@ -95,17 +143,28 @@ PERMUTE is not supported (the parser raises an error). Its syntax is in the grammar so that the standard spelling is diagnosed rather than read as a pattern variable followed by a group; write the alternations out instead. +RPR is not allowed in WITH RECURSIVE or CREATE RECURSIVE VIEW (ISO/IEC +9075-2 7.17; ISO/IEC 19075-5 6.17.5). transformWithClause() +(parse_cte.c) rejects it by walking the raw parse tree with +contain_rpr_walker(), before the CTEs are analyzed. + Chapter II Overall Processing Pipeline ============================================================================ -RPR processing is divided into three phases: +RPR processing is divided into three phases. The planner handles the two +halves of a row pattern window separately: the DEFINE expressions travel +through the planner's ordinary expression machinery, and the PATTERN is +compiled into the element array the executor runs: +--------------------------------------------------------------+ | 1. Parsing (Parser) | | SQL text -> PATTERN parse tree + DEFINE expression tree | | | - | 2. Compilation (Optimizer/Planner) | + | 2. Planning (Optimizer/Planner) | + | DEFINE expressions -> pull-up, qual preprocessing, | + | grouping, input target, Var fixup (Chapter XIII) | | PATTERN parse tree -> optimization -> flat NFA elements | + | (Chapter IV) | | | | 3. Execution (Executor) | | Row-by-row matching via NFA simulation | @@ -135,14 +194,25 @@ following: - Only ROWS is allowed (RANGE, GROUPS are not) - The start boundary must be CURRENT ROW - EXCLUDE option is not allowed - - The end boundary must not be CURRENT ROW (UNBOUNDED FOLLOWING or a - positive offset FOLLOWING only) + - The end boundary must be UNBOUNDED FOLLOWING or offset FOLLOWING + (not CURRENT ROW); the offset's value, even a literal's, is not + checked here but at execution (X-4) (2) Transcription to WindowClause - Copies the rpPattern and rpSkipTo fields (3) DEFINE clause transformation (transformDefineClause) + The two frame diagnostics need somewhere to point, and a defaulted frame + leaves only the start of the window definition. WindowDef therefore + carries frameLocation and excludeLocation, which the frame productions in + gram.y set to the ROWS/RANGE/GROUPS keyword and to the EXCLUDE keyword; + transformRPR() falls back to the window's own location when either is -1. + A frame or exclusion production added later has to set them too, or its + errors lose their cursor position. Note that the EXCLUDE check reads the + FRAMEOPTION_EXCLUSION bits, not excludeLocation: EXCLUDE NO OTHERS sets + no bit and is accepted, since it excludes nothing. + III-2. PATTERN parse tree The parser transforms the PATTERN clause into an RPRPatternNode tree. @@ -163,6 +233,14 @@ All nodes have min/max fields to express quantifiers: If the reluctant field is true, the quantifier is reluctant (non-greedy). +The braced forms are range-checked in the grammar itself. Every bound must +be below RPR_QUANTITY_INF (parsenodes.h), which is also the sentinel the +unbounded spellings store in max. {n} and {,m} require a bound of at least +1, as does the upper bound of {n,m}; the lower bound of {n,m} and the bound +of {n,} may be 0; and {n,m} requires n <= m. So A{0}, A{,0} and A{0,0} are +rejected, while A{0,} is another way to write A*. That cap on the lower +bound is the only one the grammar imposes, which IX-6 revisits as a cost. + Example: PATTERN ((A+ B) | C*) ALT @@ -175,28 +253,215 @@ Example: PATTERN ((A+ B) | C*) Parentheses always produce a GROUP node; a GROUP(1, 1) like the one above is unwrapped later, by Phase 1 (h). +The lexer counts '|' as both a self character and an operator character, so +a quantifier written hard against an alternation arrives as a single Op +token rather than as two: "A*|B" yields Op "*|", not '*' then '|'. Every +reluctant spelling glues the same way ("*?|", "+?|", "??|"), as does the Op +after a braced quantifier, as in "A{2,3}?|B". + +Making '|' a self character takes a lone '|' out of Op everywhere, not only +inside PATTERN. The expression grammar therefore spells it out: a_expr and +b_expr carry prefix and infix '|' productions at the precedence of Op, and +MathOp lists '|', so all_Op and the OPERATOR(...) forms still accept it. +A new production that takes an operator through Op has to accept '|' as +well. psqlscan.l and pgc.l were not changed and still leave '|' out of +self, so they no longer match scan.l. + +row_pattern_quantifier_opt therefore accepts each glued spelling, takes the +quantifier it half spells, and sets RPRPatternNode.trailing_alt on the term +to record that an alternation operator came with it. The flag stays on the +term while the sequence keeps growing; splitRPRTrailingAlt() then splits the +finished sequence at the flagged term into ALT(left, right), where the right +branch is the whole remaining sequence. That is what keeps '|' the +lowest-precedence operator of the pattern language: "A*|B C" parses as +"A* | (B C)", identical to the spaced form. A flagged term with nothing to +its right is a dangling '|' and is rejected. + +trailing_alt is transient. splitRPRTrailingAlt() clears it on every path, +the error paths included, so a finalized tree never carries it and it +reaches neither the plan nor the query id. + III-3. DEFINE Clause Transformation transformDefineClause() first validates the PATTERN variable count and collects the names, then rejects any DEFINE variable that PATTERN does not use. After that it processes each DEFINE variable as follows: - (1) Checks for duplicate variable names - (2) Transforms the expression via transformExpr() and coerces it to - Boolean (coerce_to_boolean) right away, so that the steps below see - the final expression form + (1) Checks for duplicate variable names -- this one in a pass of its + own over the whole list, before any expression is transformed + (2) Transforms the expression and coerces it to Boolean right away, + through transformWhereClause() as for WHERE and HAVING, so that the + steps below see the final expression form (3) Wraps in a TargetEntry with the variable name set in resname - (4) Extracts Var nodes via pull_var_clause() and ensures each is - present in the query targetlist, so the planner propagates the - referenced columns through the plan tree + +Parse analysis puts nothing in the query targetlist for a DEFINE clause. +Getting what it reads to the WindowAgg is the planner's job, and it is done +the way havingQual's is: build_base_rel_tlists() marks the columns needed so +they reach the top of the join tree, and make_window_input_target() asks for +them again in the node's own input target (XIII-2). After all variables are processed: - (5) Validates navigation nesting and offsets (define_walker), marks - column origins and assigns collations + (4) Validates navigation nesting and offsets (define_walker) + +Step (4) is where the shape every later phase assumes gets established. +define_walker() requires the argument of each navigation to contain at least +one column reference, and requires each offset to be a run-time constant: an +offset may contain neither a column reference nor another navigation. The +Var-free rule is what lets the executor settle an offset once per scan (VI-6) +rather than once per row -- the offset expression is evaluated with no current +row installed and the result pinned for the whole scan, which is sound only +because no column can appear there. A Param is still allowed, and is the case +RPR_NAV_OFFSET_NEEDS_EVAL exists for. An omitted offset stays +NULL on the node and the kind's default is supplied at execution: 1 for +PREV/NEXT, 0 for FIRST/LAST, and 1 for a compound outer offset. + +Step (4) also changes the expression it walks. A PREV or NEXT whose +argument is exactly one FIRST or LAST call is merged in place into one +RPRNavExpr of a compound kind (RPR_NAV_PREV_FIRST and so on): the inner +call's argument and offset become arg and offset_arg, and the outer offset +moves to compound_offset_arg. Every other nesting is rejected: FIRST or +LAST over any navigation, PREV or NEXT over PREV or NEXT, an inner +navigation that is only part of the argument, as in PREV(v + FIRST(v)), and +a third level. A navigation inside an offset is rejected as well. Once +step (4) is done, no RPRNavExpr contains another one anywhere; the planner +relies on this (compute_matchStartDependent() asserts it), and the deparser +rebuilds the nested spelling from the compound kind. Variables that are used in PATTERN but not defined in DEFINE are implicitly evaluated as TRUE (matching all rows). +The restrictions the sections below put a DEFINE condition under are keyed on +p_rpr_define, a parse state flag transformDefineClause() holds up for the +whole of step (2), rather than on p_expr_kind. p_expr_kind names the +innermost clause, and a condition can reach two clauses that set a kind of +their own: an aggregate's FILTER, and its ORDER BY, which is also what WITHIN +GROUP writes. Keyed on the kind, every rule below would stop applying inside +those, and what they hid would be resolved and kept. A sub-select gets a +parse state of its own and does not inherit the flag, which is right: the +restrictions end at the query boundary. + +Three rules are left keyed on the kind -- the ones that reject an aggregate, +a window function and a set-returning function -- because a DEFINE condition +reaches those clauses only underneath an aggregate, and an aggregate in a +DEFINE condition is rejected at its own node. That holds as long as the +aggregate belongs to this query level, and the two ways its level can be +lifted out of the clause, an outer column reference and a sublink, are both +rejected on the way down. Relaxing either of those puts this back in play. + +III-4. Column References in a DEFINE Condition + +A name written in a DEFINE condition must be unqualified: ISO/IEC 19075-5 6.5 +reserves the qualifier slot for a row pattern variable, so nothing else may +occupy it. transformColumnRef() (parse_expr.c) enforces this wherever in a +DEFINE condition the name stands, rejecting a reference that resolves to an +outer query's column, a two-part name qualified by a FROM-clause range +variable, and every other qualified name -- including one that +p_post_columnref_hook resolves, such as a SQL function's parameter or a +PL/pgSQL variable spelled with its routine name or block label. Unqualified, +those remain readable; it is the spelling that is refused, not the value. + +A pattern variable qualifier such as A.price is decided before name +resolution, by matching the qualifier against the PATTERN variable names +that transformDefineClause() installs in the parse state for the duration of +the DEFINE transformation and clears afterwards. It has to be caught there +because a pattern variable names no range table entry, so ordinary +resolution would reject it as a qualified expression instead; it is reported +as not yet implemented. Deciding on the qualifier alone also means a +pattern variable takes that name in the qualifier slot from anything else +that could answer to it -- a FROM-clause alias, or the containing routine, +whose own parameters become unreachable by their qualified spelling when a +pattern variable is named after it. Nothing is lost that way, since a +qualified name is rejected in DEFINE whoever it names; what changes is which +of the two rules reports it. + +A reference ending in a star, such as t.* or s.t.*, is decided before name +resolution too, right after the pattern variable test: no qualifier makes a +whole-row reference legal here, so resolving it first would only choose +which rejection it gets. The remaining qualified forms are diagnosed only +after the reference has resolved, so that a misspelled column still gets the +ordinary "Perhaps you meant" hint rather than being blamed on its qualifier. + +All of these rules see only the names the ref hooks leave to the query +parser, so none of them is the last word on what a DEFINE clause accepts. +A procedural language that answers a name first keeps it, and PL/pgSQL's +p_pre_columnref_hook answers whenever the function was written with +"#variable_conflict use_variable". In such a function fn.threshold and +rec.field resolve to the PL/pgSQL datum and return before the qualified-name +rule runs, and a PL/pgSQL variable sharing a name with a pattern variable +takes A.price before the reservation above is reached. The identical text +in a function using the default resolution is rejected by both. + +This is not an oversight in the rules. use_variable redirects name +resolution wholesale -- it takes names a table column would otherwise own +too, which is why the default is to raise an ambiguity error instead -- and +a clause of one statement is not the place to carve an exception out of a +function-wide pragma. + +A lone name that resolves to a range variable is a whole-row reference with +no star to recognize it by, so that form alone is rejected only after it has +resolved. ExpandColumnRefStar() (parse_target.c) deliberately declines to +expand "something.*" in a DEFINE condition: expanding binds by RTE rather +than by name, so ROW(t.*) would slip past the checks above instead of +reaching them. It declines by reporting that it did not expand, and the +caller then hands the whole reference to transformExpr(), which is where the +star rejection comes from; NIL would not say that, being also what expanding +a relation with no columns returns. + +Where it declines is after both ref hooks have had their shot, and that is +the point of deciding there. A name a hook owns is not a reference to a +FROM-clause relation and keeps the expansion it has everywhere else. +Withholding it would not reject such a name -- none of the rules above has +anything to say about one the query parser never resolves -- it would leave +transformColumnRef() to read "rec.*" as the single whole value "rec", which +is a different condition rather than a refused one, and differs silently +wherever a row constructor is not counting its entries. The DEFINE scope +is read off the parse state, not off any exprKind, since a clause nested in +the condition carries a kind of its own. + +Parentheses turn a qualified name into field selection on a value, and that +form stays available: "(x).f" and ROW((x).*) reach a composite parameter or +record variable without occupying the qualifier slot. They are not a way +around the rules above -- a parenthesized range variable is still a +whole-row reference and is still rejected -- which is why the A_Indirection +arm of transformExpressionList() needs no DEFINE test of its own. + +III-5. Navigation Name Resolution + +Inside a DEFINE clause the names PREV, NEXT, FIRST and LAST denote row +pattern navigation rather than functions. ParseFuncOrColumn() +(parse_func.c) recognizes them before any catalog lookup, and only for an +unqualified call written in function syntax somewhere in a DEFINE condition; +column syntax and CALL are excluded. Once the name matches there is no +fallback to function resolution, so an ordinary function of one of these +names is reachable only through a schema-qualified call. That is also why +the deparser has to force-qualify such a function name (XIV-6). + +Skipping the lookup does not skip the shared checks. The recognized name is +carried through the wrong-kind-of-routine and decoration checks as if it +were an ordinary function, so DISTINCT, WITHIN GROUP, ORDER BY, FILTER, OVER +and RESPECT/IGNORE NULLS keep their usual messages, and only then is the +RPRNavExpr built. What that path lets through for a plain function -- +VARIADIC, named arguments, and any argument count other than one or two -- +is rejected with dedicated errors. Anything added to the shared path has to +stay safe to run on a name that will never reach the catalog. + +III-6. Query Jumbling + +A DEFINE clause is a list of TargetEntry whose resname carries the variable +being defined, and TargetEntry.resname is query_jumble_ignore everywhere +else in the tree. Left at that, "DEFINE A AS p > 50, B AS p < 50" and +"DEFINE B AS p > 50, A AS p < 50" would jumble alike and share one +pg_stat_statements entry, though they are different queries. +WindowClause.defineClause is therefore declared custom_query_jumble and +handled by hand in queryjumblefuncs.c: the custom function first jumbles the +list exactly as the generated code would and then appends each entry's +resname. A window with no DEFINE clause has an empty list, so the second +step contributes nothing and its query id is unchanged. + +The other RPR node fields follow the usual rule. RPRNavExpr.navno is +query_jumble_ignore because the planner assigns it (VI-6), and +RPRPatternNode.trailing_alt never survives parsing (III-2). + Chapter IV Compilation Phase ============================================================================ @@ -214,6 +479,11 @@ IV-2. The 6 Phases of buildRPRPattern() Phase 5: Finalization (finalizeRPRPattern) Phase 6: Absorbability analysis (computeAbsorbability) +Phase 2 also rejects a pattern too large for the element array or nested too +deep. The depth test is made on entry to each node, before the children +raise the counter, so the one-byte RPRDepth can never wrap. Neither limit +depends on the input rows: a pattern that compiles once compiles every time. + IV-3. Phase 1: Parse Tree Optimization After copying the parser-generated parse tree, the following optimizations are @@ -226,6 +496,18 @@ observable, so they are gated on the body consuming a fixed number of rows. Alternatives of equal length count as fixed: they pick different variables, never different rows. +RPR_QUANTITY_INF is a sentinel meaning unbounded, not a count, and the +rewrites keep it one. A min is always finite and a max is at least 1, +so the sentinel can appear only as a max; Phase 4 asserts that on every +element it writes. A rewrite that computes a new bound therefore +declines rather than store a finite result that reached the sentinel: +(b), (c) and (g) leave the nodes unmerged when a sum or product +overflows int32 or lands on RPR_QUANTITY_INF, and (e) leaves the group +alone when one more iteration would. Declining is always safe, since +the unrewritten form matches the same rows in the same order, which is +what lets these passes treat overflow as a fallback rather than as an +error. + (a) SEQ flattening: Unwrap nested SEQ nodes SEQ(A, SEQ(B, C)) -> SEQ(A, B, C) @@ -264,26 +546,47 @@ never different rows. A{2,6} takes four) (h) Single-child unwrap - SEQ(A) -> A, (A){1,1} -> A + SEQ(A) -> A, ALT(A) -> A, (A){1,1} -> A + A group whose only child is an unquantified variable hands its own + quantifier to that child instead: (A)+? -> A+? (i) Reluctance normalization: a fixed count leaves reluctance nothing to decide, so it is cleared wherever min == max A{2}? -> A{2}, (A B){2}? -> (A B){2} - This runs before and after each node's own rewrites. (b) and (g) - decline a reluctant node outright, and (c), (d), (e) and (f) compare - nodes with rprPatternEqual(), which treats a reluctant node as unequal - to its greedy twin. Without the normalization (A{2}?){3} would stay - nested where (A{2}){3} collapses to A{6}, and (A{2}? | A{2}) would - keep both branches. The absorbability analysis of IV-5 reads the flag - as well, on a group's BEGIN and with no bound test, so a fixed-count - reluctant group becomes absorbable exactly where its greedy spelling - already was. + This runs before and after each node's own rewrites. (b), (c), (e) + and (g) decline a reluctant node outright, and (c) to (f) compare + nodes with equal(), which treats a reluctant node as unequal to its + greedy twin. Without the normalization (A{2}?){3} would stay nested + where (A{2}){3} collapses to A{6}, and (A{2}? | A{2}) would keep both + branches. The absorbability analysis of IV-5 reads the flag as well, + on a group's BEGIN and with no bound test, so a fixed-count reluctant + group becomes absorbable exactly where its greedy spelling already was. IV-4. Phase 4: NFA Element Array Generation Transforms the optimized parse tree into a flat array of RPRPatternElement. This is the core data structure used for NFA simulation at runtime. +Phases 2 and 4 walk the same tree and must agree on its size: Phase 3 +allocates exactly what Phase 2 counted, and Phase 4 fills the array +with no bound test of its own. The count is one element per VAR, a +BEGIN and an END for each GROUP whose quantifier is not {1,1}, an ALT +plus one SEP per branch for each alternation, and one FIN for the whole +pattern; a SEQ contributes nothing. A new element kind therefore has +to be added to scanRPRPattern() and fillRPRPattern() together, and so +does any change to the depth an element is given. + +The rule is that a node's own markers sit at the depth the node was +given and its contents one level deeper: BEGIN and END at the group's +depth with the body at depth + 1, ALT and every SEP at the alternation's +depth with each branch at depth + 1. A SEQ adds no level, and a VAR +sits at the depth it was given. counts[] (V-1) is indexed by depth, so +a group's count lives at its markers' depth and a VAR's at its own; an +alternation keeps no count, but its branches still add a level to +maxDepth. The first element after a group body that is shallower than +the body is the group's END, which is how isUnboundedStart() finds where +the group closes and where isFixedLengthChildren() stops. + RPRPatternElement struct (16 bytes): Field Size Description @@ -295,7 +598,7 @@ RPRPatternElement struct (16 bytes): min 4B Quantifier lower bound max 4B Quantifier upper bound next 2B Next element index (sequential flow) - jump 2B Branch link (ALT/SEP), group skip/loop-back (BEGIN/END) + jump 2B Branch link (ALT/SEP), own END (BEGIN), loop-back (END) Pattern variables occupy varId 0 to RPR_VARID_MAX (0xEF) inclusive, giving 240 distinct variables. Any varId with the high nibble set @@ -320,8 +623,7 @@ Element flags (1 byte, bitmask): 0x02 RPR_ELEM_EMPTY_LOOP (END) Group body can produce empty match (all children nullable). Creates a fast-forward exit clone alongside the normal - loop-back so cycle detection doesn't kill legitimate - matches. (IV-4b) + loop-back below min. (IV-4b) 0x04 RPR_ELEM_EMPTY_PREFERRED (END) Group body prefers the empty match over a consuming one. @@ -331,7 +633,7 @@ Element flags (1 byte, bitmask): 0x08 RPR_ELEM_ABSORBABLE_BRANCH (VAR, BEGIN, END, ALT) Element lies within an absorbable region. Used at runtime to track whether the current NFA state is in an absorbable - context. See "IV-5. Absorbability Analysis" and + context. See "IV-5. Absorbability Analysis" and "VIII-2. Solution: Context Absorption" for more details about absorption. @@ -356,10 +658,11 @@ Roles of next and jump: For ALT, the first branch's content; for SEP, the next branch's content (post-ALT on the last SEP). - - jump: The element to "skip to." + - jump: A second link, whose target depends on the element kind. In ALT, the first branch's terminating SEP. In SEP, the branch link to the next branch's SEP (-1 on the last). - In BEGIN, a skip path to END+1 (for groups with min=0). + In BEGIN, the group's own END. A group with min=0 is skipped + through that END's next, without arriving at the END. In END, a loop-back to the start of the group body. The examples below build up in order: a GROUP, then an ALT (which introduces @@ -369,14 +672,15 @@ Example: PATTERN ((A B)+) -- GROUP idx varId depth min max next jump Description -------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 4 Group start + 0 BEGIN 0 1 INF 1 3 Group start 1 A(0) 1 1 1 2 -1 A 2 B(1) 1 1 1 3 -1 B 3 END 0 1 INF 4 1 Group end 4 FIN 0 1 1 -1 -1 Pattern completion - idx 0: BEGIN. next(=1) enters the group body. - jump(=4) skips to after END = FIN (used when min=0). + jump(=3) is the group's END. When min=0 the skip path leaves + through END.next (=4, FIN) without arriving at the END. - idx 3: END. next(=4) exits the group. jump(=1) loops back to the start of the group body. @@ -407,19 +711,19 @@ Example: PATTERN (A+ B | C) -- ALT - idx 6: FIN marker. Match completion signal Each branch is bounded by a trailing SEP, including the last, so a branch's - extent is fixed by its own SEP. The branch link runs from ALT through - the SEP chain, never through the branch content. That keeps it clear of a + extent is fixed by its own SEP. The branch link runs from ALT through the + SEP chain, never through the branch content. That keeps it clear of a branch that ends with a quantified group, whose BEGIN.jump is the group's - own skip-past-END path (redirected past the ALT so it never lands on a SEP). + own END. Example: PATTERN ((B C)* | A) -- GROUP + ALT combined idx varId depth min max next jump Description -------------------------------------------------------------- 0 ALT 0 1 1 1 5 Alternation start - 1 BEGIN 1 0 INF 2 8 Branch 1: (B C)* -- skip - 2 B(1) 2 1 1 3 -1 redirected from SEP(5) - 3 C(2) 2 1 1 4 -1 to post-ALT(8) + 1 BEGIN 1 0 INF 2 4 Branch 1: (B C)* -- jump is + 2 B(1) 2 1 1 3 -1 its own END; the skip + 3 C(2) 2 1 1 4 -1 leaves via END.next 4 END 1 0 INF 8 2 Branch 1 tail -> post-ALT 5 SEP 0 1 1 6 7 Branch 1 terminator 6 A(0) 1 1 1 8 -1 Branch 2: A -> post-ALT @@ -428,19 +732,20 @@ Example: PATTERN ((B C)* | A) -- GROUP + ALT combined A branch-terminal optional group's skip path: - A group's BEGIN skip-past-END jump (taken when an optional group matches - zero times) is set to "the element after END". Here that element is the - branch's own SEP terminator (idx 5), so a naive skip would land on a SEP - marker. A SEP is a compile-time boundary, never a runtime state; landing - there would (via the default VAR switch arm) mis-treat the SEP's varId as an - always-true variable and consume a spurious row, or fall through SEP.next - into the next branch. - - fillRPRPatternAlt therefore redirects any branch-terminal BEGIN.jump that - points at the branch's SEP to the post-ALT element (so idx 1's jump is 8, - not 5), and the zero-match skip ends the branch -- an empty match, exactly - as it would outside an alternation. The same redirect covers the - last-branch case, where the element after END is the final SEP. + The skip taken when an optional group matches zero times leaves through + END.next, not through "the element after END". Here the element after END + is the branch's own SEP terminator (idx 5). A SEP is a compile-time + boundary, never a runtime state; landing there would (via the default VAR + switch arm) mis-treat the SEP's varId as an always-true variable and consume + a spurious row, or fall through SEP.next into the next branch. END.next is + already redirected past the alternation with the rest of the branch tail + (idx 4's next is 8), so the zero-match skip ends the branch -- an empty + match, exactly as it would outside an alternation -- with no redirect of its + own. The same holds in the last branch, where the element after END is the + final SEP. + + BEGIN.jump names the group's END so that entering the group can mark that + END visited in one step (see IX-6). IV-4a. Reluctant Flag (RPR_ELEM_RELUCTANT) @@ -462,16 +767,16 @@ At runtime (nfa_advance), the flag controls Depth-First Search (DFS) exploration order: VAR with quantifier: (a VAR has no jump; looping stays on the element) - Greedy: primary path = stay (loop), clone = next (exit) - Reluctant: primary path = next (exit), clone = stay (loop) + Greedy: primary path = stay (loop), second path = next (exit) + Reluctant: primary path = next (exit), second path = stay (loop) END element: - Greedy: primary path = jump (loop-back), clone = next (exit) - Reluctant: primary path = next (exit), clone = jump (loop-back) + Greedy: primary path = jump (loop-back), second path = next (exit) + Reluctant: primary path = next (exit), second path = jump (loop-back) BEGIN with min=0: - Greedy: primary path = next (enter group), clone = jump (skip) - Reluctant: primary path = jump (skip), clone = next (enter group) + Greedy: primary path = next (enter group), second path = END.next (skip) + Reluctant: primary path = END.next (skip), second path = next (enter group) The absorption optimization requires greedy quantifiers. Reluctant quantifiers are excluded from absorbability analysis (see IV-5). @@ -498,9 +803,8 @@ group is unwrapped by (h), so neither leaves an END to carry the flag. It marks the END for the cycle detection of IX-6, which only ever tests a nullable END, and it lets nfa_advance_end offer a fast-forward exit beside -the loop-back below min. Without it, (A? B?){2,3} could not reach its lower -bound: iteration 1 consumes every available row, iteration 2 derives an -empty match, and nothing would carry the count to min(2). +the loop-back below min, treating the remaining required iterations as +empty matches. RPR_ELEM_EMPTY_PREFERRED -- the body's preferred derivation is the empty one, which is what orders those two paths. A bare variable consumes a @@ -533,8 +837,8 @@ Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive): Case 1: Simple VAR+ (e.g., A+) -> ABSORBABLE | ABSORBABLE_BRANCH set on the VAR Case 2: GROUP+ with fixed-length children (min == max, recursively) - e.g., (A B)+, (A B{2})+, ((A (B C){2}){2})+ - -> ABSORBABLE_BRANCH on all elements within the group, + e.g., (A B)+, (A B{2})+, ((A (B C){2}){2})+ -> + ABSORBABLE_BRANCH on all elements within the group, ABSORBABLE | ABSORBABLE_BRANCH on END Why this is safe: when every child has min == max, the group @@ -545,8 +849,23 @@ Structural conditions (isUnboundedStart + computeAbsorbabilityRecursive): Case 3: GROUP+ whose body starts with VAR+ (e.g., (A+ B)+) -> Recurses from BEGIN into the body, applying Case 1. - ABSORBABLE | ABSORBABLE_BRANCH set on A. + ABSORBABLE | ABSORBABLE_BRANCH set on A, and + ABSORBABLE_BRANCH on the enclosing BEGIN. B and END get no flags -> absorption stops once past A. + Case 4: ALT (e.g., A+ | B+) + -> Each branch, reached through the SEP chain, is judged on + its own by the cases above. The ALT gets + ABSORBABLE_BRANCH when any branch qualifies; SEPs get no + flags. e.g., A+ | C D (A+ only), ((A+ B) | C) D (A+). + (See B-7) + +The walk starts at element 0 and descends only through a greedy BEGIN +or an ALT at the start of a scope, so only the first element of each +scope can become a comparison point: A B+ gets no flags. Case 2 +rejects any ALT inside the group, even one whose branches have equal +length, so (A | B)+ gets no flags although IV-3 counts such a body as +fixed. The walk then tries the ALT's branches, so (A+ | B)+ still +flags A+ by Case 1. A reluctant group disqualifies its whole subtree. computeAbsorbability- Recursive() returns at such a BEGIN, so (A+ B)+? gets no flags at all @@ -590,10 +909,9 @@ Example: In PATTERN ((A B)+ C), a state waiting for B in the 3rd iteration exited, per the count-clear policy, so a state parked on B always enters with zero) - Counts are indexed by depth, not by elemIdx. - counts[0] is incremented when passing through END(depth 0), - and the group repetition count is preserved even when - the state is at B(depth 1). + Counts are indexed by depth, not by elemIdx. counts[0] is incremented when + passing through END(depth 0), and the group repetition count is preserved + even when the state is at B(depth 1). Definition of two states being "equal": @@ -602,6 +920,26 @@ Definition of two states being "equal": nfa_states_equal() compares counts[0..elem->depth] using memcmp. Only counts at or below the depth of the current element are meaningful. +Counts saturate rather than wrap. Every increment goes through +RPRCountIncrement(), which stops at RPR_COUNT_INF; that value is +RPR_QUANTITY_INF (PG_INT32_MAX), so a saturated count compares as +unbounded in RPRElemCanLoop() and RPRElemWithinMax() exactly as an +unbounded max does. Two consequences follow: a saturated count no +longer distinguishes the states that reached it, so nfa_states_equal() +may collapse them, and the count-dominance test of VIII-3 reads two +saturated counts as dominating each other. Both are harmless -- past +RPR_COUNT_INF iterations a quantifier can neither run out nor be +exceeded -- but a bare count++ added anywhere in the engine would +overflow int32 instead of settling there. + +That is the far end. Below it the same comparison is finer than the +future it stands for: where max is RPR_QUANTITY_INF, no decision in the +engine reads a count above min, so states differing only there behave +alike from that point on and this memcmp still keeps them apart. A +branching unbounded pattern that never reaches FIN pays for it, and the +XXX at nfa_states_equal() carries the cost and what a clamp would have +to preserve. + V-2. RPRNFAContext -- Matching Context A single context represents "a matching attempt started from a specific @@ -611,10 +949,14 @@ start row." --------------------------------------------------------------------- states Linked list of active NFA states matchStartRow Row number where matching started - matchEndRow Row number where matching completed - (-1 if incomplete) + matchEndRow Last row of the match; below matchStartRow for + an empty match, -1 before any match lastProcessedRow Last row processed - matchedState State that reached FIN (for greedy fallback) + matchedState State that reached FIN, or NULL; its being + non-NULL is what records a match (the state + itself is never read) + matchUpdated Whether the advance now running already recorded + a match (at most one per advance) hasAbsorbableState Whether this context can absorb other contexts allStatesAbsorbable Whether this context can be absorbed next, prev Doubly-linked list @@ -631,7 +973,7 @@ two states coexist within the context: State 2: elemIdx=5 (waiting for C, via branch B) In this case, since the (elemIdx, counts) of the two states are equal, -nfa_add_state_unique() retains only State 1 (branch A), which was +nfa_append_state_unique() retains only State 1 (branch A), which was added first. Because DFS processes the first branch of ALT first, the state via A is registered first, and the state via B is discarded as a duplicate. @@ -642,17 +984,29 @@ V-3. RPR Fields of WindowAggState nfaContext / nfaContextTail Doubly-linked list of active contexts nfaContextFree Reuse pool for contexts nfaStateFree Reuse pool for states - nfaVarMatched Per-row tri-state cache: varMatched[varId] (lazy) - nfaVisitedEnds Nullable ENDs reached in this DFS (cycle detection) - nfaVisitedMinWord Lowest bitmapword index touched since last reset - nfaVisitedMaxWord Highest bitmapword index touched since last reset + nfaVarMatched Lazy per-row tri-state cache, varMatched[varId] + nfaVisitedEnds Nullable ENDs this DFS reached (cycle check) + nfaVisitedMinWord Lowest bitmapword index touched since reset + nfaVisitedMaxWord Highest bitmapword index touched since reset nfaStateSize Precomputed size of RPRNFAState - defineMatchStartDependent DEFINE vars needing per-context evaluation (match_start_dependent) + defineMatchStartDependent DEFINE vars needing per-context evaluation + (match_start_dependent) nfaLastProcessedRow Last row processed by NFA (-1 = none) EXPLAIN ANALYZE instrumentation counters are omitted here; see execnodes.h for the full list. + The active context list is ordered by matchStartRow, strictly ascending + from head to tail, with at most one context per start row: + ExecRPRStartContext() only appends at the tail and asserts that the new + start row is past the tail's. The driver loop appends the context for + currentPos + 1 after each row, and the on-demand path in + update_reduced_frame creates one only where none exists. Other code + relies on the head holding the smallest matchStartRow: the lookup in + update_reduced_frame (VI-1), the tuplestore mark (VI-6), the + nav_match_start the head context uses without invalidation (VI-5), and + the tail-to-head walk of absorption (VIII-5). + Memory management: States and contexts are managed through their own free lists. @@ -665,10 +1019,14 @@ Chapter VI NFA Execution: 3-Phase Model VI-1. Entry Point and Overall Flow -When the window function processes each row, row_is_in_reduced_frame() -is called. This function determines whether the current row belongs to -a matched frame, and if necessary, calls update_reduced_frame() to -drive the NFA. +ExecWindowAgg() drives the match once for every row of the scan by +calling ensure_reduced_frame(), so the match tracks the row scan rather +than frame access. That function is idempotent: it calls +update_frameheadpos() and update_reduced_frame() only when +get_reduced_frame_status() reports the row as RF_NOT_DETERMINED. +row_is_in_reduced_frame(), which the frame access paths call to classify +a row, goes through ensure_reduced_frame() first and then reads the +recorded result. Flow of update_reduced_frame(): @@ -678,8 +1036,15 @@ Flow of update_reduced_frame(): Pseudocode of the row processing loop: - targetCtx = ExecRPRGetHeadContext(pos) + targetCtx = NULL + if nfaContext != NULL: -- head is the oldest context + if nfaContext->matchStartRow > pos: -- pos already skipped past + return + if nfaContext->matchStartRow == pos: + targetCtx = nfaContext if targetCtx == NULL: + if pos <= nfaLastProcessedRow: -- already unmatched or skipped + return targetCtx = ExecRPRStartContext(pos) for currentPos = startPos; targetCtx->states != NULL; currentPos++: @@ -696,6 +1061,27 @@ Key point: Processing a single row may require processing multiple rows ahead. Due to the nature of window functions, determining the frame for row N requires looking at rows beyond N. +Partition end: when rpr_prepare_row() reports no row at the scan +position, ExecRPRFinalizeAllContexts() stops every context that is still +running. It calls nfa_match() with a NULL varMatched, which fails every +VAR, then nfa_advance() to drain the epsilon transitions that failure +leaves behind. The point is uniformity: every context comes out with +states == NULL, so the cleanup that follows classifies them all by one +rule. Genuine FIN reaches have all been recorded in flight, so only +three shapes survive to this call: pure pursuit (matchedState == NULL), +which the forced mismatch turns into a failure; an empty-match candidate +whose VAR states are still chasing a longer match (matchedState != NULL, +matchEndRow < matchStartRow); and a recorded match whose states are +still looping for a longer one. + +ExecRPRCleanupDeadContexts() then frees every context left with no +states, with two exceptions. The context the caller passes as +excludeCtx is never freed: the caller still owns it and reads its result +from it. A context holding a recorded match is left to the SKIP logic, +and the test for that is matchedState, not matchEndRow -- an empty match +ends one row before matchStartRow (VI-2), so a row-length test would +take it for a failure and count it as pruned or mismatched. + VI-2. Context Creation: ExecRPRStartContext() Creates a new context and performs the initial advance. @@ -743,14 +1129,26 @@ variable that no active state tests at this row is never evaluated. nfaVarMatched is a tri-state array (RPRVarMatch): RPR_VAR_UNEVALUATED, RPR_VAR_TRUE, or RPR_VAR_FALSE. nfa_eval_var_match() evaluates a -variable's DEFINE on first consumption and caches the result; a NULL -result folds to RPR_VAR_FALSE (non-True is not mapped). The caller +variable's DEFINE with ExecQual() on first consumption and caches the +result, so a NULL result is cached as RPR_VAR_FALSE (XIII-5). The caller (advance_reduced_frame_nfa) holds winstate->currentpos at the scan position for the whole row (restored after the loop) because the deferred navigation opcodes read currentpos. -To support row navigation operators (PREV, NEXT, FIRST, LAST), -a 1-slot model is used: only ecxt_outertuple is set to the current +DEFINE evaluation runs in rprContext, a third ExprContext that +ExecInitWindowAgg() creates only for a window carrying a DEFINE clause. +It has to stay distinct from tmpcontext and from the output context +ps_ExprContext: nfa_eval_var_match() resets it before every predicate +evaluation, and a shared context would free the input or output tuple's +memory underneath its owner. A predicate leaves nothing behind that +outlives it -- the verdict is a by-value bool cached in nfaVarMatched -- +so no caller has to arrange the reset on its behalf. +ExecAssignExprContext() overwrites ps_ExprContext on each call, so the +DEFINE context is built between the two standard ones and the last call +is the one that establishes the output context. + +To support row navigation operators (PREV, NEXT, FIRST, LAST), a 1-slot +model is used: only ecxt_outertuple is set to the current row. Navigation is handled by EEOP_RPR_NAV_SET/RESTORE opcodes emitted during DEFINE expression compilation: @@ -758,33 +1156,122 @@ emitted during DEFINE expression compilation: (evaluate): argument expression reads from swapped slot NAV_RESTORE: restore original ecxt_outertuple +The pair is not reentrant. SET keeps the slot it swaps out in a single +field, winstate->nav_saved_outertuple, and fetches the target row into +the single nav_slot, so a navigation evaluated inside another one's +argument would overwrite both, and the outer RESTORE would put back +nav_slot rather than the current row. The executor relies on +define_walker() (III-3) never letting one RPRNavExpr reach the argument +of another: PREV or NEXT over FIRST or LAST is flattened into one +compound RPRNavExpr, and every other nesting in an argument, such as +FIRST(PREV(x)), PREV(PREV(x)) or PREV(x + FIRST(y)), is rejected. + +Between SET and the argument the compiler plants an EEOP_JUMP_IF_NULL +step whose target is the RESTORE step, so a navigation to a row that +does not exist skips the argument expression entirely instead of +evaluating it against the wrong row. That makes the SET step's resnull +a contract rather than a by-product: it has to be written on every path +-- true when the target row is out of range, a definitive false when the +row exists -- because resnull may still carry a stale value from an +earlier evaluation of the same expression. + Compound navigation (PREV(FIRST()), NEXT(FIRST()), PREV(LAST()), -NEXT(LAST())) is flattened by the parser into a single RPRNavExpr -with a compound kind (RPR_NAV_PREV_FIRST, etc.). The executor -computes the target position in two steps: first the inner reference -point (match_start + N or currentpos - N) with match-range validation, -then the outer adjustment (+/- M) with partition-range validation. -If either step is out of range, the result is NULL. +NEXT(LAST())) is flattened by the parser into a single RPRNavExpr with +a compound kind (RPR_NAV_PREV_FIRST, etc.). The executor computes the +target position in two steps: first the inner reference point +(match_start + N or currentpos - N) with match-range validation, then +the outer adjustment (+/- M) with partition-range validation. If +either step is out of range, the result is NULL. + +The offsets are optional in the source text, and the default differs by +kind: PREV and NEXT default to 1, FIRST and LAST to 0, and every compound +kind defaults to inner 0 with outer 1, so PREV(FIRST(x)) reads the row +before the match start. RPRNavExpr leaves a missing offset as a NULL +offset_arg or compound_offset_arg rather than materializing a Const; +resolve_nav_offsets() supplies the kind's default once per scan (VI-6), +and RPRNavKind (primnodes.h) is what records which default applies. + +When the computed target is the current row -- LAST(expr), PREV(expr, 0) +and NEXT(expr, 0) all resolve there -- ExecEvalRPRNavSet() skips the +tuplestore fetch and the swap altogether and just reports the row as +present. It records nav_saved_outertuple first all the same, so that +EEOP_RPR_NAV_RESTORE stays a harmless no-op: RESTORE recognizes the +elision by finding ecxt_outertuple unchanged and returns immediately, +which is correct because the argument read the current row's slot rather +than nav_slot. nav_slot caches the last fetched position (nav_slot_pos) to avoid redundant tuplestore lookups when multiple navigation calls target the same row. +That single slot is also why a navigation result cannot simply be left +where the argument produced it. A pass-by-reference result points into +nav_slot's tuple memory, and the next navigation in the same expression +frees that tuple when it re-fetches the slot for another position. +EEOP_RPR_NAV_RESTORE therefore copies a non-null pass-by-ref result into +ecxt_per_tuple_memory, which survives until the next ResetExprContext, +before it returns. Rather than look the type up on every evaluation, +ExecInitExprRec() reads the type length and by-value flag once from the +RPRNavExpr's resulttype and stores them in the shared RPRNavState as it +emits the RESTORE step; every compilation of the same navigation writes +the same pair, so repeating it is harmless. + The nfaVarMatched entries are filled lazily during Phase 1 (Match) as variables are consumed. -VI-4. Per-Context Invalidation (match_start_dependent variables) +VI-4. Slot Swap Consumers: Interpreter and JIT + +The swap happens in the middle of an already-compiled expression, so +everything that expression cached about the outer tuple goes stale at +that point and has to be refreshed: + + - Deformed columns. The expression's FETCHSOME step ran once, against + the original slot, so ExecEvalRPRNavSet() calls slot_getallattrs() + on the target slot before installing it. A narrower deform there + would leave the argument reading unset tts_values entries. + + - The caller's cached slot pointer. ExecEvalRPRNavSet() and + ExecEvalRPRNavRestore() update econtext->ecxt_outertuple only, so + every caller must reload its own copy afterwards. The interpreter + (execExprInterp.c) reassigns its local outerslot in both opcode + arms. + + - The JIT's entry-block loads. llvm_compile_expr() (llvmjit_expr.c) + normally loads tts_values and tts_isnull once in the entry block and + reuses them for every EEOP_OUTER_VAR. For an RPR window it first + scans the steps for EEOP_RPR_NAV_SET or EEOP_RPR_NAV_RESTORE, and + when it finds one, each EEOP_OUTER_VAR reloads the slot pointer from + econtext instead of using the cached entry-block values. + +The SET step reaches the tuplestore through ExecRPRNavGetSlot() +(nodeWindowAgg.h), the one executor entry point expression evaluation uses: +it bounds-checks the position against the partition and returns NULL for a +row outside it, which is what that step reports as a null result. RESTORE +fetches nothing. It puts back the slot SET swapped out, and copies a +pass-by-reference result into per-tuple memory so that a later fetch of +nav_slot cannot pull the tuple out from under it. + +Both evaluators run out of line, reached through build_EvalXFunc(), +which is why ExecEvalRPRNavSet and ExecEvalRPRNavRestore appear in +referenced_functions in llvmjit_types.c. + +DEFINE expressions are otherwise ordinary ExprStates, so a row pattern +window is JIT-compiled like any other; the RPR-specific part of +expression compilation is ExecInitExprRec()'s T_RPRNavExpr arm +(execExpr.c). + +VI-5. Per-Context Invalidation (match_start_dependent variables) DEFINE variables that depend on match_start -- those containing FIRST or a compound PREV_FIRST/NEXT_FIRST, or a LAST that carries an offset of its own, whether plain or inside a compound PREV_LAST/NEXT_LAST -- are identified at -plan time via defineMatchStartDependent. For the head -context, advance_reduced_frame_nfa sets nav_match_start to its -matchStartRow before matching, so lazy evaluation uses the correct +plan time via defineMatchStartDependent. For the head context, +advance_reduced_frame_nfa sets nav_match_start to its matchStartRow before +matching, so lazy evaluation uses the correct FIRST/LAST base position. When processing a context whose matchStartRow differs, -nfa_reevaluate_dependent_vars() resets only the dependent variables to +nfa_invalidate_dependent_vars() resets only the dependent variables to RPR_VAR_UNEVALUATED so they are re-evaluated lazily against this context's matchStartRow, installs nav_match_start to that value, and invalidates the nav_slot cache. match_start-independent variables keep their cached value @@ -792,9 +1279,7 @@ across contexts (they do not read nav_match_start). nav_match_start is left installed and NOT restored: FIRST/LAST read it at evaluation time, which happens later during nfa_match(); the next -context's invalidation or the next row's setup overwrites it. The -function also resets rprContext so one context's DEFINE scratch does not -accumulate across every context of a row. +context's invalidation or the next row's setup overwrites it. Summary of evaluation strategy by navigation content (a variable is evaluated once per row and cached, except dependent ones which are @@ -811,11 +1296,12 @@ re-evaluated once per differing context): Compound (inner LAST, no off.) cached (once per row) Compound (inner LAST, w/off.) per-context -VI-5. Tuplestore Mark and Trim (nodeWindowAgg.c) +VI-6. Tuplestore Mark and Trim (nodeWindowAgg.c) Navigation functions require access to past rows via the tuplestore. To allow tuplestore_trim() to free rows that are no longer reachable, -the executor computes two offsets at init (see build_define_offsets): +the executor computes two offsets per scan (see resolve_nav_offsets; +build_define_offsets resolves the constant ones at init for EXPLAIN): navMaxOffset (Nav Mark Lookback): Maximum backward reach from currentpos. Contributed by PREV, @@ -832,20 +1318,64 @@ the executor computes two offsets at init (see build_define_offsets): The actual mark is set to: min(lookback_mark, lookahead_mark). This ensures all rows reachable by any navigation function are retained. +The mark advance_nav_mark() moves belongs to nav_winobj, a WindowObject +that exists only for RPR navigation, with its own tuplestore read and +mark pointer pair allocated in prepare_tuplestore() and reset in +begin_partition(). Holding it apart from agg_winobj and from the +per-window-function objects is what lets the DEFINE clause's lookups +trim the tuplestore without moving anyone else's fetches. The mark only +ever advances, and every RPR window gets a nav_winobj whether or not its +DEFINE navigates at all. + +Apart from everyone else, but not from itself: the pair is one pair, and +both rpr_prepare_row() and ExecRPRNavGetSlot() reach the tuplestore +through it. The frontier row and the navigation target are not the same +row, so the two drag the single seekpos back and forth. In memory that +costs a pointer move; spilled it costs a re-read, and the XXX at +prepare_tuplestore() carries the measurement. + +Each RPRNavExpr carries a navno, its index into that list of offsets. +The parser leaves it -1; compute_define_metadata() +(optimizer/plan/createplan.c) numbers the navigations in walk order +while it classifies match_start dependency, and build_define_offsets() +fills rprNavOffsets by walking the same expressions in the same order, +so entry i is the navigation with navno i. The offsets live in +executor state rather than on the RPRNavExpr, the plan tree being +read-only, so the expression compiler looks the entry up by navno when +it emits the EEOP_RPR_NAV_SET/RESTORE pair. The two walks have to stay +in step: execExpr.c raises "RPRNavExpr navno %d out of range" instead +of indexing past the list, and rejects an entry that does not point +back at the same RPRNavExpr. + +What the compiler takes from the entry is its RPRNavState, the state +VI-3 calls shared. build_nav_offsets() creates one per navigation with +both offsets null, and the SET and RESTORE steps compiled for that +navigation both point at it, so build_define_offsets() has to run before +the ExecInitQual() loop over defineClause in ExecInitWindowAgg(). +resolve_one_nav() pins the inner and outer offsets, defaults included, +into it: at init for a navigation whose offsets are all Const +(for EXPLAIN), and again on every scan through resolve_nav_offsets(). +ExecEvalRPRNavSet() reads them from there, asserting they are set, +rather than evaluating the offset per row, so a rescan changes the +offsets the compiled DEFINE expressions use without recompiling them. + When offsets contain non-constant expressions (Param), the executor sets navMaxOffsetKind/navFirstOffsetKind to RPR_NAV_OFFSET_NEEDS_EVAL. A constant offset is resolved at init, as is a bind parameter the planner folded to a Const for a custom plan; under a generic plan that parameter stays a Param and resolves per scan, as a PARAM_EXEC offset does. Either way every navigation is settled again per scan by resolve_nav_offsets(), which is where a null or -negative offset is rejected. On overflow, the kind is set to -RPR_NAV_OFFSET_RETAIN_ALL, disabling trim for that dimension. An offset that -resolves negative is rejected at execution, so that navigation can never run and -is left out of both reaches; it behaves exactly as if it were not in the DEFINE. -Each dimension is reported only when some navigation feeds it (hasMaxNav, -hasFirstNav), so an empty one prints nothing rather than a reach of zero. - -VI-6. ExecRPRProcessRow(): 3-Phase Processing +negative offset is rejected. On a backward-reach overflow, navMaxOffsetKind is +set to RPR_NAV_OFFSET_RETAIN_ALL, disabling trim for that dimension. The +forward reach has no such sentinel: an overflowing FIRST reach clamps to +PG_INT64_MAX, which bounds nothing and which EXPLAIN prints as "infinite". An +offset that resolves negative is rejected at execution, so that navigation can +never run and is left out of both reaches; it behaves exactly as if it were not +in the DEFINE. Each dimension is reported only when some navigation feeds it +(hasMaxNav, hasFirstNav), so an empty one prints nothing rather than a reach of +zero. + +VI-7. ExecRPRProcessRow(): 3-Phase Processing NFA processing for a single row is divided into three phases: @@ -872,17 +1402,20 @@ This ordering is important: Chapter VII Phase 1: Match ============================================================================ -nfa_match() iterates through each state in the context: +nfa_match() iterates through each state in the context. Every state it +sees is a VAR: the advance phase parks only VAR states, and a fresh context +is advanced before its first match. This is asserted, not checked at +runtime. For each state: - (1) Check whether the state's elemIdx is a VAR element - (2) Compare against the current row using nfa_eval_var_match() - (3) Match success: increment repetition count, retain state - (4) Match failure: remove state + (1) Compare against the current row using nfa_eval_var_match() + (2) Match success: increment repetition count, retain state + (3) Match failure: remove state Match determination (nfa_eval_var_match): If varId is within the range of defineClauseExprs: - Use the value of varMatched[varId] + Use the value of varMatched[varId], first evaluating the DEFINE + predicate if the entry is still RPR_VAR_UNEVALUATED (VI-3) If varId exceeds the range (variable not defined in DEFINE): Unconditionally true (matches all rows) @@ -915,8 +1448,7 @@ to O(N). VIII-1. Problem In the current implementation, a new context is started for each row -processed. -Applying PATTERN (A+) to 10 rows produces 10 contexts, +processed. Applying PATTERN (A+) to 10 rows produces 10 contexts, each of which tracks state independently. If there are N rows, the total number of states becomes O(N^2): @@ -928,12 +1460,12 @@ If there are N rows, the total number of states becomes O(N^2): VIII-2. Solution: Context Absorption -Key observation: a context started earlier contains -all matches of a later-started context (monotonicity principle). +Key observation: a context started earlier contains all matches +of a later-started context (monotonicity principle). -If Context 1 started at row 1 and matched A 5 times, -the state where Context 2 (started at row 2) matched A 4 times -is already contained within Context 1. +If Context 1 started at row 1 and matched A 5 times, the state +where Context 2 (started at row 2) matched A 4 times is already +contained within Context 1. Therefore Context 2 can be "absorbed" into Context 1. @@ -962,7 +1494,7 @@ on a non-absorbable branch, which an absorbing context cannot reproduce. Absorption therefore excludes any context holding a recorded match (see nfa_update_absorption_flags()). This costs no efficiency: SKIP PAST LAST ROW still prunes such redundant contexts once the covering match is -recorded (nfa_add_matched_state()). +recorded (nfa_prune_skipped_contexts(), called from ExecRPRProcessRow()). VIII-3. Absorption Conditions @@ -979,9 +1511,9 @@ Planner-time prerequisites (all must hold for absorption to be enabled): resolves to a different row for each context at the same currentpos. An earlier context's DEFINE result no longer subsumes a later one's, making count-dominance comparison - invalid. Rather than comparing matchStartRow at runtime - (which would complicate the absorb path), any match_start - dependency disables absorption entirely. + invalid. Rather than comparing matchStartRow at runtime (which + would complicate the absorb path), any match_start dependency + disables absorption entirely. Navigation content match_start dep. absorption ------------------------------------------------------------ @@ -1022,11 +1554,15 @@ Runtime conditions (evaluated per context pair): Cover condition (nfa_states_covered) -- "count-dominance": - A state with the same elemIdx exists in the earlier context, - and the count at that depth is greater than or equal -- then it is - covered. The earlier context's per-depth iteration count thus - dominates the later one's; this is the count-dominance comparison - referenced in VIII-3(c). + Every state of the later context must sit on an element carrying + RPR_ELEM_ABSORBABLE, the comparison point; a state anywhere else + makes the two contexts incomparable and nothing is covered. Such a + state is covered when the earlier context holds an absorbable state + with the same elemIdx whose count at that element's depth is greater + than or equal -- a same-elemIdx state that has already left the + absorbable region does not cover. The earlier context's iteration + count thus dominates the later one's; this is the count-dominance + comparison referenced in VIII-3(c). VIII-4. Dual-Flag Design @@ -1095,7 +1631,7 @@ Example: PATTERN (A | B) C The first branch A of the ALT takes precedence over the second branch B. When both A and B can match, the match via A is selected. -nfa_add_state_unique() prevents duplicate addition of the same state, +nfa_append_state_unique() prevents duplicate addition of the same state, so the state added first (= from the preferred branch) is retained. IX-3. Routing Function: nfa_route_to_elem() @@ -1111,12 +1647,12 @@ is handled in two places. nfa_route_to_elem() branches on the type of the next element: If the next element is VAR: - (1) Add the state to the context (nfa_add_state_unique) + (1) Add the state to the context (nfa_append_state_unique) (2) If the VAR has min=0, also add a skip path (recurse via next). - A reluctant VAR (A??, A*?) reverses the order: the skip path goes - first, and the waiting state is dropped if it reaches FIN - -> Expansion stops here (VAR is the element that "will consume the next - row") + A reluctant VAR (A??, A*?) reverses the order: the skip path + goes first, and the waiting state is dropped if it reaches FIN + -> Expansion stops here (VAR is the element that "will consume the + next row") If the next element is non-VAR (ALT, BEGIN, END, FIN): -> Recursively call nfa_advance_state() to continue expansion @@ -1143,8 +1679,9 @@ IX-4. Per-Element advance Behavior (b) BEGIN (nfa_advance_begin) Handles group entry. - jump points past the group: the element after END, or the post-ALT element - when the group ends an alternation branch (IV-4). + jump names the group's own END. The skip path goes to END.next without + arriving at the END; END.next is the element after END, or the post-ALT + element when the group ends an alternation branch (IV-4). BEGIN does not reset the count at its depth; it only asserts the slot is already zero. Under the count-clear policy the previous occupant @@ -1153,7 +1690,7 @@ IX-4. Per-Element advance Behavior Greedy (default): (1) Enter the group body (move via next) - (2) If min=0, also add a group skip path (move via jump) + (2) If min=0, also add a group skip path (move to END.next) Reluctant: Order reversed -- skip path first, group entry second. @@ -1170,11 +1707,11 @@ IX-4. Per-Element advance Behavior Loop-back (move via jump, repeat the group body) If the RPR_ELEM_EMPTY_LOOP flag is set: - In addition to loop-back, also add a fast-forward exit path. - This is because the body may produce an empty match, causing count - to never reach min. fast-forward resets counts[depth] to 0 - and exits via next (treating the remaining required iterations - as empty matches). + In addition to loop-back, also add a fast-forward exit path. This + is because the body may produce an empty match, causing count to + never reach min. fast-forward resets counts[depth] to 0 and exits + via next (treating the remaining required iterations as empty + matches). The body decides which of the two comes first, not the group's own greed: the fast-forward is explored first exactly when @@ -1209,7 +1746,18 @@ IX-4. Per-Element advance Behavior count >= max: Unconditional exit (move via next) - On exit: reset counts[depth] = 0. + On exit: reset counts[depth] = 0, and if the next element is an outer END, + increment the count at the outer depth, as in (c). + + Every exit and skip in the advance phase goes through + nfa_state_exit_to(), which clears the exited depth slot and increments + the count of an END it lands on: the exits of (c) and (d), the + fast-forward of (c), the min=0 VAR skip of IX-3 and the group skip of + (b). A skip that lands on an outer END therefore counts one iteration + of that group, and the group's min check and the below-min + fall-through of IX-6 read that count. The inline END chain of + nfa_match() (Chapter VII) repeats the clear and increment by hand, so + the two must change together. (e) FIN @@ -1221,10 +1769,26 @@ IX-4. Per-Element advance Behavior has the highest preferment, so the rest are inferior paths. This is the core mechanism that guarantees preferment. - In SKIP PAST LAST ROW mode, upon reaching FIN, subsequent contexts - that started within the match range are immediately pruned. - -IX-5. State Deduplication: nfa_add_state_unique() + The same rule holds inside one state's DFS. Wherever two + continuations are explored in order -- ALT branches, BEGIN's entry and + skip, END's loop-back and exit or fast-forward, a reluctant VAR's exit + and loop, an optional reluctant VAR's skip and entry -- the second is + explored only if the first did not record a match, in greedy as well + as reluctant order. matchUpdated stays set for the rest of the + advance, so every enclosing frame stops as well. Otherwise a later + continuation could reach FIN again in the same DFS (FIN is not marked + visited) or park a state that completes on a later row, and replace + the preferred match. nfa_add_matched_state() asserts that one advance + records at most one match, and nfa_append_state_unique() that nothing + is parked after it. + + In SKIP PAST LAST ROW mode the later contexts that started within the + match range become unreachable, but reaching FIN does not free them: + it only sets matchUpdated. ExecRPRProcessRow() reads that flag once + nfa_advance() has finished with the context and calls + nfa_prune_skipped_contexts() there. + +IX-5. State Deduplication: nfa_append_state_unique() When adding a new state to a context, it is compared against existing states; @@ -1246,30 +1810,39 @@ Example: PATTERN ((A? B?)+) A? and B? both have min=0, so the body can pass through without matching. If the group repeats: BEGIN -> A? skip -> B? skip -> END -> - BEGIN -> ... + A? skip -> ... The loop-back re-enters the body directly, since + END.jump is the group's first child; BEGIN is visited only on initial + group entry. To prevent this: - (1) At compile time: set the RPR_ELEM_EMPTY_LOOP flag on the END - of groups whose body is nullable. - The runtime effect of this flag is described in IX-4(c): - when count < min, a fast-forward exit path is added, - resolving the deadlock where count cannot increase due to empty - matches. + (1) At compile time: set the RPR_ELEM_EMPTY_LOOP flag on the END of + groups whose body is nullable. The runtime effect of this flag + is described in IX-4(c): when count < min, a fast-forward exit + path is added, resolving the deadlock where count cannot + increase due to empty matches. (2) At runtime: initialize the nfaVisitedEnds bitmap immediately before - DFS expansion of each state within advance (once per state). - During DFS, nfa_advance_state marks an END carrying - RPR_ELEM_EMPTY_LOOP on entry, and nothing else. Reaching a marked - END means the body derived an empty match for this iteration -- a - DFS takes only epsilon transitions, so no row was consumed since - the last visit. The state is not discarded: it leaves the group - there, so that "leave the group" keeps its rank among the - alternatives (see IX-4(c)). + DFS expansion of each state within advance (once per state). During + DFS, an END carrying RPR_ELEM_EMPTY_LOOP is marked in two places, + and nothing else is: nfa_advance_state marks it on arrival, and + nfa_advance_begin marks it when the group is entered through its + BEGIN (BEGIN.jump names the END). Reaching a marked END means the + body derived an empty match for this iteration -- a DFS takes only + epsilon transitions, so no row was consumed since the last visit, or + since the group was entered. The state that reaches it is not + discarded: it leaves the group there, so that "leave the group" + keeps its rank among the alternatives (see IX-4(c)). The entry mark + is what catches the first iteration: without it the first arrival + finds the END unmarked, an empty iteration at count >= min loops + back, and a derivation the standard excludes is kept -- + ((A? | B){1,2} C) over rows {B},{A,C},{C} then matched rows 1-2 + instead of rows 1-3. A loop-back needs no entry mark, since it + leaves the END it has just marked. Nothing else is marked, because nothing else can cycle. A revisit is a cycle only when it carries no progress, and a state is really - (elemIdx, counts) -- the identity nfa_add_state_unique() compares. + (elemIdx, counts) -- the identity nfa_append_state_unique() compares. A VAR consumes a row, and so does every derivation of a body that cannot match empty; a loop-back into either is progress, not a cycle. Marking them would discard legitimate re-entry and lose the match @@ -1326,6 +1899,31 @@ not been evaluated yet (RF_NOT_DETERMINED). A row's status against the current match result can be obtained by calling get_reduced_frame_status(). +The frame accessors in nodeWindowAgg.c -- WinGetSlotInFrame() and +ignorenulls_getfuncarginframe(), the latter serving IGNORE NULLS -- +clip every seek to the reduced frame. Each asks +row_is_in_reduced_frame() about frameheadpos and takes the length it +returns as the frame's extent: a WINDOW_SEEK_HEAD relpos at or past +that length is out of frame, as is a WINDOW_SEEK_TAIL relpos whose +backward distance reaches it, the tail case landing on +frameheadpos + relpos + length - 1. That arithmetic assumes the reduced +frame is one contiguous run beginning at frameheadpos, which holds only +because RPR rejects EXCLUDE (III-1) and pins the frame start at +CURRENT ROW; relaxing either restriction means revisiting both +accessors. The same guarantee is why a WINDOW_SEEK_TAIL access under +RPR marks frameheadpos rather than the accessed row: the frame start +never moves backwards, so the mark can never end up ahead of a row a +later fetch still needs. + +An empty match is still recorded as a success: update_reduced_frame() +passes it to ExecRPRRecordContextSuccess() with length 0, so EXPLAIN +counts it under NFA Matched. The frame accessors never see that 0, +though. row_is_in_reduced_frame() returns -1 for RF_EMPTY_MATCH exactly +as for RF_UNMATCHED, so the row's reduced frame is empty. It cannot +return 0 there: 0 is its "RPR not defined" answer, which the accessors +and the aggregation loop of X-5 read as the unclipped full frame. +RF_FRAME_HEAD returns the match length (>= 1) and RF_SKIPPED returns -2. + X-2. AFTER MATCH SKIP Determines the starting point for the next match attempt after a successful @@ -1339,6 +1937,24 @@ match: New match attempt begins from the row after the match end row. Only non-overlapping matches are possible. +The clause is optional and its absence is not neutral: the grammar +supplies SKIP PAST LAST ROW, so that is what an RPR window gets by +default, and with it the absorption prerequisite of VIII-3(a). + +RPSkipTo has a third value, ST_NONE, which the RPR productions never +produce. It is what a window with no row pattern common syntax leaves in +WindowClause.rpSkipTo, so ST_NONE means "not an RPR window", never "an +RPR window that did not say". + +The result slot of X-1 holds one match at a time, so SKIP TO NEXT ROW +needs it cleared before each row: ExecWindowAgg() calls +clear_reduced_frame() at the top of every row when rpSkipTo is +ST_NEXT_ROW. Without that, a row inside the previous match would +answer RF_SKIPPED and be reported as an interior row instead of +starting a match of its own. SKIP PAST LAST ROW keeps the slot across +rows, which is exactly what makes the interior rows of its match report +as skipped. + X-3. INITIAL vs SEEK Standard definition (ISO/IEC 19075-5 6.12): @@ -1360,18 +1976,39 @@ X-4. Bounded Frame Handling offset (n >= 1) FOLLOWING; a CURRENT ROW end or a zero offset is rejected, since it would reduce the frame to the single current row. + The zero-offset rejection happens only at execution, in + calculate_frame_offsets(), the same place the ordinary frame bounds + are computed. The parser accepts any offset FOLLOWING, so a literal + 0 and an offset that is not constant until the scan -- a bind + parameter, say -- both reach that check, and it raises "frame ending + offset must be positive with row pattern recognition". + When the frame is bounded (e.g., ROWS BETWEEN CURRENT ROW AND 5 - FOLLOWING), ExecRPRProcessRow receives hasLimitedFrame=true and - frameOffset indicating the upper bound. Before the match phase, - any context whose match has exceeded the frame boundary - (currentPos >= matchStartRow + frameOffset + 1) is finalized early - by forcing a mismatch. This prevents matches from extending beyond - the window frame. The sum is clamped to PG_INT64_MAX on overflow. + FOLLOWING), ExecRPRProcessRow derives the upper bound itself from + winstate->frameOptions and winstate->endOffsetValue, using a + frameOffset of -1 to mean the frame runs to the partition end. In the + match phase, a context whose frame boundary has been reached + (currentPos == matchStartRow + frameOffset + 1) is matched with a NULL + varMatched instead, which forces a mismatch and finalizes it. This + prevents matches from extending beyond the window frame. The sum is + clamped to PG_INT64_MAX on overflow. Note that bounded frames also disable context absorption at the planner level (see VIII-3(b)), since the frame boundary breaks the monotonicity assumption required for correct absorption. +X-5. Window Aggregates over the Reduced Frame + + RPR switches off the moving-aggregate path. eval_windowaggregates() + marks every plain aggregate for restart on every row when + rpr_is_defined(), because one row's reduced frame need not overlap the + next row's at all, and overlap is the assumption an inverse transition + function rests on. The aggregation loop then reads the reduced frame + itself to find where to stop: it stops when currentpos is determined + but aggregatedupto is not, when row_is_in_reduced_frame() reports an + unmatched row, or when the base row of the aggregation turns out to be + an interior (RF_SKIPPED) row of a match. + Chapter XI Worked Example: Full Execution Trace ============================================================================ @@ -1441,15 +2078,18 @@ RPR_VAR_UNEVALUATED. Phase 2 (Absorb): skipped (no states) Phase 3 (Advance): skipped (no states) + Context C1 created (matchStartRow=1). + Initial advance: C1.states = [{elemIdx=0, counts=[0]}] + C0.states is empty, so the loop terminates. - matchEndRow < matchStartRow -> unmatched. + matchedState is NULL -> unmatched. --- Row 1 (price=110) --- update_reduced_frame(1) called. - Context C1 created (matchStartRow=1). - Initial advance: C1.states = [{elemIdx=0, counts=[0]}] + C1 is the head context and starts at 1, so it is the target. + C1.states = [{elemIdx=0, counts=[0]}] DEFINE values, row 1: A: 110 > PREV(100) -> true @@ -1521,7 +2161,10 @@ RPR_VAR_UNEVALUATED. Early termination: no remaining states, so completed immediately. C1.states = [] (empty after reaching FIN) - C1.states is empty and matchEndRow=3 >= matchStartRow=1 -> match succeeds. + Context C4 created (matchStartRow=4). + + C1.states is empty and matchedState is set -> match succeeds, + spanning matchStartRow=1 through matchEndRow=3. rpr_match_start = 1, rpr_match_length = 3 @@ -1530,7 +2173,7 @@ RPR_VAR_UNEVALUATED. update_reduced_frame(4) called. C3 was pruned when C1 recorded its match: under SKIP PAST LAST ROW every context that started within the match's range is freed there. - New context C4 created (matchStartRow=4). + C4 is the head context and starts at 4, so it is the target. DEFINE values, row 4: A: 130 > PREV(115) -> true @@ -1556,8 +2199,8 @@ XII-1. Flat Array vs Tree-Based NFA RPRPatternElement structs rather than as a tree. The array is contiguous and cache-friendly, elements reference each - other by 2-byte index instead of by pointer, and the whole structure - can be serialized with memcpy when passed to plan nodes. + other by 2-byte index instead of by pointer, and the whole array can + be copied with a single memcpy when the plan node is copied. XII-2. Forward-only Execution vs Backtracking @@ -1568,9 +2211,9 @@ XII-2. Forward-only Execution vs Backtracking forward-only NFA simulation is polynomial. Forward-only also fits the window pipeline, which delivers sorted rows sequentially: it needs no re-fetching of earlier rows, and each row's DEFINE conditions (SQL - expressions such as PREV or running aggregates, with high re-evaluation - cost) are evaluated once per row and cached; only match_start-dependent - variables are re-evaluated per context (VI-4). DFS order yields preferment + expressions such as PREV or NEXT navigation, with high re-evaluation cost) + are evaluated once per row and cached; only match_start-dependent variables + are re-evaluated per context (VI-5). DFS order yields preferment naturally, with greedy or reluctant behavior per quantifier obtained by reversing that order. @@ -1614,10 +2257,10 @@ XII-5. Execution Optimization Summary (2) Group Skip (IX-4(b)) - At the BEGIN of a group with min=0, uses jump to skip the entire - group. Moves directly to the first element outside the group without - exploring the group body. Greedy enters then skips; Reluctant skips - then enters. + At the BEGIN of a group with min=0, skips the entire group through + END.next (BEGIN.jump names the END). Moves directly to the first + element outside the group without exploring the group body. Greedy + enters then skips; Reluctant skips then enters. Significance: For optional groups (min=0), immediately generates a skip path without exploring the body, avoiding unnecessary DFS @@ -1625,16 +2268,15 @@ XII-5. Execution Optimization Summary (3) State Deduplication (IX-5) - During advance, DFS may generate states with the same (elemIdx, - counts) combination through multiple paths. Additionally, for - group absorption, nfa_match performs inline advance from bounded - VARs (count >= max) within the absorbable region (ABSORBABLE_BRANCH) - through END chains to reach the comparison point (ABSORBABLE END). - This process can also produce duplicate states reaching the same END. - nfa_add_state_unique() blocks duplicate addition during advance. The - inline advance adds nothing -- it moves states in place -- so the - duplicates it leaves on an END are collapsed when the next advance - re-adds their successors. + During advance, DFS may generate states with the same (elemIdx, counts) + combination through multiple paths. Additionally, for group absorption, + nfa_match performs inline advance from bounded VARs (count >= max) within + the absorbable region (ABSORBABLE_BRANCH) through END chains to reach the + comparison point (ABSORBABLE END). This process can also produce + duplicate states reaching the same END. nfa_append_state_unique() blocks + duplicate addition during advance. The inline advance adds nothing -- it + moves states in place -- so the duplicates it leaves on an END are + collapsed when the next advance re-adds their successors. Significance: Prevents exponential growth of the state count in ALT branches and quantifier expansion. Since DFS order causes the @@ -1645,7 +2287,7 @@ XII-5. Execution Optimization Summary (4) Cycle Detection and Fast-Forward (IX-6, IX-4(c)) When a nullable group body (e.g., A?) repeats empty matches, - the END -> BEGIN loop-back can continue indefinitely. + the END -> first-child loop-back can continue indefinitely. Two mechanisms resolve this: - A visited bitmap (nfaVisitedEnds) marks a nullable END whose body @@ -1653,10 +2295,9 @@ XII-5. Execution Optimization Summary state leaves the group there once count >= min; below min it falls through to the must-loop path, whose per-arrival count increment reaches min in bounded steps (termination) - - At an END with the RPR_ELEM_EMPTY_LOOP flag set, when - count < min, the remaining required iterations are treated as - empty matches and a fast-forward exit path out of the group is - added (correctness) + - At an END with the RPR_ELEM_EMPTY_LOOP flag set, when count < min, + the remaining required iterations are treated as empty matches and a + fast-forward exit path out of the group is added (correctness) Significance: Cycle detection guarantees termination, and fast-forward guarantees that the min condition is satisfied. @@ -1701,6 +2342,449 @@ XII-5. Execution Optimization Summary level, achieving O(n^2) -> O(n) time complexity. Without this, performance degrades sharply on long partitions. +Chapter XIII Planner Integration +============================================================================ + +The compilation of Chapter IV is only part of what the planner does with a +row pattern window. The rest is spread over the code that handles window +clauses in general, and it exists because DEFINE is the one window clause +field that carries an expression tree of its own. This chapter collects +those contracts. Each is a rule that a change elsewhere in the planner can +break without any RPR-specific code being touched. + +XIII-1. Ownership of the DEFINE Expression Tree + +defineClause is the one field in which a window clause owns an expression +tree. partitionClause and orderClause hold only SortGroupClause references +into the query targetlist, and a frame offset may not contain Vars, so for +every other window clause field a Query-wide scan sees the expressions +through the targetlist. The DEFINE expressions are reached only through the +window clause itself. + +query_tree_walker() and query_tree_mutator() (nodeFuncs.c) therefore descend +into wc->defineClause in both branches, the QTW_EXAMINE_SORTGROUP one and +the plain one, and expression_tree_walker() descends into it from +T_WindowClause. Every Query-wide rewriter thus reaches the Vars a DEFINE +clause holds, and cannot tell a dead window's Vars from a live one's. Join +removal, for instance, deletes a relid from the whole parse tree once +nothing needs the relation, which requires that no ordinary Var of it be +left anywhere. + +Whoever decides that a window clause will not be executed is therefore +responsible for emptying defineClause at that moment, rather than expecting +later scans of the tree to skip it. That decision is made in one place, +grouping_planner() (planner.c): it empties defineClause in every window +clause that is not in activeWindows, which also covers a query whose window +functions were all folded away and so has no active window at all. The +generic walkers are not the only reader: build_base_rel_tlists() marks what +a DEFINE clause reads as needed at relation 0 (XIII-2), and a column needed +by nothing that runs would keep an outer join from being removed. +grouping_planner() runs for a subquery too, when that subquery is planned, +and so before the subquery's own query_planner() builds its relation +targetlists or removes any join. Planning the outer query does not touch a +subquery's DEFINE clause (XIII-2). Only defineClause is cleared, never the +WindowClause itself: winref is a one-based index into windowClause, so the +list must keep its length and its order. rpPattern stays as well. It +holds no Vars, an undefined pattern variable simply matches TRUE, and it is +what marks the clause as a row pattern window (XIII-6). + +XIII-2. Keeping a DEFINE-only Column Alive + +A column that nothing reads except a DEFINE expression still has to reach +the WindowAgg, and nothing in subquery pruning has to protect it for that. +A DEFINE clause reads the column of a relation in its own query's range +table, through a Var of its own level; it never reads the subquery output +entry that may carry the same column upward. build_base_rel_tlists() +(initsplan.c) marks every Var and PlaceHolderVar the clause holds as needed +at relation 0, so the column is carried to the top of the join tree, and +make_window_input_target() (planner.c) adds it to the WindowAgg's input +target. When remove_unused_subquery_outputs() (allpaths.c), planning the +outer query, replaces an output entry no outer reference reads with a NULL +constant, that changes what the subquery returns and not what its DEFINE +clause sees. The function has no row pattern code. + +When the relation a DEFINE clause reads is itself a subquery, the Var names +one of that subquery's output columns, and the mark build_base_rel_tlists() +made puts it in the relation's reltarget. remove_unused_subquery_outputs() +takes attrs_used from that reltarget, so the column is kept like any other +the upper query reads. + +A window clause that will not run gets no such mark: grouping_planner() +empties its DEFINE clause before query_planner() calls +build_base_rel_tlists() (XIII-1). + +XIII-3. A DEFINE Clause That Takes Part in Grouping + +A DEFINE expression may reference a GROUP BY column, so parseCheckAggregates() +puts GROUP Vars into defineClause the same way it puts them into the +targetlist, and subquery_planner() expands them again with +flatten_group_exprs(). It passes the same root it passes for the targetlist, +so that the varnullingrels a grouping set attached survive onto the +replacement. + +Expanding them separately is not an option. set_upper_references() later +matches the DEFINE copy of an expression against the targetlist copy and +insists the two agree; a mismatch is not a wrong answer at runtime but a +"variable not found in subplan target list" failure at plan time. + +This is also why make_window_input_target() stops at a subexpression the +input target already computes whole. The grouping step produces only that +expression, so asking for the Vars underneath it would ask the grouping step +for columns it cannot produce. This is the one rule the havingQual handling +it is modelled on does not need: make_group_input_target() builds the input +of the grouping step, while the window input target sits above it. + +XIII-4. Navigation Arguments, Subquery Pull-up and Join Aliases + +A navigation's argument is evaluated at the row the navigation lands on, not +at the row being tested (VI-3). When subquery pull-up substitutes a +subquery output expression into a DEFINE clause, a replacement that does not +depend on the row -- a constant, or anything built only from values outside +the subquery -- must not simply be folded into that argument, or PREV(x) +would collapse to a value that no longer varies with the row it is read at. + +replace_rte_variables_mutator() (rewriteManip.c) therefore handles RPRNavExpr +itself instead of leaving it to the generic mutator: it sets in_rpr_nav_arg +while it walks arg and restores the previous value before walking offset_arg +and compound_offset_arg, which are ordinary expressions read at the current +row. pullup_replace_vars_callback() (prepjointree.c) adds that flag to the +conditions that make a replacement a wrapping candidate, beside +varnullingrels and the caller's own wrap option. A replacement that is +itself a simple Var or PlaceHolderVar still escapes the wrapper, as does an +expression that contains the subquery's Vars and no non-strict constructs; +this costs nothing since such a replacement already varies with the row. +Anything else -- including the row-independent expression that would +otherwise be folded into the argument -- comes back wrapped in a +PlaceHolderVar. + +The pull-up does not reach the DEFINE clause through query_tree_mutator(). +perform_pullup_replace_vars() (prepjointree.c) names each part of the upper +query it rewrites, and among them a loop over windowClause passes every +non-empty defineClause to pullup_replace_vars(). subquery_planner() does +the same for flatten_group_exprs() (XIII-3). The guarantee of XIII-1 covers +only the generic walkers; a pass that rewrites the upper query field by +field has to list defineClause itself. + +Join alias expansion substitutes into a DEFINE clause as well: a Var naming +a join output column is replaced by the expression behind it. +flatten_join_alias_vars_mutator() (var.c) carries its own copy of the same +protection. It handles RPRNavExpr itself and sets in_rpr_nav_arg over arg +alone, as replace_rte_variables_mutator() does, and while that flag is set +it wraps a replacement in a PlaceHolderVar unless it is a Var or a +PlaceHolderVar of the same level. Unlike pullup_replace_vars_callback(), +it wraps a strict expression over row Vars as well. +It wraps only when it has a PlannerInfo; flatten_join_alias_for_parser() +passes none and gets the replacement unwrapped. + +XIII-5. Preprocessing a DEFINE Clause as a Qual + +A DEFINE condition is a search condition in the sense WHERE is one: the +parser coerces it to boolean through transformWhereClause() (III-3), and a +row for which it yields FALSE or NULL is not a match. subquery_planner() +(planner.c) therefore hands each condition to preprocess_expression() as +EXPRKIND_QUAL, in the loop that preprocesses the window clause's frame +offsets. That is after subquery pull-up, and before the GROUP Vars of +XIII-3 are expanded and before grouping_planner() empties the DEFINE clause +of a window it will not run (XIII-1). + +As a qual the condition goes through every step a WHERE clause does. Join +alias Vars are flattened first (XIII-4). eval_const_expressions() then folds +constants, inlines SQL functions and inserts the actual values of default +arguments. canonicalize_qual() runs with is_check false, so a NULL +constant at the top level of an AND or OR is treated as FALSE, which is +sound only because a NULL result and a FALSE one are told apart nowhere +downstream. Uplevel Vars become Params, and the result comes back as an +implicit-AND list. A TargetEntry holds one expression, so the loop turns +the list straight back into one with make_ands_explicit(); a condition that +folds to TRUE is left as a constant TRUE. + +The NFA evaluates a DEFINE at most once per row and caches the result +(VI-3), re-evaluating only the match_start dependent variables of VI-5. +The number of evaluations is not something a query can rely on, so a +volatile function is rejected. The check runs right after the +preprocessing, over the window clause's whole defineClause, and raises +"DEFINE clause cannot contain volatile functions". +It sits in the planner rather than in parse analysis to follow the +convention of not checking expression volatility while parsing, and running +after folding matters both ways. Folding can remove a volatile call -- a +dead CASE arm, or a VOLATILE SQL function whose body inlines to a constant +-- and it can bring in one parse analysis never saw: a STABLE function +whose default argument is volatile gets that argument spliced in here +(rpr_off_leak() in rpr_base.sql). The check sees only what is still there +when this subquery is planned. A window dropped with a subquery that +pull-up flattens, and a subquery the planner never plans, are not checked, +which is the same rule that lets a volatile fold away. A window that no +window function references is checked all the same: grouping_planner() +empties its DEFINE clause (XIII-1) only after the check has run. In a +subquery kept by OFFSET 0 such a window's volatile DEFINE is therefore +rejected, as it is at the top level. + +A volatile expression the DEFINE clause shares with GROUP BY passes the +check, and rightly so. Parse analysis has replaced the DEFINE copy with a +GROUP Var (XIII-3), and although that Var is expanded back after the check, +setrefs.c resolves the expansion against the grouping step's output: the +pattern match reads the value GROUP BY computed once per input row, and no +volatile evaluation is left in the DEFINE clause. + +Downstream the condition is an ordinary expression again. +set_upper_references() (setrefs.c) fixes its Vars to OUTER_VAR (XIII-7). +ExecInitWindowAgg() (nodeWindowAgg.c) splits it back into an implicit-AND +list with make_ands_implicit() and compiles it with ExecInitQual(), which +builds no ExprState at all for a constant TRUE. nfa_eval_var_match() +(execRPR.c) evaluates it with ExecQual() in rprContext (VI-3), so a NULL +result is no match, and a missing ExprState is always a match. + +The compiled conditions go into defineClauseExprs in DEFINE order, and the +list index is the varId, because buildRPRPattern() (rpr.c) enters the +DEFINE names into varNames in that order before it scans PATTERN. Nothing +between the two checks that index. Every step that touches the list, this +preprocessing included, keeps its order today, but a reorder would +evaluate one variable's condition for another and give a wrong answer with +nothing to show for it. ExecInitWindowAgg() therefore asserts, for each +entry, that its index is below numVars and that varNames holds the entry's +resname at that index. + +XIII-6. Optimizations an RPR Window Is Excluded From + +Two prosupport-driven optimizations skip a row pattern window. Both +recognize it by a non-null rpPattern, not by a non-empty defineClause, +which grouping_planner() may have emptied (XIII-1). + +find_window_run_conditions() (allpaths.c) declines to push a run condition +down. A run condition stops evaluating a monotonic window function once the +qual can no longer be satisfied; but in a row pattern window the partition is +divided into reduced frames, and each one has to be evaluated to the end of +the partition, so an early stop would cut a later reduced frame short. + +optimize_window_clauses() (planner.c) does not offer the clause to the +window functions' support functions at all. A support function is free to +propose any frameOptions it likes, and RPR requires the frame shape of +Chapter I; skipping the clause outright is what keeps one from replacing the +frame with a shape RPR cannot run. The duplicate-clause check that follows +a successful rewrite still compares rpSkipTo, defineClause and rpPattern. + +XIII-7. Var Fixup and Costing + +The DEFINE expressions cross the plan-node interface inside the WindowAgg, +so set_upper_references() (setrefs.c) rewrites their Vars to OUTER_VAR +alongside the node's targetlist and qual. That is what lets the NFA +evaluate a DEFINE against the outer tuple slot (VI-3). The generic plan +walk does not reach a window clause's own expressions, so the fixup is +spelled out for defineClause by hand. + +SS_finalize_plan() has the same blind spot and the same fix. A DEFINE +expression may carry a Param -- a navigation offset settled per scan is the +case that matters (VI-6) -- and the parameter sets a plan node advertises are +collected by walking its expressions. The T_WindowAgg arm therefore runs +finalize_primnode() over defineClause beside startOffset and endOffset, so +that a DEFINE Param reaches extParam and allParam. A parameter missing from +those sets is one that does not force a rescan when it changes. + +Costing sees an RPR window only through the WindowClause. When rpPattern is +set, cost_windowagg() (costsize.c) charges each DEFINE expression's per-tuple +cost once per input tuple, once for every DEFINE variable, on top of the +window functions' own costs. That is an upper bound, since the lazy +evaluation of VI-3 skips a variable no active state tests at that row, but it +keeps an expensive DEFINE visible to the choice of plan below the WindowAgg. + + +Chapter XIV Deparse and EXPLAIN Output +============================================================================ + +An RPR window is printed back by two independent printers, and they produce +different text on purpose. Both must round-trip: what pg_get_viewdef() +prints has to re-parse into the same query, and what EXPLAIN prints has to +describe the pattern the executor will actually run. + +XIV-1. Two Printers, Two Spellings + +pg_get_viewdef() and friends (get_rule_windowspec(), get_rule_pattern() in +ruleutils.c) walk the parse tree the parser built, so a stored view shows +the PATTERN as the user wrote it. The clause is emitted in full, each part +on its own line: AFTER MATCH SKIP, then INITIAL, then PATTERN, then DEFINE. +INITIAL is printed unconditionally, since SEEK is not implemented and the +window clause records no flag that would distinguish the two. + +EXPLAIN (show_window_def(), deparse_rpr_pattern() in explain.c) walks the +compiled element array instead, so it shows the pattern after the Phase 1 +rewrites of IV-3: PATTERN (A A) is stored as written but explains as "a{2}". +EXPLAIN also parenthesizes every group and every alternation for +self-consistency, so a top-level A | B explains as "(a | b)" where +pg_get_viewdef() prints it bare. Only the pattern is shown; the DEFINE +clause and the skip mode do not appear in EXPLAIN output. + +XIV-2. Reading the Compiled Array + +Two markers may follow a quantifier in EXPLAIN's output, and they report the +flags of IV-5: "#" on an element carrying RPR_ELEM_ABSORBABLE, the comparison +point, and "~" on one carrying only RPR_ELEM_ABSORBABLE_BRANCH, the region. +So "a+#" is an absorbable A+, "(a~ b~){2,}#" an absorbable (A B){2,}, and a +pattern that prints no marker at all was found unabsorbable. Neither +character can occur in an unquoted variable name, and a name containing one +is double-quoted, so a marker is never read as part of a name. + +The printer leans on two compile-time invariants. A {1,1} group never +reaches the array (IV-3 (h)), so every surviving BEGIN/END pair carries a +non-trivial quantifier, which is read from the END element. A fixed count +is normalized to greedy (IV-3 (i)), so a trailing "?" in EXPLAIN's output is +always reluctance and never {0,1}. + +It also relies on two properties of the SEP chain of IV-4. A nested +alternation's last SEP has its next redirected past the enclosing +alternation, exactly as a branch tail does, so next is not a way to find +where an alternation ends. The last SEP is however always emitted as the +alternation's final element, so the index of the last SEP plus one is this +alternation's own post-ALT element. That is how rpr_alt_scope_end() +(explain.c) bounds an alternation and walks its branch boundaries, and a +change to the SEP chain has to keep both properties. + +XIV-3. Pattern Variable Quoting + +A pattern variable is printed by quote_pattern_variable() (ruleutils.c), +which is quote_identifier() plus one extra case: the name permute is quoted +even though PERMUTE is an unreserved keyword. A bare permute followed by +'(' inside a PATTERN would be re-read as the PERMUTE syntax the parser +rejects, so the deparsed text would no longer re-parse. The DEFINE clause +has no such hazard, because a name there is always followed by AS; +get_rule_define() therefore uses plain quote_identifier(), and one variable +can legitimately print bare in DEFINE and quoted in PATTERN. + +quote_pattern_variable() is exported from ruleutils.h precisely so that +EXPLAIN's own printer can call it. Both printers must spell a variable the +same way, so a new printer calls it rather than quote_identifier(). + +XIV-4. Reluctance On A Fixed Count + +The parse-tree printer emits nothing at all for a {1,1} node, so a reluctant +{1,1} would print as a bare '?', which re-parses as the {0,1} quantifier. +It therefore emits an explicit {1} first, and A{1}? deparses as a{1}?. + +EXPLAIN's printer has no such case and instead asserts min != max on a +reluctant element, because IV-3 (i) has already cleared reluctance wherever +min == max. The parse tree ruleutils.c reads has not been through that +pass: buildRPRPattern() runs Phase 1 on a copy of the pattern and never +writes back to the WindowClause. That is why only one of the two printers +needs the guard. + +XIV-5. Settling the Column Names a DEFINE Clause References + +Inside DEFINE a column reference has no qualifier available, because the +qualifier slot names a pattern variable. get_rule_define() prints with +varprefix off for that reason, so every column it prints has to resolve, +unqualified, to the same column when the text is read back. + +set_deparse_for_query() calls mark_define_columns() (ruleutils.c) before +set_using_names() chooses any USING name and before column aliases are +assigned. It collects the level-zero Vars of every window's defineClause and +hands each to mark_define_column(), which makes the printed name unique +within the owning RTE and against the names reserved so far, stores it in +that RTE's colnames entry, and reserves it with reserve_colname() in +dpns->using_names, the list that holds the globally unique USING names. No +other RTE may then be given that name, so a same-named column elsewhere in +the query is uniquified and its RTE gets a column alias list. Without this, +another relation of the query acquiring such a column would make an existing +view's DEFINE clause ambiguous on re-parse. + +Settling these names first lets set_using_names() choose around them rather +than over them. Before it invents a name for a merged column it asks +preset_input_colname() whether an input of the join, followed down through +joinaliasvars, has settled one already, and if so adopts that name. + +mark_define_column() has to resolve the Var the way the printer will resolve +it -- through varnosyn/varattnosyn, which the parser sets on every Var it +makes, so that a Var reading a join column names the join RTE -- or the name +it settles is not the name that reaches the output. A system column, whose +name comes from the catalog, cannot be renamed and is only reserved. The +other columns that cannot be renamed, those of a relation RTE outside the +FROM clause, are not reachable from DEFINE, where the qualifier slot names a +pattern variable; nor are whole-row references, which the parser rejects, or +dropped columns. + +The guarantee rests on set_relation_column_names(), whose rules apply to +every query, with a DEFINE clause or not. For a function RTE it appends the +columns the composite result type has gained since parse time +(function_rte_late_colnames(); only for a single function without WITH +ORDINALITY or a column definition list), so a reserved name is kept off +them and the positional column alias list counts them. A table function +RTE (XMLTABLE, JSON_TABLE) prints a column alias list when it has +user-written column aliases or a column was renamed, as other non-relation +RTEs do. The columns colname_is_fixed() reports are never renamed there. + +XIV-6. Navigation Names Shadow User Functions + +Within a DEFINE clause the parser binds an unqualified prev, next, first or +last to a navigation operation before any catalog lookup (III-5), so an +unqualified call to a user function of one of those names would change meaning +across a deparse and re-parse. get_rule_define() sets inRPRDefine in the +deparse context for the duration of the clause, and generate_function_name() +force-qualifies exactly those four names while it is set, the same treatment +cube and rollup get inside GROUP BY. Only the exact lower-case spellings are +at risk: a mixed-case function name deparses quoted and cannot match the +parser's downcased comparison. + +inRPRDefine is part of the deparse context, so every routine that builds one +initializes it, and get_rule_define() saves and restores it around the clause +the way it does varprefix. + +XIV-7. DEFINE Vars Under a GROUP RTE + +When a query groups, parse analysis replaces grouped expressions with Vars of +a GROUP RTE, and the deparser expands those back with flatten_group_exprs() +before printing. The targetlist and havingQual expansion does not reach a +window's DEFINE clause, yet that clause carries GROUP Vars of its own whenever +it references a subexpression the grouping step computes (XIII-3). +get_query_def() therefore runs flatten_group_exprs() over each window's +defineClause as well. Without it the deparsed DEFINE would name the grouping +step's output rather than the expression the user wrote, and the view would +not re-parse. + +Expansion alone is not enough when the grouped expression is written over a +column merged by USING. What it brings back is then the expression the parser +built for the merge -- for a FULL join, a COALESCE of the two inputs -- and +because a DEFINE clause prints without qualifiers that would come out as +COALESCE(id, id), which re-parses as one merged column nested inside another. +collapse_define_join_vars() runs right after the expansion and folds each such +expression, recognised against the join RTEs' joinaliasvars with nulling marks +ignored, back into a Var naming the merged column, which is what the user +wrote. Inputs are folded before the node that holds them, so a merge built +over another merge is seen whole once its inner merge has become a Var again. + +XIV-8. Navigation Trim in EXPLAIN + +The two navigation reaches of VI-6 are printed as Nav Mark Lookback and Nav +Mark Lookahead, read straight out of the WindowAggState. They appear for a +plain EXPLAIN as well, because executor init runs and that is where a +constant offset is settled. Each dimension prints its kind rather than +merely a number: "runtime" for RPR_NAV_OFFSET_NEEDS_EVAL, since the value is +only known per scan, "retain all" for RPR_NAV_OFFSET_RETAIN_ALL, and the +offset itself for RPR_NAV_OFFSET_FIXED. Only the backward dimension can +reach the retain-all state; a forward reach that overflows clamps to +PG_INT64_MAX, which prints as "infinite", and EXPLAIN asserts that the +lookahead is never retain-all. + +XIV-9. NFA Counters Under EXPLAIN ANALYZE + +With ANALYZE, once the tuplestore exists, show_windowagg_info() (explain.c) +adds the matcher's counters from the WindowAggState via show_rpr_nfa_stats(). +States: peak live, total created, and merged, the new states +nfa_append_state_unique() discards as duplicates (IX-5). Contexts: peak live +and total created, plus the outcome counters, which the code that frees a +context updates; ExecRPRFreeContext() itself records no outcome. +update_reduced_frame() counts the context whose result it registers as +matched, with length matchEndRow - matchStartRow + 1 (0 for an empty match), +or else as failed. ExecRPRCleanupDeadContexts() counts a context that died +without a recorded match as failed, unless it never processed its start row, +as with one created for a row beyond the partition. Absorption counts its +context as absorbed (VIII), and SKIP PAST LAST ROW counts the contexts it +frees because they start inside a recorded match as skipped (X-2). +ExecRPRRecordContextFailure() reports a failure of length 1 as pruned and any +other as mismatched, so the pruned counter is not SKIP pruning. Every length +but a match's is lastProcessedRow - matchStartRow + 1. Matched, mismatched, +absorbed and skipped carry min/max/avg lengths, shown only when the count is +nonzero. The text format folds these into the NFA States, NFA Contexts and +NFA lines and prints the absorbed/skipped line only when either is nonzero; +the other formats emit every count as its own property. + Appendix A. Data Structure Relationship Diagram ============================================================================ @@ -1721,6 +2805,7 @@ Appendix A. Data Structure Relationship Diagram WindowAgg (plan node) |--- rpSkipTo: RPSkipTo |--- defineClause: List + |--- defineMatchStartDependent: Bitmapset* (see VI-5) +--- rpPattern: RPRPattern* |--- numVars: int |--- varNames: char** @@ -1743,7 +2828,7 @@ Appendix A. Data Structure Relationship Diagram |--- defineClauseExprs: List (DEFINE order, index == varId) |--- nfaVarMatched: RPRVarMatch[] (per-row tri-state cache, lazy) |--- defineMatchStartDependent: Bitmapset* (match_start_dependent - | DEFINE vars; see VI-4) + | DEFINE vars; see VI-5) |--- nfaVisitedEnds: bitmapword* (cycle detection) |--- nfaVisitedMinWord / nfaVisitedMaxWord: int16 | (touched-word range for fast reset) @@ -1757,7 +2842,7 @@ Appendix A. Data Structure Relationship Diagram | | +--- isAbsorbable | |--- matchStartRow, matchEndRow | |--- lastProcessedRow - | |--- matchedState (cloned on FIN arrival) + | |--- matchedState (the FIN-arriving state, moved here) | |--- hasAbsorbableState | +--- allStatesAbsorbable |--- nfaContextFree (recycling pool) @@ -1792,9 +2877,9 @@ B-3. PATTERN (A | B | C) ---------------------------------------- 0 ALT 0 1 1 1 2 next -> branch 1, jump -> SEP1 1 A 1 1 1 7 -1 branch 1 -> post-ALT - 2 SEP 0 1 1 3 4 branch 1 term.; next -> B, jump -> SEP2 + 2 SEP 0 1 1 3 4 branch 1 term.; next B, jump SEP2 3 B 1 1 1 7 -1 branch 2 -> post-ALT - 4 SEP 0 1 1 5 6 branch 2 term.; next -> C, jump -> SEP3 + 4 SEP 0 1 1 5 6 branch 2 term.; next C, jump SEP3 5 C 1 1 1 7 -1 branch 3 -> post-ALT 6 SEP 0 1 1 7 -1 branch 3 terminator (last) 7 FIN 0 1 1 -1 -1 @@ -1807,7 +2892,7 @@ B-4. PATTERN ((A B)+ C) idx varId depth min max next jump flags -------------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH + 0 BEGIN 0 1 INF 1 3 ABSORBABLE_BRANCH 1 A 1 1 1 2 -1 ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 ABSORBABLE_BRANCH 3 END 0 1 INF 4 1 ABSORBABLE | ABSORBABLE_BRANCH @@ -1821,7 +2906,7 @@ B-5. PATTERN ((A | B)+? C) idx varId depth min max next jump flags ------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 7 RELUCTANT, group start + 0 BEGIN 0 1 INF 1 6 RELUCTANT, group start 1 ALT 1 1 1 2 3 next -> branch 1, jump -> SEP1 2 A 2 1 1 6 -1 branch 1 -> END 3 SEP 1 1 1 4 5 branch 1 term.; jump -> SEP2 @@ -1838,7 +2923,7 @@ B-6. PATTERN ((A+ B)+ C) -- Absorbability flag example idx varId depth min max next jump flags --------------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 4 ABSORBABLE_BRANCH, group start + 0 BEGIN 0 1 INF 1 3 ABSORBABLE_BRANCH, group start 1 A 1 1 INF 2 -1 ABSORBABLE | ABSORBABLE_BRANCH 2 B 1 1 1 3 -1 3 END 0 1 INF 4 1 group end @@ -1854,7 +2939,7 @@ B-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT idx varId depth min max next jump flags --------------------------------------------------------------------------- - 0 BEGIN 0 1 INF 1 8 ABSORBABLE_BRANCH + 0 BEGIN 0 1 INF 1 7 ABSORBABLE_BRANCH 1 ALT 1 1 1 2 4 ABSORBABLE_BRANCH; jump -> SEP1 2 A 2 1 INF 3 -1 ABSORBABLE | ABSORBABLE_BRANCH 3 B 2 1 1 7 -1 branch 1 -> END @@ -1873,8 +2958,9 @@ B-7. PATTERN ((A+ B | C*)+ D) -- Per-branch absorption in ALT END has EMPTY_LOOP: branch 2 (C*) is nullable, making the group body nullable. BEGIN and ALT get ABSORBABLE_BRANCH (on the path to absorbable elements). - The SEP branch-separator markers carry no flags: computeAbsorbabilityRecursive - walks the SEP chain but marks only branch content. + The SEP branch-separator markers carry no flags: + computeAbsorbabilityRecursive walks the SEP chain but marks only + branch content. References: -- 2.54.0 (Apple Git-157)