Way to improve performance in MySQL on POINT(lat, long)

Question

I have an application that needs to query a table with latitude and longitude coordinates, which are stored using MYSQL's POINT datatype.

I have a stored function that finds nearby lats and longs within a given radius of a given GPS location. However, my table will contain hundreds of thousands of entries, so performance needs to be optimal.

I have wrote the following stored function, but it takes about 4.01 seconds to return about 9,000 rows out of a possible 800,000+ rows. Is there a better way of finding nearby GPS coordinates?

Here is my stored function:

    CREATE PROCEDURE `FindNearbyPoints`(
    IN RADIUS FLOAT,
    IN LAT FLOAT,
    IN LON FLOAT
)
BEGIN

    DECLARE EARTH_RADIUS FLOAT DEFAULT 3959;
    DECLARE maxLat FLOAT DEFAULT (LAT + DEGREES(RADIUS/EARTH_RADIUS));
    DECLARE minLat FLOAT DEFAULT (LAT - DEGREES(RADIUS/EARTH_RADIUS));

    /* compensate for degrees longitude getting smaller with increasing latitude*/
    DECLARE maxLon FLOAT DEFAULT (LON + DEGREES(RADIUS/EARTH_RADIUS/COS(RADIANS(LAT))));
    DECLARE minLon FLOAT DEFAULT (LON - DEGREES(RADIUS/EARTH_RADIUS/COS(RADIANS(LAT))));

    SELECT *, acos(sin(LAT)*sin(radians(X(Location))) + cos(LAT)*cos(radians(X(Location)))*cos(radians(Y(Location))-LON))*EARTH_RADIUS As D
    FROM (
        Select *
        From my_table
        Where X(Location)>minLat And X(Location)<maxLat
        And Y(Location)>minLon And Y(Location)<maxLon
    ) AS FIRST_CUT
    WHERE acos(sin(LAT)*sin(X(Location)) + cos(LAT)*cos(X(Location))*cos(Y(Location)-LON))*EARTH_RADIUS < RADIUS
    ORDER BY D;

END

Much of my inspiration for the function came from: http://www.movable-type.co.uk/scripts/latlong-db.html

Answer 1

I'm not sure how your database is set up, but you might look into using SPATIAL indexing and then constructing a minimal bounding rectangle to perform the query. Once you return records via the bounding box, you can quickly order them by distance and eliminate those that are outside of your radius. We use this kind of indexing in genomics and routinely query datasets of a billion rows quite effectively.

There are details on spatial indexing in the mysql docs.