To: Marcelo Zabani <mzabani@gmail.com>
cc: pgsql-performance@postgresql.org
Subject: Re: gist indexes for distance calculations 
In-reply-to: <AANLkTikvpQS+1q3HBrVCgCjRF+2-LPGzmVHQO+EJk3QG@mail.gmail.com> 
References: <AANLkTikvpQS+1q3HBrVCgCjRF+2-LPGzmVHQO+EJk3QG@mail.gmail.com>
Comments: In-reply-to Marcelo Zabani <mzabani@gmail.com>
	message dated "Thu, 30 Sep 2010 15:33:03 -0300"
Date: Thu, 30 Sep 2010 15:16:36 -0400
Message-ID: <11340.1285874196@sss.pgh.pa.us>
From: Tom Lane <tgl@sss.pgh.pa.us>

Marcelo Zabani <mzabani@gmail.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