Spatial Indexes: MySQL

In two previous articles I introduced The spherical Earth model and importing data into SQLite for querying geographical data. In this article we're going to have a look at importing the data into MySQL and finding out how to best store and query spatial data in the databases.

MySQL

MySQL has some support for Spatial Extensions, but it's not particularly useful. For example, there is no way to query anything within the radius around a specific point. Their community pages list a method of implementing it, but it only calculates for a flat Earth model.

Instead, we'll have to implement our own algorithms again. But first of all, let us import the data into MySQL. First we create the MySQL database:

derick@whisky:~$ mysqladmin -u root -p create poi
mysql> CREATE TABLE poi(id int, type int, lat float, lon float, name char(255), address char(255), cuisine char(64), phone char(18));

And then we take the script from the previous article on importing data, and change the third line from:

$d = ezcDbFactory::create( 'sqlite://' . dirname( __FILE__ ) . '/pois.sqlite' );

to:

$d = ezcDbFactory::create( 'mysql://root:root@localhost/poi' );

Of course, substitute the username and password (root, root) and the database name (poi) to one that suits yourself. We then run again:

php parseoi.php.txt great_britain_pubs.osm

And check that our import is complete:

mysql> SELECT count(*) from poi\G
*************************** 1. row ***************************
count(*): 28147

Now that we have all the POIs imported, we can query the database. Because MySQL doesn't have working spatial extensions, nor the register-function capabilities from SQLite such as we saw in the previous article, we have to come up with a new solution. The most obvious one is writing a stored procedure for the task, another (non-explored option) would be to write a user defined function. Writing the stored procedure is simple enough; we just have to convert the distance() function to SQL. On the MySQL command line you can enter:

delimiter //

CREATE FUNCTION distance (latA double, lonA double, latB double, LonB double)
    RETURNS double DETERMINISTIC
BEGIN
    SET @RlatA = radians(latA);
    SET @RlonA = radians(lonA);
    SET @RlatB = radians(latB);
    SET @RlonB = radians(LonB);
    SET @deltaLat = @RlatA - @RlatB;
    SET @deltaLon = @RlonA - @RlonB;
    SET @d = SIN(@deltaLat/2) * SIN(@deltaLat/2) +
        COS(@RlatA) * COS(@RlatB) * SIN(@deltaLon/2)*SIN(@deltaLon/2);
    RETURN 2 * ASIN(SQRT(@d)) * 6371.01;
END//

Fetching all the pubs within a 250 meter radius around 51.5375°N, 0.1933°W is than as easy as running:

mysql> SELECT name, address, phone
       FROM poi
       WHERE DISTANCE(lat, lon, 51.5375, -0.1933) < 0.25;

With the result being:

| name            | address                        | phone           |
+-----------------+--------------------------------+-----------------+
| Mrs Betsy Smith | Kilburn High Road 77 , NW6 6HY | +44 20 76245793 |
| The Cock Tavern | Kilburn High Road 125          | NULL            |
| The Old Bell    | NULL                           | NULL            |
| The Westbury    | Kilburn High Road 34 , NW6 5UA | +44 20 76257500 |
+-----------------+--------------------------------+-----------------+
4 rows in set (0.72 sec)

If we want to also include the distance from the centre point in the result, we need to modify the query to:

mysql> SELECT name, DISTANCE(lat, lon, 51.5375, -0.1933) AS dist
       FROM poi
       HAVING dist < 0.25
       ORDER BY dist;

with as result:

| name            | dist                |
+-----------------+---------------------+
| Mrs Betsy Smith | 0.00825473345748987 |
| The Cock Tavern |     0.2420193460511 |
| The Old Bell    |   0.103123484090313 |
| The Westbury    |   0.150294300836645 |
+-----------------+---------------------+
4 rows in set (0.72 sec)

In both cases, the query takes 0.72 seconds. This is not overly fast, and the main reason for this is that the distance() function has to be called for every row in the table. An index can not be created on this either. However, what we can do is to filter out the results roughly first, by calculating a bounding box of latitude/longitude pairs around the centre point. Calculating the latitude boundaries can be done by:

d = (distInKm / 6371.01 * 2π) * 360
lat1 = centreLat - d
lat2 = centreLat + d

In our example that becomes:

d = (0.250 / 6371.01 * 2π) * 360 = 0.0022483
lat1 = 51.5375 - 0.0022483 = 51.5352.. -> 51.5351
lat2 = 51.5375 + 0.0022483 = 51.5397.. -> 51.5398

Or in PHP:

<?php
function findLatBoundary($dist, $lat, &$lat1, &$lat2)
{
    $d = ($dist / 6371.01 * 2 * M_PI) * 360;
    $lat1 = $lat - $d;
    $lat2 = $lat + $d;
}
?>

We round slightly up and down to combat inaccuracies in the calculations—it is a rough estimate after all. After adding the index on the lat column, and the index on the lon column, we reissue the query:

mysql> CREATE index poi_lat ON poi(lat);
mysql> CREATE index poi_lon ON poi(lon);

mysql> SELECT name, DISTANCE(lat, lon, 51.5375, -0.1933) AS dist
       FROM poi
       WHERE lat BETWEEN 51.5351 AND 51.5398
       HAVING dist < 0.25;

Which returns the same result as before, but faster:

| name            | dist                |
+-----------------+---------------------+
| The Westbury    |   0.150294300836645 |
| The Old Bell    |   0.103123484090313 |
| Mrs Betsy Smith | 0.00825473345748987 |
| The Cock Tavern |     0.2420193460511 |
+-----------------+---------------------+
4 rows in set (0.01 sec)

We can pre-filter the result set even more, by also limiting on the longitude boundary. This involves a few more calculations than for the latitude boundaries. The distance in degrees longitude that belongs to a distance in km depends on the latitude of the location. So first we need to calculate the latitude boundaries as we have done above, and with that information calculate the longitude boundaries.

In the first step (red), we calculate the northern and southern boundaries of the circle. We then calculate the western and eastern boundaries for the northern boundary (green), and southern boundary (blue).

In PHP this algorithm becomes:

<?php
function findLonBoundary($dist, $lat, $lon, $lat1, $lat2, &$lon1, &$lon2)
{
    $d = $lat - $lat1;

    $d1 = $d / cos(deg2rad($lat1));
    $d2 = $d / cos(deg2rad($lat2));

    $lon1 = min($lon - $d1, $lon - $d2);
    $lon2 = max($lon + $d1, $lon + $d2);
}
?>

If we use both functions we calculate as boundaries:

<?php
$dist = 0.25;
$lat = 51.5375;
$lon = -0.1933;

findLatBoundary($dist, $lat, $lat1, $lat2);
findLonBoundary($dist, $lat, $lon, $lat1, $lat2, $lon1, $lon2);

echo "SELECT name, DISTANCE(lat, lon, $lat, $lon) AS dist
      FROM poi
      WHERE lat BETWEEN $lat1 AND $lat2
        AND lon BETWEEN $lon1 AND $lon2
      HAVING dist < $dist
      ORDER BY dist;\n";
?>

Which returns the query to execute:

SELECT name, DISTANCE(lat, lon, 51.5375, -0.1933) AS dist
FROM poi
WHERE lat BETWEEN 51.535251699514 AND 51.539748300486
  AND lon BETWEEN -0.19691479627963 AND -0.18968520372037
  HAVING dist < 0.25
  ORDER BY dist;

If we run this query, we get as result:

| name            | dist                |
+-----------------+---------------------+
| Mrs Betsy Smith | 0.00825473345748987 |
| The Old Bell    |   0.103123484090313 |
| The Westbury    |   0.150294300836645 |
| The Cock Tavern |     0.2420193460511 |
+-----------------+---------------------+
4 rows in set (0.00 sec)

As you can see, we are getting the result a lot faster now—0.00 sec vs 0.72 sec. Please do note, that if we would just have used the boundaries without using the HAVING dist < 0.25 clause, we would have gotten one extra result that is slightly too far away (0.281 km):

| name            | dist                |
+-----------------+---------------------+
| Mrs Betsy Smith | 0.00825473345748987 |
| The Old Bell    |   0.103123484090313 |
| The Westbury    |   0.150294300836645 |
| The Cock Tavern |     0.2420193460511 |
| Bar Hemia       |   0.281138534935208 |
+-----------------+---------------------+

Conclusion

In this article we saw how we can use a MySQL stored procedure to find our pubs and bars within a certain distance from a central location. In the next part, we will be looking on how to solve the same problem with PostgreSQL.