pg.ddx.io  pgsql-patches@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: David Rowley <dgrowley@gmail.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 20:25:56 +0300
Message-ID: <48C16BA4.2060407@enterprisedb.com> (raw)
In-Reply-To: <27136.1220634737@sss.pgh.pa.us>
References: <2F2A1443F6064162BECA6BB37625222E@amd64>
	<27136.1220634737@sss.pgh.pa.us>

Tom Lane wrote:
> "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.

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



view thread (21+ messages)  latest in thread

Message-ID: <48C16BA4.2060407@enterprisedb.com>
Permalink:  ../48C16BA4.2060407@enterprisedb.com/
Also on:    postgresql.org/message-id/48C16BA4.2060407@enterprisedb.com

 · 

reply
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: heikki.linnakangas@enterprisedb.com, tgl@sss.pgh.pa.us, dgrowley@gmail.com, peter_e@gmx.net
  Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
  In-Reply-To: <48C16BA4.2060407@enterprisedb.com>

* 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