Bounding Boxes for Geospatial Queries in MySQL | PHP

globe image

So let’s assume you have a database table called users that stores user information, including longitude and latitude. If you want to find other users closest to a specific user, you can use a simple search formula as described here. However, as your table grows larger, this query will become slower and it won’t take advantage of indexes, even if the longitude and latitude columns are indexed. To optimize the query, you can consider using a bounding box approach.

What is a bounding Box?

square box over a map

A bounding box is an area surrounding a specific location. Our problem arises when we need to find the closest users to our specific user, as we have to iterate through the entire table and perform our calculation. However, what if we could first obtain all users within 2 miles (or any other distance) from the specific user and then perform our calculations only on those users? This way, we can easily identify those who are closer.

So, how do you calculate it? Well, the method depends on the programming language you are using. A quick online search should provide you with the necessary information. If you are using PHP, the calculation would look something like this:

if (! function_exists('create_coordinates_bounding_box'))
{

    function create_coordinates_bounding_box($latitude, $longitude, $distance = 2): array
    {
        $radius = config('distance.search_radius');
        $earth_radius = 6371;
        $max_latitude = $latitude + rad2deg($distance / $earth_radius);
        $min_latitude = $latitude - rad2deg($distance / $earth_radius);
        $max_longitude = $longitude + rad2deg(asin($distance / $earth_radius) / cos(deg2rad($latitude)));
        $min_longitude = $longitude - rad2deg(asin($distance / $earth_radius) / cos(deg2rad($latitude)));
        return [
            'max_latitude' => $max_latitude,
            'min_latitude' => $min_latitude,
            'max_longitude' => $max_longitude,
            'min_longitude' => $min_longitude,
        ];
    }
}

The purpose of the function (for Laravel users helper function) is to take the distance and return the maximum latitude and longitude (max lat, long) and minimum latitude and longitude (min lat, long), which represent the X and Y axes for the bounding box (where the lines intersect). The idea is to use the users that exist within the box for searching. You might wonder why we still need to search. Well, that’s because this function only returns users within the box, and there may be some redundant users who are not exactly 2 miles away from your location (due to the Earth being round and all).

Now, let’s discuss how to use the bounding box. Your SQL query will probably look like this:

    SELECT
        user_id, 
        ST_DISTANCE_SPHERE(
            POINT(specific_user_longitude,specific_user_latitude),
            POINT(longitude,latitude)
        ) * 0.000621371 AS distance
    FROM
        user_coordinates
    WHERE
        latitude BETWEEN min_latitude AND max_latitude
        AND longitude BETWEEN mix_longitude AND max_longitude
        having distance < 2
        ORDER BY distance;

We use the BETWEEN clause to get users within those latitude and longitude ranges. The ST_DISTANCE_SPHERE function is a convenient way to calculate the distance. Using the Laravel ORM, your code might look something like this:

 $bounding_box = create_coordinates_bounding_box(latitude: $latitude, longitude: $longitude);
 DB::raw("
        ST_Distance_Sphere(
            point($longitude, $latitude),
            point(longitude, latitude)
        ) * 0.000621371 as distance
        " ))
        ->from('users')
        ->whereBetween('latitude', [$bounding_box['min_latitude'], $bounding_box['max_latitude']])
        ->whereBetween('longitude', [$bounding_box['min_longitude'], $bounding_box['max_longitude']])
        ->havingRaw('distance < '.config('distance.search_radius'))
        ->orderBy('distance')
        ->limit(5);
           

So yeah or using the StackOverflow formula

SELECT
 *,(6371 *
    ACOS(COS(RADIANS(specific_user_longitude)) * COS(RADIANS(user_coordinates.longitude)) *
    COS(RADIANS(user_coordinates.latitude) - RADIANS(specific_user_latitude)) + SIN(RADIANS(specific_user_longitude)) *
    SIN(RADIANS(user_coordinates.longitude)))) as distance
FROM
 user_coordinates
WHERE
 latitude BETWEEN min_latitude AND max_latitude
        AND longitude BETWEEN mix_longitude AND max_longitude
    HAVING distance < 3
ORDER BY distance
LIMIT 5;

So, that’s about it. If you want a more detailed explanation, you can check out this video: Link to Video.

I hope this helps!