To: "David Rowley" <dgrowley@gmail.com>,
	"'Heikki Linnakangas'" <heikki.linnakangas@enterprisedb.com>,
	"'Peter Eisentraut'" <peter_e@gmx.net>, pgsql-patches@postgresql.org
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time
	hacker)
In-reply-to: <26072.1220739661@sss.pgh.pa.us> 
References: <C848A7ECB1E346388B9BD7F7966C0DDC@amd64>
	<26072.1220739661@sss.pgh.pa.us>
Comments: In-reply-to Tom Lane <tgl@sss.pgh.pa.us>
	message dated "Sat, 06 Sep 2008 18:21:01 -0400"
Date: Sat, 06 Sep 2008 18:50:47 -0400
Message-ID: <26522.1220741447@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

I wrote:
> I looked this over a bit and was immediately confused by one thing:
> the introductory comment says that the skip table size ought to be based
> on the length of the haystack, which makes sense to me, but the code is
> actually initializing it on the basis of len2, ie, the length of the
> needle.  Isn't that a bug?  Was the same bug present in the tests you
> made to determine the best table sizes?

BTW, to the extent that you feel like testing a different idea,
I would suggest:

* don't bother initializing the skiptable when len1 < len2

* otherwise, choose its size based on len1 - len2, not just len1 or
len2.  This is (one less than) the maximum number of search loop
consultations of the skip table that can happen, so it seems like a
plausible number, and better than either length alone.

			regards, tom lane