大きなテーブルからランダムに行を取得する方法

ちょっと古い記事だけど、「Selecting Rows Randomly from a Large Table」をざっくり意訳しました。

多くの行数がある巨大なテーブルから、ランダムにサンプリングしてデータを取得したいことがあります。

ランダムにサンプリングするために、テーブルからTOP Nで選択することがあります。しかし、このサンプルではランダムではなく、必ずしも再現性はないですがテーブルの最初のN行を取得します。

小さなテーブルからランダムに行数を取得する場合には、一般的には次のようなクエリを使用します。

SELECT TOP 10 PERCENT * FROM test
ORDER BY NEWID()

ポイントは、「NEWID()」関数を使用していることです。

NEWID関数は、グローバルに一意な識別子GUIDをメモリ上の各行に生成します。

GUIDでORDER BYによるソートをすると、ランダムにテーブルの行が並べ替えられます。

テーブルからランダムにサンプリングして最初の10%の行数を取得できます。

ランダムにデータを取得したい場合、よくNEWIDクエリの仕様が提案されます。

小さなテーブルであれば、とてもシンプルに動作します。

でも、NEWIDクエリは大きなテーブルで使用すると、大きな問題を引き起こします。

tempdbデータベースにテーブルのすべての行をコピーして、ORDER BYを実行します。

この場合、2つの問題が起こります。

tempdbを使用せずに、あまり遅くなく、ランダムに行を取得するには、次のような方法があります。

SELECT * FROM test
WHERE
	(ABS(CAST((BINARY_CHECKSUM(*) * RAND()) as int)) % 100) < 10

基本的な考え方は、テーブルの各行にランダムで0から99の間の数字を生成して、指定の%数字よりも小さい値をランダムですべての行から選択するというものです。

この例では、10％をランダムで取得したいので、10よりも小さい値をもつ行を選択しています。

BINARY_CHECKSUM関数は、指定したカラムの値をベースにチェックサム値を生成します。

異なる行どうしでは、チェックサム値は異なる値になります。

チェックサムは行の値が変わらない限り毎回同じ値を返してしまうため、完全なランダム値を入手することができません。この問題を解決するために、RAND関数を追加します。

RAND関数は、ごちゃまぜな値を返します。これで、クエリを発行するたびに行に毎回ことなる値をランダムに取得できます。ABSとCAST関数を使用することで、BINARY_CHECKSUM(*)*RANDが返すマイナス値をfloatに変換します。

BINARY_CHECKSUM(*)は、*だとコストが高いので特定列を指定することをお勧めします。

SELECT * FROM test
WHERE
	(ABS(CAST((BINARY_CHECKSUM (keycol1, NEWID())) as int)) % 100) < 10

BINARY_CHECKSUMクエリは、ソートが不要で、時間とI/Oは線形になります。

実験

1億行、7億行、14億行のテーブルに対して、NEWIDとBINARY_CHECKSUMをテストしました。

NEWID：14秒

BINARY_CHECKSUM：0.7秒

NEWID：134秒

BINARY_CHECKSUM：10秒

NEWID：253秒

BINARY_CHECKSUM：21秒