MySQL select coordinates within range

Question

I've in my database 100 000 addresses (that is records).

Each one of them has its own coordinates (latitude and longitude).

Now, given the geo location of the user (latitude and longitude), I want to show on a map only the addresses inside the 5 miles range (using Google maps v3 APIs).

This means that usually only 5 or 6 addresses have to be shown out of the 100 000 addresses.

One solution could be retrieving all the records and apply a formula in Java to calculate the distance of each address and show it only if it's inside the range.

That would be a waste of processing power, because I would need to retrieve all the records, when I only need to show 5 or 6 of them on the map.

How can I solve this problem on the database side (MySQL), in order to return only the addresses in the 5 miles range?

Answer 1

You can use what is called the Haversine formula.

$sql = "SELECT *, ( 3959 * acos( cos( radians(" . $lat . ") ) * cos( radians( lat ) ) * cos( radians( lng ) - radians(" . $lng . ") ) + sin( radians(" . $lat . ") ) * sin( radians( lat ) ) ) ) AS distance FROM your_table HAVING distance < 5";

Where $lat and $lng are the coordinates of your point, and lat/lng are your table columns. The above will list the locations within a 5 nm range. Replace 3959 by 6371 to change to kilometers.

This link could be useful: https://developers.google.com/maps/articles/phpsqlsearch_v3

Edit: I didn't see you mentioned Java. This example is in PHP but the query is still what you need.

Answer 2

My approach - and I am using it - is to think like a technician, I am happy with +/- 5%

This solution is not meant to control rockets, boats or a like, and only for distances below ~100km its just a solution like Fermi problem

So lets start for a pragmatic solution:

First: for many problems we can ignore that earth is not flat (distance <~100km) ,

The circumference of the earth is more or less 40000 km (more or less exactly for some reason)

A circle has exactly 360 deg.

So 1 km is: 360/40000 deg => 0.00278 deg

And then just select lat/long within this 0.003 per km, it will be something like where long > 42 - 0.003 and long < 42 + 0.003 - same for lat, where 42 is your lat/long as middpoint. The Database will use the indices.

the problem: you get a square as result not a circle (not real distance)

If you need the circle, script it after getting the results.

I just show the official toilette with in 2 km, so a square is ok, and the accuracy, too. The reason is, that there are streets and houses, so people can't walk directly ...

Edit: Technical / mathematical explain:

For very small triangles (one angle << 5 deg) you can ignore the use of trigonometry. So sin(5 deg) ~= 5/180*PI

Answer 3

DELIMITER $
DROP FUNCTION IF EXISTS calc_distance$

CREATE FUNCTION calc_distance(
    user_lat FLOAT(9,6),
    user_lng FLOAT(9,6),
    field_lat FLOAT(9,6),
    field_lng FLOAT(9,6)
) RETURNS INTEGER

BEGIN
    DECLARE ulat FLOAT;
    DECLARE ulng FLOAT;
    DECLARE flat FLOAT;
    DECLARE flng FLOAT;

    SET ulat = RADIANS(user_lat);
    SET ulng = RADIANS(user_lng);
    SET flat = RADIANS(field_lat);
    SET flng = RADIANS(field_lng);
    RETURN
        6371393
        * ACOS(
            COS(ulat) * COS(flat) * COS(flng - ulng)
            + SIN(ulat) * SIN(flat)
        );
END$
DELIMITER ;

Usage

if (($radius = $search->getRadiusMeters())) {
    $query['where'][] = "calc_distance($lat, $lng, addr.lat, addr.lng) < $radius";
}

Answer 4

I would think MySQL's geo spatial extensions would solve this for you: https://dev.mysql.com/doc/refman/8.0/en/spatial-convenience-functions.html#function_st-distance-sphere

Otherwise you could index on lattitude then query WHERE lattitude > userLat-5miles and lattitude < userLat+5miles. That would massively reduce the number of possible rows to process in the application layer.