PostgreSQLのカウントを高速化する方法

写真ソース

誰もが数える方法を知っていますが、誰もがすぐに数える方法を知っているわけではありません。 この記事では、PostgreSQLのカウント最適化方法を詳しく見ていきます。 行数のカウントを桁違いに高速化できるトリックがあります。

真剣に問題に取り組む場合、 countのいくつかのオプションを強調表示する必要があります 。各オプションには独自のメソッドがあります。 決定する必要があるもの：

• 行の正確な数が必要かどうか、または推定で十分かどうか
• 重複を考慮する必要があるか、一意の値のみに関心があるか。
• テーブルのすべての行をカウントする必要があるかどうか、または特定の条件を満たす行のみを選択する必要があるかどうか。

特定の状況ごとにソリューションを分析し、速度とリソース消費を比較します。 一元化されたデータベースの状況を調べた後、Citusを使用して、分散データベースでのcountの並列実行を実証します。

内容

• DBの準備
• 重複して数える
  
  • 正確なカウント
  • 格付け
    
    • テーブル全体のスコア
    • サンプルのスコア
• 明確なカウント（重複なし）
  
  • 正確なカウント
    
    • メモリ不足のデフォルト動作
    • 特殊な集約
    • ハッシュ集計
    • インデックスオンリースキャン
  • 格付け
    
    • HyperLogLog
• 並列化
  
  • クラスターのセットアップ
  • 正確なカウント
    
    • 重複あり
    • 個別（重複なし）
  • 重複なしでスコア
• まとめ

DBの準備

テストでは、 pgbenchが初期化されるcountというデータベースを使用します。

[user@comp ~]$ pgbench -i count 

テストテーブルを作成します。

 --       CREATE TABLE items AS SELECT (random()*1000000)::integer AS n, md5(random()::text) AS s FROM generate_series(1,1000000); --        VACUUM ANALYZE; 

重複して数える

正確なカウント

したがって、最初から始めましょう。テーブル全体または重複部分がある部分の正確な行数-古き良きcount(*)取得することを検討します。 このコマンドのランタイムは、行数をカウントする他の方法の速度を評価するための基礎を提供します。

Pgbenchは、パフォーマンス統計を繰り返し照会および収集するための便利なツールです。

 #     PostgreSQL 9.5.4 echo "SELECT count(*) FROM items;" | pgbench -d count -t 50 -P 1 -f - # average 84.915 ms # stddev 5.251 ms 

count(1) vs count(*)に関するメモ。 count(*)は現在の行のすべての列の値を処理する必要があるため、 count(1)速いと考えるかもしれません。 実際にはその逆です。 SELECT *構造とは異なり、 count(*)内のアスタリスクcount(*)は何も意味しません。 PostgreSQLは、式count(*)を引数なしのカウントの特殊なケースとして扱います。 （この式をcount()形式で記述するのが正しいでしょう）。 一方、 count(1)は1つの引数を取り、PostgreSQLはこの引数（1）が実際にNULLでないことを各行で確認する必要があります。

count(1)を使用した以前のテストでは、次の結果が生成されました。

 # average 98.896 ms # stddev 7.280 ms 

いずれにせよ、 count(1)とcount(*)どちらも定義上低速です。 同時トランザクションの一貫性を確保するために、PostgreSQLはMultiversion Concurrency Control（MVCC）を使用します。 これは、各トランザクションがテーブル内の異なる行、さらに異なる行数を見ることができることを意味します。 したがって、DBMSがキャッシュに入れることができる行の数に対して単一の正しい値はありません。システムはすべての行をスキャンして、どの行が単一のトランザクションから見えるかを計算する必要があります。 正確なカウントの実行時間は、テーブルのサイズの増加に比例して増加します。

 EXPLAIN SELECT count(*) FROM items; Aggregate (cost=20834.00..20834.01 rows=1 width=0) -> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=0) 

要求コストの88％のアカウントをスキャンします。 テーブルのサイズを2倍にすると、 スキャンと集計のコストが比例して増加し、クエリの実行時間が約2倍になります 。

