HN 日本語サマリー

← 一覧へ戻る
プログラミング

COUNTにおけるDISTINCT

The DISTINCT in Your COUNT (boringsql.com)

17 pointsby gmcabrita3 コメント

要約

PostgreSQLにおいて、COUNT(DISTINCT column)のような集計関数にDISTINCT句が含まれると、クエリ全体が並列実行できなくなり、パフォーマンスが著しく低下することがあります。これは、DISTINCT集計の性質上、各ワーカーが個別の結果をマージする際に重複を排除するための情報を共有できないためです。この問題を回避するには、GROUP BY句を使って事前に重複を除去し、その後でグループ数をカウントするリライト手法が有効です。

全文翻訳

COUNTにおけるDISTINCT

あらゆる分析ワークロードで目にするクエリがあります。

SELECT count(DISTINCT user_id) FROM events;

これは、最も単純な処理のように見えます:ユニークなユーザー数をカウントする。コアに余裕のあるマシンであれば、Postgresが複数の並列ワーカーを割り当ててすぐに完了すると期待するでしょう。しかし、そうはなりません。そのたった一つのキーワード、DISTINCTが、クエリ全体で並列クエリを無効にしてしまい、テーブルが大きくなるほどそのコストは増大します。さらに悪いことに、それに対する設定やインデックスの変更もありません。問題は、集計処理がどのように実行されるかという点にあります。

スキーマ

1000万件のイベント、約5万人のユニークユーザー、少数の国。何も珍しいことはありません。

CREATE TABLE events (
    id      bigint GENERATED ALWAYS AS IDENTITY,
    user_id int    NOT NULL,
    country text   NOT NULL,
    amount  numeric(10,2) NOT NULL
);

INSERT INTO events (user_id, country, amount)
SELECT (random()*50000)::int + 1,
       (ARRAY['US','DE','GB','FR','JP','BR','IN','CA'])[(random()*7)::int + 1],
       (random()*500)::numeric(10,2)
FROM generate_series(1, 10000000);

ANALYZE events;

max_parallel_workers_per_gatherは、新規クラスターではデフォルトの2に設定されています。これらの例では、これを4に、work_memを64MBに引き上げたため、以下のプランでリソース不足が原因ということはありません。

2つのCOUNT、2つの異なるプラン

単純なcount(*)から始めましょう。これは重複排除するものが何もありません。

EXPLAIN (ANALYZE, COSTS OFF) SELECT count(*) FROM events;
 Finalize Aggregate (actual rows=1.00 loops=1)
   ->  Gather (actual rows=5.00 loops=1)
         Workers Planned: 4
         Workers Launched: 4
         ->  Partial Aggregate (actual rows=1.00 loops=5)
               ->  Parallel Seq Scan on events (actual rows=2000000.00 loops=5)

4つのワーカーとリーダー(loops=5)がそれぞれスライスをスキャンし、実行中のカウントを保持し、リーダーが最後に5つの部分的なカウントを合計します。

ここで、一つの単語を追加します。

EXPLAIN (ANALYZE, COSTS OFF, BUFFERS) SELECT count(DISTINCT user_id) FROM events;
 Aggregate (actual rows=1.00 loops=1)
   Buffers: shared hit=15915 read=47783, temp read=14681 written=14684
   ->  Sort (actual rows=10000000.00 loops=1)
         Sort Key: user_id
         Sort Method: external merge  Disk: 117448kB
         Buffers: shared hit=15915 read=47783, temp read=14681 written=14684
         ->  Seq Scan on events (actual rows=10000000.00 loops=1)
               Buffers: shared hit=15912 read=47783

GatherもPartial Aggregateも、並列スキャンもありません。単一のプロセスが1000万行すべてを読み込み、user_idでそれらすべてをソートして重複を隣接させ、ソートされた出力をウォークして実行回数をカウントします。ソートは64MBのwork_memに収まらないため、115MBをディスク上のテンポラリファイルにスピルします。並列count(*)が決して触れなかったディスクI/Oに加え、1つのコアでテーブル全体を処理します。

プランナーが分割できない理由

Postgresの並列集計は2つの部分で機能します。各ワーカーは、見た行の部分的な状態(transition state)を構築するPartial Aggregateを実行します。countの場合、その状態は単なる数値です。リーダーは、集計の結合関数(combine function)でこれらの部分的な状態をマージするFinalize Aggregateを実行します。これは、2つの部分的な状態を1つに折りたたむ方法を知っています。countの結合関数は部分的なカウントを加算します。sum、avg、min、maxも同様の関数を持っています。並列スキャンし、最後に結合する。それが並列集計のロジック全体です。

