this patch allow to use Knuth-Morrison-Pratt algorithm for strpos() function 
(see Cormen et al. Introduction to Algorithms, MIT Press, 2001).

It also works with multibyte wchar.

In worst case current brute force strpos() takes O(n * m) (n && m is length of 
time (example: 'aaa...aaab' search in 'aaa...aaa').
KMP algo always takes O(n + m) time. 
To check this someone need to create a table with one text attribute, and 
insert several thousands
record 'aa..aa'(for example, with lenght = 1000) . After execute "select 
count(*) from test where 
strpos(a, 'aaa....aab') > 0;" on current and modified version.

Also, I advise to use "select .. where strpos(att, 'word') > 0;" instead 
"select .. where attr like '%word%'"
(strpos must be faster than regex).

In general, this belongs to artificial expressions. In natural language KMP is 
equal (execution time)
current strpos() nearly.

Ajtkulov Pavel

P. S. Sorry for prime English.

Attachment: varlena.c.patch
Description: Binary data

---------------------------(end of broadcast)---------------------------
TIP 5: don't forget to increase your free space map settings

Reply via email to