Re: gist indexes for distance calculations

Thanks a lot everyone for all the info! It is all really helpful.

2010/10/1 Merlin Moncure <mmoncure(at)gmail(dot)com>

> On Thu, Sep 30, 2010 at 2:33 PM, Marcelo Zabani <mzabani(at)gmail(dot)com>
> wrote:
> > Hi everyone. I have a question, and it's well beyond me to even speculate
> > about the inner workings of postgresql on this.
> >
> > I have a "places" table, and a "coordinates" column, of type POINT.
> >
> > If I want to find every place within, for example, a distance of 1 unit
> from
> > an arbitrary point, I'll do:
> >
> > CREATE INDEX ON places USING gist (circle(coordinates, 1));
> >
> > And then I'll fetch the desired rows like this:
> >
> > SELECT * FROM places WHERE circle(coordinates, 1) @> circle('(a,b)', 0);
> > (where (a,b) is an arbitrary point)
> >
> > 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).
> >
> > 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;
> >
> > If you can also pinpoint me to where I can find this sort of information
> > (index utilization and planning, performance tuning), I'd be very
> grateful.
>
> A quick heads up: It's possible, although it may not necessarily help,
> to further reduce distance calcs by drawing an inner bounding box of
> points that are confirmed good. Your outer box is made by squaring
> the circle on lat/lon projection -- you can also calculate the biggest
> lat lon 'rectangle' that completely fits inside the circle, and play
> with a query that looks something like this (pseudo sql):
>
> select * from points where (point inside good box) or (point inside
> possible box and dist(point, mypoint < n));
>
> You get reduction of dist calcs at expense of second gist lookup. You
> can also, of course, do this on application side, but what's the fun
> in that? :-).
>
> merlin
>

--
Marcelo Zabani
(19) 9341-0221