Optimising SQL distance query

Question

I'm running an MySQL query that returns results based on location. However I have noticed recently that its really slowing down my PHP app. I used CodeIgniter and the profiler shows the query taking 4.2seconds. The geoname table has 500,000 rows. I have some indexes on the key columns, how else can speed up this query?

Here is my SQL:

SELECT `products`.`product_name`
     , `geoname`.`geonameid`
     , `geoname`.`latitude`
     , `geoname`.`longitude`
     , `products`.`product_id`
     , AVG(ratings.vote) as rating
     , count(comments.comment_id) as total_comments
     ,   (6371 * acos(cos(radians(38.7666667)) 
               * cos(radians(geoname.latitude)) 
               * cos(radians(geoname.longitude) - radians(-3.3833333)) 
             +   sin(radians(38.7666667)) 
               * sin(radians(geoname.latitude)))
         ) AS distance
FROM (`foods`)
JOIN `geoname` ON `geoname`.`geonameid` = `products`.`geoname_id`
LEFT JOIN `ratings` 
  ON `ratings`.`var_id` = `products`.`product_id`
LEFT JOIN `comments` 
  ON `comments`.`var_id` = `products `.`product_id`
WHERE `products`.`product_id` != 82
GROUP BY `products`.`product_id`
HAVING `distance` < 99
ORDER BY `distance`
LIMIT 10

Answer 1

If you ask MySQL to EXPLAIN PLAN, I think you'll find that the distance calculations are rendering your indexes useless. You're forcing the query engine to do a TABLE SCAN.

The only way to save the situation would be to put distance in a separate column and index that.

Answer 2

Let's start with the query itself the cos(radians(geoname.latitude)) and other functions seem like an invariant, so we can do a little preprocessing and store the calculated values in the table. (calculating trig functions mostly involve using a series expansio which is costly).

6371 * acos(cos(radians(38.7666667)) - this is equal to radians(38.76667) * 6371 so why us it? it costs.

Secondly if You don't care THAT much about precision You can precalc the radians itself for let's say 10000 points from 0 to pi/2 - that should give a nice approximation, up to 4 decimal numbers eg less than a km

(6371 * acos(cos(radians(38.7666667))
 * cos(radians(geoname.latitude))
 * cos(radians(geoname.longitude) - radians(-3.3833333))
+ sin(radians(38.7666667))
* sin(radians(geoname.latitude))))

also remember that sin(a) when a > pi/2 and a < pi equals to sin(pi - a) when a> pi and a < 3/2 pi equals to -sin(a-pi) and when a > 3/2 pi and a < 2pi it's equal to -sin (2pi - a). similiar functions can be made for cos function.

Try this and see if it helps. luke

Answer 3

If you can approximate any search location to, say, 1000 on 10000 points in space, you could, in fact, store distances in a helper table along the lines of:

create table distance (
position1_id int,
position2_id int,
distance int -- probably precise enough
)

with an index on position1_id and distance. The table would have anywhere from a 10^6 to 10^8 rows, but using index data, I imagine you could quickly retrieve the nearest position2_id. Even if this wouldn't be precise enough for you (because of having to settle for limited resolution), it would allow you to quickly eliminate probably >99% of the locations you don't care about in a specific case.