Re: Row pattern recognition

Hi Tatsuo, Jian,

I found a wrong result that comes from the context-absorption
optimization, and wanted to run it by you both.

WITH d(id, a, c) AS (
VALUES (1, true, false),
(2, true, true),
(3, true, false),
(4, false, false))
SELECT id, count(*) OVER w AS cnt
FROM d
WINDOW w AS (
ORDER BY id
ROWS BETWEEN CURRENT ROW AND UNBOUNDED FOLLOWING
AFTER MATCH SKIP PAST LAST ROW
PATTERN (A{5,} | C)
DEFINE A AS a, C AS c);

id | cnt
----+-----
1 | 0
2 | 0
3 | 0
4 | 0

id = 2 returns cnt = 0, but C matches [2,2] there, so it should be
1. EXPLAIN ANALYZE on the query reports "0 matched" and "2 absorbed".

The cause: whether a context can be absorbed is decided from its
in-progress states. Once the id=2 context records the C match [2,2],
that match moves to matchedState and its C state leaves the
in-progress set, so only the A run remains and the context is judged
fully absorbable. The id=1 context's longer A run then dominates it
and frees the whole context -- including the recorded [2,2] match.
The dominance argument only covers a context's future matches; it
does not account for a match already recorded on the non-absorbable
branch.

The fix: bring matchedState into the absorption comparison as well --
a context should be absorbed only when the absorbing context also
covers the recorded match, not just the in-progress states, so a
match the absorber cannot reproduce is never dropped.

Best regards,
Henson