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
