MySQLでSQLのみを使用してランダム取得を劇的に早くする方法

MySQLでランダムに20行をとるためには以下のようにやればいい。

SELECT * FROM table_name ORDER BY RAND() LIMIT 0, 20;

簡単に取得できるのはいいんだけど、行数が増えると劇的に遅い。どれくらい違うかって言うと10万行のデータベースでも↓ぐらい違う。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0070 秒)
SELECT * FROM table_name LIMIT 0 , 20

表示中の列 0 - 19 (20 合計, クエリの実行時間 1.1884 秒)
SELECT * FROM table_name ORDER BY RAND() LIMIT 0, 20;

なんでこんなに時間がかかるのかと調べてみると、どうも*を使うから遅いらしい。ということで、列名に主キーを指定して試してみる。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0745 秒)
SELECT table_id FROM table_name ORDER BY RAND() LIMIT 0, 20;

確かに劇的に早くなってる。それならこれでサブクエリを作成して引っ掛ければ早くなるのでは？と試してみた。

表示中の列 0 - 19 (20 合計, クエリの実行時間 0.0740 秒)
SELECT * FROM table_name AS tbl,
  ( SELECT table_id FROM table_name ORDER BY RAND() LIMIT 0 , 20) AS randam
  WHERE tbl.table_id = randam.table_id LIMIT 0 , 20

これならRAND()を使用しない検索と同じくらいの速さになるみたい。主キーだからインデックスで早くなるのかなぁ。よくわかってないけど、RAND()を使う場合はサブクエリで取得してから使ったほうがいいみたいです。