[postgis-users] Nearest Neighbor on Large Datasets

[Spencer Gardner]

Thanks! That did the trick. I had previously tried a slightly different version of your solution but it was far less efficient.

From: postgis-users-bounces at lists.osgeo.org [mailto:postgis-users-bounces at lists.osgeo.org] On Behalf Of Pierre Racine
Sent: Monday, April 08, 2013 10:41 AM
To: PostGIS Users Discussion
Subject: Re: [postgis-users] Nearest Neighbor on Large Datasets

Try this:

SELECT grid.pk_uid, point.pk_uid AS el_id, point.elevation
FROM grid_rail_lines grid, elev_rail_combined point
WHERE point.pk_uid  = (SELECT point.pk_uid id2
        FROM grid_rail_lines point
        ORDER BY point.geom <-> grid.geom
        LIMIT 1)
ORDER BY grid.pk_uid

From: postgis-users-bounces at lists.osgeo.org<mailto:postgis-users-bounces at lists.osgeo.org> [mailto:postgis-users-bounces at lists.osgeo.org] On Behalf Of Spencer Gardner
Sent: Monday, April 08, 2013 11:08 AM
To: 'PostGIS Users Discussion'
Subject: [postgis-users] Nearest Neighbor on Large Datasets

I have a layer of grid cells and a layer of discreet points representing elevation samples. My grid layer has a total of about 430,000 cells, the elevation data contains about 320,000 points, and both datasets have spatial indexes on them. I need to join each grid cell with the nearest elevation point (within at most 30 feet of the cell's center point). To accomplish this, I created the following query:

SELECT DISTINCT ON (grid_rail_lines.pk_uid)
  grid_rail_lines.pk_uid
, elev_rail_combined.pk_uid AS el_id
, elev_rail_combined.elevation
FROM
  grid_rail_lines JOIN elev_rail_combined
    ON grid_rail_lines.the_geom<->elev_rail_combined.the_geom < 30
ORDER BY
  grid_rail_lines.pk_uid ASC
, grid_rail_lines.the_geom<->elev_rail_combined.the_geom ASC


EXPLAIN provides the following information (also available at depesz<http://explain.depesz.com/s/Vsm>):

Unique  (cost=141973943356.82..142206589733.23 rows=434170 width=624)
  ->  Sort  (cost=141973943356.82..142090266545.03 rows=46529275283 width=624)
        Sort Key: grid_rail_lines.pk_uid, ((grid_rail_lines.the_geom <-> elev_rail_combined.the_geom))
        ->  Nested Loop  (cost=0.00..4910712887.16 rows=46529275283 width=624)
              Join Filter: ((grid_rail_lines.the_geom <-> elev_rail_combined.the_geom) < 30::double precision)
              ->  Seq Scan on grid_rail_lines  (cost=0.00..13202.70 rows=434170 width=484)
              ->  Seq Scan on elev_rail_combined  (cost=0.00..6220.05 rows=321505 width=140)


I let this query run over the weekend and it took a total of 21 hours. These datasets are rather large so I expect it to take a long time, but I wonder if there is a more efficient way to conduct the join. As far as I can tell, I've structured the query as recommended in the documentation. Does anyone have ideas for how to improve performance?

Thanks,
Spencer
________________________________
This e-mail and any files transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If you are NOT the intended recipient and receive this communication, please delete this message and any attachments. Thank you.
------------------------------------------------------------------------------

This e-mail and any files transmitted with it are confidential and are intended solely for the use of the individual or entity to whom they are addressed. If you are NOT the intended recipient and receive this communication, please delete this message and any attachments. Thank you.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.osgeo.org/pipermail/postgis-users/attachments/20130408/28f20a96/attachment.html>