TABLESAMPLE による行の選択方法

TABLESAMPLE による行の選択方法

大規模テーブルに対する多くの探索的な質問は、大まかな回答で十分ですが、status にインデックスがない場合、「出荷済み注文はおおよそいくつあるか」という単純な質問でさえフルスキャンが必要になります。200万行のordersテーブルでは、Postgresはマッチする行を数えるためだけに、8 kBのページすべて、つまり18,085ページ（141 MB）を読み込む必要があります。

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM orders WHERE status = 'shipped';

 Aggregate
   Buffers: shared hit=18085
   ->  Seq Scan on orders (actual rows=500000.00 loops=1)
         Filter: (status = 'shipped'::text)
         Rows Removed by Filter: 1500000
 Execution Time: 56.188 ms

shared hit=18085は、メモリ上に既に存在するすべてのページに対して1回のバッファアクセスがあったことを意味します（EXPLAIN出力でのバッファ統計の読み方でカウンターについて説明しています）。141 MBのヒープサイズは問題になりません。1 TBのテーブルで1億3400万ページの場合を考えてみましょう。スキャンは、回答がどれほど小さくても、毎回ディスクからすべてのページを読み込みます。

Postgresは、shared_buffersの4分の1を超えるテーブルを小さなリングバッファを通して読み込みます。詳細はバッファの紹介を参照してください。

少なくともPostgresは、小さなリングバッファを通して大きなテーブルを読み込むことで、独自のキャッシュをフラッシュすることを避けています。しかし、ディスクは依然としてフルリードを実行します。プライマリサーバーで本番トラフィックを処理している場合、これは他のすべてと共有されます。必要なのが「おおよそいくつ」や「代表的なサンプルはありますか」といった探索的な確認だけの場合、1 TB全体を読むのはコストが高すぎます。

SQL標準には、これを助けるためのTABLESAMPLEがあります。これはFROM句のテーブル名の直後に配置され、残りのクエリはそのテーブルが選択したページの部分集合に対して実行されます。

SELECT
  id, status, created_at, amount
FROM orders TABLESAMPLE SYSTEM (1) REPEATABLE (7)
LIMIT 5;

 id  |  status   |       created_at       | amount
-----+-----------+------------------------+--------
 429 | delivered | 2024-01-01 00:07:09+00 |  38.46
 430 | delivered | 2024-01-01 00:07:10+00 | 150.72
 431 | delivered | 2024-01-01 00:07:11+00 | 295.59
 432 | delivered | 2024-01-01 00:07:12+00 | 488.23
 433 | delivered | 2024-01-01 00:07:13+00 | 238.84

(1)の値はパーセンテージであり、サンプルのサイズは固定されていません。5つの異なるシードで18,107から20,416行の範囲の結果が得られました。正確な行数が必要な場合は、contribのtsm_system_rowsがSYSTEM_ROWS (n)メソッドを追加します。行は物理的な順序で返されるため、これら5行は隣接しています（ID 429から433）。そして、計算されるものはすべてサンプルに対して計算されるため、合計は手動でスケールアップする必要があります。count(*)とsum()は100倍、平均、比率、極値はそのまま読み取られます。

出荷済み注文のカウントを、バッファ数とともにスケールアップして再度示します。

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) * 100 FROM orders TABLESAMPLE SYSTEM (1)
WHERE status = 'shipped';

 Aggregate
   Buffers: shared hit=177
   ->  Sample Scan on orders (actual rows=4920.00 loops=1)
         Sampling: system ('1'::real)
         Filter: (status = 'shipped'::text)
 Execution Time: 0.829 ms

18,085ページではなく177ページで、推定値は実際の500,000に対して492,000となり、この種のカウントでは有効です。行はcreated_at順に1秒間に1行ずつ挿入されるため、最も古い行はテーブルの先頭にあります。同じ1%のサンプルでそれを求めます。

SELECT min(created_at) FROM orders TABLESAMPLE SYSTEM (1);

6回の実行結果：

 2024-01-01 02:51:13+00
 2024-01-01 01:36:19+00
 2024-01-01 01:27:24+00
 2024-01-01 04:41:47+00
 2024-01-01 02:51:13+00
 2024-01-01 00:44:36+00

実際の回答は00:00:01です。サンプルは44分からほぼ5時間までずれており、実行1回目と5回目は秒単位で一致していますが、ランダムな行のサンプルではほとんど起こり得ないことです。TABLESAMPLEの奇妙な点はすべて1つの事実から来ています。それは行を選択するのではなく、アドレスを選択することです。

セットアップ

この記事のすべては、PostgreSQL 18.6でpostgres:18イメージを使用してキャプチャされました。shared_buffers = 1GBでキャッシュはウォーム状態なので、タイミングは互いの方法を比較するためのものであり、あなたの環境での予測ではありません。

