Content-Type: multipart/mixed; boundary="------------16BwNw4m06Sf7I3Q9RM4oRPA"
Message-ID: <022a392f-2a9e-3df1-a509-a5bd51160fa5@timescale.com>
Date: Thu, 20 Jul 2023 16:36:37 -0700
MIME-Version: 1.0
User-Agent: Mozilla/5.0 (X11; Linux x86_64; rv:102.0) Gecko/20100101
 Thunderbird/102.13.0
Subject: Re: Row pattern recognition
To: Tatsuo Ishii <ishii@sraoss.co.jp>
Cc: pgsql-hackers@postgresql.org, vik@postgresfriends.org
References: <90bff6fa-01b7-cf60-f4f4-3412514a7cd2@postgresfriends.org>
 <20230628.095819.1123345378945479712.t-ishii@sranhm.sra.co.jp>
 <07214b3a-5893-f6ce-ef55-0e5d24c94925@timescale.com>
 <20230720.141513.1986681389874528348.t-ishii@sranhm.sra.co.jp>
Content-Language: en-US
From: Jacob Champion <jchampion@timescale.com>
In-Reply-To: <20230720.141513.1986681389874528348.t-ishii@sranhm.sra.co.jp>
Archived-At: 
 <https://www.postgresql.org/message-id/022a392f-2a9e-3df1-a509-a5bd51160fa5%40timescale.com>
Precedence: bulk

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

Hi Ishii-san,

On 7/19/23 22:15, Tatsuo Ishii wrote:
> Currently my patch has a limitation for the sake of simple
> implementation: a pattern like "A+" is parsed and analyzed in the raw
> parser. This makes subsequent process much easier because the pattern
> element variable (in this case "A") and the quantifier (in this case
> "+") is already identified by the raw parser. However there are much
> more cases are allowed in the standard as you already pointed out. For
> those cases probably we should give up to parse PATTERN items in the
> raw parser, and instead the raw parser just accepts the elements as
> Sconst?

Is there a concern that the PATTERN grammar can't be represented in
Bison? I thought it was all context-free... Or is the concern that the
parse tree of the pattern is hard to feed into a regex engine?

> Any comments, especially on the PREV/NEXT implementation part is
> welcome. Currently the DEFINE expression like "price > PREV(price)" is
> prepared in ExecInitWindowAgg using ExecInitExpr,tweaking var->varno
> in Var node so that PREV uses OUTER_VAR, NEXT uses INNER_VAR.  Then
> evaluate the expression in ExecWindowAgg using ExecEvalExpr, setting
> previous row TupleSlot to ExprContext->ecxt_outertuple, and next row
> TupleSlot to ExprContext->ecxt_innertuple. I think this is temporary
> hack and should be gotten ride of before v1 is committed. Better idea?

I'm not familiar enough with this code yet to offer very concrete
suggestions, sorry... But at some point in the future, we need to be
able to skip forward and backward from arbitrary points, like

    DEFINE B AS B.price > PREV(FIRST(A.price), 3)

so there won't be just one pair of "previous and next" tuples. Maybe
that can help clarify the design? It feels like it'll need to eventually
be a "real" function that operates on the window state, even if it
doesn't support all of the possible complexities in v1.

--

Taking a closer look at the regex engine:

It looks like the + qualifier has trouble when it meets the end of the
frame. For instance, try removing the last row of the 'stock' table in
rpr.sql; some of the final matches will disappear unexpectedly. Or try a
pattern like

    PATTERN ( a+ )
     DEFINE a AS TRUE

which doesn't seem to match anything in my testing.

There's also the issue of backtracking in the face of reclassification,
as I think Vik was alluding to upthread. The pattern

    PATTERN ( a+ b+ )
     DEFINE a AS col = 2,
            b AS col = 2

doesn't match a sequence of values (2 2 ...) with the current
implementation, even with a dummy row at the end to avoid the
end-of-frame bug.

(I've attached two failing tests against v2, to hopefully better
illustrate, along with what I _think_ should be the correct results.)

