From the EXPLAINs it seems quite clear what happens - the "limit only" one uses index on latitude because it finds it most useful, then tries all found rows for longitude until it gathers 100 of them and quits.

The "order only" uses the same path, but does not stop after 100 because it needs all of them - it then sorts all matching rows by a filesort (I suppose only a small part of those 81k are returned so the sort is fast).

But the slow one (wrongly) uses ["order by .. limit" optimization](http://dev.mysql.com/doc/refman/5.6/en/limit-optimization.html) - for some reason it thinks that lot of rows will satisfy the condition so goes by the `indexedColumn` order. But in reality there are too few matching ones so it walks a big part of the table before finding the 100 matching rows. That means that big portion of the table needs to be read to memory from disk in the case the available memory is not big enough to contain it.

The results - you actually do NOT want to use the index on `indexedColumn` as there are so few matching rows that sorting them "the slow way" is actually more effective than using the index. You can do that by `ignore index(indexedColumn)` and/or you can probably add a composite index over both `(Latitude, Longitude)`. That should return only few hundreds of rows and any operation on them will become trivial.