Subject: Re: Row pattern recognition

From: Tatsuo Ishii <[email-masked]>
Date: Sat, 28 Sep 2024 19:43:59 +0900 (JST)

> With some bigger partitions, I hit an `ERROR:  wrong pos: 1024`. A
> test that reproduces it is attached.

Thanks for the report. Attached is a patch on top of v22 patches to
fix the bug. We keep info in an array
(WindowAggState.reduced_frame_map) to track the rpr pattern match
result status for each row in a frame. If pattern match succeeds, the
first row in the reduced frame has status RF_FRAME_HEAD and rest of
rows have RF_SKIPPED state. A row with pattern match failure state has
RF_UNMATCHED state. Any row which is never tested has state
RF_NOT_DETERMINED. At begining the map is initialized with 1024
entries with all RF_NOT_DETERMINED state. Eventually they are replaced
with other than RF_NOT_DETERMINED state. In the error case rpr engine
tries to find 1024 th row's state in the map and failed because the
row's state has not been tested yet. I think we should treat it as
RF_NOT_DETERMINED rather than an error. Attached patch does it.

> While playing with the feature, I've been trying to identify runs of
> matched rows by eye. But it's pretty difficult -- the best I can do is
> manually count rows using a `COUNT(*) OVER ...`. So I'd like to
> suggest that MEASURES be part of the eventual v1 feature, if there's
> no other way to determine whether a row was skipped by a previous
> match. (That was less obvious to me before the fix in v17.)

I think implementing MEASURES is challenging. Especially we need to
find how our parser accepts "colname OVER
window_definition". Currently PostgreSQL's parser only accepts "func()
OVER window_definition" Even it is technically possible, I think the
v1 patch size will become much larger than now due to this.

How about inventing new window function that returns row state instead?

- match found (yes/no)
- skipped due to AFTER MATCH SKIP PAST LAST ROW (no match)

For the rest of the mail I need more time to understand. I will reply
back after studying it. For now, I just want to thank you for the
valuable information!

> --
> 
> I've been working on an implementation [1] of SQL/RPR's "parenthesized
> language" and preferment order. (These are defined in SQL/Foundation
> 2023, section 9.41.) The tool gives you a way to figure out, for a
> given pattern, what matches are supposed to be attempted and in what
> order:
> 
>     $ ./src/test/modules/rpr/rpr_prefer "a b? a"
>     ( ( a ( b ) ) a )
>     ( ( a ( ) ) a )
> 
> Many simple patterns result in an infinite set of possible matches. So
> if you use an unbounded quantifiers, you have to also use --max-rows
> to limit the size of the hypothetical window frame:
> 
>     $ ./src/test/modules/rpr/rpr_prefer --max-rows 2 "^ PERMUTE(a*, b+)? $"
>     ( ( ^ ( ( ( ( ( ( a ) ( b ) ) ) - ) ) ) ) $ )
>     ( ( ^ ( ( ( ( ( ( ) ( b b ) ) ) - ) ) ) ) $ )
>     ( ( ^ ( ( ( ( ( ( ) ( b ) ) ) - ) ) ) ) $ )
>     ( ( ^ ( ( ( - ( ( ( b b ) ( ) ) ) ) ) ) ) $ )
>     ( ( ^ ( ( ( - ( ( ( b ) ( a ) ) ) ) ) ) ) $ )
>     ( ( ^ ( ( ( - ( ( ( b ) ( ) ) ) ) ) ) ) $ )
>     ( ( ^ ( ) ) $ )
> 
> I've found this useful to check my personal understanding of the spec
> and the match behavior, but it could also potentially be used to
> generate test cases, or to help users debug their own patterns. For
> example, a pattern that has a bunch of duplicate sequences in its PL
> is probably not very well optimized:
> 
>     $ ./src/test/modules/rpr/rpr_prefer --max-rows 4 "a+ a+"
>     ( ( a a a ) ( a ) )
>     ( ( a a ) ( a a ) )
>     ( ( a a ) ( a ) )
>     ( ( a ) ( a a a ) )
>     ( ( a ) ( a a ) )
>     ( ( a ) ( a ) )
> 
> And patterns with catastrophic backtracking behavior tend to show a
> "sawtooth" pattern in the output, with a huge number of potential
> matches being generated relative to the number of rows in the frame.
> 
> My implementation is really messy -- it leaks memory like a sieve, and
> I cannibalized the parser from ECPG, which just ended up as an
> exercise in teaching myself flex/bison. But if there's interest in
> having this kind of tool in the tree, I can work on making it
> reviewable. Either way, I should be able to use it to double-check
> more complicated test cases.
> 
> A while back [2], you were wondering whether our Bison implementation
> would be able to parse the PATTERN grammar directly. I think this tool
> proves that the answer is "yes", but PERMUTE in particular causes a
> shift/reduce conflict. To fix it, I applied the same precedence
> workaround that we use for CUBE and ROLLUP.
> 
> Thanks again!
> --Jacob
> 
> [1] https://github.com/jchampio/postgres/tree/dev/rpr
> [2] https://www.postgresql.org/message-id/20230721.151648.412762379013769790.t-ishii%40sranhm.sra.co.jp
diff --git a/src/backend/executor/nodeWindowAgg.c b/src/backend/executor/nodeWindowAgg.c
index e46a3dd1b7..4a5a6fbf07 100644
--- a/src/backend/executor/nodeWindowAgg.c
+++ b/src/backend/executor/nodeWindowAgg.c
@@ -4148,9 +4148,15 @@ int
 get_reduced_frame_map(WindowAggState *winstate, int64 pos)
 {
 	Assert(winstate->reduced_frame_map != NULL);
+	Assert(pos >= 0);
 
-	if (pos < 0 || pos >= winstate->alloc_sz)
-		elog(ERROR, "wrong pos: " INT64_FORMAT, pos);
+	/*
+	 * If pos is not in the reduced frame map, it means that any info
+	 * regarding the pos has not been registered yet. So we return
+	 * RF_NOT_DETERMINED.
+	 */
+	if (pos >= winstate->alloc_sz)
+		return RF_NOT_DETERMINED;
 
 	return winstate->reduced_frame_map[pos];
 }

---

From: Tatsuo Ishii <[email-masked]>
Date: Mon, 30 Sep 2024 09:07:51 +0900 (JST)

> - skipped due to AFTER MATCH SKIP PAST LAST ROW (no match)

Please disregard my proposal. Even if we make such a function, it
would always return NULL for unmatched rows or skipped rows, and I
think the function does not solve your problem.

However, I wonder if supporting MEASURES solves the problem either
because any columns defined by MEASURES will return NULL except the
first row in a reduced frame. Can you please show an example how to
identify runs of matched rows using MEASURES?

> back after studying it. For now, I just want to thank you for the

I wonder how Oracle solves the problem (an infinite set of possible
matches) without using "--max-rows" or something like that because in
my understanding Oracle supports the regular expressions and PERMUTE.

>> more complicated test cases.

I definitely am interested in the tool!

>> workaround that we use for CUBE and ROLLUP.

That's a good news!

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

---

From: Jacob Champion <[email-masked]>
Date: Tue, 1 Oct 2024 05:48:02 -0700

> > v1 patch size will become much larger than now due to this.

[resending, to the whole list this time]

Yeah. In any case, I'm not the right person to bolt MEASURES onto the
existing grammar... my misadventures in the PATTERN parser have
highlighted how little I know about Bison. :D

> identify runs of matched rows using MEASURES?

I think you're probably right; my suggestion can't distinguish between
skipped (but previously matched) rows and entirely-unmatched rows. The
test case I'd been working with returned an empty match as a fallback,
so it wouldn't have had that problem in practice. I was hoping that
one of the existing whole-partition window functions would allow me to
cobble something together based on the COUNT(*) measure, but after
searching for a while I haven't been able to come up with a solution.

Maybe it's just too niche for the window-function version of this --
after all, it only makes sense when using both INITIAL and AFTER MATCH
SKIP PAST LAST ROW. A more general solution could identify the
row_number of the first and last rows of the window frame, perhaps?
But a frame isn't guaranteed to be contiguous, so maybe that doesn't
make sense either. Ugh.

> my understanding Oracle supports the regular expressions and PERMUTE.

I chose a confusing way to describe it, sorry. The parenthesized
language for a pattern can be an infinite set, because A+ could match
"( A )" or "( A A )" or "( A A A )" and so on forever. But that
doesn't apply to our regex engine in practice; our tables have a
finite number of rows, and I *think* the PL for a finite number of
rows is also finite, due to the complicated rules on where empty
matches are allowed to appear in the language. (In any case, my tool
doesn't guard against infinite recursion...)

> I definitely am interested in the tool!

Okay, good to know! I will need to clean it up considerably, and
figure out whether I've duplicated more code than I should have.

> >> workaround that we use for CUBE and ROLLUP.

+1

Thanks,
--Jacob