Postgis KNN vs ST_DWithin for nearest neighbour search with a radius

2017-10-16 19:36:51

We are trying to get nearest neighbors within a user given radius. As far as I understand ST_DWithin degrades as distances are increased. The problem with using KNN is that it keeps on searching even though the radius is crossed.

For example,

let's say we are searching for 3 petrol stations in 1 km. KNN keeps searching for 3 candidates and we had to filter out those outside the radius after KNN is done. This leads to unnecessary time consumption.

Is there a way that we can do nearest neighbors search within a user given radius which combines the benefit of both. Or is there an alternative better than these 2 ?

Boundless has a good article how to solve your problem:

select *

from table1, table2

where st_distance(table1.the_geom,table2.the_geom) < 1000

order by table1.the_geom <-> table2.the_geom

limit 3

From the article:

The <-> is a “distance” operator, [...] it [..] makes use of the index when it appears in the ORDER BY clause.

Notes:

You need spati

  • Boundless has a good article how to solve your problem:

    select *

    from table1, table2

    where st_distance(table1.the_geom,table2.the_geom) < 1000

    order by table1.the_geom <-> table2.the_geom

    limit 3

    From the article:

    The <-> is a “distance” operator, [...] it [..] makes use of the index when it appears in the ORDER BY clause.

    Notes:

    You need spatial indexes on the_geom to perform fast !

    <-> uses box calculations that are approximations. If you want an exact result you need to limit to a higher number, and run a sort by st_distance on the result.

    Like this:

    with index_query as (

    select *, st_distance(table1.the_geom,table2.the_geom) as distance

    from table1, table2

    order by table1.the_geom <-> table2.the_geom

    limit 10

    )

    select * from index_query where distance < 1000 order by distance limit 3;

    2017-10-16 22:18:10