Re: Row pattern recognition

Hi Tatsuo,

This round focused on reviewing nodeWindowAgg.c -- the NFA executor
-- which was the last piece remaining on my review list.  I've also
added a comprehensive NFA runtime test suite.

The attached patch continues the incremental series on top of v42.
Here are the changes:


FIXME issues documented:

These require non-trivial structural changes, so I've documented
them as FIXME comments for now rather than attempting a fix.

- altPriority tracks only the last ALT choice, so repeated or nested
  ALTs like (A|B)+ cannot correctly implement SQL standard lexical
  ordering.  A full-path classifier structure is needed.

- Cycle prevention condition (count == 0 && min == 0) is insufficient
  for patterns like (A*)* where cycles occur at count > 0.  Currently
  relies on implicit duplicate detection in nfa_add_state_unique.


Bugs fixed:

- Fix nfa_advance_begin() routing order: enter group first (lexically
  first), then skip path (lexically second).

- Add ALT scope boundary check in nfa_advance_alt() and
  computeAbsorbabilityRecursive() to stop branch traversal when
  element depth exits ALT scope.

- Disallow RANGE and GROUPS frame types with row pattern
  recognition, as the SQL standard only requires ROWS.
  Also remove the now-dead frame-type determination code.


NFA executor refactoring (nodeWindowAgg.c):

- Simplify nfa_process_row() phase 1: remove nfa_advance() call
  after forced mismatch at frame boundary, since all states are
  already at VAR positions and mismatch removes them.  Replace
  the redundant phase 3 frame boundary check with Assert.

- Simplify update_reduced_frame() result registration: mismatch
  path now returns early, and the post-processing SKIP mode cleanup
  block (nfa_remove_contexts_up_to vs nfa_context_free) is removed
  since eager pruning handles SKIP PAST LAST ROW and both paths
  now simply call nfa_context_free().

- Replace nfa_remove_contexts_up_to() with eager pruning inside
  nfa_add_matched_state().  When matchEndRow is extended during
  greedy matching, pending contexts within the match range are
  pruned incrementally instead of after match completion.  For
  SKIP PAST LAST ROW patterns like START UP+, this reduces the
  number of live contexts at each row from O(n) to O(1), avoiding
  O(n^2) per-row processing of contexts that would be skipped
  anyway.

- Optimize nfa_states_equal() to compare counts only up to the
  current element's depth instead of the full maxDepth.

- Rename nfa_state_clone -> nfa_state_create,
  nfa_find_context_for_pos -> nfa_get_head_context for clarity.

- Add nfa_record_context_success/skipped/absorbed statistics helpers.

- Remove unused RPRPattern parameter from
  nfa_update_absorption_flags().


Absorbability refactoring (rpr.c):

- Remove parentDepth parameter from isUnboundedStart() and
  computeAbsorbabilityRecursive().  Scope boundaries are now
  determined by element depth comparison instead of an explicit
  parent depth parameter.

- Simplify isUnboundedStart(): check simple VAR case first, then
  GROUP case with a depth-bounded loop instead of a FIN-terminated
  traversal with multiple break conditions.


Test changes:

- Add rpr_nfa.sql: comprehensive NFA runtime test suite covering
  quantifier boundaries (min/max/exact), alternation priority, nested
  patterns, frame boundary variations, INITIAL mode (syntax error
  expected), pathological patterns, context absorption, and FIXME
  reproduction cases.

- Add nth_value out-of-frame tests, ReScan/LATERAL test, and
  nth_value IGNORE NULLS test to rpr.sql.

- Change selected EXPLAIN test queries in rpr_explain.sql from
  EXPLAIN (COSTS OFF) to EXPLAIN (ANALYZE, ...) to verify actual
  NFA execution statistics.

- Fix stale comments across rpr.sql, rpr_base.sql, and rpr_nfa.sql:
  remove resolved BUG annotations, update error messages to match
  actual output, correct optimization result descriptions, and
  standardize Expected comment placement to after SQL statements.


Other changes:

- Run pgindent on RPR source files.  Add /*----------*/ comment
  guards to protect structured comments from reformatting.


Coverage:

I ran gcov on the modified lines (diff-only coverage).  The attached
coverage.zip contains an HTML report.  Summary:

- 18 files, 124 functions, 2238 modified lines analyzed
- Overall: 92.1% line coverage (2061/2238)
- Core files (nodeWindowAgg.c, rpr.c, explain.c, parse_rpr.c):
  98.0-98.5% each
- Node serialization (outfuncs.c, readfuncs.c, equalfuncs.c):
  0% -- these implement RPRPattern serialization for plan caching,
  but regression tests don't exercise prepared statements with RPR
- ruleutils.c: 96.3% -- untested lines are the reluctant quantifier
  display path ({1}?), which is currently rejected at parse time

The node serialization functions (141 lines, 0% coverage) are the
largest untested area.  I'm not sure how to trigger these paths
in the regression test framework.  Any suggestions?

I'll send a separate email within a few days listing the FIXME
issues and other unresolved items from the mailing list discussion
for your review.


Best regards,
Henson