Re: Row pattern recognition

Hi Henson,

Thanks for the patches! I applied them on top of v42 and rebased
against current master.  Attached are the v43 patches.

> 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

Thanks for the report.

> 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 think we can leave it as it is, until reluctant quantifier is
implemented.

> 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.

Looking forward to reading your email.

Best regards,
--
Tatsuo Ishii
SRA OSS K.K.
English: http://www.sraoss.co.jp/index_en/
Japanese:http://www.sraoss.co.jp