Spot,

CREATE TABLE t2
AS
SELECT MD5(RAND()) X
FROM
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z1,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z2,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z3,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z4,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z5,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z6,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z7,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z8,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z9,
(SELECT 1 z UNION SELECT 2 UNION SELECT 3 UNION SELECT 4) z0

1048576 row(s) affected

Execution Time : 00:00:21:187
Transfer Time : 00:00:00:000
Total Time : 00:00:21:187

CREATE INDEX ind_x ON t2(X);
1048576 row(s) affected

Execution Time : 00:00:45:031
Transfer Time : 00:00:00:000
Total Time : 00:00:45:031

SELECT
FLOOR
(
(SELECT MIN(X) FROM `t2`)
+ RAND() *
(
(SELECT MAX(X) FROM `t2`)-(SELECT MIN(X) FROM `t2`)+1
)
) z2
FROM t2
LIMIT 1

16 ms в первый раз, потом <1 ms
Експлаин -- все подвыборки: "optimized away"

Вин7-54, ИНтел-Е5400@2.7ГГ