DomainKey-Signature: a=rsa-sha1; c=nofws; d=gmail.com; s=gamma;
	h=from:to:cc:subject:date:message-id:mime-version:content-type
	:content-transfer-encoding:x-priority:x-msmail-priority:x-mailer
	:in-reply-to:x-mimeole:thread-index:importance;
	b=QOIqpUekrUzPpTBYAEPApXKi4Xc4Ww4teqUjGVV22a0Bv7SwdmMOku9PSYmGwLpZAE
	YVv1Avhaa4SU3xmehvzetCAGwolNWZguX1XZyUyHiobqYYpZUxipNoPSDmB0k3+CAKfi
	mk3R58JmnMNbYCJ7b43loSeHwJE2LIIqYODMg=
From: "David Rowley" <dgrowley@gmail.com>
To: "'Heikki Linnakangas'" <heikki.linnakangas@enterprisedb.com>,
	"Tom Lane" <tgl@sss.pgh.pa.us>
Cc: "'Peter Eisentraut'" <peter_e@gmx.net>,
	<pgsql-patches@postgresql.org>
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time
	hacker)
Date: Fri, 5 Sep 2008 18:02:54 +0100
Message-ID: <2F2A1443F6064162BECA6BB37625222E@amd64>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="US-ASCII"
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <48C061B3.1090709@enterprisedb.com>
Thread-Index: AckO3fNYIqcphxeAQgOqBWN3LNRf/gAmPtcg
Importance: Normal

Heikki Linnakangas wrote:
> After reading the wikipedia article on Boyer-Moore search algorithm, =
it=20
> looks to me like this patch actually implements the simpler=20
> Boyer-Moore-Horspool algorithm that only uses one lookup table. That's =

> probably fine, as it ought to be faster on small needles and haystacks =

> because it requires less effort to build the lookup tables, even =
though=20
> the worst-case performance is worse. It should still be faster than =
what=20
> we have now.

Yes, correct, I really didn't want to slow down smaller searches. This
method seemed to fit the bill better. What I didn't realise is that this
method also had a name.

Tom Lane wrote:
> Hmm.  B-M-H has worst case search speed O(M*N) (where M =3D length of
> pattern, N =3D length of search string); whereas full B-M is O(N). =
Maybe we
> should build the second table when M is large?=20

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?

> The skip table really should be constructed only once in=20
> text_position_start and stored in TextPositionState. That would make a =

> big difference to the performance of those functions that call=20
> text_position_next repeatedly: replace_text, split_text and =
text_to_array.

Of course you are right. That will help for replace and the like. I'll
update the patch tonight.

Thanks both for the feedback.

David.