CREATE EXTENSION IF NOT EXISTS pageinspect;

CREATE TABLE orders (
    id          bigint GENERATED ALWAYS AS IDENTITY PRIMARY KEY,
    customer_id bigint        NOT NULL,
    status      text          NOT NULL,
    created_at  timestamptz   NOT NULL,
    amount      numeric(10,2) NOT NULL
);

SELECT setseed(0.42);
INSERT INTO orders (customer_id, status, created_at, amount)
SELECT (random() * 50000)::bigint + 1,
       CASE WHEN i <= 1300000 THEN 'delivered'
            WHEN i <= 1800000 THEN 'shipped'
            WHEN i <= 1900000 THEN 'cancelled'
            ELSE 'pending' END,
       timestamptz '2024-01-01 00:00:00+00' + i * interval '1 second',
       round((random() * 500)::numeric, 2)
FROM generate_series(1, 2000000) AS i;
VACUUM ANALYZE orders;

-- 同じ行をランダムな物理順序で
CREATE TABLE orders_shuffled AS SELECT * FROM orders ORDER BY random();
VACUUM ANALYZE orders_shuffled;

CREATE TABLE customers AS SELECT id FROM generate_series(1, 50001) AS id;
ALTER TABLE customers ADD PRIMARY KEY (id);

-- 各ページに十分な空き容量がある小さなコピー、pageinspect用
CREATE TABLE h (LIKE orders INCLUDING ALL) WITH (fillfactor = 70);
INSERT INTO h OVERRIDING SYSTEM VALUE
SELECT * FROM orders WHERE id <= 1000 ORDER BY id;

各行にはアドレスがある

ページは0から番号付けされ、ヘッダーの直後に各ページは行ポインタの配列を保持します。各行に1つずつ、1から番号付けされています（PostgreSQLの8KBページ内部でバイトごとに分解しています）。ページ番号と行ポインタを組み合わせたものが、行のctidです。

SELECT ctid, id, created_at FROM orders ORDER BY id LIMIT 3;

 ctid  | id |       created_at
-------+----+------------------------
 (0,1) |  1 | 2024-01-01 00:00:01+00
 (0,2) |  2 | 2024-01-01 00:00:02+00
 (0,3) |  3 | 2024-01-01 00:00:03+00

組み込みのサンプリングメソッドは、そのアドレスの一部をシードとともにハッシュ化し、1%のカットオフ以下のものを保持します。違いはどの部分をハッシュ化するかだけです。SYSTEMは、src/backend/access/tablesample/system.cにあり、ページ番号（関連する行にトリミングされたもの）をハッシュ化します。

hashinput[0] = nextblock;          /* page */
hashinput[1] = sampler->seed;
hash = DatumGetUInt32(hash_any((const unsigned char *) hashinput,
                               (int) sizeof(hashinput)));
if (hash < sampler->cutoff)        /* keep the whole page */

BERNOULLIは、bernoulli.cにあり、ページと行ポインタ番号をハッシュ化します。

hashinput[0] = blockno;            /* page */
hashinput[1] = tupoffset;          /* line pointer */
hashinput[2] = sampler->seed;

したがって、SYSTEMはページごとに1つのコインを投げ、勝ったページのすべての行を取得します。BERNOULLIは行ポインタごとに1つのコインを投げ、これは行ポインタの数を確認するためにすべてのページを開く必要があることを意味します。これがパフォーマンスの全体像です。このテーブルでは、SYSTEMは1.2ミリ秒で、BERNOULLIは10.4ミリ秒で回答します。

ページはバンドルとして来る

ここでの1ページは約107行を保持し、行は時間順に挿入されたため、1ページは107秒連続した注文に相当します。ctidのページ部分でSYSTEMサンプルをグループ化すると、バンドルがそこにあります。

SELECT (ctid::text::point)[0]::int AS page, count(*) AS rows,
       min(created_at)::time AS first, max(created_at)::time AS last
FROM orders TABLESAMPLE SYSTEM (1) REPEATABLE (7)
GROUP BY 1 ORDER BY 1 LIMIT 4;

 page | rows |  first   |   last
------+------+----------+----------
    4 |  107 | 00:07:09 | 00:08:55
   38 |  107 | 01:07:47 | 01:09:33
   57 |  107 | 01:41:40 | 01:43:26
  265 |  107 | 07:52:36 | 07:54:22

サンプルは20,000個の散らばった秒ではありません。それは約200個の短いタイムラインの断片であり、min()はハッシュが最初に保持した断片の開始を返します。上記の実行1回目と5回目は同じ最初のページを保持しました。

