Re: Row pattern recognition

Hi Henson,

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

I think your analysis is correct. I see that AST is correctly
generated. So the issue is in the executor phase.

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

Either way works for me.

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

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