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

Re: GiST index performance

From: Matthew Wakeling <matthew(at)flymine(dot)org>
To: Oleg Bartunov <oleg(at)sai(dot)msu(dot)su>
Cc: 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: 2009-05-07 12:31:09
Message-ID: (view raw, whole thread or download thread mbox)
Lists: pgsql-performance
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 


 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

In response to


pgsql-performance by date

Next:From: David BrainDate: 2009-05-07 14:14:27
Subject: Slow select performance despite seemingly reasonable query plan
Previous:From: Simon RiggsDate: 2009-05-07 12:21:32
Subject: Re: Any better plan for this query?..

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