テーブルをシャッフルすると、問題は消えます。orders_shuffledは、ORDER BY random()順で書き込まれた同じ行を保持しているため、各ページは3週間のさまざまな時間帯の数秒のデータであり、同じクエリは毎回真実に数分以内に収まります。

 2024-01-01 00:00:06+00
 2024-01-01 00:01:20+00
 2024-01-01 00:01:43+00
 2024-01-01 00:01:24+00
 2024-01-01 00:02:50+00
 2024-01-01 00:05:07+00

元の時間順テーブルに対するBERNOULLIは、行ポインタごとのコインフリップは何もバンドルしないため、同様にうまく機能します。

誰も最小値をサンプリングしませんが、バンドルは平均値にも同様に悪影響を与えます。200個のシード全体で、SYSTEMサンプルからのavg(created_at)は、BERNOULLIからの同じ平均値よりも10倍も大きく変動します。ページ単位で考えると理由は明らかです。1つのページからの107行は、そのページからの1行が持つ情報量と同じくらいしかタイムラインについて教えてくれません。したがって、20,000行のSYSTEMサンプルは、200行のサンプルと同程度の精度しか持ちません。ランダムなamountのように、行の配置とは無関係な列は、両方のメソッドで同様に平均化されます。時間列、常に増加するID、バッチでロードされたものはすべて、それが重要になる列です。

REPEATABLEはアドレスを記憶する

REPEATABLE (42)はシードを固定します。同じシード、同じハッシュ、同じアドレス。それらのアドレスが同じ行を保持しているかどうかは、それらの間で行われたテーブルの変更に依存します。アドレスモデルは、このテーブルのすべての行を予測します。各実行はシード42でサンプルをキャプチャし、テーブルを変更し、再度キャプチャして、最初のサンプルからいくつの行がまだ残っているかを数えます。

追加は新しいアドレスを作成し、削除は古いアドレスを空にします。生き残った行は移動しないため、何も変わりません。VACUUMは無効な行ポインタを使用不可とマークし、各ページ内のタプルデータを圧縮しますが、生きている行を指す行ポインタを再番号付けすることはありません（ページレベルでのVACUUMで各フェーズを説明しています）。VACUUM FULLとCLUSTERはテーブルの新しいコピーを作成し、すべての行が新しいアドレスを取得し、両方のサンプルは実質的に再描画されます。

UPDATEは興味深い行です。Postgresは行をインプレースで上書きしません。更新は新しいバージョンを書き込み、ページに空きがあり、インデックス付き列が変更されていない場合、インデックスに触れることなくそのバージョンを同じページに配置します。これはHOTアップデートです（PostgresのHOTアップデート）。ここでは99%がHOTアップデートでした。同じページということは、SYSTEMはそれに気づかないということです。しかし、新しいバージョンは新しい行ポインタを取得し、pageinspectはhの1行でそれを示します。

SELECT ctid FROM h WHERE id = 3;   -- (0,3)
UPDATE h SET amount = amount + 1 WHERE id = 3;
SELECT ctid FROM h WHERE id = 3;   -- (0,76)

SELECT lp, lp_flags, lp_off, t_ctid
FROM heap_page_items(get_raw_page('h', 0)) WHERE lp IN (3, 76);

 lp | lp_flags | lp_off | t_ctid
----+----------+--------+--------
  3 |        2 |     76 | 
 76 |        1 |   2792 | (0,76)

行ポインタ3は現在LP_REDIRECT（lp_flags = 2）であり、「76に移動した」という標識です。これにより、(0,3)を指すインデックスエントリは引き続き行を見つけます。BERNOULLIは標識を読みません。これは行ポインタ76をハッシュ化し、これは新しい1%のコインフリップであるため、更新されたほとんどすべての行がサンプルからドロップアウトし、別の1%がドロップインします。

キーをハッシュ化する

シードを固定したい場合、通常は開発またはテスト用のサブセットが毎日同じであることを望みます。アドレスはそれを保証できません。なぜなら、更新や書き直しが行を移動させるからです。主キーは移動しないため、キーをハッシュ化します。

SELECT * FROM orders WHERE (hashint8extended(id, 42) & 1023) < 10;

hashint8extendedはシード付きのbigintをハッシュ化します。1,024個のバケットのうち10個を保持すると、行の0.98%が返されます。同じ変更を経ても、削除、UPDATE、VACUUM FULL、CLUSTERを含めて、すべての生き残った行を各ステップで保持しました。バンドルもありません。200シードでのavg(created_at)の変動は、BERNOULLIのものと一致します。

キーは外部キーにもなり得ます。customersをhashint8extended(id, 42)で、ordersをhashint8extended(customer_id, 42)でサンプリングすると、19,432件の注文すべてを持つ484件の顧客が得られます。同じ2つのテーブルをSYSTEM (1) REPEATABLE (42)でサンプリングすると、サンプリングされた注文の17,517件が、サンプルに含まれていない顧客を指します。

