Received: from localhost (unknown [200.46.204.183]) by postgresql.org (Postfix) with ESMTP id 6EFB564FCDD for ; Fri, 5 Sep 2008 14:12:57 -0300 (ADT) Received: from postgresql.org ([200.46.204.86]) by localhost (mx1.hub.org [200.46.204.183]) (amavisd-maia, port 10024) with ESMTP id 88937-04 for ; Fri, 5 Sep 2008 14:12:52 -0300 (ADT) X-Greylist: from auto-whitelisted by SQLgrey-1.7.6 Received: from sss.pgh.pa.us (sss.pgh.pa.us [66.207.139.130]) by postgresql.org (Postfix) with ESMTP id 6995564FCBA for ; Fri, 5 Sep 2008 14:12:52 -0300 (ADT) Received: from sss2.sss.pgh.pa.us (tgl@localhost [127.0.0.1]) by sss.pgh.pa.us (8.14.2/8.14.2) with ESMTP id m85HCHMA027137; Fri, 5 Sep 2008 13:12:17 -0400 (EDT) To: "David Rowley" cc: "'Heikki Linnakangas'" , "'Peter Eisentraut'" , pgsql-patches@postgresql.org Subject: Re: [HACKERS] TODO item: Implement Boyer-Moore searching (First time hacker) In-reply-to: <2F2A1443F6064162BECA6BB37625222E@amd64> References: <2F2A1443F6064162BECA6BB37625222E@amd64> Comments: In-reply-to "David Rowley" message dated "Fri, 05 Sep 2008 18:02:54 +0100" Date: Fri, 05 Sep 2008 13:12:17 -0400 Message-ID: <27136.1220634737@sss.pgh.pa.us> From: Tom Lane X-Virus-Scanned: Maia Mailguard 1.0.1 X-Spam-Status: No, hits=0 tagged_above=0 required=5 tests=none X-Spam-Level: X-Archive-Number: 200809/57 X-Sequence-Number: 7072 "David Rowley" writes: > 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? Yes. Let's get B-M-H in during this fest and then you can look into whether a follow-on patch is worthwhile. regards, tom lane