Skip site navigation (1) Skip section navigation (2)

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

From: "David Rowley" <dgrowley(at)gmail(dot)com>
To: "'Heikki Linnakangas'" <heikki(dot)linnakangas(at)enterprisedb(dot)com>,"'Tom Lane'" <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: "'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-08 19:19:35
Message-ID: 0D0F8DC5EE1341A199B5BDA73F870BA7@amd64 (view raw or flat)
Thread:
Lists: pgsql-hackerspgsql-patches
Heikki Linnakangas Wrote:
> Tom Lane wrote:
> > Heikki Linnakangas <heikki(dot)linnakangas(at)enterprisedb(dot)com> writes:
> >> Also, it would be nice to use B-M(-H) for LIKE as well.
> > 
> > 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 
> '%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.



In response to

pgsql-hackers by date

Next:From: Tom LaneDate: 2008-09-08 19:38:52
Subject: A few thoughts on the plan inval extension patch
Previous:From: David RowleyDate: 2008-09-08 19:15:02
Subject: Re: [PATCHES] TODO item: Implement Boyer-Moore searching (First time hacker)

pgsql-patches by date

Next:From: Ryan BradetichDate: 2008-09-09 03:08:12
Subject: Re: [PgFoundry] Unsigned Data Types [1 of 2]
Previous:From: David RowleyDate: 2008-09-08 19:15:02
Subject: Re: [PATCHES] TODO item: Implement Boyer-Moore searching (First time hacker)

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group