Re: gist indexes for distance calculations

From: Tom Lane Marcelo Zabani pgsql-performance(at)postgresql(dot)org Re: gist indexes for distance calculations 2010-09-30 19:16:36 11340.1285874196@sss.pgh.pa.us (view raw or whole thread) 2010-09-30 18:33:03 from Marcelo Zabani  2010-09-30 19:16:36 from Tom Lane  2010-10-01 02:50:14 from Marcelo Zabani   2010-10-01 04:45:29 from Karim Nassar  2010-10-01 05:56:18 from Jesper Krogh   2010-10-12 00:52:23 from Robert Haas  2010-10-01 16:04:19 from Merlin Moncure   2010-10-01 17:12:01 from Marcelo Zabani pgsql-performance
```Marcelo Zabani <mzabani(at)gmail(dot)com> writes:
> CREATE INDEX ON places USING gist (circle(coordinates, 1));

> I'd like to know how this index works, though, as it seems to me the only
> way to have this kind of index to work is to calculate the distance of every
> point in a square of sides 2*1=2 units centered on (a, b).

I believe it is a bounding-box based implementation; that is, each
non-leaf entry in the index stores the bounding box that covers all the
entries in the child page (plus its children if any).  So a lookup
descends to only those child pages that could possibly contain entries
overlapping the target circle.

> So, am I wrong to think it works like that? If it does work like that, could
> I have instead two columns of type FLOAT (xcoordinate and ycoordinate) and
> create traditional b-tree indexes on both of these, and then do something
> like:

> SELECT * FROM places WHERE xcoordinate >= (a-1) AND xcoordinate <= (a+1) AND
> ycoordinate >= (b-1) AND ycoordinate <= (b+1) And
> SQRT(POW(a-xcoordinate,2)+POW(b-ycoordinate,2))<=1;

Well, there's nothing stopping you from doing that, but search
performance is likely to be a whole lot worse than with an actual 2-D
index.  The reason is that it'll have to fetch index entries for
everything in the vertical strip between a-1 and a+1, as well as
everything in the horizontal strip between b-1 and b+1; most of which is
nowhere near the target.  If your circles are always very very small
this might work tolerably, but in most applications the amount of stuff
fetched soon gets out of hand.

regards, tom lane

```

pgsql-performance by date

 Next: From: Mark Kirkwood Date: 2010-09-30 21:01:26 Subject: Re: Memory usage - indexes Previous: From: Marcelo Zabani Date: 2010-09-30 18:33:03 Subject: gist indexes for distance calculations

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