What is the fastest way to select nearest geographical place from mysql database?

Question

I have a table in a MySQL database containing geographic coordinates and other information about places. Each row in the table represents a geographical place and has coordinates such as: Latitude = 45.05235 and Longitude = 8.02354 which is a place somewhere in Europe.

Given on some input geographical coordinates (same format) I need to select from that table the nearest place, or the nearest places within some radius.

I'm already using indices, however I want to speed up the process since these functions are used many times.

It might help if I could select the nearest place or places within a certain radius directly with one query. Any other solutions are also very welcome of course.

I made a function that gets the nearest place (which is working but slow):

<?php
//Function for getting nearest destinations:
function nearest_destination($lat1,$lon1,$radius,$type,$maxdistance){
  //Determine geo bounds:
  $lonlow = $lon1 - rad2deg($maxdistance/6371);
  $lonhigh = $lon1 + rad2deg($maxdistance/6371);
  $latlow = $lat1 - rad2deg($maxdistance/6371);
  $lathigh = $lat1 + rad2deg($maxdistance/6371);
  
  //Database details and connect to database
  include(realpath($_SERVER["DOCUMENT_ROOT"]).'/connect_to_db.php'); 
  //Set initial counters to zero
  $ii=0;
  $i=0;
  
  while($row = mysql_fetch_array($result, MYSQL_ASSOC)){
    $shortnamelist[$ii]=$row['shortname'];
    $fullnamelist[$ii]=$row['fullname'];
    $latitudelist[$ii]=$row['latitude'];
    $longitudelist[$ii]=$row['longitude'];
    $lon2=$row['longitude'];
    $lat2=$row['latitude'];
    
    //Calculate the distance:
    $delta_lon = $lon2 - $lon1;
    $earth_radius = "6371"; # in km
    $distance  = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($delta_lon)) ;
    $distance  = acos($distance);
    $distance  = $earth_radius*$distance;
    $distance  = round($distance, 4);
    $distancelist[$ii] = $distance;
    $ii=$ii+1;
  }
  
  //Select position of nearest, and select the destination
  if(isset($distancelist)){
    $minkey=array_keys($distancelist, min($distancelist));
    $minkey=$minkey[0];
    
    $fullname=$fullnamelist[$minkey];
    $shortname=$shortnamelist[$minkey];
    $latitude=$latitudelist[$minkey];
    $longitude=$longitudelist[$minkey];
    
    // remove the big arrays to conserve memory:
    unset($fullnamelist);
    unset($latitudelist);
    unset($longitudelist);
    unset($distancelist);
    unset($shortnamelist);
  }
  
  if(isset($destinid)=='TRUE'){
    $nearest_destination = array("shortname" => $shortname, "fullname" => $fullname, "latitude" => $latitude, "longitude" => $longitude, "distancelist" => $distancelisting);}
  else $nearest_destination = 0;
  mysql_close ();
  return $nearest_destination;
}
?>

This is the function that selects the nearest places within a certain radius (working but slow):

<?php
//Function for getting nearest destinations:
function nearest_destination($lat1,$lon1,$radius,$type,$maxdistance){
  //Determine geo bounds:
  $lonlow = $lon1 - rad2deg($maxdistance/6371);
  $lonhigh = $lon1 + rad2deg($maxdistance/6371);
  $latlow = $lat1 - rad2deg($maxdistance/6371);
  $lathigh = $lat1 + rad2deg($maxdistance/6371);
  
  // Convert from string to number:
  $lon1=floatval($lon1);
  $lat1=floatval($lat1);
  
  //Database details and connect to database
  include(realpath($_SERVER["DOCUMENT_ROOT"]).'/connect_to_database.php'); //Get DB login details
  
  //Select data from destinations table:
  $sql="SELECT shortname, fullname, latitude, longitude FROM destinations WHERE type='$type' AND longitude > $lonlow AND longitude < $lonhigh AND latitude > $latlow AND latitude < $lathigh";
  $result=mysql_query($sql);
  
  //Set initial counter to zero
  $i=0;
  
  while($row = mysql_fetch_array($result, MYSQL_ASSOC)){
    $lon2=$row['longitude'];
    $lat2=$row['latitude'];
    $lon2=floatval($lon2);
    $lat2=floatval($lat2);
    
    //Calculate the distance:
    $delta_lon = $lon2 - $lon1;
    $earth_radius = "6371"; # in km
    $distance  = sin(deg2rad($lat1)) * sin(deg2rad($lat2)) + cos(deg2rad($lat1)) * cos(deg2rad($lat2)) * cos(deg2rad($delta_lon)) ;
    $distance  = acos($distance);
    $distance  = $earth_radius*$distance;
    $distance  = round($distance, 4);
    
    //If distance is smaller than the radius the destination is saved in the array:
    if($distance<$radius){
      $fullname[$i]=$row['fullname'];
      $shortname[$i]=$row['shortname'];
      $latitude[$i]=$row['latitude'];
      $longitude[$i]=$row['longitude'];
      $distancelisting[$i] = $distance;
      $i=$i+1;
    }
  }
  
  if(isset($destinid)=='TRUE'){
    $nearest_destination = array("shortname" => $shortname, "fullname" => $fullname, "latitude" => $latitude, "longitude" => $longitude, "distancelist" => $distancelisting);
  }else $nearest_destination = 0;
  mysql_close ();
  return $nearest_destination;
}
?>

Answer 1

Feel free to modify as needed:

<?php
$center_lat = $_GET["lat"];
$center_lng = $_GET["lng"];
$radius = $_GET["radius"];
$unit = $_GET["unit"];
$unitConst = $unit == "mi" ? 3959 : 6371;
$sql = sprintf("SELECT Address, City, State, Country, PostalCode, PhoneNumber, Lat, Lng, ($unitConst * acos(cos(radians('%s')) * cos(radians(Lat)) * cos(radians(Lng) - radians('%s')) + sin(radians('%s')) * sin(radians(Lat)))) AS Distance FROM destinations WHERE (Lat != '0' AND Lng !=0) HAVING distance < '%s' ORDER BY distance", mysql_real_escape_string($center_lat), mysql_real_escape_string($center_lng), mysql_real_escape_string($center_lat), mysql_real_escape_string($radius));
?>

Answer 2

Using mysql gis support will improve your speeds as it was created for this. If you are constantly reading and comparing distances it will be worth it to use postgis which is a full support geospatial database. It will let you index your points for effecient distance queries. MySQL does provide limited support and relies on GEOS http://trac.osgeo.org/geos/

http://forge.mysql.com/wiki/GIS_Functions

http://postgis.refractions.net/

The most relevant link for this was posted by a comment by Anigel it gives an exact answer to your question Fastest Way to Find Distance Between Two Lat/Long Points