Find value within a range in database table

If you have an index spanning MN and MX it should be pretty fast, even with 9M rows.

alter table T add index mn_mx (mn, mx);

Edit

I just tried a test w/ a 1M row table

mysql> select count(*) from T;
+----------+
| count(*) |
+----------+
|  1000001 |
+----------+
1 row in set (0.17 sec)

mysql> show create table T\G
*************************** 1. row ***************************
       Table: T
Create Table: CREATE TABLE `T` (
  `id` int(10) NOT NULL AUTO_INCREMENT,
  `mn` int(10) DEFAULT NULL,
  `mx` int(10) DEFAULT NULL,
  PRIMARY KEY (`id`),
  KEY `mn_mx` (`mn`,`mx`)
) ENGINE=InnoDB AUTO_INCREMENT=1048561 DEFAULT CHARSET=utf8
1 row in set (0.00 sec)

mysql> select * from T order by rand() limit 1;
+--------+-----------+-----------+
| id     | mn        | mx        |
+--------+-----------+-----------+
| 112940 | 948004986 | 948004989 |
+--------+-----------+-----------+
1 row in set (0.65 sec)

mysql> explain select id from T where 948004987 between mn and mx;
+----+-------------+-------+-------+---------------+-------+---------+------+--------+--------------------------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref  | rows   | Extra                    |
+----+-------------+-------+-------+---------------+-------+---------+------+--------+--------------------------+
|  1 | SIMPLE      | T     | range | mn_mx         | mn_mx | 5       | NULL | 239000 | Using where; Using index |
+----+-------------+-------+-------+---------------+-------+---------+------+--------+--------------------------+
1 row in set (0.00 sec)

mysql> select id from T where 948004987 between mn and mx;
+--------+
| id     |
+--------+
| 112938 |
| 112939 |
| 112940 |
| 112941 |
+--------+
4 rows in set (0.03 sec)

In my example I just had an incrementing range of mn values and then set mx to +3 that so that's why I got more than 1, but should apply the same to you.

Edit 2

Reworking your query will definitely be better

mysql> explain select id from T where mn<=947892055 and mx>=947892055;
+----+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+
| id | select_type | table | type  | possible_keys | key   | key_len | ref  | rows | Extra                    |
+----+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+
|  1 | SIMPLE      | T     | range | mn_mx         | mn_mx | 5       | NULL |    9 | Using where; Using index |
+----+-------------+-------+-------+---------------+-------+---------+------+------+--------------------------+

It's worth noting even though the first explain reported many more rows to be scanned I had enough innodb buffer pool set to keep the entire thing in RAM after creating it; so it was still pretty fast.

If there are no gaps in your set, a simple gte comparison will work:

SELECT ID FROM T WHERE ? >= MN ORDER BY MN ASC LIMIT 1