Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)

From: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
To: "David Rowley" <dgrowley(at)gmail(dot)com>, "'Heikki Linnakangas'" <heikki(dot)linnakangas(at)enterprisedb(dot)com>, "'Peter Eisentraut'" <peter_e(at)gmx(dot)net>, pgsql-patches(at)postgresql(dot)org
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Date: 2008-09-06 22:50:47
Message-ID: 26522.1220741447@sss.pgh.pa.us
Views: Raw Message | Whole Thread | Download mbox | Resend email
Thread:
Lists: pgsql-hackers pgsql-patches

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

In response to

Responses

Browse pgsql-hackers by date

  From Date Subject
Next Message David Rowley 2008-09-06 23:25:07 Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Previous Message Tom Lane 2008-09-06 22:45:33 Re: reducing statistics write overhead

Browse pgsql-patches by date

  From Date Subject
Next Message Jaime Casanova 2008-09-06 23:10:25 Re: [PgFoundry] Unsigned Data Types [1 of 2]
Previous Message Tom Lane 2008-09-06 22:21:01 Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)