Select 10 times slower when reversing order

Question

Why would this select, call it A, (0.02406s):

select * from char_kills
where rid_first <= 110 and rid_last >= 110
order by kills desc
limit 500;

be 10 times slower than when sort order is reversed, call it B, (0.00229s):

select * from char_kills
where rid_first <= 110 and rid_last >= 110
order by kills
limit 500;

and how could you optimize A? Using InnoDB tables on MySQL 5.5.

---

More info follows.

describe char_kills;

cid, int(10) unsigned, NO, PRI, , 
rid_first, int(10) unsigned, NO, PRI, , 
rid_last, int(10) unsigned, NO, PRI, , 
kills, int(11), NO, PRI, , 
offi_rank, smallint(5) unsigned, YES, , , 

select count(*) from char_kills;

146312

select count(*) from char_kills where rid_first <= 110 and rid_last >= 110;

7207

show indexes from char_kills;

char_kills, 0, PRIMARY, 1, kills, A, 160711, , , , BTREE, , 
char_kills, 0, PRIMARY, 2, rid_first, A, 160711, , , , BTREE, , 
char_kills, 0, PRIMARY, 3, rid_last, A, 160711, , , , BTREE, , 
char_kills, 0, PRIMARY, 4, cid, A, 160711, , , , BTREE, , 

A:

Explain:
1, SIMPLE, char_kills, index, , PRIMARY, 16, , 500, Using where

Profiling:
0.02406750, select * from char_kills where rid_first <= 110 and rid_last >= 110 order by kills desc limit 500

starting, 0.000050
checking permissions, 0.000007
Opening tables, 0.000029
System lock, 0.000008
init, 0.000022
optimizing, 0.000008
statistics, 0.000013
preparing, 0.000012
executing, 0.000003
Sorting result, 0.000006
Sending data, 0.023822
end, 0.000007
query end, 0.000004
closing tables, 0.000015
freeing items, 0.000058
logging slow query, 0.000002
cleaning up, 0.000004

B:

Explain:
1, SIMPLE, char_kills, index, , PRIMARY, 16, , 500, Using where

Profiling:
0.00229975, select * from char_kills where rid_first <= 110 and rid_last >= 110 order by kills limit 500

starting, 0.000049
checking permissions, 0.000007
Opening tables, 0.000027
System lock, 0.000008
init, 0.000019
optimizing, 0.000008
statistics, 0.000012
preparing, 0.000009
executing, 0.000003
Sorting result, 0.000004
Sending data, 0.002091
end, 0.000004
query end, 0.000003
closing tables, 0.000010
freeing items, 0.000042
logging slow query, 0.000002
cleaning up, 0.000003

More permutations

Slow:

where rid_first <= 110 and rid_last >= 110 order by kills desc limit 500; -- 0.031s, A, 7k matching rows
where rid_first >= 110 and rid_last <= 110 order by kills      limit 500; -- 0.094s, 449 rows

Fast:

where rid_first <= 110 and rid_last >= 110 order by kills      limit 500; -- 0.000s, B
where rid_first <= 110 and rid_last <= 110 order by kills      limit 500; -- 0.000s
where rid_first >= 110 and rid_last >= 110 order by kills desc limit 500; -- 0.000s
where rid_first <= 110 and rid_last <= 110 order by kills desc limit 500; -- 0.000s
where rid_first <= 110 and rid_last <= 110 order by kills desc limit 500; -- 0.000s
where rid_first <= 110                     order by kills desc limit 500; -- 0.000s
where                      rid_last >= 110 order by kills desc limit 500; -- 0.000s

Answer 1

The answer to why this happens is rather stupid (and obvious in the large Sending data time of the problem query):

Picture your database (which is stored as a file as you likely know) as a large rectangular cornfield and you are standing in front of it. If you want to pick the corn from corn plans which are located in the 4 corners of the cornfield it would obviously be slower (because you have to walk far) then to pick the corn from the corn plants in front of you.

In computers as (in anything) distance matters and it's express in IO latency (and 'misses' to find expected info somewhere).

So the reason for the slowness is that: a) the problem query happens to need to read data from all over the file (rather then sequential reads as the fast query does)

b) you haven't defragmented you database recently

c) you index is inappropriately defined

EDIT: To make it clear, the queries find the needed records nearly as fast so the problem is not in the indexing or its definition (not the biggest at least, try to make multi-column index to include all your columns just for test) but when the query says "Ok I know where everything is located now, let me go get it for displaying" <-- this fetching process is what kills one of them.