MySQLでランダムにN件取得する方法のパフォーマンス比較

こちらと同じような比較を自分でもやってみました。
私はMySQLに関してあまり深い知識を持っていないため、検証の方法や設定値の問題などがあるかもしれませんが、ざっくりとした傾向は分かるかと思います。

まず、今回使用しているテスト用環境のバージョン等です。

OS Fedora Core 7
MySQL 5.0.45
PHP 5.2.6

# やや古い・・・。

また、テストで使用するテーブルは以下のような簡単なものです。

┌────┬───────┬───┐
│　名前　│　　　型　　　│サイズ│
├────┼───────┼───┤
│ｉｄ　　│ｉｎｔ　　　　│　　　│主キー
├────┼───────┼───┤
│ｎａｍｅ│ｖａｒｃｈａｒ│　６４│
└────┴───────┴───┘

まず今回テストした6つの方法を簡単に説明します。

(1) RAND()列を追加してソート

以下のようなSQLになります。

SELECT *, RAND() AS RANDOM_VALUE
FROM test_table
ORDER BY RANDOM_VALUE
LIMIT 5

(2) ORDER BY RAND()

「ORDER BY RAND()」とORDER BY句にRAND()関数を使用できます。

SELECT *
FROM test_table
ORDER BY RAND()
LIMIT 5

(3) ORDER BY RAND()改

行のID（主キー）だけをランダムに取得してから、テーブル本体と結合します。

SELECT *
FROM test_table,
  (SELECT ID FROM test_table ORDER BY RAND() LIMIT 5) AS SUB1
WHERE test_table.ID = SUB1.ID

(4) ランダムにオフセットを決定

レコード件数から、5つのオフセット値をあらかじめランダムに（プログラムで）決定しておき、それを5回のクエリで処理します。

※オフセットの決定をPHPで行っています。

<?php
$stmt = $connection->prepare( "select count(*) as data_count from test_table" );
$stmt->execute();
$result = $stmt->fetch( PDO::FETCH_ASSOC );
$max = $result['data_count'] - 1;

//  オフセットをランダムに5つ決定する。
$offset_list = array();
while ( count( $offset_list ) < 5 ) {
    $rand_val = rand(0, $max);
    if ( in_array($rand_val, $offset_list)) {
        continue;
    }
    $offset_list[] = (int)$rand_val;
}

//  結果を取得する。
$ret = array();
$stmt   = $connection->prepare( "select * from test_table limit :offset,1" );
foreach ($offset_list as $offset) {
    $stmt->bindParam(':offset', $offset, PDO::PARAM_INT);
    $stmt->execute();
    $ret[] = $stmt->fetch( PDO::FETCH_ASSOC );
}

(5) IDをランダムに5つ指定する（その1）

あらかじめID（主キー）の最小値と最大値を取得しておき、その範囲でランダムなIDから1件ずつレコードを取得します。
ただし、IDが完全な連番ではなくて空き番号がある場合、レコードが取得できない可能性があります。これを考慮して正常なレコードを5件取得できるまで繰り返すようにしてあります。番号の空き率によっては取得失敗回数が増えてしまいます。（今回のテストデータでは、空き番号がありません）

<?php
$stmt = $connection->prepare( "select min(id) as id_min, max(id) as id_max from test_table" );
$stmt->execute();
$result = $stmt->fetch( PDO::FETCH_ASSOC );
$min = $result['id_min'];
$max = $result['id_max'];

$ret = array();
$offset_list = array();
$stmt   = $connection->prepare( "select * from test_table where id = :id" );
while ( count($ret) < 5 ) {
    while ( in_array($id = rand($min, $max), $offset_list) ) {
    }
    $offset_list[] = $id;
    $stmt->bindParam(':id', $id, PDO::PARAM_INT);
    $stmt->execute();
    $record = $stmt->fetch( PDO::FETCH_ASSOC );
    if ( count($record) < 1 ) {
        continue;
    }
    $ret[] = $record;
}

2009/07/07 13:35追記
ブコメでid:sh2さんより空振りの回避方法をご指摘いただきました。
http://b.hatena.ne.jp/sh2/20090707#bookmark-14472787

 (5)で「select * from test_table where id >= :id order by id limit 1」とすると空振りがなくなります。
