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:importance:thread-index;
	b=GdSEmdAAJ8Xi/ERD6MqDLUF2cU3WOFQGnL7RLaYJqfytQwrbGAMN7D5XaWE/nhtlyA
	kEziOwzTohMsbaiQIPUsb8GBjUQbLGRKbL32cmE6ecvMy75jzJzBvP1jLSGnPvBJrJKz
	rsEWwiYOPaPJTYPYW6Y8S8DFLGWnGH+1cTr+Y=
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: Mon, 8 Sep 2008 20:19:35 +0100
Message-ID: <0D0F8DC5EE1341A199B5BDA73F870BA7@amd64>
MIME-Version: 1.0
Content-Type: text/plain;
	charset="us-ascii"
Content-Transfer-Encoding: quoted-printable
In-Reply-To: <48C4C9FE.20905@enterprisedb.com>
Importance: Normal
Thread-Index: AckRfnaYUWsvDf3dRe+w8CrtX6WyPQAaMKgg

Heikki Linnakangas Wrote:
> Tom Lane wrote:
> > Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:
> >> Also, it would be nice to use B-M(-H) for LIKE as well.
> >=20
> > Right offhand, that seems impossible, at least in patterns with %.
> > Or were you thinking of trying to separate out the fixed substrings
> > of a pattern and search for them with BMH?

> Yep, something like that. Even if it only handled the special case of=20
> '%foobar%', that would be nice, because that's a pretty common special =

> case.

It would be a quick test to check for % at either end. But we'd also =
need to
ensure there were none in the middle. That might slow it down. I guess =
while
looping over the inner chars checking for more %'s we could be building =
a
skiptable. We'd have to abort it if we found any %'s of course

I think with out giving it much thought _'s could be handled by BMH, =
these
could just be given a skip distance of 2. Only having a lossy skip table
throws that out the window without having a special check for _

David.