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 point | Scott Gifford | 24 Aug |

• Re: ORDER BY distance from a point | SGreen | 24 Aug |

• Re: ORDER BY distance from a point | douglass_davis | 25 Aug |