Heikki Linnakangas wrote:
> After reading the wikipedia article on Boyer-Moore search algorithm, it 
> looks to me like this patch actually implements the simpler 
> Boyer-Moore-Horspool algorithm that only uses one lookup table. That's 
> probably fine, as it ought to be faster on small needles and haystacks 
> because it requires less effort to build the lookup tables, even though 
> the worst-case performance is worse. It should still be faster than what 
> we have now.

Yes, correct, I really didn't want to slow down smaller searches. This
method seemed to fit the bill better. What I didn't realise is that this
method also had a name.

Tom Lane wrote:
> Hmm.  B-M-H has worst case search speed O(M*N) (where M = length of
> pattern, N = length of search string); whereas full B-M is O(N). Maybe we
> should build the second table when M is large? 

I'll look into this. If it pays off for longer searches I'll submit a patch.
I won't have the time until after the 15th, so perhaps that's in November's
commit fest?

> The skip table really should be constructed only once in 
> text_position_start and stored in TextPositionState. That would make a 
> big difference to the performance of those functions that call 
> text_position_next repeatedly: replace_text, split_text and text_to_array.

Of course you are right. That will help for replace and the like. I'll
update the patch tonight.

Thanks both for the feedback.


Sent via pgsql-patches mailing list (pgsql-patches@postgresql.org)
To make changes to your subscription:

Reply via email to