PostgreSQL でランダムに 1行選択する方法

対象は feed の entry を本文込みで保存した 100万行ほどのテーブル。PostgreSQL 8.3.7 on x86_64-pc-linux-gnu.

まずは単純な方法。

SELECT * FROM entry ORDER BY random() LIMIT 1;

直感的
シンプル
しかしシーケンシャルスキャンが起きる

$ EXPLAIN ANALYZE SELECT * FROM entry ORDER BY random() LIMIT 1;
                                                           QUERY PLAN                                                            
---------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=174494.29..174494.30 rows=1 width=951) (actual time=5965.372..5965.374 rows=1 loops=1)
   ->  Sort  (cost=174494.29..177398.48 rows=1161674 width=951) (actual time=5965.369..5965.369 rows=1 loops=1)
         Sort Key: (random())
         Sort Method:  top-N heapsort  Memory: 26kB
         ->  Seq Scan on entry  (cost=0.00..168685.92 rows=1161674 width=951) (actual time=0.136..3401.347 rows=1161674 loops=1)
 Total runtime: 5965.454 ms

id だけ random() で取得して副問い合わせする方法。

SELECT * FROM entry WHERE id=(SELECT id FROM entry ORDER BY random() LIMIT 1);

シーケンシャルスキャンが起きるのは一緒。sort のコストが減る分、実行速度は少し速い。

EXPLAIN ANALYZE SELECT * FROM entry
   WHERE id=(SELECT id FROM entry ORDER BY random() LIMIT 1);
                                                              QUERY PLAN                                                               
---------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using entry_pkey on entry  (cost=174494.30..174502.71 rows=1 width=951) (actual time=3929.114..3929.117 rows=1 loops=1)
   Index Cond: (id = $0)
   InitPlan
     ->  Limit  (cost=174494.29..174494.30 rows=1 width=4) (actual time=3928.561..3928.563 rows=1 loops=1)
           ->  Sort  (cost=174494.29..177398.48 rows=1161674 width=4) (actual time=3928.558..3928.558 rows=1 loops=1)
                 Sort Key: (random())
                 Sort Method:  top-N heapsort  Memory: 25kB
                 ->  Seq Scan on entry  (cost=0.00..168685.92 rows=1161674 width=4) (actual time=0.088..2498.834 rows=1161674 loops=1)
 Total runtime: 3929.198 ms

id が 1 〜の連番なら、max(id) に 0 〜 1 の値を掛けることで id を決定できる。

SELECT * FROM entry WHERE id=(SELECT (max(id) * random())::int FROM entry);

id に抜けがある場合指定した id の行が存在しない可能性はあるが、(抜けが比較的少数なら) もう一回やればいい。primary key での SELECT だから、数回なら繰り返しても大したことはない。
# 7.4 以前の古い PostgreSQL だと max(id) の取得でシーケンシャルスキャンが起きてしまうので、ORDER BY id DESC LIMIT 1 で id の最大値を求める必要がある

# EXPLAIN ANALYZE SELECT id, title FROM entry WHERE id=(SELECT (max(id) * random())::int FROM entry);
                                                                         QUERY PLAN                                                                         
------------------------------------------------------------------------------------------------------------------------------------------------------------
 Index Scan using entry_pkey on entry  (cost=0.42..8.84 rows=1 width=73) (actual time=0.554..0.558 rows=1 loops=1)
   Index Cond: (id = $1)
   InitPlan
     ->  Result  (cost=0.40..0.42 rows=1 width=0) (actual time=0.068..0.069 rows=1 loops=1)
           InitPlan
             ->  Limit  (cost=0.00..0.40 rows=1 width=4) (actual time=0.045..0.047 rows=1 loops=1)
                   ->  Index Scan Backward using entry_pkey on entry  (cost=0.00..468771.09 rows=1161674 width=4) (actual time=0.042..0.042 rows=1 loops=1)
                         Filter: (id IS NOT NULL)
 Total runtime: 0.645 ms

primary key で引くだけだから当然高速。

不幸にも連番の id がない場合。
md5(id) で関数 index を作ったらどうかな。

CREATE INDEX entry_md5_idx ON entry (md5(id::text));

SELECT * FROM entry
   WHERE md5(id::text) LIKE '1234%'
   ORDER BY random() LIMIT 1;

前方一致で [0-9a-f] の数文字をランダムに指定して LIKE で取り出す。複数行引っかかるのでその中で ORDER BY random() LIMIT 1 する。

EXPLAIN ANALYZE SELECT * FROM entry
   WHERE md5(id::text) LIKE '1234%' ORDER BY random() LIMIT 1;
                                                             QUERY PLAN                                                             
------------------------------------------------------------------------------------------------------------------------------------
 Limit  (cost=8.62..8.63 rows=1 width=951) (actual time=1.994..1.997 rows=1 loops=1)
   ->  Sort  (cost=8.62..8.63 rows=1 width=951) (actual time=1.990..1.990 rows=1 loops=1)
         Sort Key: (random())
         Sort Method:  top-N heapsort  Memory: 26kB
         ->  Index Scan using entry_md5_idx on entry  (cost=0.01..8.61 rows=1 width=951) (actual time=0.769..1.854 rows=22 loops=1)
               Index Cond: ((md5((id)::text) >= '1234'::text) AND (md5((id)::text) < '1235'::text))
               Filter: (md5((id)::text) ~~ '1234%'::text)
 Total runtime: 2.112 ms

インデックスが使えるので速い。
前方一致で何文字指定するかは行数次第。少ないと大量にマッチするし、多いとまったくマッチしない場合が出る。目安としては行数を N として
$16^n = N$
$n = log_{16} N = \frac{log_e N}{log_e 16}$
となるので、n を N から求めて

perl -e 'print log(1_000_000)/log(16)'
4.98289214233104

100万行なら 4文字でいい感じに少ない行数が引っかかる。