Re: fix for BUG #3720: wrong results at using ltree

Hi all,

Here is my attempt to fix a 12-years old ltree bug (which is a todo item).

I see it's not backward-compatible, but in my understanding that's
what is documented. Previous behavior was inconsistent with
documentation (where single asterisk should match zero or more
labels).

http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

=?utf-8?Q?Filip_Rembia=C5=82kowski?= <filip(dot)rembialkowski(at)gmail(dot)com> writes:
> Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> I see it's not backward-compatible, but in my understanding that's
> what is documented. Previous behavior was inconsistent with
> documentation (where single asterisk should match zero or more
> labels).
> http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

I took a quick look through this. I see where you're going with this,
and I agree that this coding seems like a better match to what it says
in the documentation:

... you can put ! (NOT) at the start to match any label that
doesn't match any of the alternatives.

However, it seems like Teodor and Oleg went to an awful lot of trouble
to implement some other behavior. It looks like what's there is trying
to do something like "true if this pattern does not match any label
between the matches for whatever's around it", rather than just "true
if this pattern does not match at one specific position". The number
of changes in the expected output for existing regression test cases
is also disheartening: it's fairly hard to believe that whoever wrote
the test cases didn't think those expected outputs were correct.

In short, I'm wondering if we should treat this as a documentation
bug not a code bug. But to do that, we'd need a more accurate
description of what the code is supposed to do, because the statement
quoted above is certainly not a match to the actual behavior.

BTW, if we do proceed in this direction, I wonder whether the
ltree_gist code needs any adjustments.

Thoughts?

regards, tom lane

On Sun, Apr 7, 2019 at 3:46 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> =?utf-8?Q?Filip_Rembia=C5=82kowski?= <filip(dot)rembialkowski(at)gmail(dot)com> writes:
> > Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> > I see it's not backward-compatible, but in my understanding that's
> > what is documented. Previous behavior was inconsistent with
> > documentation (where single asterisk should match zero or more
> > labels).
> > http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php

[...]

> In short, I'm wondering if we should treat this as a documentation
> bug not a code bug. But to do that, we'd need a more accurate
> description of what the code is supposed to do, because the statement
> quoted above is certainly not a match to the actual behavior.

This patch doesn't apply. More importantly, it seems like we don't
have a consensus on whether we want it.

Teodor, Oleg, would you like to offer an opinion here? If I
understand correctly, the choices are doc change, code/comment change
or WONT_FIX. This seems to be an entry that we can bring to a
conclusion in this CF with some input from the ltree experts.

--
Thomas Munro
https://enterprisedb.com

On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
>
> On Sun, Apr 7, 2019 at 3:46 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
> > =?utf-8?Q?Filip_Rembia=C5=82kowski?= <filip(dot)rembialkowski(at)gmail(dot)com> writes:
> > > Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> > > I see it's not backward-compatible, but in my understanding that's
> > > what is documented. Previous behavior was inconsistent with
> > > documentation (where single asterisk should match zero or more
> > > labels).
> > > http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php
>
> [...]
>
> > In short, I'm wondering if we should treat this as a documentation
> > bug not a code bug. But to do that, we'd need a more accurate
> > description of what the code is supposed to do, because the statement
> > quoted above is certainly not a match to the actual behavior.
>
> This patch doesn't apply. More importantly, it seems like we don't
> have a consensus on whether we want it.
>
> Teodor, Oleg, would you like to offer an opinion here? If I
> understand correctly, the choices are doc change, code/comment change
> or WONT_FIX. This seems to be an entry that we can bring to a
> conclusion in this CF with some input from the ltree experts.

