1. ホーム
  2. sql

[解決済み] ランダムな行を選択する最適な方法 PostgreSQL

2022-03-23 15:12:11

質問

PostgreSQLでランダムに行を選択したいのですが、こんなことをやってみました。

select * from table where random() < 0.01;

しかし、他の人はこれを推奨しています。

select * from table order by random() limit 1000;

5億行の非常に大きなテーブルがあり、それを高速に処理したい。

どのようなアプローチが良いのでしょうか? どのような違いがあるのでしょうか? ランダムな行を選択する最良の方法は何ですか?

どのように解決するのですか?

あなたの仕様(さらにコメントで追加情報)を考えると。

  • IDカラムが数値(整数)であり、隙間が少ない(または適度に少ない)場合。
  • 明らかに書き込み操作がない、または少ない。
  • IDカラムにはインデックスが必要です。主キーで十分です。

以下のクエリでは、ビッグテーブルのシーケンシャルスキャンは必要なく、インデックススキャンだけが必要です。

まず、メインクエリの見積もりを取る。

SELECT count(*) AS ct              -- optional
     , min(id)  AS min_id
     , max(id)  AS max_id
     , max(id) - min(id) AS id_span
FROM   big;

唯一コストがかかりそうなのは count(*) (巨大なテーブルの場合)。上記の仕様であれば、必要ないでしょう。見積もりで十分であり、ほぼ無料で入手できる ( 詳しい説明はこちら ):

SELECT reltuples AS ct FROM pg_class
WHERE oid = 'schema_name.big'::regclass;

限り ct 大いに よりも小さい id_span の場合、このクエリは他のアプローチよりも優れた性能を発揮します。

WITH params AS (
   SELECT 1       AS min_id           -- minimum id <= current min id
        , 5100000 AS id_span          -- rounded up. (max_id - min_id + buffer)
    )
SELECT *
FROM  (
   SELECT p.min_id + trunc(random() * p.id_span)::integer AS id
   FROM   params p
         ,generate_series(1, 1100) g  -- 1000 + buffer
   GROUP  BY 1                        -- trim duplicates
) r
JOIN   big USING (id)
LIMIT  1000;                          -- trim surplus

  • で乱数を発生させる。 id のスペースが必要です。空白が少ないので、検索する行数に10% (空白を簡単にカバーできる程度) を追加します。

  • id は偶然に複数回選ばれる可能性があるので (大きな id 空間では非常に低いですが)、生成された番号をグループ分けしてください (あるいは DISTINCT ).

  • を結合します。 id を大きなテーブルに追加します。これは、インデックスがあるため、非常に高速になるはずです。

  • 最後に余剰分をトリミング id は、ダブりやギャップに食われないようにする。すべての行には 完全に等しい確率 が選ばれます。

ショートバージョン

できること 簡略化 というクエリです。上のクエリのCTEは、あくまで教育的な目的です。

SELECT *
FROM  (
   SELECT DISTINCT 1 + trunc(random() * 5100000)::integer AS id
   FROM   generate_series(1, 1100) g
   ) r
JOIN   big USING (id)
LIMIT  1000;

rCTEでリファイン

特に、ギャップや見積もりについてあまり自信がない場合。

WITH RECURSIVE random_pick AS (
   SELECT *
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   generate_series(1, 1030)  -- 1000 + few percent - adapt to your needs
      LIMIT  1030                      -- hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss

   UNION                               -- eliminate dupe
   SELECT b.*
   FROM  (
      SELECT 1 + trunc(random() * 5100000)::int AS id
      FROM   random_pick r             -- plus 3 percent - adapt to your needs
      LIMIT  999                       -- less than 1000, hint for query planner
      ) r
   JOIN   big b USING (id)             -- eliminate miss
   )
TABLE  random_pick
LIMIT  1000;  -- actual limit

を使って作業することができます。 より少ない剰余金 をベースクエリに追加します。ギャップが多すぎて最初の反復で十分な行が見つからない場合、rCTEは再帰項を使った反復を続ける。それでも、比較的 少ない あるいは、十分な大きさのバッファから始めなければならず、パフォーマンスを最適化する目的に反します。

重複を排除するのは UNION をrCTEに追加した。

外側の LIMIT は、十分な行数を確保した時点で CTE を停止させます。

この問い合わせは、利用可能なインデックスを使用し、実際にランダムな行を生成し、制限を満たすまで(再帰が枯渇しない限り)停止しないように注意深く作成されています。もしこれを書き換えるなら、多くの落とし穴があります。

関数にラップする

パラメータを変化させて繰り返し使用する場合。

CREATE OR REPLACE FUNCTION f_random_sample(_limit int = 1000, _gaps real = 1.03)
  RETURNS SETOF big
  LANGUAGE plpgsql VOLATILE ROWS 1000 AS
$func$
DECLARE
   _surplus  int := _limit * _gaps;
   _estimate int := (           -- get current estimate from system
      SELECT c.reltuples * _gaps
      FROM   pg_class c
      WHERE  c.oid = 'big'::regclass);
BEGIN
   RETURN QUERY
   WITH RECURSIVE random_pick AS (
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   generate_series(1, _surplus) g
         LIMIT  _surplus           -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses

      UNION                        -- eliminate dupes
      SELECT *
      FROM  (
         SELECT 1 + trunc(random() * _estimate)::int
         FROM   random_pick        -- just to make it recursive
         LIMIT  _limit             -- hint for query planner
         ) r (id)
      JOIN   big USING (id)        -- eliminate misses
   )
   TABLE  random_pick
   LIMIT  _limit;
END
$func$;

呼び出す。

SELECT * FROM f_random_sample();
SELECT * FROM f_random_sample(500, 1.05);

これを汎用的にして、どんなテーブルでも使えるようにすることもできます。PK カラムの名前とテーブルをポリモーフィック型とみなして EXECUTE ... しかし、それはこの質問の範囲を超えています。見てください。

可能な代替案

要件が許すなら 同一セットの繰り返し の呼び出し(そして我々は繰り返しの呼び出しについて話しているのです)。 マテリアライズド・ビュー . 上記のクエリを一度実行し、その結果をテーブルに書き出す。ユーザは準ランダムに選択されたものを高速で得ることができる。ランダムな選択結果は、間隔やイベントごとに更新されます。

Postgres 9.5 の紹介 TABLESAMPLE SYSTEM (n)

どこ n はパーセンテージです。 マニュアルです。

その BERNOULLISYSTEM サンプリングメソッドには、それぞれ 引数は、サンプリングするテーブルの割合です。 0から100の間の割合 . この引数には、任意の real -の値を持つ式です。

太字強調は私です。それは 超高速 しかし、その結果は 正確にはランダムではない . もう一度マニュアルを。

は、その SYSTEM メソッドよりも大幅に高速です。 BERNOULLI メソッド ただし、サンプリング比率が小さい場合は クラスタリング効果により、テーブルのサンプルのランダム性が低下します。

返される行の数は大きく変わる可能性があります。この例では だいたい 1000行です。

SELECT * FROM big TABLESAMPLE SYSTEM ((1000 * 100) / 5100000.0);

関連する

または 追加モジュールをインストールする tsm_system_rows を使用すると、要求された行数を正確に取得でき (十分な行数がある場合)、 より便利な構文を使用できるようになります。

SELECT * FROM big TABLESAMPLE SYSTEM_ROWS(1000);

参照 エヴァンの回答 をご覧ください。

でも、これではまだランダムとは言えませんね。