SQL Query for Performing Radius Search based on Latitude Longitude

Question

We have a restaurant table that has lat-long data for each row.

We need to write a query that performs a search to find all restaurants within the provided radius e.g. 1 mile, 5 miles etc.

We have the following query for this purpose:

***Parameters***

Longitude: -74.008680
Latitude: 40.711676
Radius: 1 mile

***Query***

SELECT *
FROM restaurant
WHERE (
POW( ( 69.1 * ( Longitude - -74.008680 ) * cos( 40.711676 / 57.3 ) ) , 2 ) + POW( ( 69.1 * ( Latitude - 40.711676 ) ) , 2 )
) < ( 1 *1 );

The table has about 23k rows. The size of the result set is weird at times e.g. for a 5.4 mile search, it gives back 880 rows and for 5.5 miles, it gives back 21k rows.

This table contains restaurant data for nyc - so the real distribution is not as per the result set.

Question: IS THERE ANYTHING WRONG With this query?

DB: MySQL, Longitude: DECIMAL(10,6), Latitude: DECIMAL(10,6)

Answer 1

IS THERE ANYTHING WRONG With this query?

In my opinion the WHERE clause is going to be slow because of the maths involved, and the use of functions in the WHERE clause will prevent the database using an index to speed the query - so, in effect, you will examine every restaurant in the database, and perform the great-circle maths on every row, every time you make a query.

Personally I would calculate the TopLeft and BottomRight co-ordinates of a square (which only needs to be crudly calculated using pythagoras) with sides equal to the range you are looking for, and then perform the more complicated WHERE clause test on the smaller subset of records that are within that Lat/Long square.

With an Index on Lat & Long in the database the query

WHERE     MyLat >= @MinLat AND MyLat <= @MaxLat
      AND MyLong >= @MinLong AND MyLong <= @MaxLong

should be very efficient

(Please note that I have no knowledge of MySQL specifically, only of MS SQL)

Answer 2

You may want to create a SPATIAL index on your table to make the searches faster.

To do this, add a POINT column to your table:

ALTER TABLE restaurant ADD coords POINT NOT NULL;

CREATE SPATIAL INDEX sx_restaurant_coords ON restaurant (coords);

SELECT  *
FROM    restaurant
WHERE   MBRContains(coords, LineString(Point(583734 - 1609, 4507223 - 1609), Point(583734 + 1609, 4507223 + 1609))
        AND GLength(LineString(Point(583734, 4507223), coords)) <= 1609

You should store coords as UTM coordinates within a single zone.

Answer 3

If your data is in SQL server database, you can use this:

CREATE PROC up_FindZipCodesWithinRadius

    @ZipCode char(5) ,
    @GivenMileRadius int
AS
SET NOCOUNT ON

DECLARE @lat1 float, 
    @long1 float

SELECT  @lat1= latitude,
    @long1 = longitude 
FROM ZipSource
WHERE zipcode = @ZipCode

SELECT ZipCode ,DistanceInMiles
FROM
(
    SELECT  ZipCode,3958.75 * ( Atan(Sqrt(1 - power(((Sin(@Lat1/57.2958) * Sin(latitude/57.2958)) + 
            (Cos(@Lat1/57.2958) * Cos(latitude/57.2958) * Cos((longitude/57.2958) - (@Long1/57.2958)))), 2)) / 
            ((Sin(@Lat1/57.2958) * Sin(latitude/57.2958)) + (Cos(@Lat1/57.2958) * Cos(latitude/57.2958) * 
            Cos((longitude/57.2958) - (@Long1/57.2958)))))) as DistanceInMiles
FROM ZipSource
) a
WHERE a.DistanceInMiles <= @GivenMileRadius
--AND ZipCode <> @ZipCode
ORDER BY DistanceInMiles

GO

EXEC up_FindZipCodesWithinRadius '35085',20
GO

DROP PROC up_FindZipCodesWithinRadius

Answer 4

Use a function, e.g. the one I posted here.

Then, query your restaurants, e.g. to get everything within a 5-mile radius

select * from restaurants 
  where dbo.udf_Haversine(latitude, longitude, @lat, @long) < 5

This performs fine with ZIP code data.