count(DISTINCT user_id)には、有用な結合ステップがありません。これは、誰かがそれを実装しなかったからではありません。ワーカーが何を返せるかを考えてみてください。2つのワーカーの結果を正しいグローバルなユニークカウントにマージするには、リーダーは各ワーカーがどのユーザーを見たかを知る必要があります。なぜなら、ワーカー1のスライスに現れ、再びワーカー2のスライスに現れるユーザーは、2回ではなく1回だけカウントされる必要があるからです。ユニーク値の部分カウントは結合できません。グループのハッシュテーブルはワーカー間でマージできます。しかし、カウントになったユニークカウントはマージできません。

すべてのワーカーからユニーク値のセット全体を送信して、それらを結合する必要があります。その時点で、すでにすべてのデータを1か所に移動させていることになり、これは並列集計が存在する理由そのものを回避しています。

DISTINCT(または内部のORDER BY)を持つ集計は、部分モードで実行できないため、プランナーはPartial AggregateをGatherの下に配置できません。フィードするための部分的な集計がないため、並列スキャンは何もメリットをもたらしません。プラン全体がシリアルにフォールバックします。

このチェックは、PostgreSQL 17.10、18.4、および19beta1で実行されました。部分集計は、それらのいずれでもまだユニークおよび順序付けられた集計をカバーしていません。

debug_parallel_queryは、これが並列実行を優先するコスト見積もりではないことを確認する方法です。onに設定すると、オプティマイザがシリアル実行の方が安いと判断した場合でも、プランナーは並列プランが合法な場所であればそれを選択します。

SET debug_parallel_query = on;
EXPLAIN (COSTS OFF) SELECT count(DISTINCT user_id) FROM events;
 Gather
   Workers Planned: 1
   Single Copy: true
   ->  Aggregate
         ->  Sort
               Sort Key: user_id
               ->  Seq Scan on events

Gatherが表示されますが、Workers Planned: 1とSingle Copy: trueが付いています。1つのプロセスがプラン全体(ソートを含む)を実行し、Gatherノードは、その出力をエグゼキュータの並列メカニズムを通じてルーティングするためだけに存在します。集計、ソート、またはスキャンのいずれも実際にワーカー間で分割されません。これは、debug_parallel_queryが、部分集計で作業を分割できないプランに並列インフラストラクチャを強制し、2番目のワーカーが実行できるものを見つけられなかったためです。

FILTER句にはこの問題はありません。

EXPLAIN (COSTS OFF) SELECT count(*) FILTER (WHERE country='US') FROM events;
 Finalize Aggregate
   ->  Gather
         Workers Planned: 4
         ->  Partial Aggregate
               ->  Parallel Seq Scan on events

単純なcount(*)と同じ並列形状です。FILTERは、各ワーカーがどの行を部分カウントに折り込むかを決定するだけです。

1つのDISTINCTがステートメント全体を毒する

コストはユニーク集計に限定されません。それは、クエリブロックが共有する集計ノードにスコープされます。完全に並列化可能な集計を、同じSELECT内のユニークなものと並べて配置すると、両方が並列化を失います。これは、両方を計算する1つのAggregateノードがあり、それは1つの方法でしか実行できないためです。サブクエリまたはCTEで分離された集計は異なるノードであり、影響を受けません。

EXPLAIN (COSTS OFF) SELECT sum(amount), count(DISTINCT user_id) FROM events;
 Aggregate
   ->  Sort
         Sort Key: user_id
         ->  Seq Scan on events

sum(amount)自体は4つのワーカーで実行されたでしょう。count(DISTINCT)と共有するSELECTは、それを同じシリアルソートに引きずり降ろします。

リライト:DISTINCTをGROUP BYに押し込む

Postgresが並列化できる唯一の操作であるGROUP BYで重複排除を行い、その後でグループをカウントします。

SELECT count(*)
FROM (SELECT user_id FROM events GROUP BY user_id) s;

GROUP BY user_idはまさに「ユニークなユーザーID」であり、グルーピングには部分モードがあります。各ワーカーは、見たグループの部分的なハッシュを構築し、リーダーはそれらのハッシュをマージします。その後、いくつのグループが出てきたかをカウントするのは簡単です。

