Indexing a mysql table for geo lookup using latitude/longitude

Question

I have a legacy innodb table Listing containing a business with latitude/longitude. Given an input latitude/longitude (below 51.2167/4.41667), the query is to return the first active, enabled, not-deleted 30 businesses in order of proximity (kilometers). A join with the accounts table is made to check the validity of the listing.

select 
    listing.*
from
    listing listing ,
    account account 
where
    listing.account_id = account.id 
    and listing.active = 1 
    and listing.approved = 1 
    and listing.deleted = 0 
    and listing.enabled = 1 
    and account.enabled = 1 
    and account.activated_by_user = 1 
group by
    listing.id
having
     111.222569*degrees(acos(sin(radians(listing.latitude))*sin(radians( 51.2167)) +cos(radians(listing.latitude))*cos(radians( 51.2167))*cos(radians(listing.longitude - 4.41667)))) < 250
order by
     111.222569*degrees(acos(sin(radians(listing.latitude))*sin(radians( 51.2167)) +cos(radians(listing.latitude))*cos(radians( 51.2167))*cos(radians(listing.longitude - 4.41667))))
limit 30;

The table Listing and Account each contain over 50,000 rows, but the query still takes on average 24sec to run. Without the order by, it takes 17sec.

I've already tried setting some indexes on active, approved, deleted, enabled. Can I rewrite the query or add certain indexes to efficiently perform this query - without changing the table structure?

+----+-------------+---------+-------------+-------------------------------------------------------------------------------------------------+-----------------------------------------------------------------+---------+------------------------+------+--------------------------------------------------------------------------------------------------------------------------------+
| id | select_type | table   | type        | possible_keys                                                                                   | key                                                             | key_len | ref                    | rows | Extra                                                                                                                          |
+----+-------------+---------+-------------+-------------------------------------------------------------------------------------------------+-----------------------------------------------------------------+---------+------------------------+------+--------------------------------------------------------------------------------------------------------------------------------+
|  1 | SIMPLE      | listing | index_merge | FKB4DC521D9306A80C,listing_active,listing_approved,listing_enabled,listing_deleted,index_test_1 | listing_active,listing_approved,listing_enabled,listing_deleted | 1,1,1,1 | NULL                   | 3392 | Using intersect(listing_active,listing_approved,listing_enabled,listing_deleted); Using where; Using temporary; Using filesort |
|  1 | SIMPLE      | account | eq_ref      | PRIMARY,account_enabled,account_activated_by_user,index_test_2                                  | PRIMARY                                                         | 8       | ctm.listing.account_id |    1 | Using where                                                                                                                    |
+----+-------------+---------+-------------+-------------------------------------------------------------------------------------------------+-----------------------------------------------------------------+---------+------------------------+------+--------------------------------------------------------------------------------------------------------------------------------+

Any help is greatly appreciated.

score 11 · Accepted Answer · answered May 08 '11 at 22:46

11

This is taking a long time because your query is computing that great-circle-distance formula with all the transcendental functions once for each row in your 50k row table (twice when you include the sort).

Can you limit the distance range of your search? You've probably noticed that most store-finder web apps have a pulldown menu item giving a choice "within 5 miles," "within 10 miles," and so forth.

If you CAN do this, you should add a WHERE clause to your search, and optimize it by putting an index on your LATITUDE column. Let's say you use the value RANGELIMIT for your search range limit, in miles.

Try this clause

WHERE LISTING.LATITUDE BETWEEN LOCATION.LATITUDE - (RANGELIMIT * 1.1508/60) 
                           AND LOCATION.LATITUDE + (RANGELIMIT * 1.1508/60)

This works because a nautical mile is almost exactly equal to one minute (1/60th) of a degree of latitude. The 1.1508 factor converts nautical miles into statute miles.

The clause I suggested will use a latitude index to narrow down the search, and you'll compute the great circle distance a whole lot less frequently.

You could also include a BETWEEN clause on longitude. But in my experience just doing the latitude BETWEEN search gets you excellent results.

answered May 08 '11 at 22:46

O. Jones

103,626
17
118
172

Hi Ollie, Thanks for the clear explanation. However, so far I didn't have much luck speeding up the query significantly by narrowing down the search with your suggestion, even with an index on latitude. I'll experiment some more. – javacoder May 09 '11 at 22:47
What did speed it up was changing the select: SELECT id, latitude, longitude instead of SELECT listing.* and subsequently performing queries on the listing table to get the rest of the data. – javacoder May 09 '11 at 22:48
1

I wonder whether it's worth creating a separate MyISAM table to store the listing id and a GEOMETRY for the purpose of searching. Does anyone have experience with the speed of these spatial indexes? – javacoder May 09 '11 at 22:54
I am not sure it is possible to build an index that can work out distance in two dimensions. The point of an index is to preload some aspect of your search in an ordered way. – O. Jones May 10 '11 at 11:21
Would the longitude BETWEEN condition be calculated the same way the latitude one is? – MatteoSp Nov 06 '12 at 22:19

score 1 · Answer 2 · edited May 23 '17 at 12:25

1

You might want to have a look at this question. Unfortunately you cannot create a SPATIAL index on any columns which are not a GEOMETRY type, so at the very least you will need to add one column to the table.

edited May 23 '17 at 12:25

Community

1
1

answered May 08 '11 at 21:10

jisaacstone

4,234
2
25
39

Indexing a mysql table for geo lookup using latitude/longitude

2 Answers2

Linked