Is mysql using my index or not, and can the performance of geokit be improved?

Question

I'm using geokit (acts_as_mappable) in a rails application, and the performance of radial or bounds searches degrades considerably when there is a large number of models (I've tried with 1-2million but the problem no doubt kicks in earlier than this).

Geokit does all its calculations based on lat and lng columns in the table (latitude and longitude). To improve performance geokit will typically add a bounding box 'where' clause, with the intent being to use a combined index on latitude and longitude to improve performance. However it is still incredibly slow with large numbers of models, and it seems to me that the bounding box clause should help a lot more than it does.

So my question is, is there a way to make mysql make better use of the combined lat/lng index or otherwise improve the performance of geokit sql queries? Or, can the combined index for lat/lng be made more helpful?

edit: I've got this working with rails now and written the solution up in more detail here

More Background

For example, this query finds all places within 10 miles of a given point. (I've added .length just to determine how many results come back - there are nicer ways to say this in geokit, but I wanted to force a more typical SQL query).

Place.find(:all,:origin=>latlng,:within=>10).length

It takes about 14s on a mac mini. Here is the explain plan

mysql> explain SELECT *, (ACOS(least(1,COS(0.898529183781244)*COS(-0.0157233221653665)*COS(RADIANS(places.lat))*COS(RADIANS(places.lng))+    ->  COS(0.898529183781244)*SIN(-0.0157233221653665)*COS(RADIANS(places.lat))*SIN(RADIANS(places.lng))+    ->  SIN(0.898529183781244)*SIN(RADIANS(places.lat))))*3963.19)
    ->  AS distance FROM `places` WHERE (((places.lat>51.3373601471464 AND places.lat<51.6264998528536 AND places.lng>-1.13302245886176 AND places.lng<-0.668737541138245)) AND ( (ACOS(least(1,COS(0.898529183781244)*COS(-0.0157233221653665)*COS(RADIANS(places.lat))*COS(RADIANS(places.lng))+
    ->  COS(0.898529183781244)*SIN(-0.0157233221653665)*COS(RADIANS(places.lat))*SIN(RADIANS(places.lng))+
    ->  SIN(0.898529183781244)*SIN(RADIANS(places.lat))))*3963.19)
    ->  <= 10)) 
    -> ;
+----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+
| id | select_type | table  | type  | possible_keys               | key                         | key_len | ref  | rows  | filtered | Extra       |
+----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+
|  1 | SIMPLE      | places | range | index_places_on_lat_and_lng | index_places_on_lat_and_lng | 10      | NULL | 87554 |   100.00 | Using where | 
+----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+

So mysql is examining 87554 rows even though the number of places in the result is 1135 (and the number of places actually in the bounding box is just 1323).

These are the stats on the index (which is made with a rails migration *add_index :places, [:lat, :lng]*):

| Table  | Non_unique | Key_name                         | Seq_in_index | Column_name      | Collation | Cardinality | Sub_part | Packed | Null | Index_type | Comment |
| places |          1 | index_places_on_lat_and_lng      |            2 | lng              | A         |     1373712 |     NULL | NULL   | YES  | BTREE      |         |

Nor does it seem to be related to the trig calculations, as doing a similar query for a bounding box results in a much simpler query but it performs similarly badly:

Place.find(:all,:bounds=>GeoKit::Bounds.from_point_and_radius(latlng,10)).length

Gives a similar explain plan:

   mysql> explain SELECT * FROM `places` WHERE ((places.lat>51.3373601471464 AND places.lat<51.6264998528536 AND places.lng>-1.13302245886176 AND places.lng<-0.668737541138245)) ;
    +----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+
    | id | select_type | table  | type  | possible_keys               | key                         | key_len | ref  | rows  | filtered | Extra       |
    +----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+
    |  1 | SIMPLE      | places | range | index_places_on_lat_and_lng | index_places_on_lat_and_lng | 10      | NULL | 87554 |   100.00 | Using where | 
    +----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+

Answer 1

Plain B-Tree indexes are not too good for the queries like this.

For your query, the range access method is used on the following condition:

places.lat > 51.3373601471464 AND places.lat < 51.6264998528536

, this doesn't even take lon into account.

If you want to use spatial abilities, you should keep your places as Points, create a SPATIAL index of them and use MBRContains to filter the bounding box:

ALTER TABLE places ADD place_point GEOMETRY

CREATE SPATIAL INDEX sx_places_points ON places (place_point)

UPDATE  places
SET     place_point = Point(lat, lon)

SELECT  *
FROM    places
WHERE   MBRContains(LineString(Point(51.3373, -1.1330), Point(51.6264, -0.6687)), place_point)
        AND -- do the fine filtering here

Update:

CREATE TABLE t_spatial (id INT NOT NULL, lat FLOAT NOT NULL, lon FLOAT NOT NULL, coord GEOMETRY) ENGINE=MyISAM;

INSERT
INTO    t_spatial (id, lat, lon)
VALUES  (1, 52.2532, 20.9778);

UPDATE  t_spatial
SET     coord = Point(lat, lon);

This works for me in 5.1.35.