From: Tom Lane <tgl@sss.pgh.pa.us>
To: Nikita Glukhov <n.gluhov@postgrespro.ru>
cc: Pgsql Hackers <pgsql-hackers@postgresql.org>,
        =?UTF-8?Q?Filip_Rembia=c5=82kowski?= <filip.rembialkowski@gmail.com>,
        Tomas Vondra <tomas.vondra@2ndquadrant.com>,
        Alexander Korotkov <a.korotkov@postgrespro.ru>,
        Oleg Bartunov <obartunov@postgrespro.ru>,
        Thomas Munro <thomas.munro@gmail.com>,
        Teodor Sigaev <teodor@sigaev.ru>
Subject: Re: fix for BUG #3720: wrong results at using ltree
In-reply-to: <6352.1585609100@sss.pgh.pa.us>
References: 
 <CAP_rww=waX2Oo6q+MbMSiZ9ktdj6eaJj0cQzNu=Ry2cCDij5fw@mail.gmail.com>
 <28639.1554565562@sss.pgh.pa.us>
 <CA+hUKGKVbTGHGpHBX6EGew13CrfYcagThJqBAmeATCMKnVqisQ@mail.gmail.com>
 <CAF4Au4yV8vsgA_7XCce4kFUa2BjseqWj=KVuOwcE+DGLj6AW7g@mail.gmail.com>
 <5eedfd9e-2f14-a2df-3bd9-4c92eb0f08a5@postgrespro.ru>
 <CAPpHfdsvEaqXDsLWebQ4Q4GszRZ_P6h-1_cidmiqPMtWzXnmhA@mail.gmail.com>
 <20200124182915.zz7hzdkijzsb4ic4@development>
 <a315c67d-5b3b-8005-99ef-daa9ea7036a0@postgrespro.ru>
 <19375.1585438012@sss.pgh.pa.us> <15582.1585529626@sss.pgh.pa.us>
 <23304.1585591242@sss.pgh.pa.us>
 <943dc224-eb82-8abd-15c3-f4b516f89767@postgrespro.ru>
 <3007.1585605566@sss.pgh.pa.us> <3843.1585606362@sss.pgh.pa.us>
 <9247ddc2-d1e0-7d62-55a6-62a089e99a8a@postgrespro.ru>
 <5210.1585607748@sss.pgh.pa.us>
 <4c00219b-7094-e568-cc2c-6a52cf621701@postgrespro.ru>
 <6352.1585609100@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Mon, 30 Mar 2020 18:58:20 -0400"
MIME-Version: 1.0
Content-Type: text/plain; charset="us-ascii"
Content-ID: <4901.1585669650.1@sss.pgh.pa.us>
Date: Tue, 31 Mar 2020 11:47:30 -0400
Message-ID: <4902.1585669650@sss.pgh.pa.us>
Precedence: bulk

I wrote:
> I've marked this RFC, and will push tomorrow unless somebody wants
> to object to the loss of backwards compatibility.

And done.  I noticed in some final testing that it's possible to
make this code take a long time by forcing it to backtrack a lot:

regression=# SELECT (('1' || repeat('.1', 65534))::ltree) ~ '*.*.x';
 ?column? 
----------
 f
(1 row)

Time: 54015.421 ms (00:54.015)

so I threw in a CHECK_FOR_INTERRUPTS().  Maybe it'd be worth trying
to optimize such cases, but I'm not sure that it'd ever matter for
real-world cases with reasonable-size label strings.

The old implementation seems to handle that particular case well,
evidently because it more-or-less folds adjacent stars together.
However, before anyone starts complaining about regressions, they
should note that it's really easy to get the old code to fail
via stack overflow:

regression=# SELECT (('1' || repeat('.1', 65534))::ltree) ~ '*.!1.*';
ERROR:  stack depth limit exceeded

(That's as of five minutes ago, before that it dumped core.)
So I don't feel bad about the tradeoff.  At least now we have
simple, visibly correct code that could serve as a starting
point for optimization if anyone feels the need to.

			regards, tom lane