Re: Row pattern recognition

Hi Tatsuo, Jian,

I hit a wrong result in row pattern recognition: an alternation
whose last branch is a concatenation of quantified groups matches
one group short.

  WITH d(id, dd, ee) AS (VALUES
    (1, true,  false), (2, false, true),
    (3, true,  false), (4, false, true))
  SELECT id, count(*) OVER w AS cnt
  FROM d
  WINDOW w AS (
    ORDER BY id
    ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
    PATTERN (A | (B C)+ (D E)+)
    DEFINE A AS false, B AS false, C AS false,
           D AS dd, E AS ee);

   id | cnt
  ----+-----
    1 |   4      <- wrong; should be 0 (no match)
    2 |   0
    3 |   0
    4 |   0

The rows are D E D E, with no B and no C.  By precedence
PATTERN (A | (B C)+ (D E)+) means A | ((B C)+ (D E)+), so a bare
(D E)+ satisfies no branch and no row should match.  Instead row 1
matches [1,4]: the pattern behaves as if it were written
A | (B C)+ | (D E)+.

Cause: the ALT branch walk follows the branch head's jump to reach
the next branch.  That jump was the branch link, but the group
BEGIN's skip-past-END path was later layered onto the same field,
so jump is now overloaded.  When the last branch is (B C)+ (D E)+,
the BEGIN of (B C)+ jumps past its END to the BEGIN of (D E)+, and
the walk mistakes that following group for another alternative.

The same overloaded jump is walked in three places:
nfa_advance_alt (match advance), computeAbsorbabilityRecursive
(absorption marking), and the deparse.  nfa_advance_alt gives the
wrong result above.  computeAbsorbabilityRecursive over-marks the
trailing group as absorbable, though that turns out inert at run
time.  The deparse already sidesteps the overload in
rpr_next_branch() with the relative test elem[j-1].next != j, so
EXPLAIN prints the pattern correctly.

Fix direction: at its core, separate the BEGIN jump (group skip)
from the ALT branch-link jump -- they share one field today, which
is the overload.  I am weighing two ways to do that.

One is to move the group BEGIN's skip-past-END onto next.  Group
entry is already the contiguous BEGIN+1, so next is free, and jump
is left to be the branch link only.  No new elements.

The other is explicit branch-separator markers (a new SEP varid)
that carry the branch link, chained ALT.jump -> SEP -> ... ->
jump = -1 on the last one; branch content still reaches the
post-ALT element through next.

Either way the ALT walk sees jump as a branch link or -1, so
nfa_advance_alt, computeAbsorbabilityRecursive and the deparse can
enumerate branches the same clean way, dropping the relative test
and the depth-based break.  Deparse output stays the same.

I can put together a patch along these lines if the direction
looks right.

Best regards,
Henson