From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <dgrowleyml@gmail.com>
Cc: Martin L. Buchanan <martinlbuchanan@gmail.com>
Cc: pgsql-general list <pgsql-general@lists.postgresql.org>
Subject: Re: Boyer-Moore string searching in LIKE, ILIKE, and/or POSITION?
Date: Wed, 08 Feb 2023 20:49:43 -0500
Message-ID: <3811203.1675907383@sss.pgh.pa.us> (raw)
In-Reply-To: <CAApHDvqJy1Tdg8bxXWena3vbv8x0UF9skyM2jOo-LVf-qv0OJw@mail.gmail.com>
References: <CAPfd9M=kwDT2TRTRNFUcOkoFLa5FL2Dxshjqz3zBrbqQ=1agLA@mail.gmail.com>
<CAApHDvqJy1Tdg8bxXWena3vbv8x0UF9skyM2jOo-LVf-qv0OJw@mail.gmail.com>
David Rowley <dgrowleyml@gmail.com> writes:
> On Thu, 9 Feb 2023 at 13:05, Martin L. Buchanan
> <martinlbuchanan@gmail.com> wrote:
>> str LIKE '%foo%'
>> str ILIKE '%foo%'
>> position('foo' in str) > 0
>> Is Boyer-Moore string searching now used by any of these three?
> We use a sort of "lossy" Boyer-Moore-Horspool algorithm. See
> text_position_setup() and text_position_next() in varlena.c (the lossy
> part comes from the skiptables possibly sharing the same entry for
> multiple characters as defined by what skiptablemask is set to).
Note that that's used only by the functions in that file; thus,
position() yes, but (I)LIKE no.
> Tom's argument seems to think it's impossible, so if you find that
> it's definitely not impossible, then you can assume he's wrong about
> that.
My point was that it seems like you'd need a separate BMH engine for
each %-separated segment of the LIKE pattern. I'm not quite clear on
whether BMH can handle '_' (single-char wildcard) conveniently by
itself, although my gut feel is that you can probably make that part
work. Maybe you can even extend the idea to embedded %, but that
seems more difficult.
Given that the fixed substrings of LIKE patterns are usually rather
short, I'm unconvinced that BMH would buy much compared to its
setup costs. But hey, prove me wrong.
(One way to amortize the setup costs could be to cache pre-built
BMH data structures keyed by the pattern strings, in a similar fashion
to what utils/adt/regexp.c does for compiled regular expressions.)
> ... Getting
> stuff committed that causes performance regressions in some cases and
> wins in other cases can be a pretty difficult and frustrating process.
> You have to remember, even if you think the slowdown is some corner
> case that only applies ~1% of the time, for some users in the real
> world, that might be 100% of their queries.
Yeah, whatever the shape of the preprocessing might be, it seems
likely that it would be a net loss in some use-cases. We do manage
to get past that --- the position() code didn't have BMH to start
with --- but it definitely requires solid evidence.
regards, tom lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients from your mail client; the link fills in
the headers below: reply via email
Some clients, webmail especially, drop In-Reply-To and References from
a link, and the reply then starts a new thread: use the mbox below.
To: pgsql-general@postgresql.org
Cc: tgl@sss.pgh.pa.us, dgrowleyml@gmail.com, martinlbuchanan@gmail.com
Subject: Re: Boyer-Moore string searching in LIKE, ILIKE, and/or POSITION?
In-Reply-To: <3811203.1675907383@sss.pgh.pa.us>
References: <CAPfd9M=kwDT2TRTRNFUcOkoFLa5FL2Dxshjqz3zBrbqQ=1agLA@mail.gmail.com> <CAApHDvqJy1Tdg8bxXWena3vbv8x0UF9skyM2jOo-LVf-qv0OJw@mail.gmail.com> <3811203.1675907383@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox