Quick and dirty location search tutorial

Leonardo Andrade

Some months ago, have been asked about how to generate a search result ordered by distance, without using spatial DB predicated.

For a situation such as this, the steps are the following:

  1. Store the latitude and longitude in numeric fields in the table, something like this: create table poi(id int auto_increment primary key, name varchar(64), lat float, lon float);

  2. Create the indexes (this is important, other) create index idx_poi_lat on poi(lat); create index idx_poi_lon on poi(lon);

  3. Given the point (pt_lat, pt_lon) and distance do the radius query with bounding box filtering.

About the queries, if we want, for example, to search for services around point 47.3569, 8.5432 up to distance = 10km, the query is the following:

select name, lat, lon, SQRT(POW(lat-47.3569,2)+ POW(lon-8.5432 , 2)) * 111.32 as distance from poi where lat < (47.3569 + 0.08983) and lat > (47.3569 - 0.08983) and lon < (8.5432 + 0.08983) and lon > (8.5432 - 0.08983) having distance < 10 order by distance asc;

notes:

  • conversion from degrees to KM is degree 40075.16/360 = 111.32, so for 10 km, we will search for radius in degrees: 10.0/111.32 = 0.0898. This variable will be computed when building the query.
  • filtering by lat and long makes use of the B-trees of the Mysql non-geographic index

For a more precise solution, the possible improvements are:

  • Use a storage with spatial indexing such as R-trees. PostgreSQL/Posgis, later versions of MySQL with extensions can do the trick. MongoDB also as built-in geographic indexes

  • store the coordinates in projected system (eg, Google Mercator, or a more localized one), it makes the precision better