X-Original-To: pgsql-performance-postgresql.org@localhost.postgresql.org Received: from localhost (av.hub.org [200.46.204.144]) by postgresql.org (Postfix) with ESMTP id BBC2A9DC8DC for ; Fri, 20 Jan 2006 18:33:37 -0400 (AST) Received: from postgresql.org ([200.46.204.71]) by localhost (av.hub.org [200.46.204.144]) (amavisd-new, port 10024) with ESMTP id 94850-04 for ; Fri, 20 Jan 2006 18:33:35 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- Received: from svana.org (svana.org [125.62.94.225]) by postgresql.org (Postfix) with ESMTP id D21079DC83F for ; Fri, 20 Jan 2006 18:33:31 -0400 (AST) Received: from kleptog by svana.org with local (Exim 4.50) id 1F04ox-0001IC-JW; Sat, 21 Jan 2006 09:33:27 +1100 Date: Fri, 20 Jan 2006 23:33:27 +0100 From: Martijn van Oosterhout To: Tom Lane Cc: Stephan Vollmer , pgsql-performance@postgreSQL.org Subject: Re: [GENERAL] Creation of tsearch2 index is very slow Message-ID: <20060120223327.GH31908@svana.org> Reply-To: Martijn van Oosterhout References: <43D0ED57.1020608@gmx.de> <17454.1137771321@sss.pgh.pa.us> <20060120170452.GC31908@svana.org> <26153.1137784469@sss.pgh.pa.us> <20060120201036.GE31908@svana.org> <26583.1137788505@sss.pgh.pa.us> <20060120205132.GF31908@svana.org> <26958.1137791955@sss.pgh.pa.us> <20060120213754.GG31908@svana.org> <27264.1137793817@sss.pgh.pa.us> Mime-Version: 1.0 Content-Type: multipart/signed; micalg=pgp-sha1; protocol="application/pgp-signature"; boundary="Cp3Cp8fzgozWLBWL" Content-Disposition: inline In-Reply-To: <27264.1137793817@sss.pgh.pa.us> X-PGP-Key-ID: Length=1024; ID=0x0DC67BE6 X-PGP-Key-Fingerprint: 295F A899 A81A 156D B522 48A7 6394 F08A 0DC6 7BE6 X-PGP-Key-URL: User-Agent: Mutt/1.5.9i X-SA-Exim-Connect-IP: X-SA-Exim-Mail-From: kleptog@svana.org X-SA-Exim-Scanned: No (on svana.org); SAEximRunCond expanded to false X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.129 required=5 tests=[AWL=0.129] X-Spam-Score: 0.129 X-Spam-Level: X-Archive-Number: 200601/371 X-Sequence-Number: 16849 --Cp3Cp8fzgozWLBWL Content-Type: text/plain; charset=us-ascii Content-Disposition: inline Content-Transfer-Encoding: quoted-printable On Fri, Jan 20, 2006 at 04:50:17PM -0500, Tom Lane wrote: > (hemdistcache calls hemdistsign --- I think gprof is doing something > funny with tail-calls here, and showing hemdistsign as directly called > from gtsvector_picksplit when control really arrives through hemdistcache= =2E) It may be the compiler. All these functions are declared static, which gives the compiler quite a bit of leeway to rearrange code. > The bulk of the problem is clearly in this loop, which performs O(N^2) > comparisons to find the two entries that are furthest apart in hemdist > terms: Ah. A while ago someone came onto the list asking about bit strings indexing[1]. If I'd known tsearch worked like this I would have pointed him to it. Anyway, before he went off to implement it he mentioned "Jarvis-Patrick clustering", whatever that means. Probably more relevent was this thread[2] on -hackers a while back with pseudo-code[3]. How well it works, I don't know, it worked for him evidently, he went away happy... [1] http://archives.postgresql.org/pgsql-general/2005-11/msg00473.php [2] http://archives.postgresql.org/pgsql-hackers/2005-11/msg01067.php [3] http://archives.postgresql.org/pgsql-hackers/2005-11/msg01069.php Hope this helps, --=20 Martijn van Oosterhout http://svana.org/kleptog/ > Patent. n. Genius is 5% inspiration and 95% perspiration. A patent is a > tool for doing 5% of the work and then sitting around waiting for someone > else to do the other 95% so you can sue them. --Cp3Cp8fzgozWLBWL Content-Type: application/pgp-signature; name="signature.asc" Content-Description: Digital signature Content-Disposition: inline -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.1 (GNU/Linux) iD8DBQFD0WU3IB7bNG8LQkwRAuqPAJ973X2/QA/RDPXGVMcHrSyCrq0jwQCfVBBi LozfKSrqRx8SH43mKimWeeQ= =eVLE -----END PGP SIGNATURE----- --Cp3Cp8fzgozWLBWL--