From: Tom Lane <tgl@sss.pgh.pa.us>
To: David Rowley <dgrowley@gmail.com>
Cc: 'Heikki Linnakangas' <heikki.linnakangas@enterprisedb.com>
Cc: 'Peter Eisentraut' <peter_e@gmx.net>
Cc: pgsql-patches@postgresql.org
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Date: Fri, 05 Sep 2008 13:12:17 -0400
Message-ID: <27136.1220634737@sss.pgh.pa.us> (raw)
In-Reply-To: <2F2A1443F6064162BECA6BB37625222E@amd64>
References: <2F2A1443F6064162BECA6BB37625222E@amd64>
"David Rowley" <dgrowley@gmail.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.
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 using the --to and --cc options:
reply via email
To: pgsql-patches@postgresql.org
Cc: tgl@sss.pgh.pa.us, dgrowley@gmail.com, heikki.linnakangas@enterprisedb.com, peter_e@gmx.net
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
In-Reply-To: <27136.1220634737@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