Re: text_position worst case runtime - Mailing list pgsql-hackers

From Hannu Krosing
Subject Re: text_position worst case runtime
Date
Msg-id 1148078951.3833.71.camel@localhost.localdomain
Whole thread Raw
In response to Re: text_position worst case runtime  (Hannu Krosing <hannu@skype.net>)
List pgsql-hackers
Ühel kenal päeval, L, 2006-05-20 kell 01:34, kirjutas Hannu Krosing:
> Ühel kenal päeval, R, 2006-05-19 kell 18:18, kirjutas Tom Lane:
> > Hannu Krosing <hannu@skype.net> writes:
> > > I guess our regex implementation already uses boyer-moore or similar.
> > > Why not just expose the match position of substring('text' in 'regex')
> > > using some function, called  match_position(int searched_text, int
> > > regex, int matchnum) ?
> > 
> > If it did that might be a nice solution, but I'm not sure that it does
> > use B-M ... I can't find either "Boyer" or "Moore" in its source code.
> 
> Ok, maybe it is not optimised for finding longish strings inside even
> longers trings.
> 
> I had a (false ?) memory that we used some variant of pcre, and that
> pcre uses BM. I may be false on both  accounts. (I know that python
> borrowed its re module from pcre).

http://www.mcabee.org/lists/snort-users/Mar-05/msg00026.html

seems to imply that PCRE uses BM at least for some case, so I might not
have been wrong in case 2 :)


> > There's no particular reason to suppose offhand that a regex engine
> > would be faster than the naive code for fixed patterns.
> 
> if naive code is O(n*m), then starting from some values of n and m it is
> probably faster if it is based on somewhat optimised regex engine, the
> question is, what is the threasold and dataset for fasterness 
> 
-- 
----------------
Hannu Krosing
Database Architect
Skype Technologies OÜ
Akadeemia tee 21 F, Tallinn, 12618, Estonia

Skype me:  callto:hkrosing
Get Skype for free:  http://www.skype.com




pgsql-hackers by date:

Previous
From: "Greg Sabino Mullane"
Date:
Subject: Re: String Similarity
Next
From: Bruce Momjian
Date:
Subject: Re: [OT] MySQL is bad, but THIS bad?