Re: find close (duplicate) points + create index

Hello,

I have a table with one column --
"CREATE TABLE pointtable (point POINT)".
I'm trying to find duplicate entries, where two entries are considered
duplicates if they're within a radius of 1, meaning something like ~ "select
point from pointtable where distance between points <=1".
Obviously this is not SQL syntax. Is there a way to do this - search within a
column itself?

Also, I also tried to build an index on that column, but there's no operator
class for type point. How can I do that?

Thanks,
Elinor

On Thu, Mar 04, 2004 at 12:42:23 +0200,
Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> wrote:
> Hello,
>
> I have a table with one column --
> "CREATE TABLE pointtable (point POINT)".
> I'm trying to find duplicate entries, where two entries are considered
> duplicates if they're within a radius of 1, meaning something like ~ "select
> point from pointtable where distance between points <=1".
> Obviously this is not SQL syntax. Is there a way to do this - search within a
> column itself?

Yes, you can join a table to itself and return records matching some
critera. This isn't going to be fast. I didn't see a distance between
two points function, but it is probably there somewhere. If not you
can check if one point is contained in a circle of radius 1 centered
at the other point. This is something that could use an index, though
it probably wouldn't help when checking the whole table. It probably
would speed up checking a single point for conflicts.

Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> writes:
> I'm trying to find duplicate entries, where two entries are considered
> duplicates if they're within a radius of 1, meaning something like
> "select point from pointtable where distance between points <=1".
> Obviously this is not SQL syntax.

Well, it is if you do a self-join:

select * from pointtable a, pointtable b
where distance(a.point, b.point) <= 1;

Postgres spells the "distance" operator as "<->", so this becomes

select * from pointtable a, pointtable b
where (a.point <-> b.point) <= 1;

