How to improve query performance that compute haversine formula?

Question

Given a table of locations with latitudes and longitudes, which of those locations are nearest to a given location?

Of course, finding distances on the surface of the earth means using Great Circle distances, worked out with the Haversine formula, also called the Spherical Cosine Law formula.

I have the following code:

 SELECT zip, latitude, longitude, distance
 FROM (
  SELECT z.zip,
         z.latitude, z.longitude,
         p.radius,
         p.distance_unit
             * DEGREES(ACOS(COS(RADIANS(p.latpoint))
             * COS(RADIANS(z.latitude))
             * COS(RADIANS(p.longpoint - z.longitude))
             + SIN(RADIANS(p.latpoint))
             * SIN(RADIANS(z.latitude)))) AS distance
  FROM zip AS z
   JOIN (   /* these are the query parameters */
    SELECT  42.81 AS latpoint, -70.81 AS longpoint,
            50.0  AS radius,  111.045 AS distance_unit
        ) AS p ON 1=1
  WHERE z.latitude
    BETWEEN p.latpoint  - (p.radius / p.distance_unit)
        AND p.latpoint  + (p.radius / p.distance_unit)
   AND z.longitude
    BETWEEN p.longpoint - (p.radius / (p.distance_unit * COS(RADIANS(p.latpoint))))
        AND p.longpoint + (p.radius / (p.distance_unit * COS(RADIANS(p.latpoint))))
) AS d
WHERE distance <= radius

Is there any way to improve a performance of this query?

Is it necessary to use PostGIS to improve it or it's just a wrapper to my haversine formula?

Which DBMS are you using? See [here](http://stackoverflow.com/a/11479495/330315) for an efficient solution in Postgres (using PostGIS) — , Apr 19 '17 at 10:27
As an aside, you know that the `where` part isn't limiting to within the radius, but instead to a grid 2r x 2r? — JohnHC, Apr 19 '17 at 10:28
Did you tried [ST_DWithin](https://postgis.net/docs/ST_DWithin.html) along with [ST_Distance](https://postgis.net/docs/ST_Distance.html) ? Instead of Haversine formula? — Aparichith, Apr 19 '17 at 14:49
@Dharshan, no, I don't understand how I can use this function. The query in my question is just a string in python code. Can I use ST_DWithin along with ST_Distance in this string and how? — , Apr 19 '17 at 16:08
If your DBMS supports the WITH statement you can move out some of the calculations and saves those values into variables. You can take a look at the following answer for an example: http://stackoverflow.com/questions/12552288/sql-with-clause-example — michip96, May 10 '17 at 10:19

score 4 · Answer 1 · answered May 10 '17 at 09:15

This query will never be especially fast. However, there are some ways it can be improved.

First: The Haversine formula is not necessary here. The corrections which it applies are only necessary when the curvature of the earth is a significant factor, or very near the poles. Neither of these are the case here -- the largest distance which needs to be calculated accurately is 12 miles, which is barely even over the horizon. On this scale, the earth is effectively flat, so the Pythagorean Theorem is good enough for calculating distances.

One degree of latitude is about 69 miles, and at 52°N (around where the Netherlands are), a degree of longitude is cos(52°) x 69 = 42.5 miles, so the formula becomes:

sqrt(pow(69*(lat - $latitude), 2) + pow(42.5*(lng - $longitude), 2))

Second: we can use a "scissor test" for latitude and longitudes. If a point is more than 12 miles in any cardinal direction from your target point, it certainly cannot be within a 12-mile circle of that point. We can use this fact to perform a fast comparison on the latitude and longitude, skipping the distance calculation entirely. Using the figures for one degree of latitude/longitude we derived above, we have:

WHERE (lat BETWEEN ($latitude - 12/69.0) AND ($latitude + 12/69.0)) AND (lng BETWEEN ($longitude - 12/42.5) AND ($longitude + 12/42.5))

Note that this doesn't replace the full distance check! It's simply a first step to quickly throw out points that can't possibly be within the right radius. With an index in place on lat or lng, this will allow the database server to avoid examining many of the rows in the database.

In km ? It'll be : `SELECT * FROM table WHERE (lat BETWEEN ($latitude - 19/111) AND ($latitude + 19/111)) AND (lng BETWEEN ($longitude - 19/68) AND ($longitude + 19/68)) ` Get all the points in 19km right ? — Hotgeart, Oct 14 '18 at 14:38

score 1 · Accepted Answer · answered May 04 '17 at 13:59

I guess the planner will work this query rewrite all out by himself but worth a try. At least it is neater.

select zip, latitude, longitude, distance
from (
    select z.zip,
           z.latitude, z.longitude,
           p.radius,
           p.distance_unit
               * p.degrees_acos_cos_radians_latpoint
               * cos(radians(z.latitude))
               * cos(radians(p.longpoint - z.longitude))
               + p.sin_radians_latpoint
               * sin(radians(z.latitude)))) as distance
    from
        zip z
        cross join (
            select
                latpoint, longpoint, radius, distance_unit,
                latpoint - radius / distance_unit as lat0,
                latpoint + radius / distance_unit as lat1,
                longpoint - radius / distance_unit * cos(radians(latpoint)) as long0,
                longpoint + radius / distance_unit * cos(radians(latpoint)) as long1,
                sin(radians(latpoint)) as sin_radians_latpoint,
                degrees(acos(cos(radians(latpoint)) as degrees_acos_cos_radians_latpoint
            from (
                values (42.81, -70.81, 50.0, 111.045)
            ) v (latpoint, longpoint, radius, distance_unit)
        ) p
    where
        z.latitude between lat0 and lat1
        and
        z.longitude between long0 and long1
) d
where distance <= radius

score 0 · Answer 3 · answered May 04 '17 at 18:48

The expressions are not the slow part. The problem with "finding nearest" is the difficulty in using an index to limit how many of rows to look at.

If you don't already have these on z, then they will help:

INDEX(latitude),
INDEX(longitude)

If you already had them, then make sure that one of them was actually used by the subquery.

The next step will be more drastic (and more fruitful): http://mysql.rjweb.org/doc.php/latlng

How to improve query performance that compute haversine formula?

3 Answers3