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 DAA969DCBBD for ; Fri, 20 Jan 2006 21:34:51 -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 28041-04 for ; Fri, 20 Jan 2006 21:34:53 -0400 (AST) X-Greylist: from auto-whitelisted by SQLgrey- Received: from moonunit2.moonview.localnet (wsip-68-15-5-150.sd.sd.cox.net [68.15.5.150]) by postgresql.org (Postfix) with ESMTP id 1BC749DCBB4 for ; Fri, 20 Jan 2006 21:34:47 -0400 (AST) Received: from [192.168.0.3] (moonunit3.moonview.localnet [192.168.0.3]) by moonunit2.moonview.localnet (8.13.1/8.13.1) with ESMTP id k0L0ZQlO026292; Fri, 20 Jan 2006 16:35:26 -0800 Message-ID: <43D18EA9.8060409@modgraph-usa.com> Date: Fri, 20 Jan 2006 17:30:17 -0800 From: "Craig A. James" User-Agent: Mozilla Thunderbird 1.0.6 (X11/20050716) X-Accept-Language: en-us, en MIME-Version: 1.0 To: Tom Lane CC: "Steinar H. Gunderson" , pgsql-performance@postgresql.org, Teodor Sigaev , Oleg Bartunov Subject: Re: [GENERAL] Creation of tsearch2 index is very slow References: <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> <7.0.1.0.2.20060120174141.039b03e8@earthlink.net> <6111.1137797436@sss.pgh.pa.us> <20060120225751.GA27230@uio.no> <6532.1137801157@sss.pgh.pa.us> <20060121000519.GA29755@uio.no> <6743.1137802990@sss.pgh.pa.us> In-Reply-To: <6743.1137802990@sss.pgh.pa.us> Content-Type: text/plain; charset=ISO-8859-1; format=flowed Content-Transfer-Encoding: 7bit X-Virus-Scanned: by amavisd-new at hub.org X-Spam-Status: No, score=0.053 required=5 tests=[AWL=0.053] X-Spam-Score: 0.053 X-Spam-Level: X-Archive-Number: 200601/383 X-Sequence-Number: 16861 Tom Lane wrote: > Well, we're trying to split an index page that's gotten full into two > index pages, preferably with approximately equal numbers of items in > each new page (this isn't a hard requirement though). ... If that's > correct, what you really want is to divide the values so that the unions > of the two sets have minimal overlap ... which seems to me to have > little to do with what the code does at present. This problem has been studied extensively by chemists, and they haven't found any easy solutions. The Jarvis Patrick clustering algorithm might give you hints about a fast approach. In theory it's K*O(N^2), but J-P is preferred for large datasets (millions of molecules) because the coefficient K can be made quite low. It starts with a "similarity metric" for two bit strings, the Tanimoto or Tversky coefficients: http://www.daylight.com/dayhtml/doc/theory/theory.finger.html#RTFToC83 J-P Clustering is described here: http://www.daylight.com/dayhtml/doc/cluster/cluster.a.html#cl33 J-P Clustering is probably not the best for this problem (see the illustrations in the link above to see why), but the general idea of computing N-nearest-neighbors, followed by a partitioning step, could be what's needed. Craig