From: Tom Lane <tgl@sss.pgh.pa.us>
To: Heikki Linnakangas <heikki.linnakangas@enterprisedb.com>
Cc: David Rowley <dgrowley@gmail.com>
Cc: 'Peter Eisentraut' <peter_e@gmx.net>
Cc: pgsql-patches@postgresql.org
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
Date: Thu, 04 Sep 2008 22:04:57 -0400
Message-ID: <11787.1220580297@sss.pgh.pa.us> (raw)
In-Reply-To: <48C061B3.1090709@enterprisedb.com>
References: <CC00B041B12F40749EE43D49D99A705D@amd64>
<48C061B3.1090709@enterprisedb.com>
Heikki Linnakangas <heikki.linnakangas@enterprisedb.com> writes:
> 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.
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? Although
realistically that is probably gilding the lily, since frankly there
haven't been many real-world complaints about the speed of these
functions anyway ...
> 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.
+1. The heuristic about big a skip table to make may need some
adjustment as well, since it seems to be considering only a single
search.
regards, tom lane
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Reply to all the recipients using the --to and --cc options:
reply via email
To: pgsql-patches@postgresql.org
Cc: tgl@sss.pgh.pa.us, heikki.linnakangas@enterprisedb.com, dgrowley@gmail.com, peter_e@gmx.net
Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker)
In-Reply-To: <11787.1220580297@sss.pgh.pa.us>
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
This inbox is served by DDX for PostgreSQL; see mirroring instructions
for how to clone and mirror all data and code used for this inbox