# Neighbors within distance from every row

I have a research project of 180,000 entries and I need to calculate the number of neighbors (points from the same table) that exist within a 300 meter radius for each point. My method is very slow, and I'm asking if there is a better way.

My initial thought was to left-join the table to itself, then calculate ST_Distance_Sphere for every row of the result table, then aggregate count the number of entries that are less than 300 meters - but this is turning out to be extremely slow. The initial JOIN in particular is taking more than an hour to complete (it's still running).

``````SELECT source_id as id, sum(case when dist_meters < 305 THEN 1 ELSE 0 END) as neighbors_within_distance FROM
(SELECT
a.id as source_id,
a.biz_lat as source_lat,
a.biz_lon as source_lon,
b.id as match_id,
b.biz_lat,
b.biz_lon,
ST_Distance_Sphere(ST_MakePoint(a.biz_lon, a.biz_lat), ST_MakePoint(b.biz_lon,b.biz_lat)) as dist_meters
FROM a LEFT JOIN a as b ON 1=1) as processed group by source_id
``````

I don't currently have any indexes, and the lat/lon columns are stored as floats. I could perform a KNN analysis first to select the nearest 500 points, and then filter the smaller data set down to only neighbors that meet the 300 meter criteria - but I'm not sure how to do that quickly.

Is there a better way to solve this problem?

EDIT : Here are my setup queries and example data rows

``````DROP TABLE IF EXISTS a;
CREATE TABLE a (
id              integer,
name            text,
city            text,
state           text,
zip             text,
county          text,
telephone       text,
fax             text,
email           text,
web             text,
type            text,
num_employees   text,
sic_1           text,
sic_2           text,
revenue         text,
biz_lat         float,
biz_lon         float,
class           text,
encoding_type   text,
bbox1           float,
bbox2           float,
bbox3           float,
bbox4           float,
display         text,
source          text
);
``````

An example row from the dataset

`````` ID Company Name    Street Address  City    State/Province  Postal Code County  Telephone Number    Fax Number  Company Email Address   URL/Web Address Company Type    No. of Employees    Primary SIC Code 1  Primary SIC Code 2  Headquarters    Sales/Revenue   lat lon class   type    bbox1   bbox2   bbox3   bbox4   display source
54776   26430. bizname  123 fake    Seguin  Texas   78155   El Paso (830) 555-3910              PRIVATE - PARENT    6   7359    Equipment rental & leasin, nec  Headquarters    1,098,000 (USD) 29.56570181 -97.94911784     place   house  29.56565181 29.56575181 -97.94916784    -97.94906784     123 Fake Seguin Guadalupe County  Texas 78155  United States of America
``````

You have pretty much suggested the answer to your own question already, which is that you don't have any indexes.

I would suggest that you convert your lat/lon columns to a geography (point) data type, add a spatial index, and rewrite the query to use ST_DWithin, which uses a spatial index, if available, and works with geometries or geographies.

``````ALTER TABLE a ADD column geom geography;
UPDATE a SET geom = ST_MakePoint(biz_lon, biz_lat);
CREATE INDEX ix_spatial ON a USING GIST (geom);

SELECT a.id, b.id
FROM a, a as b
WHERE ST_DWITHIN (a.geom, b.geom, 300)
AND a.id != b.id;
``````

This kind of construct is essentially a Cartesian product, or cross (spatial self) join, where ST_DWithin and the index dramatically reducing the search space. The a, b is short hand for a CROSS JOIN b. Note the `a.id != b.id` to avoid comparing a point with itself. Also, note that the 3rd form of `ST_DWithin` allows you to set a 4th parameter, `use_spheroid` to true, which will give slightly less accurate results, but be somewhat quicker, as it avoids the far more complex maths required to do spheroid calculations.

Overall, I would expect ST_DWithin on indexed geometries to be orders of magnitude faster than what you have.

If you want to get a list of all the points that are within 300 meters of every other point, you can use the `array_agg` function around b.id, eg,

``````SELECT a.id, array_to_string(array_agg(b.id), ',')
FROM a CROSS JOIN b
WHERE ST_DWITHIN (a.geom, b.geom, 300)
AND a.id != b.id
GROUP BY a.id;
``````

which will now give you comma separated list of all those ids from b that are within 300 meters for each id in a.

• ST_DWithin will not work as expected with epsg:4326 geometry. Geography has to be used in this particular case. Commented Mar 14, 2015 at 15:24
• For 300 meters, it is likely to be close enough, however, I had already edited the question to make that clear. Commented Mar 14, 2015 at 15:26
• In your SELECT statement, do I not need to LEFT JOIN a as b? Commented Mar 14, 2015 at 15:34
• No, the a,b is actually short hand for a full/cross join, and then ST_DWithin reduces the search space. I had already added this to the answer. Commented Mar 14, 2015 at 15:38
• FYI -- I did an "explain" and the difference in cost of your query and mine is many many orders of magnitude. I can't thank you enough Commented Mar 15, 2015 at 0:59
1. I really think that joining on 1 = 1 is not a good idea...
2. Try making your select statement smaller by using ST_DWithin(geom1, geom2, 300) , which is definitely faster than ST_Distance_Sphere()
3. Build indexes!
4. Can you share the data? A portion at least.

UPDATE:

I guess it would be useful to narrow down the join with distance condition before the join itself. How about `JOIN table ON 1=1 distance < 300? Would that work?

• I added the create queries and an example data row. Commented Mar 14, 2015 at 15:16