Re: Row pattern recognition

Hi hackers,

This is another increment on top of v49, following the 07-13 posting. It
carries what has accumulated since then: the review results Tatsuo sent on
07-19, the change he asked for, the INITIAL_P rename Seongjun contributed,
and several defects found in the navigation and NFA code. The attachments
are named nocfbot-XXXX-*.txt so that cfbot does not pick them up.

The bands are the same as last time:

0XXX build fixes on top of the base (rebase, platform)
1XXX reviewed by Tatsuo
2XXX awaiting review from Tatsuo
3XXX Henson, in progress
4XXX Jian, in progress
8XXX restore pre-existing code (paired with 9XXX)
9XXX separately committable (paired with 8XXX)

Within 1XXX and 2XXX the last three digits belong to the patch and do not
change; only the leading digit moves as the status does. The other bands
are numbered on their own, from 001, so a few of their numbers have shifted
since last time. The numbers follow the apply order, so applying them in
order works.

This posting's fixed branch, which I will not rewrite, is:

https://github.com/assam258-5892/postgres/tree/RPR-20260719

What moved since 07-13:

- Tatsuo reviewed v50-0008..0013 on 07-19 ("2009-2014 look good to
me"), so those six move from 2XXX to 1XXX as 1009..1014. The 1XXX
band is now v50-0001..0013.

- 2015 (the unbounded-quantifier sentinel) is revised per Tatsuo's
comment; see the 2XXX section.

- 0002 is new: the INITIAL_P rename Seongjun posted, carried here in
the build-fix band.

- 3XXX gained four patches from the defect work, so the alternation
branch-walk fix that was 3001 last time is 3002 now.

0XXX -- build fixes on top of the base

0001 Adjust row pattern recognition for fix_upper_expr() signature
change
Unchanged from last time. Commit 3b0991059f3 removed the
nrm_match parameter from fix_upper_expr(); drop the stale
NRM_EQUAL the DEFINE clause fixup still passed.

0002 Rename INITIAL keyword token to INITIAL_P to avoid macro
collision (Seongjun Shin)
With bison 2.3 -- still emitted by macOS's system bison, and the
minimum the tree supports -- the INITIAL token becomes
"#define INITIAL" in gram.h and collides with flex's built-in
INITIAL start condition, producing -Wmacro-redefined in the
backend and ecpg scanners. Rename the token to INITIAL_P,
following the existing convention (NULL_P, IN_P, ...); the SQL
keyword "initial" is unchanged. This is Seongjun's patch,
confirmed here on macOS/bison 2.3 and on Rocky/bison 3.8.2; I am
carrying it in this band so the series stays consistent until it
is folded into the raw-parser patch.

1XXX -- reviewed by Tatsuo

Tatsuo reviewed through v50-0007 earlier, and confirmed v50-0008..0013 on
07-19. So this band is v50-0001..0013.

1001 Remove blank-line changes unrelated to row pattern
recognition (= v50-0001)
1002 Remove unnecessary includes from the row pattern
recognition patch (= v50-0002)
1003 Restore line wrapping of pre-existing window clause
documentation (new)
1004 Recognize row pattern navigation operations by name in
DEFINE (= v50-0003)
1005 Use a dedicated ExprContext for RPR DEFINE clause
evaluation (= v50-0004)
1006 Drive RPR row pattern matching once per row (= v50-0005)
1007 Tidy up row pattern recognition plumbing (= v50-0006)
1008 Further tidy up row pattern recognition plumbing
(= v50-0007)

Newly reviewed on 07-19, moved up from 2XXX:

1009 Refactor transformDefineClause in row pattern recognition
[behavior change] (= v50-0008)
1010 Replace a bare block with an else in the RPR DEFINE clause
walker (= v50-0009)
1011 Rename loop index variables in row pattern deparse
helpers (= v50-0010)
1012 Rename absorption "judgment point" to "comparison point" in
comments (= v50-0011)
1013 Improve comments, documentation, and naming for row pattern
recognition (= v50-0012)
1014 Document eval_nav_offset_helper's NULL/negative offset
handling (= v50-0013)

2XXX -- awaiting review from Tatsuo

2015 Tidy up the row pattern unbounded-quantifier sentinel
(= v50-0014)
Revised per your 07-19 comment. The macro is no longer a local
copy in gram.y: RPR_QUANTITY_INF is now defined once in
nodes/parsenodes.h, next to RPRPatternNode whose max field
stores it, and gram.y and optimizer/rpr.h use that one
definition. On the placement -- you suggested primnodes.h; I
put it in parsenodes.h because that is where RPRPatternNode
lives, and parsenodes.h includes primnodes.h, so every stage
that saw the macro before still does. Happy to move it to
primnodes.h if you would rather keep it there.

2016 Simplify row pattern compilation by passing the
WindowClause (= v50-0015)
2017 Reword the row pattern variable-limit error (= v50-0016)
2018 Reformat row pattern regression tests for
readability (= v50-0017)
2019 Add row pattern recognition coverage tests and tidy
unreachable code (= v50-0018)
2020 Free RPR NFA states with pfree() under
USE_VALGRIND (= v50-0019)
2021 Clarify row pattern recognition comments on "step" and
no_equal (= v50-0020)
2022 Extract the reduced-frame guard into ensure_reduced_frame()
2023 Clean up row pattern recognition internals
2024 Improve row pattern recognition comments and documentation
2025 Expand row pattern recognition regression tests
2026 Fix context absorption discarding matches on non-absorbable
branches
[behavior change -- wrong results]

You mentioned you would continue through 2016..2021; those, and 2022..2026,
are unchanged from the 07-13 posting.

3XXX -- Henson, in progress (under peer review with Jian)

Still settling, so not ready for review yet. Once each is, I will move it
to 2XXX. Most of this band is the defect work I said I would prioritize.

These are the defects found since 07-13, almost all in how the NFA matcher
and the PATTERN optimizer choose among equally-long matches -- the
leftmost-choice-first preferment of ISO/IEC TR 19075-5 7.2 -- plus two
termination paths that could hang or recurse. 3001 closes the planner
hang; 3002, 3003 and 3004 fix wrong preferred matches, and 3004 also closes
an unbounded recursion. I do not yet treat the preferment side as fully
closed: 3003 and 3004 are the same class of bug, and there may be more edge
cases, which is why this band is still under my own review before it goes
to you.

3001 Bound the END search in row pattern absorption analysis
[defect -- planner hang]
isUnboundedStart could walk off the element array and loop with
no CHECK_FOR_INTERRUPTS on a non-normalized tree, so even a bare
EXPLAIN hangs until the backend is killed. The optimizer never
feeds such a tree in practice; this stops the walk at FIN or a
missing link and removes the dependence on the optimizer having
run first. Output is unchanged for every reachable pattern.

3002 Fix row pattern recognition alternation branch-walk overload
[behavior change -- wrong results]
(Was 3001 last time.) The branch links and the group skip shared
one jump field, so PATTERN (A | (B C)+ (D E)+) behaved as
A | (B C)+ | (D E)+. Takes the dedicated SEP marker so branch
enumeration is consistent across the runtime, absorption, and
deparse. The Assert comment you flagged is fixed here too.

3003 Preserve row pattern preferment in three PATTERN optimizations
[behavior change -- wrong results]
Three PATTERN rewrites (tryMultiplyQuantifiers,
mergeConsecutiveGroups, the suffix phase of mergeGroupPrefixSuffix)
kept the set of matchable lengths but changed which match is
preferred, so a plain query returned a different match with the
optimization than without it. Each is gated so it fires only when
it cannot reorder a repetition's exit decision across a choice
point, which the leftmost-choice-first rule (ISO/IEC TR 19075-5
7.2) makes observable.

3004 Fix row pattern preferment and cycle handling in the NFA matcher
[behavior change -- wrong results / unbounded recursion]
The matcher violated the 7.2 preferment rules in several ways, and
its zero-consumption cycle guard could either kill legitimate
matches or recurse without bound. Mark only nullable ENDs, decide
an empty iteration's order by the body's compile-time preference,
and compare a per-replacement generation counter instead of freed
state pointers.

3005 Follow local conventions in row pattern recognition additions
No functional change. Include ordering, a switch case out of
NodeTag order, a typedefs.list entry, a missing no_query_jumble on
a plan-only node, and two EXPLAIN tests that ran outside the
rpr_explain_filter.

4XXX -- Jian, in progress (under peer review with Henson)

Unchanged from 07-13. Authorship is unchanged -- except 4001, which is
mine and sits here as this band's regression guard.

These continue to circle the navigation operations, which is where we keep
turning up defects. Two are already pinned down: the loss of forward reach
for FIRST(expr, n > 0) I reported on 07-07 -- 4001 guards it and 4004
restores it -- and evaluating a navigation argument when there is no target
row (4005). The rest of the band is the refactor toward a single
offset-evaluation site (4002, 4003, 4006), partly there to make the
remaining cases easier to find; Jian and I are still turning them up, so
this is the least settled band.

4001 Add EXPLAIN test for simple FIRST(v, N) navigation mark
lookahead (authored by me)
4002 Evaluate navigation offset once at one place
4003 Drop the shared nav_traversal_walker for RPR DEFINE
4004 Fix the regression failure (= v51-0001)
4005 Stop evaluating navigation arguments in case rows not exists
(= v51-0002)
[behavior change -- wrong results]
4006 Introduce execution struct RprNavState (= v51-0003)

8XXX / 9XXX -- restorations and separately committable patches

Unchanged from 07-13. These restore pre-existing code RPR had no reason to
touch (8XXX), then put back only the parts RPR needs, as separately
committable patches (9XXX). They come in pairs and apply in the order
8001, 8002, 8003, 9001, 9002, 9003.

8001 Revert window_gettupleslot() mark-position elog to its
original message
9001 Include row positions in WindowObject mark-position error
8002 Restore funcname guard in WinCheckAndInitializeNullTreatment
9002 Remove unreachable function-name guard in null-treatment
check
8003 Remove EXCLUDE TIES window tests unrelated to row pattern
recognition
9003 Add EXCLUDE TIES window frame test coverage

As before, please let me know if any of the slicing or grouping looks off.
I am still putting defect-finding ahead of new patches, so 3XXX is where
most of the recent work is.

Best regards,
Henson