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

Re: GiST index performance

From: Bruce Momjian <bruce(at)momjian(dot)us>
To: Matthew Wakeling <matthew(at)flymine(dot)org>
Cc: Oleg Bartunov <oleg(at)sai(dot)msu(dot)su>, Tom Lane <tgl(at)sss(dot)pgh(dot)pa(dot)us>, Teodor Sigaev <teodor(at)sigaev(dot)ru>, Kevin Grittner <Kevin(dot)Grittner(at)wicourts(dot)gov>, pgsql-performance(at)postgresql(dot)org
Subject: Re: GiST index performance
Date: 2010-02-25 23:44:02
Message-ID: 201002252344.o1PNi2007379@momjian.us (view raw or flat)
Thread:
Lists: pgsql-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. +

In response to

Responses

pgsql-performance by date

Next:From: Bruce MomjianDate: 2010-02-25 23:46:33
Subject: Re: No hash join across partitioned tables?
Previous:From: Bruce MomjianDate: 2010-02-25 23:42:55
Subject: Re: GiST index performance

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