Database: Best performance way to query geo location data?

Question

I have a MySQL database. I store homes in the database and perform literally just 1 query against the database, but I need this query to be performed super fast, and that's to return all homes within a square box geo latitude & longitude. ``` SELECT * FROM homes WHERE geolat BETWEEN ??? AND ??? AND geolng BETWEEN ??? AND ??? ``` How is the best way for me to store my geo data so that I can perform this query of displaying all home within the geolocation box the quickest? Basically: - Am I using the best SQL statement to perform this query the quickest? - Does any other method exist, maybe not even using a database, for me to query the fastest way a result of homes within a boxed geolocation bounds? In case it helps, I've include my database table schema below: ``` CREATE TABLE IF NOT EXISTS `homes` ( `home_id` int(10) unsigned NOT NULL auto_increment, `address` varchar(128) collate utf8_unicode_ci NOT NULL, `city` varchar(64) collate utf8_unicode_ci NOT NULL, `state` varchar(2) collat…

Accepted Answer

There is a good paper on MySQL geolocation performance here.

EDIT Pretty sure this is using fixed radius. Also I am not 100% certain the algorithm for calculating distance is the most advanced (i.e. it'll "drill" through Earth).

What's significant is that the algorithm is cheap to give you a ball park limit on the number of rows to do proper distance search.

The algorithm pre-filters by taking candidates in a square around the source point, then calculating the distance in miles.

Pre-calculate this, or use a stored procedure as the source suggests:

```
# Pseudo code
# user_lon and user_lat are the source longitude and latitude
# radius is the radius where you want to search
lon_distance = radius / abs(cos(radians(user_lat))*69);
min_lon = user_lon - lon_distance;
max_lon = user_lon + lon_distance;
min_lat = user_lat - (radius / 69);
max_lat = user_lat + (radius / 69);
```

```
SELECT dest.*,
  3956 * 2 * ASIN(
    SQRT(
      POWER(
        SIN(
          (user_lat - dest.lat) * pi() / 180 / 2
        ), 2
      ) + COS(
        user_lat * pi() / 180
      ) * COS(
        dest.lat * pi() / 180
      ) * POWER(
        SIN(
          (user_lon - dest.lon) * pi() / 180 / 2
        ), 2
      )
    )
  ) as distance
FROM dest
WHERE 
  dest.lon between min_lon and max_lon AND
  dest.lat between min_lat and max_lat
HAVING distance < radius
ORDER BY distance
LIMIT 10
```

Database: Best performance way to query geo location data?

Solution

Problem