pg.ddx.io  pgsql-performance@postgresql.org mailing list archive  

help / color / mirror / Atom feed
From: Craig A. James <cjames@modgraph-usa.com>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Steinar H. Gunderson <sgunderson@bigfoot.com>
Cc: pgsql-performance@postgresql.org, Teodor Sigaev <teodor@sigaev.ru>
Cc: Oleg Bartunov <oleg@sai.msu.su>
Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
Date: Fri, 20 Jan 2006 17:30:17 -0800
Message-ID: <43D18EA9.8060409@modgraph-usa.com> (raw)
In-Reply-To: <6743.1137802990@sss.pgh.pa.us>
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>

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



view thread (38+ messages)  latest in thread

Message-ID: <43D18EA9.8060409@modgraph-usa.com>
Permalink:  ../43D18EA9.8060409@modgraph-usa.com/
Also on:    postgresql.org/message-id/43D18EA9.8060409@modgraph-usa.com

 · 

reply
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-performance@postgresql.org
  Cc: cjames@modgraph-usa.com, tgl@sss.pgh.pa.us, sgunderson@bigfoot.com, teodor@sigaev.ru, oleg@sai.msu.su
  Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
  In-Reply-To: <43D18EA9.8060409@modgraph-usa.com>

* 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