Re: GiST index performance

Was this corrected? I don't see any commits to seg.c.

---------------------------------------------------------------------------

Matthew Wakeling wrote:
> On Thu, 7 May 2009, Oleg Bartunov wrote:
> > Did you try Guttman quadratic split algorithm ? We also found linear
> > split algorithm for Rtree.
>
> The existing (bugfixed) seg split algorithm is the Guttman quadratic split
> algorithm. Guttman did all his work on two-dimensional and above data,
> dismissing one-dimensional data as being handled adequately by B-trees,
> which is not true for segment overlaps. It turns out that the algorithm
> has a weakness with certain types of data, and one-dimensional data is
> almost certain to exercise that weakness. The greater the number of
> dimensions, the less the weakness is exercised.
>
> The problem is that the algorithm does not calculate a split pivot.
> Instead it finds two suitable entries, and adds the remaining entries to
> those two in turn. This can lead to the majority of the entries being
> added to just one side. In fact, I saw lots of cases where 367 entries
> were being split into two pages of 366 and one entry.
>
> Guttman's linear split algorithm has the same weakness.
>
> >> One thing I am seeing is a really big difference in performance between
> >> Postgres/GiST and a Java implementation I have written, using the same
> >> algorithms. Postgres takes three minutes to perform a set of index lookups
> >> while java takes six seconds. The old version of bioseg took an hour. I
> >> can't see anything in the GiST support code that could account for this.
> >
> > is the number of index lookups different, or just index lookup time is very
> > big ?
>
> Same number of index lookups. Same algorithms. I have a set of 681879
> segments, and I load them all into the index. I then query the index for
> overlaps for each one in turn. For some reason, GiST lookups seem to be
> slow, even if they are using a good algorithm. I have seen that problem
> with btree_gist on integers too. I can't see any reason for this is the
> GiST code - it all seems pretty tight to me. We probably need to do some
> profiling.
>
> Matthew
>
> --
> I suppose some of you have done a Continuous Maths course. Yes? Continuous
> Maths? <menacing stares from audience> Whoah, it was like that, was it!
> -- Computer Science Lecturer
>
> --
> Sent via pgsql-performance mailing list (pgsql-performance(at)postgresql(dot)org)
> To make changes to your subscription:
> http://www.postgresql.org/mailpref/pgsql-performance

--
Bruce Momjian <bruce(at)momjian(dot)us> http://momjian.us
EnterpriseDB http://enterprisedb.com
PG East: http://www.enterprisedb.com/community/nav-pg-east-2010.do
+ If your life is a hard drive, Christ can be your backup. +