Slow(er) Query Response

[R Rothe]

I'm running 4.1.7 std on Linux Redhat 7.3. My application is written in 'C' and uses mysql_real_query() and mysql_use_result() for unbuffered output.

I have a table with approx 1.3Mil records, indexed to within an inch of its life.

I have the following query which performs very differently based on parameters in the where clause.

select msid, msgnum, DATE_FORMAT(mdate,'%a, %d %b %Y %H:%i:%s') as msgdate from thetable where msid=25 and msgnum >= 600000 order by msgnum;

EXPLAIN tells me that the proper index is being used for this query, which is based on [msid INT(11),msgnum BIGINT(20)]

Here is EXPLAIN's output:

id = 1
select_type = SIMPLE
table = thetable
type = ref
possible_keys = msgid,DecodeOne,bygroupid,ByBroPart
key = bygroupid
key_len = 4
ref = const
rows =69694
Extra = Using where


Here's the problem. It seems that the higher I start msgnum in the where clause, the longer it takes the query to respond even though it is using an index. Examples,

where msid=25 and msgnum between 1 and 600000 ---> give me almost instantaneous response whereas,

where msid=25 and msgnum between 300000 and 600000 ---> slows down quite a bit, almost as if it is not using the index to find the starting point but rather traversing the database.

The higher the starting point, the longer the query takes.

My my.cnf is based on the "medium" model.

I've also added, SQL_NO_CACHE SQL_BIG_RESULT HIGH_PRIORITY to the select with no noticable differences.

What am I missing?

Thanks,
Rob