Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)

Tom Lane wrote:
> "David Rowley" <dgrowley(at)gmail(dot)com> writes:
>> Tom Lane wrote:
>>> Hmm. B-M-H has worst case search speed O(M*N) (where M = length of
>>> pattern, N = length of search string); whereas full B-M is O(N). Maybe we
>>> should build the second table when M is large?
>
>> I'll look into this. If it pays off for longer searches I'll submit a patch.
>> I won't have the time until after the 15th, so perhaps that's in November's
>> commit fest?
>
> Yes. Let's get B-M-H in during this fest and then you can look into
> whether a follow-on patch is worthwhile.

Agreed.

Also, it would be nice to use B-M(-H) for LIKE as well. That's a
different codepath, but probably more widely used than textpos and
frients. I haven't looked how feasible it would be to do, though.

--
Heikki Linnakangas
EnterpriseDB http://www.enterprisedb.com