Content-Type: multipart/mixed; boundary="------------YlsZCQR21Gfdi74kbPCppQcS"
Message-ID: <fcf6dcfa-5a61-00ea-4311-d3d003b790ed@timescale.com>
Date: Thu, 7 Sep 2023 17:00:07 -0700
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.15.0
Subject: Re: Row pattern recognition
Content-Language: en-US
References: <20230728.200230.1800661389729335298.t-ishii@sranhm.sra.co.jp>
 <9e135bd6-252a-e39a-bf7d-5a9726427769@postgresfriends.org>
 <20230729.120508.992131963092683632.t-ishii@sranhm.sra.co.jp>
 <20230809.174112.1806434641666895071.t-ishii@sranhm.sra.co.jp>
From: Jacob Champion <jchampion@timescale.com>
To: Tatsuo Ishii <ishii@sraoss.co.jp>, Erik Rijkers <er@xs4all.nl>
Cc: Vik Fearing <vik@postgresfriends.org>,
 PostgreSQL-development <pgsql-hackers@postgresql.org>
In-Reply-To: <20230809.174112.1806434641666895071.t-ishii@sranhm.sra.co.jp>
Archived-At: 
 <https://www.postgresql.org/message-id/fcf6dcfa-5a61-00ea-4311-d3d003b790ed%40timescale.com>
Precedence: bulk

This is a multi-part message in MIME format.
--------------YlsZCQR21Gfdi74kbPCppQcS
Content-Type: text/plain; charset=UTF-8
Content-Transfer-Encoding: 7bit

Hello!

> (1) I completely changed the pattern matching engine so that it
> performs backtracking. Now the engine evaluates all pattern elements
> defined in PATTER against each row, saving matched pattern variables
> in a string per row. For example if the pattern element A and B
> evaluated to true, a string "AB" is created for current row.

If I understand correctly, this strategy assumes that one row's
membership in a pattern variable is independent of the other rows'
membership. But I don't think that's necessarily true:

    DEFINE
      A AS PREV(CLASSIFIER()) IS DISTINCT FROM 'A',
      ...

> See row_is_in_reduced_frame, search_str_set and search_str_set_recurse
> in nodeWindowAggs.c for more details. For now I use a naive depth
> first search and probably there is a lot of rooms for optimization
> (for example rewriting it without using
> recursion).

The depth-first match is doing a lot of subtle work here. For example, with

    PATTERN ( A+ B+ )
    DEFINE A AS TRUE,
           B AS TRUE

(i.e. all rows match both variables), and three rows in the partition,
our candidates will be tried in the order

    aaa
    aab
    aba
    abb
    ...
    bbb

The only possible matches against our regex `^a+b+` are "aab" and "abb",
and that order matches the preferment order, so it's fine. But it's easy
to come up with a pattern where that's the wrong order, like

    PATTERN ( A+ (B|A)+ )

Now "aaa" will be considered before "aab", which isn't correct.

Similarly, the assumption that we want to match the longest string only
works because we don't allow alternation yet.

> Suggestions/patches are welcome.

Cool, I will give this piece some more thought. Do you mind if I try to
add some more complicated pattern quantifiers to stress the
architecture, or would you prefer to tackle that later? Just alternation
by itself will open up a world of corner cases.

> With the new engine, cases above do not fail anymore. See new
> regression test cases. Thanks for providing valuable test cases!

You're very welcome!

On 8/9/23 01:41, Tatsuo Ishii wrote:
> - I found a bug with pattern matching code. It creates a string for
>   subsequent regular expression matching. It uses the initial letter
>   of each define variable name. For example, if the varname is "foo",
>   then "f" is used. Obviously this makes trouble if we have two or
>   more variables starting with same "f" (e.g. "food"). To fix this, I
>   assign [a-z] to each variable instead of its initial letter. However
>   this way limits us not to have more than 26 variables. I hope 26 is
>   enough for most use cases.

There are still plenty of alphanumerics left that could be assigned...

But I'm wondering if we might want to just implement the NFA directly?
The current implementation's Cartesian explosion can probably be pruned
aggressively, but replaying the entire regex match once for every
backtracked step will still duplicate a lot of work.

--

