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