List:General Discussion« Previous MessageNext Message »
From:SGreen Date:August 24 2005 8:56pm
Subject:Re: ORDER BY distance from a point
View as plain text  
Scott Gifford <sgifford@stripped> wrote on 08/24/2005 04:45:36 PM:

> Hello,
> 
> I'd like to sort my query results based on their distance from a given
> point.  The actual data I have will be in (longitude,latitude) format,
> but I can convert to something else if that will work better.
> 
> For example, I may have data like this
> 
>     Item               Latitude      Longitude
>     ----               --------      ---------
>     Scott's House      37.4419       -122.1419
>     Tom's House        37.4519       -122.2419
>     Mary's House       37.4619       -122.3419
>     Sally's House      37.4719       -122.4419
> 
> and I'd like to see these rows sorted by distance from (38,-121).
> 
> My actual data has many more columns (about 30) and rows (about
> 25,000), and joins in a few other tables.  Most queries will have a
> LIMIT clause with 10 results, possibly starting a few hundred rows in
> (LIMIT 240,10).  Currently all searches take much less than 1 second,
> and I'd like to keep it that way.
> 
> Is there a way to have MySQL do this query efficiently?  I know how to
> do the calculations, but MySQL has to calculate the Great Circle
> distance to this point for each row in the table, which is slow for
> 25,000 rows.
> 
> I tried using the GIS functions, but in the version of MySQL I have
> (4.1.7 on Debian Linux) the Distance() function isn't implemented, so
> that doesn't help much.  I'm willing to look at upgrading MySQL if
> that will help.
> 
> My database friends tell me I want to use an RTREE index, but I
> haven't yet found a version of MySQL that implements those yet except
> with the GIS functions.
> 
> Thanks for any advice, help, or hints!
> 
> ----ScottG.
> 

One strategy would be to capture a set of rows into a temporary table 
using the Pythagorean distance formula as an approximation of the Great 
Circle distance and then perform the "heavier" Great Circle calculations 
on that subset. That way you only need to do the heavier trig calcs on 
those few records that fall into your approximation zone. To order by the 
appx distance,you won't even need to take the square root of the sums of 
the squares as it would just slow you down. 

True, this approximation will only be close for small comparison regions 
(+/- 20 degrees around a point between within the band of +/- 60 degrees 
latitude) but that covers a lot of ground, don't you think?

Shawn Green
Database Administrator
Unimin Corporation - Spruce Pine
Thread
ORDER BY distance from a pointScott Gifford24 Aug
  • Re: ORDER BY distance from a pointSGreen24 Aug
  • Re: ORDER BY distance from a pointdouglass_davis25 Aug