Need help optimizing a lat/Lon geo search for mysql

Question

I have a mysql (5.0.22) myisam table with roughly 300k records in it and I want to do a lat/lon distance search within a five mile radius.

I have an index that covers the lat/lon fields and is fast (milisecond response) when I just select for lat/lon. But when I select for additional fields in the table is slows down horribly to 5-8 seconds.

I'm using myisam to take advantage of fulltext search. The other indexes perform well (e.g. select * from Listing where slug = 'xxxxx').

How can I optimize my query, table or index to speed things up?

My schema is:

CREATE TABLE  `Listing` (
  `id` int(10) unsigned NOT NULL auto_increment,
  `name` varchar(125) collate utf8_unicode_ci default NULL,
  `phone` varchar(18) collate utf8_unicode_ci default NULL,
  `fax` varchar(18) collate utf8_unicode_ci default NULL,
  `email` varchar(55) collate utf8_unicode_ci default NULL,
  `photourl` varchar(55) collate utf8_unicode_ci default NULL,
  `thumburl` varchar(5) collate utf8_unicode_ci default NULL,
  `website` varchar(85) collate utf8_unicode_ci default NULL,
  `categoryid` int(10) unsigned default NULL,
  `addressid` int(10) unsigned default NULL,
  `deleted` tinyint(1) default NULL,
  `status` int(10) unsigned default '2',
  `parentid` int(10) unsigned default NULL,
  `organizationid` int(10) unsigned default NULL,
  `listinginfoid` int(10) unsigned default NULL,
  `createuserid` int(10) unsigned default NULL,
  `createdate` datetime default NULL,
  `lasteditdate` timestamp NOT NULL default CURRENT_TIMESTAMP on update CURRENT_TIMESTAMP,
  `lastedituserid` int(10) unsigned default NULL,
  `slug` varchar(155) collate utf8_unicode_ci default NULL,
  `aclid` int(10) unsigned default NULL,
  `alt_address` varchar(80) collate utf8_unicode_ci default NULL,
  `alt_website` varchar(80) collate utf8_unicode_ci default NULL,
  `lat` decimal(10,7) default NULL,
  `lon` decimal(10,7) default NULL,
  `city` varchar(80) collate utf8_unicode_ci default NULL,
  `state` varchar(10) collate utf8_unicode_ci default NULL,
  PRIMARY KEY  (`id`),
  KEY `idx_fetch` USING BTREE (`slug`,`deleted`),
  KEY `idx_loc` (`state`,`city`),
  KEY `idx_org` (`organizationid`,`status`,`deleted`),
  KEY `idx_geo_latlon` USING BTREE (`status`,`lat`,`lon`),
  FULLTEXT KEY `idx_name` (`name`)
) ENGINE=MyISAM DEFAULT CHARSET=utf8 COLLATE=utf8_unicode_ci ROW_FORMAT=DYNAMIC;

My query is:

SELECT Listing.name, Listing.categoryid, Listing.lat, Listing.lon
, 3956 * 2 * ASIN(SQRT( POWER(SIN((Listing.lat - 37.369195) * pi()/180 / 2), 2) + COS(Listing.lat * pi()/180) * COS(37.369195 * pi()/180) * POWER(SIN((Listing.lon --122.036849) * pi()/180 / 2), 2) )) rawgeosearchdistance
FROM Listing
WHERE
    Listing.status = '2'
    AND ( Listing.lon between -122.10913433498 and -121.96456366502 )
    AND ( Listing.lat between 37.296909665016 and 37.441480334984)
HAVING rawgeosearchdistance < 5
ORDER BY rawgeosearchdistance ASC;

Explain plan without geosearch:

    +----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-------------+
    | id | select_type | table      | type  | possible_keys   | key             | key_len |ref | rows | Extra       |
    +----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-------------+
    |  1 | SIMPLE      | Listing    | range | idx_geo_latlon  | idx_geo_latlon  | 19      | NULL |  453 | Using where |
    +----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-------------+

Explain plan with geosearch:

+----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-----------------------------+
| id | select_type | table      | type  | possible_keys   | key             | key_len | ref  | rows | Extra                       |
+----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-----------------------------+
|  1 | SIMPLE      | Listing    | range | idx_geo_latlon  | idx_geo_latlon  | 19      | NULL |  453 | Using where; Using filesort |
+----+-------------+------------+-------+-----------------+-----------------+---------+------+------+-----------------------------+

Here's the explain plan with the covering index. Having the columns in the correct order made a big difference:

+----+-------------+--------+-------+---------------+---------------+---------+------+--------+------------------------------------------+
| id | select_type | table  | type  | possible_keys | key           | key_len | ref  | rows   | Extra                                    |
+----+-------------+--------+-------+---------------+---------------+---------+------+--------+------------------------------------------+
|  1 | SIMPLE      | Listing | range | idx_geo_cover | idx_geo_cover | 12      | NULL | 453     | Using where; Using index; Using filesort |
+----+-------------+--------+-------+---------------+---------------+---------+------+--------+------------------------------------------+

Thank you!

Looks like you have way too many columns in that one table. You can squeeze some performance out of your queries by normalizing your data structure a bit. :) — tom

jonstjohn jonstjohn · Accepted Answer · 2009-06-04T17:27:39

You are probably using a 'covering index' in your lat/lon only query. A covering index occurs when the index used by the query contains the data that you are selecting for. MySQL only needs to visit the index and never the data rows. See this for more info. That would explain why the lat/lon query is so fast.

I suspect that the calculations and the sheer number of rows returned, slows down the longer query. (plus any temp table that has to be created for the having clause).

Need help optimizing a lat/Lon geo search for mysql

5 Answers