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

strpos() && KMP

From: Pavel Ajtkulov <ajtkulov(at)acm(dot)org>
To: pgsql-patches(at)postgresql(dot)org
Subject: strpos() && KMP
Date: 2007-08-01 20:18:22
Message-ID: 1167412014.20070802011822@acm.org (view raw or flat)
Thread:
Lists: pgsql-patches
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
ajtkulov(at)acm(dot)org

P. S. Sorry for prime English.

Attachment: varlena.c.patch
Description: application/octet-stream (5.4 KB)

Responses

pgsql-patches by date

Next:From: Andrew DunstanDate: 2007-08-01 22:41:31
Subject: Re: strpos() && KMP
Previous:From: Heikki LinnakangasDate: 2007-08-01 20:09:06
Subject: Re: HOT patch - version 11

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