We are currently very busy and will look at the problem (and dig into
our memory)
later. There is also another ltree patch
(https://commitfest.postgresql.org/23/1977/) it would be
nice if Filip try it.

>
> --
> Thomas Munro
> https://enterprisedb.com

--
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

On 09.07.2019 17:57, Oleg Bartunov wrote:
> On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
>> On Sun, Apr 7, 2019 at 3:46 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>>> =?utf-8?Q?Filip_Rembia=C5=82kowski?= <filip(dot)rembialkowski(at)gmail(dot)com> writes:
>>>> Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
>>>> I see it's not backward-compatible, but in my understanding that's
>>>> what is documented. Previous behavior was inconsistent with
>>>> documentation (where single asterisk should match zero or more
>>>> labels).
>>>> http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php
>> [...]
>>
>>> In short, I'm wondering if we should treat this as a documentation
>>> bug not a code bug. But to do that, we'd need a more accurate
>>> description of what the code is supposed to do, because the statement
>>> quoted above is certainly not a match to the actual behavior.
>> This patch doesn't apply. More importantly, it seems like we don't
>> have a consensus on whether we want it.
>>
>> Teodor, Oleg, would you like to offer an opinion here? If I
>> understand correctly, the choices are doc change, code/comment change
>> or WONT_FIX. This seems to be an entry that we can bring to a
>> conclusion in this CF with some input from the ltree experts.
> We are currently very busy and will look at the problem (and dig into
> our memory) later. There is also another ltree patch
> (https://commitfest.postgresql.org/23/1977/) it would be nice if
> Filip try it.

I looked at "ltree syntax improvement" patch and found two more very
old bugs in ltree/lquery (fixes are attached):

1. ltree/lquery level counter overflow is wrongly checked:

SELECT nlevel((repeat('a.', 65534) || 'a')::ltree);
nlevel
--------
65535
(1 row)

-- expected 65536 or error
SELECT nlevel((repeat('a.', 65535) || 'a')::ltree);
nlevel
--------
0
(1 row)

-- expected 65537 or error
SELECT nlevel((repeat('a.', 65536) || 'a')::ltree);
nlevel
--------
1
(1 row)

-- expected 'aaaaa...' or error
SELECT (repeat('a.', 65535) || 'a')::ltree;
ltree
-------

(1 row)

-- expected 'aaaaa...' or error
SELECT (repeat('a.', 65536) || 'a')::ltree;
ltree
-------
a
(1 row)

2. '*{a}.*{b}.*{c}' is not equivalent to '*{a+b+c}' (as I expect):

SELECT ltree '1.2' ~ '*{2}';
?column?
----------
t
(1 row)

-- expected true
SELECT ltree '1.2' ~ '*{1}.*{1}';
?column?
----------
f
(1 row)

Maybe these two bugs need a separate thread?

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Hi Nikita,

On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> wrote:
> I looked at "ltree syntax improvement" patch and found two more very
> old bugs in ltree/lquery (fixes are attached):

Thank you for the fixes. I've couple notes on them.

0001-Fix-max-size-checking-for-ltree-and-lquery.patch

+#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / sizeof(nodeitem))
+#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)

Looks over caution. PG_UINT16_MAX is not even close to MaxAllocSize /
sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.

0002-Fix-successive-lquery-ops.patch

diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
index 62172d5..d4f4941 100644
--- a/contrib/ltree/lquery_op.c
+++ b/contrib/ltree/lquery_op.c
@@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
}
else
{
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
if (ptr && ptr->q)
{
ptr->nq++;
@@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
ltree_level *curt, int tree_nu
}
else
{
- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
}

curq = LQL_NEXT(curq);

I'm not sure what do these checks do. Code around is uncommented and
puzzled. But could we guarantee the same invariant on the stage of
ltree/lquery parsing?

------
Alexander Korotkov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Please create separate commitfest entry.

On Tue, Jul 16, 2019 at 8:52 PM Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru>
wrote:

>
> On 09.07.2019 17:57, Oleg Bartunov wrote:
>
> On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> <thomas(dot)munro(at)gmail(dot)com> wrote:
>
> On Sun, Apr 7, 2019 at 3:46 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:
>
> =?utf-8?Q?Filip_Rembia=C5=82kowski?= <filip(dot)rembialkowski(at)gmail(dot)com> <filip(dot)rembialkowski(at)gmail(dot)com> writes:
>
> Here is my attempt to fix a 12-years old ltree bug (which is a todo item).
> I see it's not backward-compatible, but in my understanding that's
> what is documented. Previous behavior was inconsistent with
> documentation (where single asterisk should match zero or more
> labels).http://archives.postgresql.org/pgsql-bugs/2007-11/msg00044.php
>
> [...]
>
>
> In short, I'm wondering if we should treat this as a documentation
> bug not a code bug. But to do that, we'd need a more accurate
> description of what the code is supposed to do, because the statement
> quoted above is certainly not a match to the actual behavior.
>
> This patch doesn't apply. More importantly, it seems like we don't
> have a consensus on whether we want it.
>
> Teodor, Oleg, would you like to offer an opinion here? If I
> understand correctly, the choices are doc change, code/comment change
> or WONT_FIX. This seems to be an entry that we can bring to a
> conclusion in this CF with some input from the ltree experts.
>
> We are currently very busy and will look at the problem (and dig into
> our memory) later. There is also another ltree patch
> (https://commitfest.postgresql.org/23/1977/) it would be nice if
> Filip try it.
>
> I looked at "ltree syntax improvement" patch and found two more very
> old bugs in ltree/lquery (fixes are attached):
>
> 1. ltree/lquery level counter overflow is wrongly checked:
>
> SELECT nlevel((repeat('a.', 65534) || 'a')::ltree);
> nlevel
> --------
> 65535
> (1 row)
>
> -- expected 65536 or error
> SELECT nlevel((repeat('a.', 65535) || 'a')::ltree);
> nlevel
> --------
> 0
> (1 row)
>
> -- expected 65537 or error
> SELECT nlevel((repeat('a.', 65536) || 'a')::ltree);
> nlevel
> --------
> 1
> (1 row)
>
> -- expected 'aaaaa...' or error
> SELECT (repeat('a.', 65535) || 'a')::ltree;
> ltree
> -------
>
> (1 row)
>
> -- expected 'aaaaa...' or error
> SELECT (repeat('a.', 65536) || 'a')::ltree;
> ltree
> -------
> a
> (1 row)
>
>
> 2. '*{a}.*{b}.*{c}' is not equivalent to '*{a+b+c}' (as I expect):
>
> SELECT ltree '1.2' ~ '*{2}';
> ?column?
> ----------
> t
> (1 row)
>
> -- expected true
> SELECT ltree '1.2' ~ '*{1}.*{1}';
> ?column?
> ----------
> f
> (1 row)
>
>
> Maybe these two bugs need a separate thread?
>
>
> Please create separate commitfest entry.

> --
> Nikita Glukhov
> Postgres Professional: http://www.postgrespro.com
> The Russian Postgres Company
>
>
>

--
Ibrar Ahmed

On 2019-Jul-09, Oleg Bartunov wrote:

> On Mon, Jul 8, 2019 at 7:22 AM Thomas Munro <thomas(dot)munro(at)gmail(dot)com> wrote:
> >
> > On Sun, Apr 7, 2019 at 3:46 AM Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us> wrote:

> > > In short, I'm wondering if we should treat this as a documentation
> > > bug not a code bug. But to do that, we'd need a more accurate
> > > description of what the code is supposed to do, because the statement
> > > quoted above is certainly not a match to the actual behavior.

> > Teodor, Oleg, would you like to offer an opinion here?

> We are currently very busy and will look at the problem (and dig into
> our memory) later.

Hi Oleg, Teodor. Did you find time to refresh your memory on these things?
It would be good to have these bugfixes sorted out.

--
Álvaro Herrera https://www.2ndQuadrant.com/
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

The following review has been posted through the commitfest application:
make installcheck-world: tested, passed
Implements feature: tested, passed
Spec compliant: not tested
Documentation: tested, failed

This is my first PostgreSQL commitfest and review, guidance welcome.

This patch is straightforward, it applies cleanly, and it includes tests (I've also tested the feature manually).

The (existing) documentation states "The length of a label path must be less than 65kB," I believe that the 65kB mentioned here should instead be 64kB - perhaps the patch could be updated with this single-character fix? At first I thought the 65kB limit would be applied to the label path string (e.g. 'Top.Countries.Europe.Russia' would be 27 bytes), but it seems the limit applies to the number of labels in the path - perhaps `kB` is not the right measurement here and it should explicitly state 65536?

It is not stated in the documentation what should happen if the label path length is greater than 65535, so raising an error makes sense (but may be a breaking change).

The new status of this patch is: Waiting on Author

On Thu, Sep 05, 2019 at 04:50:58PM -0400, Alvaro Herrera from 2ndQuadrant wrote:
> Hi Oleg, Teodor. Did you find time to refresh your memory on these things?
> It would be good to have these bugfixes sorted out.

Two months later. Now would be a good time as well! Alexander, you
have also looked at two patches from Nikita upthread. If these look
good enough for you, are you working on merging them into the tree?
--
Michael

Hi Nikita,

This patch seems inactive / stuck in "waiting on author" since November.
It's marked as bugfix, so it'd be good to get it committed instead of
just punting it to the next CF.

I did a quick review, and I came mostly with the same two complaints as
Alexander ...

On Wed, Jul 17, 2019 at 09:33:46PM +0300, Alexander Korotkov wrote:
>Hi Nikita,
>
>On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> wrote:
>> I looked at "ltree syntax improvement" patch and found two more very
>> old bugs in ltree/lquery (fixes are attached):
>
>Thank you for the fixes. I've couple notes on them.
>
>0001-Fix-max-size-checking-for-ltree-and-lquery.patch
>
>+#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / sizeof(nodeitem))
>+#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)
>
>Looks over caution. PG_UINT16_MAX is not even close to MaxAllocSize /
>sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.
>

Yeah, I'm also puzzled by the usage of PG_UINT16_MAX here. It's so much
lower than the other values we could jut use the constant directly, but
let's say the structs could grow from the ~16B to chnge this.

The main question is why we need PG_UINT16_MAX at all? It kinda implies
we need to squish the value into a 2B counter or something, but is that
actually true? I don't see anything like that in ltree_io.c.

So it seems more like an arbitrary value considered "sane" - which is
fine, but then a comment saying so would be nice, and we could pick a
value that is "nicer" for humans. Or just use value computed from the
MaxAllocSize limit, without the Min().

>0002-Fix-successive-lquery-ops.patch
>
>diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
>index 62172d5..d4f4941 100644
>--- a/contrib/ltree/lquery_op.c
>+++ b/contrib/ltree/lquery_op.c
>@@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
>ltree_level *curt, int tree_nu
> }
> else
> {
>- low_pos = cur_tpos + curq->low;
>- high_pos = cur_tpos + curq->high;
>+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
>+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
> if (ptr && ptr->q)
> {
> ptr->nq++;
>@@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
>ltree_level *curt, int tree_nu
> }
> else
> {
>- low_pos = cur_tpos + curq->low;
>- high_pos = cur_tpos + curq->high;
>+ low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
>+ high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
> }
>
> curq = LQL_NEXT(curq);
>
>I'm not sure what do these checks do. Code around is uncommented and
>puzzled. But could we guarantee the same invariant on the stage of
>ltree/lquery parsing?
>

Unfortunately, the current code is somewhat undercommented :-(

Anyway, I don't quite understand why we need these caps. It kinda seems
like a band-aid for potential overflow.

Why should it be OK for the values to even get past the maximum, with
sane input data? And isn't there a better upper limit (e.g. based on
how much space we actually allocated)?

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

Hi,

I've moved this patch to the next CF - it's still in WoA state, but it's
supposedly a bugfix so I've decided not to return it with feedback.

regards

--
Tomas Vondra http://www.2ndQuadrant.com
PostgreSQL Development, 24x7 Support, Remote DBA, Training & Services

On 24.01.2020 21:29, Tomas Vondra wrote:
> Hi Nikita,
>
> This patch seems inactive / stuck in "waiting on author" since November.
> It's marked as bugfix, so it'd be good to get it committed instead of
> just punting it to the next CF.
>
> I did a quick review, and I came mostly with the same two complaints as
> Alexander ...
>
> On Wed, Jul 17, 2019 at 09:33:46PM +0300, Alexander Korotkov wrote:
>> Hi Nikita,
>>
>> On Tue, Jul 16, 2019 at 6:52 PM Nikita Glukhov
>> <n(dot)gluhov(at)postgrespro(dot)ru> wrote:
>>> I looked at "ltree syntax improvement" patch and found two more very
>>> old bugs in ltree/lquery (fixes are attached):
>>
>> Thank you for the fixes.  I've couple notes on them.
>>
>> 0001-Fix-max-size-checking-for-ltree-and-lquery.patch
>>
>> +#define LTREE_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize /
>> sizeof(nodeitem))
>> +#define LQUERY_MAX_LEVELS Min(PG_UINT16_MAX, MaxAllocSize / ITEMSIZE)
>>
>> Looks over caution.  PG_UINT16_MAX is not even close to MaxAllocSize /
>> sizeof(nodeitem) or MaxAllocSize / ITEMSIZE.
>>
>
> Yeah, I'm also puzzled by the usage of PG_UINT16_MAX here. It's so much
> lower than the other values we could jut use the constant directly, but
> let's say the structs could grow from the ~16B to chnge this.

Ok, LTREE_MAX_LEVELS and LQUERY_MAX_LEVELS are defined simply as PG_UINT16_MAX now.

>
> The main question is why we need PG_UINT16_MAX at all? It kinda implies
> we need to squish the value into a 2B counter or something, but is that
> actually true? I don't see anything like that in ltree_io.c.

ltree.numlevel and lquery.numlevel are uint16 fields.

I also found two places in ltree_concat() where numlevel can overflow.

The first is ltree_concat() (operator ||(ltree, ltree)):

=# SELECT nlevel(('a' || repeat('.a', 65533))::ltree || 'a');
nlevel
--------
65535
(1 row)

=# SELECT nlevel(('a' || repeat('.a', 65534))::ltree || 'a');
nlevel
--------
0
(1 row)

The second is parsing of low and high level limits in lquery_in():

=# SELECT '*{65535}'::lquery;
lquery
----------
*{65535}
(1 row)

=# SELECT '*{65536}'::lquery;
lquery
--------
*{0}
(1 row)

=# SELECT '*{65537}'::lquery;
lquery
--------
*{1}
(1 row)

The both problems are fixed in the new version of the patch.

> So it seems more like an arbitrary value considered "sane" - which is
> fine, but then a comment saying so would be nice, and we could pick a
> value that is "nicer" for humans. Or just use value computed from the
> MaxAllocSize limit, without the Min().
>
>> 0002-Fix-successive-lquery-ops.patch
>>
>> diff --git a/contrib/ltree/lquery_op.c b/contrib/ltree/lquery_op.c
>> index 62172d5..d4f4941 100644
>> --- a/contrib/ltree/lquery_op.c
>> +++ b/contrib/ltree/lquery_op.c
>> @@ -255,8 +255,8 @@ checkCond(lquery_level *curq, int query_numlevel,
>> ltree_level *curt, int tree_nu
>>  }
>>  else
>>  {
>> - low_pos = cur_tpos + curq->low;
>> - high_pos = cur_tpos + curq->high;
>> + low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
>> + high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
>>  if (ptr && ptr->q)
>>  {
>>  ptr->nq++;
>> @@ -282,8 +282,8 @@ checkCond(lquery_level *curq, int query_numlevel,
>> ltree_level *curt, int tree_nu
>>  }
>>  else
>>  {
>> - low_pos = cur_tpos + curq->low;
>> - high_pos = cur_tpos + curq->high;
>> + low_pos = Min(low_pos + curq->low, PG_UINT16_MAX);
>> + high_pos = Min(high_pos + curq->high, PG_UINT16_MAX);
>>  }
>>
>>  curq = LQL_NEXT(curq);
>>
>> I'm not sure what do these checks do.  Code around is uncommented and
>> puzzled.  But could we guarantee the same invariant on the stage of
>> ltree/lquery parsing?
>>
>
> Unfortunately, the current code is somewhat undercommented :-(

The main problem is that no one really understands how it works now.

low_pos and high_pos seem to be a range of tree levels, from which is allowed
to match the rest of lquery.

For example, when we are matching '.b' in the 'a.*{2,3}.*{4,5}.b'::lquery,
low_pos = 1 + 2 + 4 = 7 and high_pos = 1 + 3 + 5 = 9.

The main goal of the patch is to fix calculation of low_pos and high_pos:

- low_pos = cur_tpos + curq->low;
- high_pos = cur_tpos + curq->high;
+ low_pos = low_pos + curq->low;
+ high_pos = high_pos + curq->high;

>
> Anyway, I don't quite understand why we need these caps. It kinda seems
> like a band-aid for potential overflow.
>
> Why should it be OK for the values to even get past the maximum, with
> sane input data? And isn't there a better upper limit (e.g. based on
> how much space we actually allocated)?

We can compare low_pos to tree_numlevel and return false earlier, if it is
greater. And it seems that high_pos we can also limit to tree_numlevel.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
> On 24.01.2020 21:29, Tomas Vondra wrote:
>> Unfortunately, the current code is somewhat undercommented :-(

> The main problem is that no one really understands how it works now.

Indeed. I was disturbed to realize that lquery_op.c, despite being
far from trivial code, contained NOT ONE SINGLE COMMENT before today,
other than the content-free file header and a commented-out (visibly
unsafe, too) debugging printing function. This is a long way south
of minimally acceptable, in my book.

Anyway, I concur that Nikita's two patches are bug fixes, so I pushed
them. Nonetheless, he *did* hijack this thread, so in hopes of restoring
attention to the original topic, here's a rebased version of the original
patch.

My main complaint about it remains the same, that it changes a
disturbingly large number of existing regression-test results,
suggesting that there's not a meeting of the minds about what
this logic is supposed to do. Maybe it's okay or maybe it's
not, but who's going to decide?

Also, now that I've looked at it a bit more, I'd be inclined to
strip out the parts of the patch that remove setting up the
LQUERY_HASNOT flag. Even if we're not using that right now,
we might want it again someday, and we're not saving much of
anything by introducing a minor on-disk incompatibility.

regards, tom lane

I wrote:
> My main complaint about it remains the same, that it changes a
> disturbingly large number of existing regression-test results,
> suggesting that there's not a meeting of the minds about what
> this logic is supposed to do. Maybe it's okay or maybe it's
> not, but who's going to decide?

Well ... *somebody's* got to decide, and since Oleg and Teodor aren't
stepping up, I took it on myself to study this more closely.

It seems to me that indeed the existing behavior is broken: given
what the documentation has to say, it's really hard to argue that
an lquery like "*.!foo.*" means something other than "match any
ltree that has at least one label that is not 'foo'". But the
existing code produces

regression=# select 'bar.foo.baz'::ltree ~ '*.!foo.*'::lquery;
?column?
----------
f
(1 row)

I agree that's just plain wrong, and so are all the regression
test cases that this patch is changing the results of.

However, I think there is a valid use-case that the existing
code is trying to solve: how can you say "match any ltree in
which no label is 'foo'"? That is the effective behavior right
now of a pattern like this, and it seems useful. So if we change
this, we ought to provide some other way to get that result.

What I propose we do about that is allow lquery quantifiers to
be attached to regular items as well as star items, so that the
need is met by saying this:

regression=# select 'bar.foo.baz'::ltree ~ '!foo{,}'::lquery;
?column?
----------
f
(1 row)

regression=# select 'bar.fool.baz'::ltree ~ '!foo{,}'::lquery;
?column?
----------
t
(1 row)

Also, once we do that, it's possible to treat star and non-star items
basically alike in checkCond, with checkLevel being the place that
accounts for them being different. This results in logic that's far
simpler and much more nearly like the way that LIKE patterns are
implemented, which seems like a good thing to me.

Hence, attached are two revised patches that attack the problem
this way. The first one is somewhat unrelated to the original
point --- it's trying to clean up the error messages in ltree_in
and lquery_in so that they are more consistent and agree with
the terminology used in the documentation. (Notably, the term
"level" is used nowhere in the ltree docs, except in the legacy
function name nlevel().) However its movement of the check for
high < low is needed to make that cover the case of a bogus non-star
quantifier in patch 0002. These also depend on the cosmetic
patches I just committed, so you need HEAD as of today to get
them to apply.

regards, tom lane

I wrote:
> Hence, attached are two revised patches that attack the problem
> this way. The first one is somewhat unrelated to the original
> point --- it's trying to clean up the error messages in ltree_in
> and lquery_in so that they are more consistent and agree with
> the terminology used in the documentation. (Notably, the term
> "level" is used nowhere in the ltree docs, except in the legacy
> function name nlevel().)

One thing I changed in that patch was to change the syntax error
reports to say "at character %d" not "in position %d", because
I thought the latter was pretty confusing --- it's not obvious
whether it's counting characters or labels or what. However,
I now notice that what the code is providing is a zero-based
character index, which is out of line with our practice
elsewhere: core parser errors are reported using 1-based indexes.
If we reword these messages then we should adopt that practice too.
Hence, new patch versions that do it like that. (0002 is unchanged.)

regards, tom lane

On 30.03.2020 21:00, Tom Lane wrote:

> Hence, new patch versions that do it like that. (0002 is unchanged.)

I tried to simplify a bit loops in checkCond() by merging two of them into
one with an explicit exit condition. Also I added return statement after
this loop, so it's now clear that we can't fall into next "while" loop.

The rest code in 0001 and 0002 is unchanged.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
> On 30.03.2020 21:00, Tom Lane wrote:
>> Hence, new patch versions that do it like that. (0002 is unchanged.)

> I tried to simplify a bit loops in checkCond() by merging two of them into
> one with an explicit exit condition. Also I added return statement after
> this loop, so it's now clear that we can't fall into next "while" loop.

I dunno, that doesn't really seem clearer to me (although some of it
might be that you expended no effort on making the comments match
the new code logic).

regards, tom lane

I wrote:
> I dunno, that doesn't really seem clearer to me (although some of it
> might be that you expended no effort on making the comments match
> the new code logic).

... although looking closer, this formulation does have one very nice
advantage: for the typical non-star case with high = low = 1, the
only recursive call is a tail recursion, so it ought to consume less
stack space than what I wrote.

Let me see what I can do with the comments.

regards, tom lane

On 31.03.2020 1:12, Tom Lane wrote:

> I wrote:
>> I dunno, that doesn't really seem clearer to me (although some of it
>> might be that you expended no effort on making the comments match
>> the new code logic).
> ... although looking closer, this formulation does have one very nice
> advantage: for the typical non-star case with high = low = 1, the
> only recursive call is a tail recursion, so it ought to consume less
> stack space than what I wrote.

And we even can simply transform this tail call into a loop:

-if (tlen > 0 && qlen > 0)
+while (tlen > 0 && qlen > 0)

> Let me see what I can do with the comments.

Thanks.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
> And we even can simply transform this tail call into a loop:

> -if (tlen > 0 && qlen > 0)
> +while (tlen > 0 && qlen > 0)

Yeah, the same occurred to me ... and then we can drop the other loop too.
I've got it down to this now:

/*
* Try to match an lquery (of qlen items) to an ltree (of tlen items)
*/
static bool
checkCond(lquery_level *curq, int qlen,
ltree_level *curt, int tlen)
{
/* Since this function recurses, it could be driven to stack overflow */
check_stack_depth();

/* Loop while we have query items to consider */
while (qlen > 0)
{
int low,
high;
lquery_level *nextq;

/*
* Get min and max repetition counts for this query item, dealing with
* the backwards-compatibility hack that the low/high fields aren't
* meaningful for non-'*' items unless LQL_COUNT is set.
*/
if ((curq->flag & LQL_COUNT) || curq->numvar == 0)
low = curq->low, high = curq->high;
else
low = high = 1;

/*
* We may limit "high" to the remaining text length; this avoids
* separate tests below.
*/
if (high > tlen)
high = tlen;

/* Fail if a match of required number of items is impossible */
if (high < low)
return false;

/*
* Recursively check the rest of the pattern against each possible
* start point following some of this item's match(es).
*/
nextq = LQL_NEXT(curq);
qlen--;

for (int matchcnt = 0; matchcnt < high; matchcnt++)
{
/*
* If we've consumed an acceptable number of matches of this item,
* and the rest of the pattern matches beginning here, we're good.
*/
if (matchcnt >= low && checkCond(nextq, qlen, curt, tlen))
return true;

/*
* Otherwise, try to match one more text item to this query item.
*/
if (!checkLevel(curq, curt))
return false;

curt = LEVEL_NEXT(curt);
tlen--;
}

/*
* Once we've consumed "high" matches, we can succeed only if the rest
* of the pattern matches beginning here. Loop around (if you prefer,
* think of this as tail recursion).
*/
curq = nextq;
}

/*
* Once we're out of query items, we match only if there's no remaining
* text either.
*/
return (tlen == 0);
}

regards, tom lane

On 31.03.2020 1:35, Tom Lane wrote:
> Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
>> And we even can simply transform this tail call into a loop:
>>
>> -if (tlen > 0 && qlen > 0)
>> +while (tlen > 0 && qlen > 0)
> Yeah, the same occurred to me ... and then we can drop the other loop too.

I think now it looks as simple as the whole algorithm is.

--
Nikita Glukhov
Postgres Professional: http://www.postgrespro.com
The Russian Postgres Company

Nikita Glukhov <n(dot)gluhov(at)postgrespro(dot)ru> writes:
> I think now it looks as simple as the whole algorithm is.

Yeah, I think we've gotten checkCond to the point of "there's no
longer anything to take away".

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

regards, tom lane

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