Added to TODO: > * Implement Boyer-Moore searching in strpos() > > http://archives.postgresql.org/pgsql-patches/2007-08/msg00012.php
--------------------------------------------------------------------------- Pavel Ajtkulov wrote: > Hello, > > 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 strings) > 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 > [EMAIL PROTECTED] > > P. S. Sorry for prime English. [ Attachment, skipping... ] > > ---------------------------(end of broadcast)--------------------------- > TIP 5: don't forget to increase your free space map settings -- Bruce Momjian <[EMAIL PROTECTED]> http://momjian.us EnterpriseDB http://www.enterprisedb.com + If your life is a hard drive, Christ can be your backup. + ---------------------------(end of broadcast)--------------------------- TIP 1: if posting/reading through Usenet, please send an appropriate subscribe-nomail command to [EMAIL PROTECTED] so that your message can get through to the mailing list cleanly
