Find nearest postcode to Latitude Longitude in MySQL

Question

I have a table Postcode which holds all UK postcode (approx 1.8m i think)

CREATE TABLE `Postcode` (
  `ID` int(11) NOT NULL AUTO_INCREMENT,
  `Postcode` varchar(8) DEFAULT NULL,
  `Postcode_Simple` varchar(8) DEFAULT NULL,
  `Positional_Quality_Indicator` int(11) DEFAULT NULL,
  `Eastings` int(11) DEFAULT NULL,
  `Northings` int(11) DEFAULT NULL,
  `Latitude` double DEFAULT NULL,
  `Longitude` double DEFAULT NULL,
  `LatLong` point DEFAULT NULL,
  PRIMARY KEY (`ID`),
  UNIQUE KEY `Postcode` (`Postcode`),
  KEY `Postcode_Simple` (`Postcode_Simple`),
  KEY `LatLong` (`LatLong`(25))
) ENGINE=InnoDB AUTO_INCREMENT=1755933 DEFAULT CHARSET=latin1;

What I want to achieve is...Given a co-ordinate, locate the postcode nearest to the co-ordinate. Problem is I'm having a bit of an issue with the query (actually in a stored procedure) I've written to do this. The query is:

SELECT
    Postcode
FROM
    (SELECT
        Postcode,
        GLENGTH(
            LINESTRINGFROMWKB(
                LINESTRING(
                    LatLong, 
                    GEOMFROMTEXT(CONCAT('POINT(', varLatitude, ' ', varLongitude, ')'))
                )
            )
        ) AS distance
    FROM
        Postcode
    WHERE
        NOT LatLong IS NULL) P
ORDER BY
    Distance
LIMIT
    1;

The problem I'm having is that the query takes some 12seconds to run and I cannot have it take that long to get a result. Can anyone think of any ways I can reliably speed this query up?

(Here's the explain for the query)

id select_type table      type possible_keys key    key_len ref    rows    Extra
1  PRIMARY     <derived2> ALL  (NULL)        (NULL) (NULL)  (NULL) 1688034 Using filesort
2  DERIVED     Postcode   ALL  LatLong       (NULL) (NULL)  (NULL) 1717998 Using where

I've been trying to think of a way to narrow down the initial amount of data that I must perform the distance calculation on, but I haven't been able to come up with anything that doesn't restrict to finding postcodes within a given distance.

Answer 1

Maybe try something along the lines of:

SELECT Postcode, lat, lon
FROM
(
SELECT Postcode, MAX(latitude) AS lat, MAX(longitude) AS lon
FROM PostCode

-- field name
GROUP BY Postcode 

HAVING MAX(latitude)<varLatitude AND MAX(longitude)<varLongitude

LIMIT 1
) AS temp

which will basically bring the postcode whose lat and lon are less than the ones you specify but greater than any other lat/lon combination that is less than your vars; so effectively the closest lat/lon to your vars, hence the closest postcode. You can try the same using MIN and greater then instead to go the other way round.

The above will only get you a single result/postcode. If you're looking to have something niftier with like finding a group of postcodes given in a specific radius of lat/long then you should have a look at the formula explained at https://developers.google.com/maps/articles/phpsqlsearch_v3#findnearsql

Answer 2

I've written a tutorial on pretty much exactly what you're after.

Basically, you're on the right lines. In order to improve the efficiency of the search, you'll need to reduce the number of GLength() calculations made by making use of a spatial index on your LatLong field. If you restrict the search to a refined area, such as polygon 10 miles around the point you're comparing the postcodes to, you'll find the query is much quicker.