Thread: index on points

Hi all,
we are just programming a Geographical Information System for the hole
country of Bavaria.
Therefore we decided to use PostgreSQL as our DB. At this time we have
the problem to find points in a polygon. In postgres you have the
operator '@' to find points in a polygon. But if you have many points it
is realy to slow without indexing the points.
In the TODO list I saw it is planned to create an index on points and
other geometric types. Will it be implemented at any of the next
releases?
Has someone any idea to realize it now on another way?
Thanks for helping,
Peter
--
        Bezirksfinanzdirektion Muenchen
              Vermessungsabteilung
.........................................................
 Peter Keller        :  Tel: (+49) 089-2190-2594
 Vermessungsrat     :  Fax: (+49) 089-2190-2459
 Alexandrastr. 3    :  mailto:Peter.Keller@bvv.bayern.de
 80538 Muenchen        :  web: http://www.bayern.de/vermessung

Peter Keller <peter.keller@bvv.bayern.de> writes:
> Therefore we decided to use PostgreSQL as our DB. At this time we have
> the problem to find points in a polygon. In postgres you have the
> operator '@' to find points in a polygon. But if you have many points it
> is realy to slow without indexing the points.
> In the TODO list I saw it is planned to create an index on points and
> other geometric types. Will it be implemented at any of the next
> releases?

There is already support for r-tree indexes, but as far as I know the
'@' operator is not connected up to indexes.  In theory it'd be a
straightforward extension (I think ...).  Just needs someone interested
enough to work on it.  Are you that someone?

            regards, tom lane

Tom Lane wrote:
>
> Peter Keller <peter.keller@bvv.bayern.de> writes:
> > Therefore we decided to use PostgreSQL as our DB. At this time we have
> > the problem to find points in a polygon. In postgres you have the
> > operator '@' to find points in a polygon. But if you have many points it
> > is realy to slow without indexing the points.
> > In the TODO list I saw it is planned to create an index on points and
> > other geometric types. Will it be implemented at any of the next
> > releases?
>
> There is already support for r-tree indexes, but as far as I know the
> '@' operator is not connected up to indexes.  In theory it'd be a
> straightforward extension (I think ...).  Just needs someone interested
> enough to work on it.  Are you that someone?
>
>                         regards, tom lane

well, not that straightforward, i wouldn't think, especially if you're
talking about a polygon at the other end, but still definitely
possible.  there may be a workaround with the way it works now, though.
i'm just throwing this out without testing it, but i think something
like this might work:  coerce both the point and polygon into boxes (i
think box(polygon) gives you the bounding box, at least) and use the
overlap (&&) operator, which works fine with r-tree indexes on two
boxes, then use the contained operator (@) on what you get from that.

for example:

1) create the rtree index on the polygon field:
   create index test_index on test_data using rtree(box(polygon_field));
2) remember to vacuum after you create the index
3) perform a query something like this:
   select * from test_data
   where box(point,point) && box(polygon_field)
     and point @ polygon_field;

again, i haven't tested this to make sure that the index would be used
properly, but it should filter out enough of the chaff to make the query
reasonably fast.  hope that helps (even more, i hope it works)

--

Jeff Hoffmann
PropertyKey.com

Jeff Hoffmann <jeff@propertykey.com> writes:
> Tom Lane wrote:
>> There is already support for r-tree indexes, but as far as I know the
>> '@' operator is not connected up to indexes.

> i'm just throwing this out without testing it, but i think something
> like this might work:  coerce both the point and polygon into boxes (i
> think box(polygon) gives you the bounding box, at least) and use the
> overlap (&&) operator, which works fine with r-tree indexes on two
> boxes, then use the contained operator (@) on what you get from that.

Right, that's pretty much exactly what index support for @ would do for
you under-the-hood.  I wouldn't expect the index to give you an answer
finer-grained than bounding boxes, so you'd still need to run @ itself
on the candidates found by the indexable query.

Jeff has a good point that doing the transformation by hand might be
an acceptable answer for the time being.  You can hack a lot of queries
in the time it will take to teach the system to do that same
transformation ...

            regards, tom lane