I'm not quite understanding the match loop in evaluate_pattern(). It
looks like we're building up a string to pass to the regex engine, but
by the we call regexp_instr, don't we already know whether or not the
pattern will match based on the expression evaluation we've done?

Thanks,
--Jacob
--------------16BwNw4m06Sf7I3Q9RM4oRPA
Content-Type: text/plain; charset=UTF-8; name="tests.diff.txt"
Content-Disposition: attachment; filename="tests.diff.txt"
Content-Transfer-Encoding: base64

ZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvcnByLm91dCBiL3NyYy90
ZXN0L3JlZ3Jlc3MvZXhwZWN0ZWQvcnByLm91dAppbmRleCA2YmY4ODE4OTExLi42OGU5YTk4
Njg0IDEwMDY0NAotLS0gYS9zcmMvdGVzdC9yZWdyZXNzL2V4cGVjdGVkL3Jwci5vdXQKKysr
IGIvc3JjL3Rlc3QvcmVncmVzcy9leHBlY3RlZC9ycHIub3V0CkBAIC0yMzAsNiArMjMwLDc5
IEBAIFNFTEVDVCBjb21wYW55LCB0ZGF0ZSwgcHJpY2UsIHJwcihwcmljZSkgT1ZFUiB3IEZS
T00gc3RvY2sKICBjb21wYW55MiB8IDA3LTEwLTIwMjMgfCAgMTMwMCB8ICAgICAKICgyMCBy
b3dzKQogCistLSBtYXRjaCBldmVyeXRoaW5nCitTRUxFQ1QgY29tcGFueSwgdGRhdGUsIHBy
aWNlLCBycHIocHJpY2UpIE9WRVIgdyBGUk9NIHN0b2NrCisgV0lORE9XIHcgQVMgKAorIFBB
UlRJVElPTiBCWSBjb21wYW55CisgT1JERVIgQlkgdGRhdGUKKyBST1dTIEJFVFdFRU4gQ1VS
UkVOVCBST1cgQU5EIFVOQk9VTkRFRCBGT0xMT1dJTkcKKyBBRlRFUiBNQVRDSCBTS0lQIFRP
IE5FWFQgUk9XCisgSU5JVElBTAorIFBBVFRFUk4gKEErKQorIERFRklORQorICBBIEFTIFRS
VUUKKyk7CisgY29tcGFueSAgfCAgIHRkYXRlICAgIHwgcHJpY2UgfCBycHIgCistLS0tLS0t
LS0tKy0tLS0tLS0tLS0tLSstLS0tLS0tKy0tLS0tCisgY29tcGFueTEgfCAwNy0wMS0yMDIz
IHwgICAxMDAgfCAxMDAKKyBjb21wYW55MSB8IDA3LTAyLTIwMjMgfCAgIDIwMCB8ICAgIAor
IGNvbXBhbnkxIHwgMDctMDMtMjAyMyB8ICAgMTUwIHwgICAgCisgY29tcGFueTEgfCAwNy0w
NC0yMDIzIHwgICAxNDAgfCAgICAKKyBjb21wYW55MSB8IDA3LTA1LTIwMjMgfCAgIDE1MCB8
ICAgIAorIGNvbXBhbnkxIHwgMDctMDYtMjAyMyB8ICAgIDkwIHwgICAgCisgY29tcGFueTEg
fCAwNy0wNy0yMDIzIHwgICAxMTAgfCAgICAKKyBjb21wYW55MSB8IDA3LTA4LTIwMjMgfCAg
IDEzMCB8ICAgIAorIGNvbXBhbnkxIHwgMDctMDktMjAyMyB8ICAgMTIwIHwgICAgCisgY29t
cGFueTEgfCAwNy0xMC0yMDIzIHwgICAxMzAgfCAgICAKKyBjb21wYW55MiB8IDA3LTAxLTIw
MjMgfCAgICA1MCB8ICA1MAorIGNvbXBhbnkyIHwgMDctMDItMjAyMyB8ICAyMDAwIHwgICAg
CisgY29tcGFueTIgfCAwNy0wMy0yMDIzIHwgIDE1MDAgfCAgICAKKyBjb21wYW55MiB8IDA3
LTA0LTIwMjMgfCAgMTQwMCB8ICAgIAorIGNvbXBhbnkyIHwgMDctMDUtMjAyMyB8ICAxNTAw
IHwgICAgCisgY29tcGFueTIgfCAwNy0wNi0yMDIzIHwgICAgNjAgfCAgICAKKyBjb21wYW55
MiB8IDA3LTA3LTIwMjMgfCAgMTEwMCB8ICAgIAorIGNvbXBhbnkyIHwgMDctMDgtMjAyMyB8
ICAxMzAwIHwgICAgCisgY29tcGFueTIgfCAwNy0wOS0yMDIzIHwgIDEyMDAgfCAgICAKKyBj
b21wYW55MiB8IDA3LTEwLTIwMjMgfCAgMTMwMCB8ICAgIAorKDIwIHJvd3MpCisKKy0tIGJh
Y2t0cmFja2luZyB3aXRoIHJlY2xhc3NpZmljYXRpb24gb2Ygcm93cworU0VMRUNUIGNvbXBh
bnksIHRkYXRlLCBwcmljZSwgcnByKHByaWNlKSBPVkVSIHcgRlJPTSBzdG9jaworIFdJTkRP
VyB3IEFTICgKKyBQQVJUSVRJT04gQlkgY29tcGFueQorIE9SREVSIEJZIHRkYXRlCisgUk9X
UyBCRVRXRUVOIENVUlJFTlQgUk9XIEFORCBVTkJPVU5ERUQgRk9MTE9XSU5HCisgQUZURVIg
TUFUQ0ggU0tJUCBUTyBORVhUIFJPVworIElOSVRJQUwKKyBQQVRURVJOIChBKyBCKykKKyBE
RUZJTkUKKyAgQSBBUyBwcmljZSA+IDEwMCwKKyAgQiBBUyBwcmljZSA+IDEwMAorKTsKKyBj
b21wYW55ICB8ICAgdGRhdGUgICAgfCBwcmljZSB8IHJwciAgCistLS0tLS0tLS0tKy0tLS0t
LS0tLS0tLSstLS0tLS0tKy0tLS0tLQorIGNvbXBhbnkxIHwgMDctMDEtMjAyMyB8ICAgMTAw
IHwgIDEwMAorIGNvbXBhbnkxIHwgMDctMDItMjAyMyB8ICAgMjAwIHwgICAgIAorIGNvbXBh
bnkxIHwgMDctMDMtMjAyMyB8ICAgMTUwIHwgICAgIAorIGNvbXBhbnkxIHwgMDctMDQtMjAy
MyB8ICAgMTQwIHwgICAgIAorIGNvbXBhbnkxIHwgMDctMDUtMjAyMyB8ICAgMTUwIHwgICAg
IAorIGNvbXBhbnkxIHwgMDctMDYtMjAyMyB8ICAgIDkwIHwgICAgIAorIGNvbXBhbnkxIHwg
MDctMDctMjAyMyB8ICAgMTEwIHwgIDExMAorIGNvbXBhbnkxIHwgMDctMDgtMjAyMyB8ICAg
MTMwIHwgICAgIAorIGNvbXBhbnkxIHwgMDctMDktMjAyMyB8ICAgMTIwIHwgICAgIAorIGNv
bXBhbnkxIHwgMDctMTAtMjAyMyB8ICAgMTMwIHwgICAgIAorIGNvbXBhbnkyIHwgMDctMDEt
MjAyMyB8ICAgIDUwIHwgICAgIAorIGNvbXBhbnkyIHwgMDctMDItMjAyMyB8ICAyMDAwIHwg
MjAwMAorIGNvbXBhbnkyIHwgMDctMDMtMjAyMyB8ICAxNTAwIHwgICAgIAorIGNvbXBhbnky
IHwgMDctMDQtMjAyMyB8ICAxNDAwIHwgICAgIAorIGNvbXBhbnkyIHwgMDctMDUtMjAyMyB8
ICAxNTAwIHwgICAgIAorIGNvbXBhbnkyIHwgMDctMDYtMjAyMyB8ICAgIDYwIHwgICAgIAor
IGNvbXBhbnkyIHwgMDctMDctMjAyMyB8ICAxMTAwIHwgMTEwMAorIGNvbXBhbnkyIHwgMDct
MDgtMjAyMyB8ICAxMzAwIHwgICAgIAorIGNvbXBhbnkyIHwgMDctMDktMjAyMyB8ICAxMjAw
IHwgICAgIAorIGNvbXBhbnkyIHwgMDctMTAtMjAyMyB8ICAxMzAwIHwgICAgIAorKDIwIHJv
d3MpCisKIC0tCiAtLSBFcnJvciBjYXNlcwogLS0KZGlmZiAtLWdpdCBhL3NyYy90ZXN0L3Jl
Z3Jlc3Mvc3FsL3Jwci5zcWwgYi9zcmMvdGVzdC9yZWdyZXNzL3NxbC9ycHIuc3FsCmluZGV4
IDk1MWM5YWJmZTkuLmYxY2QwMzY5ZjQgMTAwNjQ0Ci0tLSBhL3NyYy90ZXN0L3JlZ3Jlc3Mv
c3FsL3Jwci5zcWwKKysrIGIvc3JjL3Rlc3QvcmVncmVzcy9zcWwvcnByLnNxbApAQCAtOTQs
NiArOTQsMzMgQEAgU0VMRUNUIGNvbXBhbnksIHRkYXRlLCBwcmljZSwgcnByKHByaWNlKSBP
VkVSIHcgRlJPTSBzdG9jawogICBVUERPV04gQVMgcHJpY2UgPiBQUkVWKHByaWNlKSBBTkQg
cHJpY2UgPiBORVhUKHByaWNlKQogKTsKIAorLS0gbWF0Y2ggZXZlcnl0aGluZworU0VMRUNU
IGNvbXBhbnksIHRkYXRlLCBwcmljZSwgcnByKHByaWNlKSBPVkVSIHcgRlJPTSBzdG9jawor
IFdJTkRPVyB3IEFTICgKKyBQQVJUSVRJT04gQlkgY29tcGFueQorIE9SREVSIEJZIHRkYXRl
CisgUk9XUyBCRVRXRUVOIENVUlJFTlQgUk9XIEFORCBVTkJPVU5ERUQgRk9MTE9XSU5HCisg
QUZURVIgTUFUQ0ggU0tJUCBUTyBORVhUIFJPVworIElOSVRJQUwKKyBQQVRURVJOIChBKykK
KyBERUZJTkUKKyAgQSBBUyBUUlVFCispOworCistLSBiYWNrdHJhY2tpbmcgd2l0aCByZWNs
YXNzaWZpY2F0aW9uIG9mIHJvd3MKK1NFTEVDVCBjb21wYW55LCB0ZGF0ZSwgcHJpY2UsIHJw
cihwcmljZSkgT1ZFUiB3IEZST00gc3RvY2sKKyBXSU5ET1cgdyBBUyAoCisgUEFSVElUSU9O
IEJZIGNvbXBhbnkKKyBPUkRFUiBCWSB0ZGF0ZQorIFJPV1MgQkVUV0VFTiBDVVJSRU5UIFJP
VyBBTkQgVU5CT1VOREVEIEZPTExPV0lORworIEFGVEVSIE1BVENIIFNLSVAgVE8gTkVYVCBS
T1cKKyBJTklUSUFMCisgUEFUVEVSTiAoQSsgQispCisgREVGSU5FCisgIEEgQVMgcHJpY2Ug
PiAxMDAsCisgIEIgQVMgcHJpY2UgPiAxMDAKKyk7CisKIC0tCiAtLSBFcnJvciBjYXNlcwog
LS0K

--------------16BwNw4m06Sf7I3Q9RM4oRPA--