Making it fast is a more difficult problem :-( ... if you write the
above query as-is then the system will sit there and compare each row of
pointtable to each other row, looking for pairs of rows that match the
where-clause. Okay if you just have some thousands of rows, but on a
big table this will take longer than you want to wait.

> Also, I also tried to build an index on that column, but there's no operator
> class for type point. How can I do that?

A btree index on a point column would be quite useless, since btree
understands only a one-dimensional continuum with less-than, equal,
greater-than relationships. But I think you might be able to do
something with an rtree index. I'd look at making an rtree index on
the unit box around each point, and then using an "overlaps" test as
an indexable coarse filter before the exact distance check.

regards, tom lane

You suggested:

> select * from pointtable a, pointtable b
> where (a.point <-> b.point) <= 1;

Thanks, Thats what I'll do.

> Making it fast is a more difficult problem :-( ... if you write the
> above query as-is then the system will sit there and compare each row of
> pointtable to each other row, looking for pairs of rows that match the
> where-clause. Okay if you just have some thousands of rows, but on a
> big table this will take longer than you want to wait.

This query will only work on a few thousand lines, but I will have other
queries on type point that will require comparing tables with millions of
rows. Therefore I must learn how to build indexes on points.

> A btree index on a point column would be quite useless, since btree
> understands only a one-dimensional continuum with less-than, equal,
> greater-than relationships. But I think you might be able to do
> something with an rtree index.

That much I know. I didn't find how I can use rtree to build an index on
points, seeing how when I tried the following:
"create INDEX Phot_point_a ON Phot USING RTREE (point_a);"
I got this error:
"ERROR: data type point has no default operator class for access method
"rtree"
HINT: You must specify an operator class for the index or define a default
operator class for the data type."

And then I found out that in postgres the only operator classes defined for
rtree indexes are: bigbox_ops, box_ops and poly_ops. Neither of which works
with points, only with type box and polygon. Therefore I also have to create
an operator class. I didn't understand how to do that. Do you know how?

> I'd look at making an rtree index on
> the unit box around each point, and then using an "overlaps" test as
> an indexable coarse filter before the exact distance check.

I didn't understand this either.

Thanks,
Elinor

On Wed, 10 Mar 2004, Tom Lane wrote:
> Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> writes:

> > I'm trying to find duplicate entries, where two entries are considered
> > duplicates if they're within a radius of 1, meaning something like
> > "select point from pointtable where distance between points <=1".
> > Obviously this is not SQL syntax.
>
> Well, it is if you do a self-join:
>
> select * from pointtable a, pointtable b
> where distance(a.point, b.point) <= 1;
>
> Postgres spells the "distance" operator as "<->", so this becomes
>
> select * from pointtable a, pointtable b
> where (a.point <-> b.point) <= 1;
>
> Making it fast is a more difficult problem :-( ... if you write the
> above query as-is then the system will sit there and compare each row of
> pointtable to each other row, looking for pairs of rows that match the
> where-clause. Okay if you just have some thousands of rows, but on a
> big table this will take longer than you want to wait.

I'm guessing distance is defined to be:
sqrt( (x1-x0)^2 + (y1-y0)^2 )
or
sqrt( (x1-x0)^2 + (y1-y0)^2 + (z1-z0)^2 )

You obviously need to find the difference in the x,y (and possibly
z if used) coordinates, as is multiplying that difference by
itself and summing them. However, you don't need to take the
square root, which is often a computationally expensive thing.
Two points which are close in terms of distance, are also close in
terms of distance squared.

If you are only interested in points that are within a distance of
1 (or a distance squared of 1*1), then you can stop calculating
the distance when any of the differences is bigger than 1. Since
you don't care, other than knowing it is too big, just stop the
calculation and return some number bigger than 1. That should
help in speeding things up a bit. How you do this in PostgreSQL,
I can't help you. :-)

> > Also, I also tried to build an index on that column, but
> > there's no operator class for type point. How can I do that?
>
> A btree index on a point column would be quite useless, since btree
> understands only a one-dimensional continuum with less-than, equal,
> greater-than relationships. But I think you might be able to do
> something with an rtree index. I'd look at making an rtree index on
> the unit box around each point, and then using an "overlaps" test as
> an indexable coarse filter before the exact distance check.

You probably want to look a little at how GIS (Geographical
Information Systems) works. There are lots of different
techniques they use to search and partition things. Quadtree
and oct-tree come to mind.

Gord

Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> writes:
> And then I found out that in postgres the only operator classes defined for
> rtree indexes are: bigbox_ops, box_ops and poly_ops. Neither of which works
> with points, only with type box and polygon. Therefore I also have to create
> an operator class.

No you don't. What you want is a functional index built on a box or polygon
surrounding the point. For instance, given

regression=# create table p1 (point_a point);
CREATE TABLE
regression=# create index p1i on p1 using rtree (box(point_a, point_a));
CREATE INDEX

you could do searches for points enclosed in a specific box like this:

regression=# explain select * from p1 where box(point_a, point_a) && '(0,1),(0,1)'::box;
QUERY PLAN
----------------------------------------------------------------
Index Scan using p1i on p1 (cost=0.00..17.07 rows=5 width=16)
Index Cond: (box(point_a, point_a) && '(0,1),(0,1)'::box)
(2 rows)

since box-overlap (&&) is one of the rtree-indexable operators.

The most useful way to solve your original problem seems to be

regression=# explain select * from p1 a, p1 b where
regression-# box(a.point_a, a.point_a) && box(circle(b.point_a,sqrt(2)))
regression-# and (a.point_a <-> b.point_a) <= 1;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.01..17220.00 rows=1667 width=32)
Join Filter: (("inner".point_a <-> "outer".point_a) <= 1::double precision)
-> Seq Scan on p1 b (cost=0.00..20.00 rows=1000 width=16)
-> Index Scan using p1i on p1 a (cost=0.01..17.07 rows=5 width=16)
Index Cond: (box(a.point_a, a.point_a) && box(circle("outer".point_a, 1.4142135623731::double precision)))
(5 rows)

The indexable condition finds "a" rows that are within the bounding box
of a circle surrounding the "b" row, and then we only need to apply the
exact distance check to those rows.

(If you're wondering about the sqrt(2), there's an oddity in the
built-in circle-to-box function: it divides the circle radius
by sqrt(2). I think this is a bug and will propose changing it
for 7.5.)

regards, tom lane

What's going on? the same message I've sent 3 times! not once did it arrive

I am trying to install postgreSQL with perl support on a Slackware Linux
9.1. I have compiled perl with shared libraries, the rest of the settings
default. Then I configured postgres with --with-perl and it worked fine.
But when I am executing 'make' I get an error: plperl no such file or
directory. I have tried everything. Please help!

On Wed, Mar 10, 2004 at 11:22:47 +0200,
Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> wrote:
>
> That much I know. I didn't find how I can use rtree to build an index on
> points, seeing how when I tried the following:
> "create INDEX Phot_point_a ON Phot USING RTREE (point_a);"
> I got this error:
> "ERROR: data type point has no default operator class for access method
> "rtree"
> HINT: You must specify an operator class for the index or define a default
> operator class for the data type."
>
> And then I found out that in postgres the only operator classes defined for
> rtree indexes are: bigbox_ops, box_ops and poly_ops. Neither of which works
> with points, only with type box and polygon. Therefore I also have to create
> an operator class. I didn't understand how to do that. Do you know how?

rtree indexes on points doesn't make sense since containment is the same
as equals. You want to use boxes. A point is a box with the same point
for both of the defining corners. When you do searches you use a box
that describes where you are looking and look for boxes (including points)
that are located in the search box.

You can also use the cube type and gist indexes to do the same thing.

On Wed, 10 Mar 2004, Elinor Medezinski wrote:

> > I'd look at making an rtree index on
> > the unit box around each point, and then using an "overlaps" test as
> > an indexable coarse filter before the exact distance check.
>
> I didn't understand this either.

Lets say a 2D point comes from GPS, and has coordinates (from some
particular zone) of (483121.534, 5124378.745). The units are
meters, and so these coordinates are both specified to the nearest
millimeter (which is too many significant figures for a GPS
measurement without special equipment).

We can construct a small box around this point, by chopping off
the fractional meters, and either adding or subtracting 1. We
will also assume that any boxes we make, have sides parallel to
our axis. So, the Upper Left point is (483120,5124379) and the
Lower Right point is (483122,5124377).

This isn't a unit box, it's a 4 unit box. But, it requires less
care in constructing it (in my mind) than making the unit box.
But you can work with unit boxes too. To check that are box
(point) of interest overlaps another box, you check to see that
the minimum X of this box is greater than the minimum X of the
other box and less than the maximum X of the other box. Likewise
for the Y coordinates. You are considering small boxes around
points, and all the boxes are squares. The more general problem,
allows for N-sided polygons, where it is possible for the bounding
boxes to overlap, but for the one box to not be inside the other
box.

If the bounding boxes don't overlap, there is no sense calculating
a distance (in some cases) as the points/boxes are too far apart.

Gord

Hi Tom,
Following your advice quite a long time ago, I built an index on
my very large table called object:

myDB=# select count(*) from object;
count
---------
2797036
(1 row)
Time: 8354.25 ms

using RTREE INDEX on a column of type point:

myDB=# create index object_point_a on object using rtree
(box(point_a,point_a));
CREATE INDEX
Time: 220546.54 ms

Then I tried the query you suggested to find points closer to
each other than 1.5:
SELECT * FROM object a,object b
WHERE box(a.point_a,a.point_a)&&box(circle(b.point_a,sqrt(2)))
AND (a.point_a<->b.point_a)<1;

After many many minutes, it started giving these lines:
server sent data ("D" message) without prior row description
("T" message)
server sent data ("D" message) without prior row description
("T" message)
server sent data ("D" message) without prior row description
("T" message)
.....

Eventually I lost patience and killed it. I am pretty sure I
tried it once, but perhaps the table wasn't as big.
Any suggestions?

Thanks,
Elinor




Elinor Medezinski <elinor ( at ) bellatrix ( dot ) tau ( dot )
ac ( dot ) il> writes:

> And then I found out that in postgres the only operator classes defined for
> rtree indexes are: bigbox_ops, box_ops and poly_ops. Neither of which works
> with points, only with type box and polygon. Therefore I also have to create
> an operator class.

No you don't. What you want is a functional index built on a box or polygon
surrounding the point. For instance, given

regression=# create table p1 (point_a point);
CREATE TABLE
regression=# create index p1i on p1 using rtree (box(point_a, point_a));
CREATE INDEX

you could do searches for points enclosed in a specific box like this:

regression=# explain select * from p1 where box(point_a, point_a) && '(0,1),(0,1)'::box;
QUERY PLAN
----------------------------------------------------------------
Index Scan using p1i on p1 (cost=0.00..17.07 rows=5 width=16)
Index Cond: (box(point_a, point_a) && '(0,1),(0,1)'::box)
(2 rows)

since box-overlap (&&) is one of the rtree-indexable operators.

The most useful way to solve your original problem seems to be

regression=# explain select * from p1 a, p1 b where
regression-# box(a.point_a, a.point_a) && box(circle(b.point_a,sqrt(2)))
regression-# and (a.point_a <-> b.point_a) <= 1;
QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
Nested Loop (cost=0.01..17220.00 rows=1667 width=32)
Join Filter: (("inner".point_a <-> "outer".point_a) <= 1::double precision)
-> Seq Scan on p1 b (cost=0.00..20.00 rows=1000 width=16)
-> Index Scan using p1i on p1 a (cost=0.01..17.07 rows=5 width=16)
Index Cond: (box(a.point_a, a.point_a) && box(circle("outer".point_a, 1.4142135623731::double precision)))
(5 rows)

The indexable condition finds "a" rows that are within the bounding box
of a circle surrounding the "b" row, and then we only need to apply the
exact distance check to those rows.

(If you're wondering about the sqrt(2), there's an oddity in the
built-in circle-to-box function: it divides the circle radius
by sqrt(2). I think this is a bug and will propose changing it
for 7.5.)

regards, tom lane

On Wed, 2004-03-10 at 07:27, Tom Lane wrote:

> Elinor Medezinski <elinor(at)bellatrix(dot)tau(dot)ac(dot)il> writes:
> > I'm trying to find duplicate entries, where two entries are considered
> > duplicates if they're within a radius of 1, meaning something like
> > "select point from pointtable where distance between points <=1".
> > Obviously this is not SQL syntax.
>
> Well, it is if you do a self-join:
>
> select * from pointtable a, pointtable b
> where distance(a.point, b.point) <= 1;
>
> Postgres spells the "distance" operator as "<->", so this becomes
>
> select * from pointtable a, pointtable b
> where (a.point <-> b.point) <= 1;
>
> Making it fast is a more difficult problem :-( ... if you write the
> above query as-is then the system will sit there and compare each row of
> pointtable to each other row, looking for pairs of rows that match the
> where-clause. Okay if you just have some thousands of rows, but on a
> big table this will take longer than you want to wait.
>
> > Also, I also tried to build an index on that column, but there's no operator
> > class for type point. How can I do that?
>
> A btree index on a point column would be quite useless, since btree
> understands only a one-dimensional continuum with less-than, equal,
> greater-than relationships. But I think you might be able to do
> something with an rtree index. I'd look at making an rtree index on
> the unit box around each point, and then using an "overlaps" test as
> an indexable coarse filter before the exact distance check.
>
> regards, tom lane
>
> +++++++++++++++++++++++++++++++++++++++++++
> This Mail Was Scanned By Mail-seCure System
> at the Tel-Aviv University CC.

Elinor <elinor(at)wise1(dot)tau(dot)ac(dot)il> writes:
> After many many minutes, it started giving these lines:
> server sent data ("D" message) without prior row description
> ("T" message)

Up till fairly recently (8.0 or maybe 7.4), libpq would do that if it
ran out of memory to hold the query result. I think you miswrote the
query and it's returning a huge number of rows. If you actually want
to fetch a huge number of rows, try using a cursor ...

regards, tom lane