EXPLAIN (ANALYZE, COSTS OFF)
SELECT count(*) FROM (SELECT user_id FROM events GROUP BY user_id) s;
 Aggregate (actual rows=1.00 loops=1)
   ->  Finalize HashAggregate (actual rows=50001.00 loops=1)
         Group Key: events.user_id
         Batches: 1  Memory Usage: 3097kB
         ->  Gather (actual rows=250005.00 loops=1)
               Workers Planned: 4
               Workers Launched: 4
               ->  Partial HashAggregate (actual rows=50001.00 loops=5)
                     Group Key: events.user_id
                     Batches: 1  Memory Usage: 3097kB
                     Worker 0:  Batches: 1  Memory Usage: 3097kB
                     Worker 1:  Batches: 1  Memory Usage: 3097kB
                     Worker 2:  Batches: 1  Memory Usage: 3097kB
                     Worker 3:  Batches: 1  Memory Usage: 3097kB
                     ->  Parallel Seq Scan on events (actual rows=2000000.00 loops=5)

リライトは再び並列化されています。4つのワーカーがそれぞれスライスをローカルなユーザーセットにハッシュし、リーダーがそれらをメモリ内の最終的な50,001グループにマージします。ソートやディスクへのスピルはありません。

この10M行テーブルでの壁時計時間の差は、同一ハードウェアおよび設定で、3回の実行の中央値です。

クエリ
count(DISTINCT user_id)
count(*) FROM (… GROUP BY user_id)
プラン
シリアルソート、ディスクへの115MBスピル
並列ハッシュ、メモリ内
時間
1211 ms
360 ms

近似的な回答で十分な場合、これはHyperLogLogが解決するために設計された問題です。そのスケッチは小さな状態であり、原理的には、正確なユニークカウントが欠いている結合関数を持っています。そのため、ワーカーからの部分的なスケッチはマージされるはずです。postgresql-hll拡張機能はそのアイデアに基づいて構築されており、境界付きのエラー率を犠牲にして、ダッシュボードスタイルのユニークカウントによく推奨されます。

どちらも50001を返します。リライトはここで約3.4倍高速であり、テーブルが大きくなるにつれてその差は広がるはずです。シリアルソートのコストは行数とともに増加しますが、並列ハッシュは各ワーカーでスループットを増やし続けます。

ORDER BY集計も同じ壁にぶつかる

このブロックはDISTINCTに限定されません。入力に特定の順序が必要な集計、順序付きセット集計および順序付き集計は、同じ理由で並列化に失敗します。なぜなら、ワーカーのローカルに順序付けられた部分的な結果は、ワーカー間で再順序付けなしにマージできないからです。

EXPLAIN (COSTS OFF) SELECT string_agg(country, ',' ORDER BY country) FROM events;
 Aggregate
   ->  Sort
         Sort Key: country
         ->  Seq Scan on events

内部にORDER BYを持つstring_agg、array_agg、json_agg、およびpercentile_cont/percentile_discはすべてここに該当します。グローバルな順序またはグローバルなユニーク性を主張する集計がある場合は、EXPLAINがそうでないと告げるまで、それが1コアで実行されると想定してください。

より難しいケース:グループごとのユニークカウント

上記のクリーンなリライトは、テーブル全体に対する単一のユニークカウント用です。同じクエリのグループごとのバージョン、

SELECT country, count(DISTINCT user_id) FROM events GROUP BY country;

もシリアルです(country, user_idでソートされたGroupAggregate)。同じ考え方が適用されます。ワーカーが分割できるグルーピングでまず重複排除を行い、その後集計します。

SELECT country, count(*)
FROM (SELECT country, user_id FROM events GROUP BY country, user_id) s
GROUP BY country;

これは作業を並列化可能にしますが、プランナーが実際に並列パスを選択するかどうかは、カーディナリティとコストに依存します。私のテストでは、全体カウントのリライトは確実に並列化されましたが、このスタックされたグルーピング形式は、プランナーが2つのハッシュ集計レイヤーをすでに十分に安価と判断したため、シリアルにとどまることがありました。ルールは同じです。まずGROUP BYにユニーク性をプッシュしますが、それに信頼する前にEXPLAINを確認してください。

本当に気にするべき時

小さなテーブルでは、これらは実際には何も問題になりません。スキャンが数千行であれば、シリアル処理は瞬時に完了し、リライトはノイズを追加するだけです。ユニーク集計のペナルティは、単一コアがソートしなければならない行数に比例する関数であるため、まさにそれが痛いところで現れます。大規模なファクトテーブルや、他のコアがアイドル状態である間に単一コアで実行される夜間ロールアップなどです。

EXPLAIN (ANALYZE)での兆候は、一度知っていれば間違いありません。真上にGatherがないトップレベルのAggregate、大きなSortとexternal merge ... Disk:の行、そしてテーブル全体に対する単一のloops=1スキャンです。それがユニークまたは順序付き集計の上にある形状を、重要なテーブルで見た場合は、リライトする価値があります。