スピードアップする方法は？ 2つのオプションがあります：推定値が必要であることを決定するか、自分でキャッシュに行数を入れます。 2番目のケースでは、各テーブルの値と、 countをすばやく実行する各WHERE式を個別に保存する必要があります 。

itemsテーブル全体のcount(*)値を手動でキャッシュする例を見てみましょう。 次のトリガーベースのソリューションは、 A。Elein Mustainによって提案された方法の適応です。 PostgreSQL MVCCエンジンは、 itemsと行カウント値を含むテーブルとの間の一貫性を維持します。

 BEGIN; CREATE TABLE row_counts ( relname text PRIMARY KEY, reltuples bigint ); --       INSERT INTO row_counts (relname, reltuples) VALUES ('items', (SELECT count(*) from items)); CREATE OR REPLACE FUNCTION adjust_count() RETURNS TRIGGER AS $$ DECLARE BEGIN IF TG_OP = 'INSERT' THEN EXECUTE 'UPDATE row_counts set reltuples=reltuples +1 where relname = ''' || TG_RELNAME || ''''; RETURN NEW; ELSIF TG_OP = 'DELETE' THEN EXECUTE 'UPDATE row_counts set reltuples=reltuples -1 where relname = ''' || TG_RELNAME || ''''; RETURN OLD; END IF; END; $$ LANGUAGE 'plpgsql'; CREATE TRIGGER items_count BEFORE INSERT OR DELETE ON items FOR EACH ROW EXECUTE PROCEDURE adjust_count(); COMMIT; 

この場合のキャッシュ値の読み取りと更新の速度はテーブルのサイズに依存せず、行数の値の取得は非常に高速です。 ただし、この手法では、挿入および削除操作のオーバーヘッドが増加します。 トリガーを使用しない場合、次のコマンドは4.7秒で実行されますが、トリガーを使用した挿入では50倍遅くなります 。

 INSERT INTO items (n, s) SELECT (random()*1000000)::integer AS n, md5(random()::text) AS s FROM generate_series(1,1000000); 

格付け

テーブル全体のスコア

テーブル内の行数をキャッシュするアプローチにより、貼り付け操作が遅くなります。 正確な数ではなく、推定値に満足する準備ができている場合、挿入時間に影響を与えずに高速の読み取り操作を取得できます。 このために、PostgreSQLによって収集されたオーバーヘッドを使用できます。 それらのソースは、 統計情報コレクタと自動バキュームデーモンです。

推定値を取得するためのオプション：

 --   "stats collector" SELECT n_live_tup FROM pg_stat_all_tables WHERE relname = 'items'; --  VACUUM  ANALYZE SELECT reltuples FROM pg_class WHERE relname = 'items'; 

しかし、より信頼性の高いソースがあり、そのデータはより頻繁に更新されます。 Andrew Gierth（RhodiumToad）のアドバイス：

覚えておいてください：スケジューラは実際にはreltuplesを使用しません; reltuples / relpages比に現在のページ数を掛けます。

ここでのロジックは次のとおりです。テーブル内のデータ量が増加しても、物理ページに収まる行の平均数は通常、合計数ほど変化しません。 現在の行数のより正確な推定値を取得するために、平均行数に、テーブルが占有している現在のページ数に関する現在の情報を掛けることができます。

 -- pg_relation_size  block_size   , --        --      SELECT (reltuples/relpages) * ( pg_relation_size('items') / (current_setting('block_size')::integer) ) FROM pg_class where relname = 'items'; 

サンプルのスコア

前のセクションでは、テーブル全体の推定行数を取得することを検討しましたが、同じことは可能ですが、 WHERE一致する行に対してのみ可能ですか？ Michael Fuhrは興味深い方法を思いつきました。クエリに対してEXPLAINを実行し、結果を分析します。

 CREATE FUNCTION count_estimate(query text) RETURNS integer AS $$ DECLARE rec record; rows integer; BEGIN FOR rec IN EXECUTE 'EXPLAIN ' || query LOOP rows := substring(rec."QUERY PLAN" FROM ' rows=([[:digit:]]+)'); EXIT WHEN rows IS NOT NULL; END LOOP; RETURN rows; END; $$ LANGUAGE plpgsql VOLATILE STRICT; 

この関数は次のように使用できます。

 SELECT count_estimate('SELECT 1 FROM items WHERE n < 1000'); 

このメソッドの精度は、 WHERE選択性を評価するためにさまざまなメソッドを使用するスケジューラーと、クエリから返される行数を取得できる場所に依存します。

明確なカウント（重複なし）

正確なカウント

メモリ不足のデフォルト動作

重複したカウントはゆっくり実行される場合がありますが、個別カウントの方がはるかに悪いです。 限られた作業メモリとインデックスなしでは、PostgreSQLは最適化を効率的に実行できません。 デフォルト構成では、DBMSは各並列リクエスト（ work_mem ）にハード制限を課します。 開発に使用するコンピューターでは、このデフォルト値は4メガバイトに設定されていました。

work_mem工場設定で100万行を処理するパフォーマンスを評価しましょう。

 echo "SELECT count(DISTINCT n) FROM items;" | pgbench -d count -t 50 -P 1 -f - # average 742.855 ms # stddev 21.907 ms echo "SELECT count(DISTINCT s) FROM items;" | pgbench -d count -t 5 -P 1 -f - # average 31747.337 ms # stddev 267.183 ms 

EXPLAINを実行すると、クエリの実行時間のほとんどが集約に費やされたことがわかります。 また、 テキストタイプの列の行数をカウントすることは、整数よりもはるかに遅いことに注意してください。

 --     "integer", n Aggregate (cost=20834.00..20834.01 rows=1 width=4) (actual time=860.620..860.620 rows=1 loops=1) Output: count(DISTINCT n) Buffers: shared hit=3904 read=4430, temp read=1467 written=1467 -> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.005..107.702 rows=1000000 loops=1) Output: n, s Buffers: shared hit=3904 read=4430 --     "text", s Aggregate (cost=20834.00..20834.01 rows=1 width=33) (actual time=31172.340..31172.340 rows=1 loops=1) Output: count(DISTINCT s) Buffers: shared hit=3936 read=4398, temp read=5111 written=5111 -> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=33) (actual time=0.005..142.276 rows=1000000 loops=1) Output: n, s Buffers: shared hit=3936 read=4398 

「集合体」の内部で何が起こりますか？ EXPLAIN出力のこのプロシージャの説明は不透明です。 同様のクエリの分析は、状況を理解するのに役立ちます。 count distinctをselect distinct置き換えcount distinct 。

 EXPLAIN (ANALYZE, VERBOSE) SELECT DISTINCT n FROM items; Unique (cost=131666.34..136666.34 rows=498824 width=4) (actual time=766.775..1229.040 rows=631846 loops=1) Output: n -> Sort (cost=131666.34..134166.34 rows=1000000 width=4) (actual time=766.774..1075.712 rows=1000000 loops=1) Output: n Sort Key: items.n Sort Method: external merge Disk: 13632kB -> Seq Scan on public.items (cost=0.00..18334.00 rows=1000000 width=4) (actual time=0.006..178.153 rows=1000000 loops=1) Output: n 

work_memが不十分で、外部データ構造（インデックスなど）が存在しない状況では、PostgreSQLはメモリとディスク間でマージソートテーブルを実行し 、結果を反復して重複を削除しsort | uniq sort | uniq

特に整数列nではなく、文字列sを使用する場合、ソートはクエリの実行時間の大部分を占めます。 両方の場合の重複（一意のフィルター）の削除は、ほぼ同じ速度で実行されます。

特殊な集約

一意の値の数をカウントするために、Thomas Vondraは、長さが制限されたタイプ（64ビットを超えてはならない）で機能する特殊な集約メソッドを作成しました。 この方法は、作業メモリを増やしたりインデックスを作成したりしなくても、デフォルトのソートベースの方法よりも高速です。 次の手順に従ってインストールします。

1. tvondra / count_distinctプロジェクトのコピーを作成します。
2. 安定したブランチに切り替えます： git checkout REL2_0_STABLE 。
3. make install実行します。
4. データベースで、 CREATE EXTENSION. count_distinct;実行しますCREATE EXTENSION. count_distinct; CREATE EXTENSION. count_distinct; 。

この記事では、 Thomasが集計の仕組みについて説明しています。 彼のメソッドはメモリ内に一意の要素のソートされた配列を作成し、プロセスでそれを圧縮すると簡単に言います。

 echo "SELECT COUNT_DISTINCT(n) FROM items;" | pgbench -d count -t 50 -P 1 -f - # average 434.726 ms # stddev 19.955 ms 

これは、テストデータで平均742ミリ秒で実行される標準カウントdistinctよりも速く動作します。 count_distinctなど、Cで記述された拡張機能はwork_memパラメーターに限定されないため、プロセスで作成された配列は、当初計画したよりも多くのメモリを接続ごとに使用する可能性があることに注意してください。

ハッシュ集計

再計算されたすべての列がwork_memに収まる場合、PostgreSQLはハッシュテーブルを使用して一意の値を取得します。

 SET work_mem='1GB'; EXPLAIN SELECT DISTINCT n FROM items; HashAggregate (cost=20834.00..25822.24 rows=498824 width=4) Group Key: n -> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=4) 

これは、調査した方法の中で最速です。 nで平均372ミリ秒、 s 23秒で実行されます。 select distinct n select count(distinct n)をselect count(distinct n)と、ハッシュの集計もHashAggregateに適用されることを条件に、 select count(distinct n) select distinct nおよびselect count(distinct n)クエリはほぼ同じ時間動作します。

注意： work_memは各並列リクエストを参照するため、作業メモリに高い制限を設定すると、不快な結果を招く可能性があります。 さらに、より良いものを思いつくことができます。

インデックスのみのスキャン

この機能はPostgreSQL 9.2で登場しました。 インデックスにクエリに必要なすべてのデータが含まれている場合、システムはテーブル自体（「ヒープ」）に触れることなく、インデックスのみを使用できます。 インデックスタイプはインデックスのみのスキャンをサポートする必要があります （例： btree ）。 GiSTおよびSP-GiSTインデックスは、特定のクラスの演算子に対してのみインデックスのみのスキャンをサポートします 。

列nおよびs btreeインデックスを作成します。

 CREATE INDEX items_n_idx ON items USING btree (n); CREATE INDEX items_s_idx ON items USING btree (s); 

これらの列から一意の値を選択するために、別の戦略が使用されるようになりました。

 EXPLAIN SELECT DISTINCT n FROM items; Unique (cost=0.42..28480.42 rows=491891 width=4) -> Index Only Scan using items_n_idx on items (cost=0.42..25980.42 rows=1000000 width=4) 

しかし、ここで奇妙な問題に遭遇しSELECT COUNT(DISTINCT n) FROM itemsは、 SELECT DISTINCT nがデフォルトでこれを行うにもかかわらず、インデックスを使用しません。 ブログのヒント（ 「postgresを50倍高速化するトリック！」 ）に従うことで、サブクエリのcountとはcount distinct countを書き換えることにより、スケジューラーにヒントを与えることができます。

 -- SELECT COUNT(DISTINCT n) FROM items; --      EXPLAIN SELECT COUNT(*) FROM (SELECT DISTINCT n FROM items) t; Aggregate (cost=34629.06..34629.07 rows=1 width=0) -> Unique (cost=0.42..28480.42 rows=491891 width=4) -> Index Only Scan using items_n_idx on items (cost=0.42..25980.42 rows=1000000 width=4) 

順序対称の二分木探索は高速です。 このクエリの平均所要時間は177ミリ秒（列s 270ミリ秒）です。

備考 work_memの値がテーブル全体をホストするのに十分な場合、PostgreSQLはインデックスが存在する場合でもHashAggregateを選択します。 これは逆説です。システムにより多くのメモリを割り当てると、最悪のクエリプランが選択されることになります。 SET enable_hashagg=false;設定することにより、 インデックスのみのスキャンの選択を強制することができSET enable_hashagg=false; 、他のリクエストの計画を損なわないように、 trueに戻すことを忘れないでください。

格付け

HyperLogLog

以前に検討された方法は、インデックス、ハッシュテーブル、メモリ内のソートされた配列、または集中型データベースの統計テーブルへのアクセスに依存します。 本当に大量のデータがある場合、および/またはそれらが分散データベースの複数のノード間で共有される場合、これらの方法は私たちに適さなくなります。

この場合、確率的データ構造が助けになります。これは、大まかな見積もりをすばやく行うことができ、十分に並列化されています。 count distinctでこれらの構造の1つを試してみましょう。 HyperLogLog（HLL）と呼ばれるカーディナリティー推定量を検討してください。 一連の要素を表すために少量のメモリを使用します。 このメカニズムの和集合演算は損失なしで機能するため、数量推定の精度を損なうことなく任意のHLL値を組み合わせることができます。

HLLは、「良い」ハッシュ関数のプロパティ、特にハッシュ値間の距離を使用します。 値を均等に分布させる関数は、値を可能な限り広げる傾向があります。 新しいハッシュが追加されると、空き領域が小さくなり、要素が互いにくっつき始めます。 ハッシュ値間の最小距離を分析することにより、アルゴリズムはソース要素の最も可能性の高い数を推定できます。

速度を測定しましょう。 まず、PostgreSQLの拡張機能をインストールします。

1. postgresql-hllプロジェクトのコピーを作成します。
2. make install実行します。
3. データベースにhll拡張機能を作成します。CREATE CREATE EXTENSION hll; 。

HLLは、テーブルの順次スキャン（順次スキャン）中に高速データ集約を実行します。

 EXPLAIN SELECT #hll_add_agg(hll_hash_integer(n)) FROM items; Aggregate (cost=23334.00..23334.01 rows=1 width=4) -> Seq Scan on items (cost=0.00..18334.00 rows=1000000 width=4) 

count distinct実行するときの平均HLL速度は、列n 239ミリ秒、 s 284ミリ秒でした。 100万件のレコードのインデックスのみのスキャンよりも少し遅くなりました。 HLLの真の強さは、損失なしに行われる連想および可換の和集合演算により明らかになります。 これは、それらを並行して実行し、組み合わせて最終結果を計算できることを意味します。

並列化

Googleアナリティクスなどのリアルタイム分析を収集するアプリケーションは、 countを積極的に使用し、この操作は十分に並列化されています。 このセクションでは、 Citus Cloudにデプロイされた小さなCitusクラスターに基づいて、いくつかの行カウント方法のパフォーマンスを測定します。

アイデアは、分散データベースノードを複数のマシンに展開することです。 ノードは同じスキームを持ち、各ノードには一般的なデータセット（シャード）の一部が含まれます。 行数のカウントは、並行して、つまり異なるマシンで同時に実行されます。

クラスターのセットアップ

私たちの目標は比較パフォーマンスを評価することであり、最大速度を取得しないため、テストでは小さなクラスターのみを作成します。

Citus Cloudでは、8台のマシンのクラスターを作成し、各マシンに可能な限り弱い構成を選択しました。 この例を再現したい場合は、 ここに登録してください 。

クラスターを作成した後、調整ノードに接続してSQLクエリを実行します。 まず、テーブルを作成します。

 CREATE TABLE items ( n integer, s text ); 

現時点では、テーブルはコーディネーターデータベースにのみ存在します。 テーブルを分割し、その部分を作業ノードに配置する必要があります。 Citusは、選択された分布列（分布列）の値を処理することにより、特定のセグメント（断片）に各行を割り当てます。 次の例では、 itemsテーブルの将来の行を分散するタスクを設定しますn列の値のハッシュを使用して、特定のセグメントに属するかどうかを判断します。

 SELECT master_create_distributed_table('items', 'n', 'hash'); SELECT master_create_worker_shards('items', 32, 1); 

調整ノードを使用して、ランダムデータをデータベースセグメントにロードします。 （Citusは、データをすばやくロードするために使用されるMX （マスターレスモード）もサポートしていますが、現在は興味がありません。）

クラスターコーディネーターデータベースのURLを受信した後、高速ネットワーク接続のコンピューターで次のコードを実行します。 （生成されたデータはすべてこのマシンからネットワークを介して送信されるため、十分な速度が必要です。）

 cat << EOF > randgen.sql COPY ( SELECT (random()*100000000)::integer AS n, md5(random()::text) AS s FROM generate_series(1,100000000) ) TO STDOUT; EOF psql $CITUS_URL -q -f randgen.sql | \ psql $CITUS_URL -c "COPY items (n, s) FROM STDIN" 

集中データベースの例では、100万行を使用しました。 今回は、1億を取りましょう。

正確なカウント

重複あり

通常のカウント （重複なし）は問題を引き起こしません。 コーディネーターは、すべてのノードでクエリを実行し、結果を要約します。 EXPLAIN出力には、作業ノードの1つで選択されたプラン（「分散クエリ」）とコーディネーターで選択されたプラン（「マスタークエリ」）が表示されます。

 EXPLAIN VERBOSE SELECT count(*) FROM items; Distributed Query into pg_merge_job_0003 Executor: Real-Time Task Count: 32 Tasks Shown: One of 32 -> Task Node: host=*** port=5432 dbname=citus -> Aggregate (cost=65159.34..65159.35 rows=1 width=0) Output: count(*) -> Seq Scan on public.items_102009 items (cost=0.00..57340.27 rows=3127627 width=0) Output: n, s Master Query -> Aggregate (cost=0.00..0.02 rows=1 width=0) Output: (sum(intermediate_column_3_0))::bigint -> Seq Scan on pg_temp_2.pg_merge_job_0003 (cost=0.00..0.00 rows=0 width=0) Output: intermediate_column_3_0 

参照用：クラスターでは、このリクエストは1.2秒実行されます。 分散データベースを使用する場合、 個別のカウントはより深刻な問題を引き起こします。

個別（重複なし）

分散データベースで一意の列値を計算することの難しさは、異なるノードで重複を探す必要があることです。 ただし、分布列の値を読み取る場合、これは問題です。 この列に同じ値を持つ行は1つのセグメントに分類され、セグメント間の重複を防ぎます。

Citusは、分布列の一意の値をカウントするには、各ノードでcount distinctのcount distinctクエリを実行し、結果を追加する必要があることを知っています。 クラスターはこのタスクを3.4秒で実行します。

通常の列（非分布）で一意の値の数を見つけることはより困難です。 論理的には、2つの可能性があります。

1. すべての行を調整ノードにコピーし、そこでカウントします。
2. , , , , .

. .

«» (repartitioning). , , , . , . . Citus , .

, HLL, . (non-distribution), . HLL . HLL , , .

Citus postgresql-hll. citus.count_distinct_error_rate , Citus count distinct HLL. 例：

 SET citus.count_distinct_error_rate = 0.005; EXPLAIN VERBOSE SELECT count(DISTINCT n) FROM items; Distributed Query into pg_merge_job_0090 Executor: Real-Time Task Count: 32 Tasks Shown: One of 32 -> Task Node: host=*** port=5432 dbname=citus -> Aggregate (cost=72978.41..72978.42 rows=1 width=4) Output: hll_add_agg(hll_hash_integer(n, 0), 15) -> Seq Scan on public.items_102009 items (cost=0.00..57340.27 rows=3127627 width=4) Output: n, s Master Query -> Aggregate (cost=0.00..0.02 rows=1 width=0) Output: (hll_cardinality(hll_union_agg(intermediate_column_90_0)))::bigint -> Seq Scan on pg_temp_2.pg_merge_job_0090 (cost=0.00..0.00 rows=0 width=0) Output: intermediate_column_90_0 

: 3,2 n 3,8 s . 100 (non-distribution) ! HLL — .

まとめ

index-only scan , HyperLogLog (HLL) (> 100 ). , (distinct count) .