To: "Dolafi, Tom" <dolafit@janelia.hhmi.org>
cc: pgsql-performance@postgresql.org, Oleg Bartunov <oleg@sai.msu.su>,
	Teodor Sigaev <teodor@sigaev.ru>
Subject: Re: rtree/gist index taking enormous amount of space in 8.2.3 
In-reply-to: <AE9860225100F14D87B26D0D4D6766DB46F3E7@EXCHANGE03.janelia.priv> 
References: <AE9860225100F14D87B26D0D4D6766DB46F246@EXCHANGE03.janelia.priv>
	<13616.1183046917@sss.pgh.pa.us>
	<AE9860225100F14D87B26D0D4D6766DB46F3E7@EXCHANGE03.janelia.priv>
Comments: In-reply-to "Dolafi, Tom" <dolafit@janelia.hhmi.org>
	message dated "Fri, 29 Jun 2007 09:51:19 -0400"
Date: Fri, 29 Jun 2007 13:57:44 -0400
Message-ID: <6410.1183139864@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

"Dolafi, Tom" <dolafit@janelia.hhmi.org> writes:
> min(fmin) |   max(fmin)    |    avg(fmin)      
>    1      |   55296469     |    11423945     
> min(fmax) |   max(fmax)    |    avg(fmax)
>   18      |   55553288     |    11424491

OK, I was able to reproduce a problem after making the further guess
that fmax is usually a little bit greater than fmin.  The attached test
script generates an rtree index of around 800 pages on 8.1.9, and the
index build time is about 6 seconds on my machine.  On CVS HEAD, the
script generates a gist index of over 30000 pages and the build time is
over 60 seconds.  Since I'm using random() the numbers move around a
bit, but they're consistently awful.  I experimented with a few other
distributions, such as fmin and fmax chosen independently in the same
range, and saw gist build time usually better than rtree and index size
only somewhat larger, so this particular distribution apparently fools
gist_box_picksplit rather badly.  The problem seems nonlinear too ---
I had originally tried it with 1 million test rows instead of 100000,
and gave up waiting for the index build after more than an hour.

Oleg, Teodor, can this be improved?

			regards, tom lane

drop table featureloc;

CREATE TABLE featureloc
(
  fmin integer,
  fmax integer
);

insert into featureloc
  select r1, r1 + 1 + random() * 1000 from
  (select 1 + random() * 55000000 as r1, 1 + random() * 55000000 as r2
   from generate_series(1,100000) offset 0) as ss;

CREATE OR REPLACE FUNCTION boxrange(integer, integer)
  RETURNS box AS
    'SELECT box (point(0, $1), point($2, 500000000))'
  LANGUAGE 'sql' STRICT IMMUTABLE;

CREATE INDEX binloc_boxrange
  ON featureloc
  USING rtree
  (boxrange(fmin, fmax));

vacuum verbose featureloc;