Re: Row pattern recognition

Hi hackers,

This is an increment on top of v49: it carries what has accumulated
since the last posting, plus one adjustment needed by a recent rebase
onto master. The attachments are named nocfbot-XXXX-*.txt so that
cfbot does not pick them up.

This time the patch numbers are grouped into bands by status. Patches
have gone back and forth on this thread often enough that the same
number has ended up meaning different patches, and this is an attempt
to remove that confusion:

0XXX compile failure caused by the rebase onto master
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)

3XXX and 4XXX are where Jian and I review each other's work. Once a
patch settles there, it moves to 2XXX for Tatsuo's review.

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. So 2009
becomes 1009 once it is reviewed. That is why 2XXX starts at 2009
here: 1008 is the last reviewed one. The other bands are numbered on
their own, from 001.

The numbers follow the apply order, so applying them in order works.

The same series is on GitHub. Until now I pointed at the RPR branch,
which keeps getting rewritten; from this posting on, each mail gets
its own dated branch that I will not rewrite, so a review can refer to
a fixed tree:

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

What was posted as v50-0001..0020 has moved to the numbers below; the
contents are unchanged. v50-0021, which adjusted the rpr_base
expected output, is no longer a separate patch: it is folded into
1004, so that patch expects master's current error message from the
start. Otherwise the commits in the middle of the series fail
rpr_base when checked out on their own.

0XXX -- rebase adjustment

0001 Adjust row pattern recognition for fix_upper_expr() signature
change
Commit 3b0991059f3 removed the nrm_match parameter from
fix_upper_expr(), but the DEFINE clause fixup in
set_upper_references() still passed NRM_EQUAL. Drop the stale
argument. The fix_join_expr() calls in the same file are
unaffected; that function still takes nrm_match.

1XXX -- reviewed by Tatsuo

Tatsuo reviewed through v50-0005 explicitly, the cost-model question
on v50-0006 was settled on 07-06, and v50-0007 was reviewed on 07-11.
So this band is v50-0001..0007.

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)
This is the one exception in this band: it is new and has not
been reviewed yet. It restores the line wrapping of
pre-existing documentation that RPR had no reason to touch.
Like 1001 and 1002, it is a plain restoration, so it is grouped
with them. Please include it in your review.

1004 Recognize row pattern navigation operations by name in
DEFINE (= v50-0003)
Also carries the one line from v50-0021, as noted above.
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)
The Assert comment you flagged in nfa_advance_alt() is fixed in
3001, which replaces that code entirely.

2XXX -- awaiting review from Tatsuo

Posted earlier but not yet reviewed (2009..2021), and what has
accumulated since (2022..2026).

2009 Refactor transformDefineClause in row pattern recognition
[behavior change] (= v50-0008)
2010 Replace a bare block with an else in the RPR DEFINE clause
walker (= v50-0009)
2011 Rename loop index variables in row pattern deparse
helpers (= v50-0010)
2012 Rename absorption "judgment point" to "comparison point" in
comments (= v50-0011)
2013 Improve comments, documentation, and naming for row pattern
recognition (= v50-0012)
2014 Document eval_nav_offset_helper's NULL/negative offset
handling (= v50-0013)
2015 Tidy up the row pattern unbounded-quantifier
sentinel (= v50-0014)
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)

From here on, new since the last posting.

2022 Extract the reduced-frame guard into ensure_reduced_frame()
Replaces the (void) row_is_in_reduced_frame() smell Tatsuo
pointed out with an idempotent helper. Output is unchanged.

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]
The fix for the defect I reported on this thread on 07-07. A
dominating context did not cover a recorded match in the
absorption comparison, so the match was discarded outright.
matchedState is now part of that comparison.

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

I am still reviewing this myself, so it is not settled yet. Once it
is, I will move it to 2XXX -- Tatsuo, please review it then.

3001 Fix row pattern recognition alternation branch-walk overload
[behavior change -- wrong results]
The fix for the defect I reported on 07-08, for which I said I
would prepare a patch. The branch links and the group skip
shared the single jump field, so PATTERN (A | (B C)+ (D E)+)
behaved as A | (B C)+ | (D E)+. Of the two directions you
agreed to, this takes the dedicated SEP marker: a per-branch
end marker makes branch enumeration consistent across the three
places that walk it -- the runtime, absorption, and deparse.
The Assert comment is fixed here too. One nuance: the links
themselves can be -1 -- that is what ends the walk -- so the
comment now speaks of the walk rather than the links.

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

This is still going back and forth with Jian, so it is not settled
yet. Once it is, I will move it to 2XXX -- Tatsuo, please review it
then. Authorship is unchanged -- except for 4001, which is mine and
sits here as this band's regression guard.

4001 Add EXPLAIN test for simple FIRST(v, N) navigation mark
lookahead (authored by me)
Asserts that the forward reach of a simple FIRST(v, N) with a
constant offset shows up in EXPLAIN. The existing coverage had
only FIRST(v) with no offset, and the compound navigations.
This is the test I said would come with the next patch mail; it
sits right in front of the nav-offset patches because that is
the value they change.

4002 Evaluate navigation offset once at one place
This is where the loss of forward reach for FIRST(expr, n > 0)
that I reported on 07-07 shows up: on top of this patch, 4001
sees "Nav Mark Lookahead: 0" where it expects 5.

4003 Drop the shared nav_traversal_walker for RPR DEFINE
Built on top of 4002.

From here on, the v51-0001..0003 Jian posted on 07-11.

4004 Fix the regression failure (= v51-0001)
Restores the forward reach 4002 lost; 4001 passes again.

4005 Stop evaluating navigation arguments in case rows not exists
(= v51-0002)
[behavior change -- wrong results]
Does not evaluate a navigation argument when there is no target
row.

4006 Introduce execution struct RprNavState (= v51-0003)
Keeps the resolved offsets in execution state rather than in the
plan tree.

Jian, I went into the defect-related material in a separate reply. We
keep finding defects in the navigation operations, and that is exactly
the code these refactors touch. Working on top of these patches would
put us on the same base and make it easier for us to check each other.

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

These restore pre-existing code that RPR had no reason to touch
(8XXX), and then put back only the parts RPR actually needs, as
separate patches (9XXX). The intent is that this series' diff
carries only what RPR genuinely changes, and that the 9XXX patches
can be committed independently of RPR. They come in pairs.

8001 Revert window_gettupleslot() mark-position elog to its
original message
9001 Include row positions in WindowObject mark-position error
After 8001 restored the original message, this adds back only
the row positions, which are what the diagnosis needs.

8002 Restore funcname guard in WinCheckAndInitializeNullTreatment
9002 Remove unreachable function-name guard in null-treatment
check
Of the guards 8002 restored, this drops the one that RPR makes
unreachable.

8003 Remove EXCLUDE TIES window tests unrelated to row pattern
recognition
9003 Add EXCLUDE TIES window frame test coverage
Of the tests 8003 removed, this puts back only the frame
coverage that RPR actually needs.

The attachments apply in the order 8001, 8002, 8003, 9001, 9002,
9003.

Please let me know if any of the slicing or grouping looks off, and if
you have any thoughts on the numbering scheme itself.

One last thing. For the time being I will put finding and analyzing
defects ahead of writing patches. We keep turning up defects in the
navigation code, and building cases, running them and tracking down
the causes is worth more right now.

Best regards,
Henson