Re: [v9.2] make_greater_string() does not return a string in some cases

On Thu, Sep 22, 2011 at 8:59 AM, Greg Stark <stark@mit.edu> wrote:
> On Thu, Sep 22, 2011 at 1:49 PM, Robert Haas <robertmhaas@gmail.com> wrote:
>> My thought was that it would avoid the need to do any character
>> incrementing at all.  You could just start scanning forward as if the
>> operator were >= and then stop when you hit the first string that
>> doesn't have the same initial substring.
>
> But the whole problem is that not all the strings with the initial
> substring are in a contiguous block. The best we can hope for is that
> they're fairly dense within a block without too many non-matching
> strings. The example with / shows how that can happen.
>
> If you're looking for foo/% and you start with foo/ you'll find:
>
> foo/
> foo0
> foo/0
> foo1
> foo/1
> ...
>
> Even just case-insensitive collations don't put all the strings with a
> common prefix in a contiguous block. If you're searching for foo%
> you'll find:
>
> foo
> Foobar
> foobar

If that were true for the sorts of indexes we're using for LIKE
queries, the existing approach wouldn't work either.   All we're doing
is translating:
a LIKE 'foo/%'

to

a ~=>~ 'foo/%' AND a ~<~ 'foo0'

...where ~=>~ and ~<~ are just text-pattern-ops versions of => and <
that ignore the normal collation rules and just compare bytes.

In general, if we wanted to get rid of text_pattern_ops and make all
of this work with arbitrary indexes, yeah, that would be very
difficult.

--
Robert Haas
EnterpriseDB: http://www.enterprisedb.com
The Enterprise PostgreSQL Company