I have a table called Stores with 10k rows which has a column location geometry(Point,4326).

CREATE INDEX "Stores_spatial_gix"
ON "Stores"
USING gist

Upon KNN query

explain analyze select *
 from "Stores"
 order by ST_distance_sphere(location,st_point(-82.373978, 29.633657)) limit 3

I get about 800ms each time. What am I doing wrong that it takes so long time?

  • You have a full table scan query there, requiring that distance be calculated for each row, then the results be sorted. I'm amazed the query is that fast -- the table contents must be cached. – Vince Jul 12 '15 at 16:47
  • Well this is just some preliminary data. There will be 1M+ rows. – Morteza Shahriari Nia Jul 12 '15 at 16:52
  • Then that query will take forever if you don't add an ST_DWithin constraint. – Vince Jul 12 '15 at 17:00
  • I have benchmarked and a table with point column and an index gives out the same KNN query in 0.452 ms! So there is something definitely off here. Due to some library dependency I'm stuck with geometry and can't use point. So it is possible, but needs a right approach. – Morteza Shahriari Nia Jul 12 '15 at 17:15
  • x-posted to stackoverflow.com/q/31369847/398670 (for anyone else looking later) – Craig Ringer Jul 13 '15 at 4:14

Assuming you are using PostGIS 2+, you can make use of the <-> operator. See http://postgis.refractions.net/documentation/manual-2.0/geometry_distance_centroid.html

So in your example it might look like

ORDER BY location <-> 'SRID= 4326;POINT(-82.373978 29.633657)'::geometry limit 3;

Note the results may be returned misordered.

If you can put an ST_DWithin constraint in too, that may help out.

  • Does the same inaccuracy apply when I do point <-> point for KNN? – Morteza Shahriari Nia Jul 12 '15 at 18:18
  • Inaccuracy in the ordering? – Guy Jul 13 '15 at 9:01
  • @MortezaShahriariNia, any progress? – Guy Jul 13 '15 at 13:56
  • Yes, this approach works. As you mentioned it might suffer from misorderings. I ended up using a hybrid approach as I explain in a new answer here. Also there should be no comma in constructing point, but I couldn't edit the answer – Morteza Shahriari Nia Jul 13 '15 at 19:49
  • Updated. Feel free to mark as complete – Guy Jul 13 '15 at 20:30

Here is what I ended up doing:

WITH index_query AS (
  SELECT ST_distance_sphere(location, 'SRID=4326;POINT(-82.373978 29.633657)'::geometry) as distance, ST_X("Stores"."location"), ST_Y("Stores"."location")
    FROM "Stores"
  ORDER BY location <-> 'SRID=4326;POINT(-82.373978 29.633657)'::geometry LIMIT 100) 
   FROM index_query 
  ORDER BY distance limit 10;

Results are spit out in 2.5ms in a table with 1M geometry records. The hybrid idea is taken from here to avoid misorderings.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.