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