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

Question

I use geokit (actions_as_mappable) in a rails application, and the search performance by radius or borders is significantly degraded when there are a large number of models (I tried with 1-2 million, but the problem is undoubtedly earlier than that).

Geokit does all its calculations based on lat and lng columns in the table (latitude and longitude). To improve performance, geokit typically adds a “where” bounding box, with the goal of using a combined latitude and longitude index to improve performance. However, with a large number of models it is still incredibly slow, and it seems to me that the proposal of a bounding box should help a lot more than that.

So my question is: is there a way to make mysql use the combined lat / lng index better, or otherwise improve geokit sql query performance? Or, can a combined index for lat / lng be useful?

edit: I now work with rails and the solution is written in more detail here

More background

For example, this query finds all locations within a 10 mile radius of a given point. (I added .length to determine how many results will return - there are better ways to say this in geokit, but I wanted to force a more typical SQL query).

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

Mac mini takes about 14 seconds. Here is an explanation 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 | +----+-------------+--------+-------+-----------------------------+-----------------------------+---------+------+-------+----------+-------------+ 

Thus, mysql examines 87,554 rows, although the number of places in the result is 1135 (and the number of places in the bounding box is 1323).

These are index statistics (using the rail 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 | | 

And it seems that this is not related to trigger calculations, since a similar query for the bounding box leads to a much simpler query, but it works just as bad:

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

Gives a similar plan of explanation:

  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

Regular B-Tree indexes are not very good for such queries.

For your request, the range access method is used under the following condition:

 places.lat > 51.3373601471464 AND places.lat < 51.6264998528536 

it doesn't even take into account lon .

If you want to use spatial abilities, you must save your places as Points , create a MBRContains index 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 .