MYSQL Geo Search having distance performance

Question

I have a mysql select statement for a search on my website which is having performance problems when the site gets really busy. The query below searches for adverts from a table with over 100k records, within 25 miles of the given lat and lon and sorts by distance. The number of miles can differ as it is selected by the user.

The problem is that I think it is slow because it does the calculations for all records in the table rather than ones that are within 25 miles of the lat and lon. Is it possible to amend this query so that where clause selects only adverts within 25 miles? Ive read about bounding box's and spatial indexes but im not sure how to apply them to this query, do I need to add a where clause that selects records 25 miles radius of the lat and lon, how do I do this?

SELECT 
    adverts.*, 
    round(sqrt((((adverts.latitude - '53.410778') * (adverts.latitude - '53.410778')) * 69.1 * 69.1) + ((adverts.longitude - '-2.97784') * (adverts.longitude - '-2.97784') * 53 * 53)), 1) as distance
FROM 
    adverts
WHERE 
    (adverts.type_id = '3')
HAVING 
    DISTANCE < 25
ORDER BY 
    distance ASC 
LIMIT 120,10

Edit: Updated to include table schema, please note that table is more complicated and so is the query but I have removed the things which aren't necessary for this problem.

CREATE TABLE `adverts` (
`advert_id` int(10) NOT NULL AUTO_INCREMENT,
`type_id` tinyint(1) NOT NULL,
`headline` varchar(50) NOT NULL,
`description` text NOT NULL,
`price` int(4) NOT NULL,
`postcode` varchar(7) NOT NULL,
`latitude` float NOT NULL,
`longitude` float NOT NULL,
PRIMARY KEY (`advert_id`),
KEY `latlon` (`latitude`,`longitude`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8

when i do an explain on the mysql statement the number of rows is set to 67900 which is a lot more than is in a 25 mile radius, also the extra is set to "Using where; Using filesort".

The query takes 0.3 seconds which is really slow, especially when the websites gets lots of requests per second.

Answer 1

The fastest way to do this is to use the geospatial extensions for MySQL, which should be easy enough as you are already using a MyISAM table. The documentation for these extensions can be found here: http://dev.mysql.com/doc/refman/5.6/en/spatial-extensions.html

Add a new column with a POINT datatype:

ALTER TABLE `adverts` 
ADD COLUMN `geopoint` POINT NOT NULL AFTER `longitude`
ADD SPATIAL KEY `geopoint` (`geopoint`)

You can then populate this column from your existing latitude and longitude fields:

UPDATE `adverts` 
SET `geopoint` = GeomFromText(CONCAT('POINT(',`latitude`,' ',`longitude`,')'));

The next step is to create a bounding box based on the input latitude and longitude that will be used in your WHERE clause as a CONTAINS constraint. You will need to determine a set of X,Y POINT coordinates that work for your requirements based on the desired search area and given starting point.

Your final query will search for all POINT data that is within your search POLYGON, and you can then use a distance calculation to further refine and sort your data:

SELECT a.*, 
    ROUND( SQRT( ( ( (adverts.latitude - '53.410778') * (adverts.latitude - '53.410778') ) * 69.1 * 69.1 ) + ( (adverts.longitude - '-2.97784') * (adverts.longitude - '-2.97784') * 53 * 53 ) ), 1 ) AS distance
FROM adverts a
WHERE a.type_id = 3
AND CONTAINS(a.geopoint, GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))'))
HAVING distance < 25
ORDER BY distance DESC
LIMIT 0, 30

Note that the GeomFromText('Polygon((0 0,0 3,3 3,3 0,0 0))') in the above will not work, you will need to replace the coordinates with valid points around your search start. If you expect the lat/long to change, you should consider using a trigger to keep the POINT data and associated SPATIAL KEY up to date. With large datasets you should see vastly improved performance over calculating a distance for every record and filtering using a HAVING clause. I personally defined functions for use in determining the distance and creating the bounding POLYGON.

Answer 2

There a few ways to speed up your query, personally I'd take advantage of the POW function.

Returns the value of X raised to the power of Y.

Manual multiplication will slow your query down with large tables, although achieving the same result.

SELECT a .* , 
    round( sqrt( 
        (POW( a.latitude -'53.410778', 2)* 68.1 * 68.1) + 
        (POW(a.latitude -'-2.97784', 2) * 53.1 * 53.1) 
     )) AS distance
 FROM adverts a
     WHERE a.type_id = 3
     HAVING distance < 25
     LIMIT 0 , 30

The above query runs in 0.0008 sec on table schema with 10,000 records (Your query tested on the same table schema took 0.0129 sec), so it was a considerable increase in performance.

Other Optimization Tips

• An sql query becomes faster if you use the actual columns names in SELECT statement instead of *.
• Fully reference the table name mydatabase.mytable.
• If you have to ORDER BY use the primary key (Its an indexed field, or create an index on the field you intend on ORDERING).
• Use mysql framework functions for math calculations it will speed up the process.
• And finally try and make your queries as simple as possible with these steps (the simpler the faster).

Sources

• http://beginner-sql-tutorial.com/sql-query-tuning.htm
• http://infolab.stanford.edu/~hyunjung/cs346/ioannidis.pdf
• http://www.webmasterworld.com/forum112/59.htm
• http://odetocode.com/code/237.aspx
• http://blog.sqlauthority.com/2007/06/14/sql-server-easy-sequence-of-select-from-join-where-group-by-having-order-by/