空き番直後のIDについて選択される確率が増えてしまうけど

なるほど。おっしゃる通りですね。
これは折りを見て、IDの空き番号があるデータを何種類か用意して、きちんと計測してみたいところです。
おそらく、クエリの発行回数が必ず指定回数でおさまるsh2さんの方法が、オールラウンドに良好だと思われますが・・・。
ツッコミありがとうございました！！

(6) IDをランダムに5つ指定する（その2）

(5)の方法と似ていますが、クエリの発行回数を減らすために、ランダムなIDを複数決定しておき、WHERE句にINを使用して1つのSQLで複数取得します。
こちらもIDの空き番号を考慮して、目的の件数よりもやや多め（以下では10件）のIDを渡しています。（この場合は理論上空き番号率が50%まで許容できます）
ここで渡すIDの数を多くするほど、パフォーマンスが低下します。

また、結果のランダム性を確保するために、ORDER BY RAND()でさらにランダムに並べ替えています。

<?php
$stmt = $connection->prepare( "select min(id) as id_min, max(id) as id_max from test_table" );
$stmt->execute();
$result = $stmt->fetch( PDO::FETCH_ASSOC );
$min = $result['id_min'];
$max = $result['id_max'];

$ret = array();
$offset_list = array();
while ( count($offset_list) < 10 ) {
	while ( in_array($id = rand($min, $max), $offset_list) ) {
	}
	$offset_list[] = $id;
}


$stmt	= $connection->prepare( "select * from test_table where id in (" . implode(',',$offset_list) . ") order by rand() limit 5" );
$stmt->execute();
$rec = $stmt->fetchAll( PDO::FETCH_ASSOC );

速度比較

上記6つの方法（すべてPHPから実行、5件のレコードを変数に格納するまで）を、以下の2つの場合について実行時間の計測を行いました。

MyISAMとInnoDB
テーブルのレコード数1万件と100万件
それぞれ5回実行し、各実行時間の平均をとっています

まず、データ量が1万件の場合は、どの方法でも0.1秒以下の実行時間です。
ただし、処理するテーブルにフィールドがたくさんあるなど、テーブル全体のデータ量が多い場合、(1)と(2)の方法ではデータ量に比例してパフォーマンスが劣化します。これは、RAND()列を追加したり、ORDER BY RAND()を使用すると、処理対象のテーブルの使用するフィールド、およびRAND()の列で一時テーブルが作成され、その一時テーブルでソートが行われるからです。一時テーブルそのものの作成と並べ替えにかかる時間、およびメモリを圧迫することによるオーバーヘッドなど、いくつかの要因でパフォーマンスが劣化しやすいです。
したがって、ORDER BY RAND()を使用する場合でも、少なくとも(3)の方法のように主キーだけでランダムレコードを取得するようにした方がよいと思われます。

MyISAMとInnoDBの比較では、(4)の方法でかなり差が出ています。これは、MyISAMの場合はSELECT COUNT(*)がテーブルのレコード数に関係なく一瞬で取得できるのに対して、InnoDBではレコード数に依存した実行時間がかかってしまうためです。
InnoDBのこの問題を回避するために、こちらのようにレコード数を別テーブルにキャッシュしておくような対策もあります。
ただ、レコード数が100万件クラスになると、MyISAMでも処理時間が1秒を超えますので、ウェブページでリアルタイムに結果を表示するような場合には使用できないでしょう。
（OFFSETに比例して実行時間が長くなります。）

最後の(5)と(6)の方法ですが、レコードを主キーから取り出すので圧倒的に高速です。1万件の場合でも実行時間が1桁違いまし、レコード数が100万件になっても、パフォーマンスが劣化しません。（実際は、インデックスがメモリに収まっているのかどうか、という個別の状況で劣化具合は変化すると思います。）

しかし、(6)の方法を単体で用いるのはやはりリスクが大きいでしょう。運用中にIDの空き番号の状況が変化して、100件ランダムなIDを与えてみたけど、その中に実際に存在するレコードが3件しかなかった、となる可能性も考えられます。そこに保険をかけておく必要が出てくるのですが、そうなると、確実に5件取得できる(5)の方法が無難なのかもしれません。

P.S.
MySQLに詳しい友人のFakeさんが、きっとすごい方法を見つけてくれると期待しています・・・・ｗ