MIN on an indexed field too slow

[Camelia Ticau]

Please see the table and the query captures below:

mysql> select version();
+---------------------+
| version() |
+---------------------+
| 4.0.16-standard-log |
+---------------------+
1 row in set (0.00 sec)

mysql> show create table oaa_account\G
*************************** 1. row ***************************
Table: oaa_account
Create Table: CREATE TABLE `oaa_account` (
`recordnumber` bigint(20) NOT NULL default '0',
`recordtype` int(11) NOT NULL default '0',
`oaarecord` blob,
PRIMARY KEY (`recordnumber`,`recordtype`)
) TYPE=InnoDB MAX_ROWS=10000000 AVG_ROW_LENGTH=8210
1 row in set (0.03 sec)

mysql> show index from oaa_account\G
*************************** 1. row ***************************
Table: oaa_account
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 1
Column_name: recordnumber
Collation: A
Cardinality: 379007
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
*************************** 2. row ***************************
Table: oaa_account
Non_unique: 0
Key_name: PRIMARY
Seq_in_index: 2
Column_name: recordtype
Collation: A
Cardinality: 379007
Sub_part: NULL
Packed: NULL
Null:
Index_type: BTREE
Comment:
2 rows in set (0.04 sec)

mysql> select recordnumber, recordtype from oaa_account where recordnumber>=66728315 limit 3;
+--------------+------------+
| recordnumber | recordtype |
+--------------+------------+
| 66728318 | 0 |
| 66728320 | 0 |
| 66728322 | 0 |
+--------------+------------+
3 rows in set (0.01 sec)

The slow log shows that MySQL examined 271545 rows, to get the result of a MIN query:

# Time: 060301 14:24:54
# User@Host: mysql[mysql] @ cwpanapps1 [192.12.100.1]
# Query_time: 18 Lock_time: 0 Rows_sent: 1 Rows_examined: 271545
SELECT MIN(recordNumber) FROM oaa_account WHERE recordType = 0 AND recordNumber
> 66728314;

Why does MySQL scan so many rows (271545) to process a MIN query, if the records are sorted by (recordnumber, recordtype)?

Thank you,
Camelia