Effect of Distance on PostGIS range queries

Question

I am using Radius query function of PostGIS, for finding points within radius using geography column:

select count(*) from goeocde_table WHERE  ST_DWithin(geog, ST_MakePoint(-76.07,36.21),640000) ;

I have defined a spatial index on top of geog column. However, I see a large performance impact as soon as I increase the radius. Is it expected?

Answer 1

In short, yes. Spatial indexes in Postgres/Postgis are based on R-trees, which is a tree structure that attempts to subdivide your area based on bounding boxes, see http://en.wikipedia.org/wiki/R-tree, while trying to maintain a balance between speed of search and speed of insertion/deletion of new values. So, if you were lucky enough to issue a query where your point plus the distance around it was entirely contained within one of the boxes on a leaf node, then you would get a very quick response. As soon as you enlarge the search area, so that it intersects with neighboring bounding boxes, there will be many more candidates to search for distance from you point to any potential candidate.

Also, note that, the points in your query are in lat/lon, but the search distance is in metres, so based on your sample query above, you are requesting a very large search area. There is another spatial operator in Postgis, <->, that can lead to drastically quicker searches if you are looking for the x nearest neighbors to a point, see http://postgis.net/docs/geometry_distance_centroid.html