Skip site navigation (1) Skip section navigation (2)

Re: [GENERAL] Creation of tsearch2 index is very slow

From: Martijn van Oosterhout <kleptog(at)svana(dot)org>
To: Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>
Cc: Ron <rjpeace(at)earthlink(dot)net>, pgsql-performance(at)postgreSQL(dot)org
Subject: Re: [GENERAL] Creation of tsearch2 index is very slow
Date: 2006-01-21 13:08:30
Message-ID: 20060121130830.GA9955@svana.org (view raw or flat)
Thread:
Lists: pgsql-generalpgsql-performance
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 = shift;
 
  my $m1 = 0;
  my $m2 = 1;
  my $dist = -1;

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

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

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

Have a nice day,
-- 
Martijn van Oosterhout   <kleptog(at)svana(dot)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.

In response to

Responses

pgsql-performance by date

Next:From: K C LauDate: 2006-01-21 13:12:47
Subject: Re: SELECT MIN, MAX took longer time than SELECT
Previous:From: RonDate: 2006-01-21 12:22:32
Subject: Re: [GENERAL] Creation of tsearch2 index is very

pgsql-general by date

Next:From: Sander SteffannDate: 2006-01-21 13:09:54
Subject: Re: RAID 5 and postgresql
Previous:From: Gregory S. WilliamsonDate: 2006-01-21 12:48:51
Subject: Re: Is there a way to list running queries

Privacy Policy | About PostgreSQL
Copyright © 1996-2014 The PostgreSQL Global Development Group