I've attached another test case; it looks like last_value() is depending
on some sort of side effect from either first_value() or nth_value(). I
know the window frame itself is still under construction, so apologies
if this is an expected failure.

Thanks!
--Jacob
--------------YlsZCQR21Gfdi74kbPCppQcS
Content-Type: text/plain; charset=UTF-8; name="test-last_value.diff.txt"
Content-Disposition: attachment; filename="test-last_value.diff.txt"
Content-Transfer-Encoding: base64

ZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvcnByLm91dCBiL3NyYy90
ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvcnByLm91dAppbmRleCAzNDBjY2YyNDJjLi5iZDM1ZTgz
ODllIDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3Jwci5vdXQKKysr
IGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9ycHIub3V0CkBAIC04OSw2ICs4OSw0NCBA
QCBTRUxFQ1QgY29tcGFueSwgdGRhdGUsIHByaWNlLCBmaXJzdF92YWx1ZShwcmljZSkgT1ZF
UiB3LCBsYXN0X3ZhbHVlKHByaWNlKSBPVkVSCiAgY29tcGFueTIgfCAwNy0xMC0yMDIzIHwg
IDEzMDAgfCAgICAgICAgICAgICB8ICAgICAgICAgICAgfCAKICgyMCByb3dzKQogCistLSBs
YXN0X3ZhbHVlKCkgc2hvdWxkIHJlbWFpbiBjb25zaXN0ZW50CitTRUxFQ1QgY29tcGFueSwg
dGRhdGUsIHByaWNlLCBsYXN0X3ZhbHVlKHByaWNlKSBPVkVSIHcKKyBGUk9NIHN0b2NrCisg
V0lORE9XIHcgQVMgKAorIFBBUlRJVElPTiBCWSBjb21wYW55CisgT1JERVIgQlkgdGRhdGUK
KyBST1dTIEJFVFdFRU4gQ1VSUkVOVCBST1cgQU5EIFVOQk9VTkRFRCBGT0xMT1dJTkcKKyBJ
TklUSUFMCisgUEFUVEVSTiAoU1RBUlQgVVArIERPV04rKQorIERFRklORQorICBTVEFSVCBB
UyBUUlVFLAorICBVUCBBUyBwcmljZSA+IFBSRVYocHJpY2UpLAorICBET1dOIEFTIHByaWNl
IDwgUFJFVihwcmljZSkKKyk7CisgY29tcGFueSAgfCAgIHRkYXRlICAgIHwgcHJpY2UgfCBs
YXN0X3ZhbHVlIAorLS0tLS0tLS0tLSstLS0tLS0tLS0tLS0rLS0tLS0tLSstLS0tLS0tLS0t
LS0KKyBjb21wYW55MSB8IDA3LTAxLTIwMjMgfCAgIDEwMCB8ICAgICAgICAxNDAKKyBjb21w
YW55MSB8IDA3LTAyLTIwMjMgfCAgIDIwMCB8ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3
LTAzLTIwMjMgfCAgIDE1MCB8ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3LTA0LTIwMjMg
fCAgIDE0MCB8ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3LTA1LTIwMjMgfCAgIDE1MCB8
ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3LTA2LTIwMjMgfCAgICA5MCB8ICAgICAgICAx
MjAKKyBjb21wYW55MSB8IDA3LTA3LTIwMjMgfCAgIDExMCB8ICAgICAgICAgICAKKyBjb21w
YW55MSB8IDA3LTA4LTIwMjMgfCAgIDEzMCB8ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3
LTA5LTIwMjMgfCAgIDEyMCB8ICAgICAgICAgICAKKyBjb21wYW55MSB8IDA3LTEwLTIwMjMg
fCAgIDEzMCB8ICAgICAgICAgICAKKyBjb21wYW55MiB8IDA3LTAxLTIwMjMgfCAgICA1MCB8
ICAgICAgIDE0MDAKKyBjb21wYW55MiB8IDA3LTAyLTIwMjMgfCAgMjAwMCB8ICAgICAgICAg
ICAKKyBjb21wYW55MiB8IDA3LTAzLTIwMjMgfCAgMTUwMCB8ICAgICAgICAgICAKKyBjb21w
YW55MiB8IDA3LTA0LTIwMjMgfCAgMTQwMCB8ICAgICAgICAgICAKKyBjb21wYW55MiB8IDA3
LTA1LTIwMjMgfCAgMTUwMCB8ICAgICAgICAgICAKKyBjb21wYW55MiB8IDA3LTA2LTIwMjMg
fCAgICA2MCB8ICAgICAgIDEyMDAKKyBjb21wYW55MiB8IDA3LTA3LTIwMjMgfCAgMTEwMCB8
ICAgICAgICAgICAKKyBjb21wYW55MiB8IDA3LTA4LTIwMjMgfCAgMTMwMCB8ICAgICAgICAg
ICAKKyBjb21wYW55MiB8IDA3LTA5LTIwMjMgfCAgMTIwMCB8ICAgICAgICAgICAKKyBjb21w
YW55MiB8IDA3LTEwLTIwMjMgfCAgMTMwMCB8ICAgICAgICAgICAKKygyMCByb3dzKQorCiAt
LSBvbWl0ICJTVEFSVCIgaW4gREVGSU5FIGJ1dCBpdCBpcyBvayBiZWNhdXNlICJTVEFSVCBB
UyBUUlVFIiBpcwogLS0gaW1wbGljaXRseSBkZWZpbmVkLiBwZXIgc3BlYy4KIFNFTEVDVCBj
b21wYW55LCB0ZGF0ZSwgcHJpY2UsIGZpcnN0X3ZhbHVlKHByaWNlKSBPVkVSIHcsIGxhc3Rf
dmFsdWUocHJpY2UpIE9WRVIgdywKZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3JlZ3Jlc3Mvc3Fs
L3Jwci5zcWwgYi9zcmMvdGVzdC9yZWdyZXNzL3NxbC9ycHIuc3FsCmluZGV4IGM0ZjcwNGNk
YzQuLjE5YjFlOThhYzkgMTAwNjQ0Ci0tLSBhL3NyYy90ZXN0L3JlZ3Jlc3Mvc3FsL3Jwci5z
cWwKKysrIGIvc3JjL3Rlc3QvcmVncmVzcy9zcWwvcnByLnNxbApAQCAtNDUsNiArNDUsMjEg
QEAgU0VMRUNUIGNvbXBhbnksIHRkYXRlLCBwcmljZSwgZmlyc3RfdmFsdWUocHJpY2UpIE9W
RVIgdywgbGFzdF92YWx1ZShwcmljZSkgT1ZFUgogICBET1dOIEFTIHByaWNlIDwgUFJFVihw
cmljZSkKICk7CiAKKy0tIGxhc3RfdmFsdWUoKSBzaG91bGQgcmVtYWluIGNvbnNpc3RlbnQK
K1NFTEVDVCBjb21wYW55LCB0ZGF0ZSwgcHJpY2UsIGxhc3RfdmFsdWUocHJpY2UpIE9WRVIg
dworIEZST00gc3RvY2sKKyBXSU5ET1cgdyBBUyAoCisgUEFSVElUSU9OIEJZIGNvbXBhbnkK
KyBPUkRFUiBCWSB0ZGF0ZQorIFJPV1MgQkVUV0VFTiBDVVJSRU5UIFJPVyBBTkQgVU5CT1VO
REVEIEZPTExPV0lORworIElOSVRJQUwKKyBQQVRURVJOIChTVEFSVCBVUCsgRE9XTispCisg
REVGSU5FCisgIFNUQVJUIEFTIFRSVUUsCisgIFVQIEFTIHByaWNlID4gUFJFVihwcmljZSks
CisgIERPV04gQVMgcHJpY2UgPCBQUkVWKHByaWNlKQorKTsKKwogLS0gb21pdCAiU1RBUlQi
IGluIERFRklORSBidXQgaXQgaXMgb2sgYmVjYXVzZSAiU1RBUlQgQVMgVFJVRSIgaXMKIC0t
IGltcGxpY2l0bHkgZGVmaW5lZC4gcGVyIHNwZWMuCiBTRUxFQ1QgY29tcGFueSwgdGRhdGUs
IHByaWNlLCBmaXJzdF92YWx1ZShwcmljZSkgT1ZFUiB3LCBsYXN0X3ZhbHVlKHByaWNlKSBP
VkVSIHcsCg==

--------------YlsZCQR21Gfdi74kbPCppQcS--