価格はフルスキャンです。なぜなら、ハッシュは各行に対して計算する必要があるからです。シリアルでは44.4ミリ秒、2つの並列ワーカーでは21.5ミリ秒です。頻繁に取得するサブセットの場合、(hashint8extended(id, 42) & 1023)（ここでは14 MB）の式インデックスは、それを8.5ミリ秒のビットマップスキャンに変換します。シードはインデックス定義で固定されています。

JOINは縮小しない

これまでのすべては1つのテーブルを読み込んでいました。注文を顧客に結合してカウントします。

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) FROM orders o JOIN customers c ON c.id = o.customer_id;

フルジョインは、2つのワーカーによる並列ハッシュジョインで84.4ミリ秒で回答します。18,751回のバッファヒットのうち、666回を除いてすべてがordersに対して行われました。注文側をサンプリングします。

EXPLAIN (ANALYZE, BUFFERS)
SELECT count(*) * 100
FROM orders o TABLESAMPLE SYSTEM (1) REPEATABLE (7)
JOIN customers c ON c.id = o.customer_id;

 Aggregate
   Buffers: shared hit=424
   ->  Hash Join (actual rows=22316.00 loops=1)
         Hash Cond: (o.customer_id = c.id)
         ->  Sample Scan on orders o (actual rows=22316.00 loops=1)
               Sampling: system ('1'::real)
               Buffers: shared hit=202
         ->  Hash
               Buckets: 65536  Batches: 1  Memory Usage: 2270kB
               Buffers: shared hit=222
               ->  Seq Scan on customers c (actual rows=50001.00 loops=1)
                     Buffers: shared hit=222
 Execution Time: 25.590 ms

サンプルスキャンはその役割を果たし、18,085ページに対して202ページでした。customersに対するハッシュは、サンプルのサイズを小さくするのはそれが座っているテーブルだけなので、依然としてそのすべての222ページを読み込みます。ハッシュの構築は、25.6ミリ秒のうちの11.5ミリ秒を占めます。クエリは90倍ではなく、3.3倍速くなります。残りの大部分は、サンプルがまったく触れなかったテーブルです。ワーカーもいなくなりました。サンプルスキャンはリーダープロセスで実行されるため、テーブルのサイズに関係なくプランはシリアルにフォールバックします。

別のジョイン形状を強制すると、コストが削除されるのではなく移動します。

SET enable_hashjoin = off;
SET enable_mergejoin = off;

同じクエリは、22,316回のcustomers_pkeyに対するインデックスオンリースキャン、サンプルの202ページに対する44,636回のバッファヒットを実行し、21.6ミリ秒で完了します。サンプリングされた各行は、顧客ルックアップの全コストを支払います。

反対側の述語は通常通り機能します。WHERE c.id <= 500を追加すると、500行に対するハッシュが構築され、1.5ミリ秒で回答します。ただし、一部の質問は完全に壊れます。50,001人の顧客すべてに注文がありますが、1%のサンプルでは次のようになります。

SELECT count(DISTINCT customer_id) FROM orders TABLESAMPLE SYSTEM (1) REPEATABLE (7);

 count
-------
 18034

100倍しても、すべての注文が外れたページに配置された顧客を戻すことはできません。サンプルは、それが保持したものの合計とカウントをスケールしますが、カウントするために見る必要があるものはすべて低く出てきます。

ジョイン出力を直接サンプリングすることはオプションではありません。TABLESAMPLEはFROM句の1つのテーブルにアタッチされ、ジョインやサブクエリに配置すると構文エラーになります。両側をサンプリングするのが最も近い方法ですが、ほとんど役に立ちません。

SELECT count(*)
FROM orders o TABLESAMPLE SYSTEM (1) REPEATABLE (7)
JOIN customers c TABLESAMPLE SYSTEM (1) REPEATABLE (7) ON c.id = o.customer_id;

 count
-------
   288

実際のジョインは200万行です。2つの独立したアドレス描画は288行を保持します。なぜなら、サンプリングされた注文がその顧客を見つけるのは、両方のページハッシュが一致するペアを保持した場合だけだからです。サンプリングされたテーブルのペアが結合可能である必要がある場合、両側で外部キーをハッシュ化するのがその方法です。

どちらを選ぶか

挿入順序とは無関係な列に対する迅速な数値を得るにはSYSTEM。そうでない可能性があり、テーブル全体を一度読むことが許容できる場合はBERNOULLI。サブセットが翌日も同じ行である必要がある場合、または外部キーを維持する必要がある場合は、ハッシュ化されたキー。フィルタリングされたサブセットが必要な場合は、どれも役に立ちません。サンプルはWHERE句が実行される前に選択されるため、フィルターは既に作成された描画をトリミングするだけです。

ANALYZEもサンプルからpg_statsを構築します。独自のブロックサンプラーと設定できないシードを使用するため、データが変わらない場合でも実行間で数値が変動します。