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 522AD9DC802
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Sat, 21 Jan 2006 09:08:39 -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 61297-01
	for <pgsql-performance-postgresql.org@localhost.postgresql.org>;
	Sat, 21 Jan 2006 09:08:39 -0400 (AST)
X-Greylist: from auto-whitelisted by SQLgrey-
Received: from svana.org (unknown [125.62.94.225])
	by postgresql.org (Postfix) with ESMTP id 06E949DC800
	for <pgsql-performance@postgreSQL.org>;
	Sat, 21 Jan 2006 09:08:33 -0400 (AST)
Received: from kleptog by svana.org with local (Exim 4.50)
	id 1F0ITm-0002jM-RP; Sun, 22 Jan 2006 00:08:30 +1100
Date: Sat, 21 Jan 2006 14:08:30 +0100
From: Martijn van Oosterhout <kleptog@svana.org>
To: Tom Lane <tgl@sss.pgh.pa.us>
Cc: Ron <rjpeace@earthlink.net>, pgsql-performance@postgreSQL.org
Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
Message-ID: <20060121130830.GA9955@svana.org>
Reply-To: Martijn van Oosterhout <kleptog@svana.org>
References: <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>
	<7.0.1.0.2.20060120174141.039b03e8@earthlink.net>
	<6111.1137797436@sss.pgh.pa.us>
Mime-Version: 1.0
Content-Type: multipart/signed; micalg=pgp-sha1;
	protocol="application/pgp-signature"; boundary="oyUTqETQ0mS9luUI"
Content-Disposition: inline
In-Reply-To: <6111.1137797436@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: <http://svana.org/kleptog/0DC67BE6.pgp.asc>
User-Agent: Mutt/1.5.9i
X-SA-Exim-Connect-IP: <locally generated>
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/386
X-Sequence-Number: 16864


--oyUTqETQ0mS9luUI
Content-Type: text/plain; charset=us-ascii
Content-Disposition: inline
Content-Transfer-Encoding: quoted-printable

On Fri, Jan 20, 2006 at 05:50:36PM -0500, Tom Lane wrote:
> Yeah, but fetching from a small constant table is pretty quick too;
> I doubt it's worth getting involved in machine-specific assembly code
> for this.  I'm much more interested in the idea of improving the
> furthest-distance algorithm in gtsvector_picksplit --- if we can do
> that, it'll probably drop the distance calculation down to the point
> where it's not really worth the trouble to assembly-code it.

I've played with another algorithm. Very simple but it's only O(N). It
doesn't get the longest distance but it does get close. Basically you
take the first two elements as your starting length. Then you loop over
each remaining string, each time finding the longest pair out of each
set of three.

I've only tried it on random strings. The maximum distance for 128
random strings tends to be around 291-295. This algorithm tends to find
lengths around 280. Pseudo code below (in Perl).

However, IMHO, this algorithm is optimising the wrong thing. It
shouldn't be trying to split into sets that are far apart, it should be
trying to split into sets that minimize the number of set bits (ie
distance from zero), since that's what's will speed up searching.
That's harder though (this algorithm does approximate it sort of)
and I havn't come up with an algorithm yet

sub MaxDistFast
{
  my $strings =3D shift;
=20
  my $m1 =3D 0;
  my $m2 =3D 1;
  my $dist =3D -1;

  for my $i (2..$#$strings)
  {
    my $d1 =3D HammDist( $strings->[$i], $strings->[$m1] );
    my $d2 =3D HammDist( $strings->[$i], $strings->[$m2] );

    my $m =3D ($d1 > $d2) ? $m1 : $m2;
    my $d =3D ($d1 > $d2) ? $d1 : $d2;
   =20
    if( $d > $dist )
    {
      $dist =3D $d;
      $m1 =3D $i; =20
      $m2 =3D $m;
    }
  }
  return($m1,$m2,$dist);
}

Full program available at:
http://svana.org/kleptog/temp/picksplit.pl

Have a nice day,
--=20
Martijn van Oosterhout   <kleptog@svana.org>   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.

--oyUTqETQ0mS9luUI
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)

iD8DBQFD0jJOIB7bNG8LQkwRAjCFAJ9SxIKwvMZr7myOsxl3mZ53qzT3egCggNhI
Kejd3P2V+Ija5mieo6q0Vxw=
=zvLw
-----END PGP SIGNATURE-----

--oyUTqETQ0mS9luUI--