multi-column optimizer statistics

はじめに

にゃーん
この記事は、PostgreSQL 10全部ぬこ Advent Calendar 2017 の25日目、最終日のエントリです。これで完走できた！

最後のネタは検証が面倒くさそうで後回しにしていたmulti-column optimizer statisticsに挑んでみようかと。

この機能はなぜ必要だったのか

PostgreSQLのプランナが実行計画を立てるときに、列単位にANALYZE処理背景で更新された統計情報を使うのだが、列同士の対応関係(多変量相関)は管理していないため、クエリによっては適切な実行計画を立てることができないケースがあった（たぶん）。

PostgreSQL 10での改善

PostgreSQL 10では列間の相関と、固有値の数の情報（拡張統計情報）を管理するための機能が追加された。また、その情報を使って、より適切な実行計画を生成できるようになった（はず）。

システムカタログの追加

この拡張統計情報を管理するために、以下のシステムカタログpg_statistic_extが追加された。

(´-`).oO(どうでもいいが、このSTATISTICSという用語、発音しづらいだろう・・・)

postgres=# \d pg_statistic_ext
                Table "pg_catalog.pg_statistic_ext"
     Column      |      Type       | Collation | Nullable | Default 
-----------------+-----------------+-----------+----------+---------
 stxrelid        | oid             |           | not null | 
 stxname         | name            |           | not null | 
 stxnamespace    | oid             |           | not null | 
 stxowner        | oid             |           | not null | 
 stxkeys         | int2vector      |           | not null | 
 stxkind         | "char"[]        |           | not null | 
 stxndistinct    | pg_ndistinct    |           |          | 
 stxdependencies | pg_dependencies |           |          | 
Indexes:
    "pg_statistic_ext_name_index" UNIQUE, btree (stxname, stxnamespace)
    "pg_statistic_ext_oid_index" UNIQUE, btree (oid)
    "pg_statistic_ext_relid_index" btree (stxrelid)

列名	列の型	参照先	説明
stxrelid	oid	pg_class.oid	このオブジェクトによって記述された列を含む表。
stxname	name		統計オブジェクトの名前。
stxnamespace	oid	pg_namespace.oid	この統計オブジェクトを含む名前空間のOID。
stxowner	oid	pg_authid.oid	統計オブジェクトの所有者。
stxkeys	int2vector	pg_attribute.attnum	この統計オブジェクトによってカバーされる表の列を示す属性番号の配列。 例えば1,3の値は、第1および第3のテーブル列がカバーされていることを意味する。
stxkind	char[]		有効な統計種類のコードを含む配列。 有効な値は次のとおり。 n個の異なる統計情報の場合はd、依存関係の統計情報の場合はf。
stxndistinct	pg_ndistinct		n_distinctの個数。pg_ndistinct型としてシリアライズされる。。
stxdependencies	pg_dependencies		pg_dependencies型としてシリアライズされた依存性統計。

統計情報を追加するSQLコマンド

上記のpg_statistic_extシステムカタログへの登録・更新・削除を行うために、以下のSQLコマンドが追加された。

• ALTER STATISTICS
• CREATE STATISTICS
• DROP STATISTICS

CREATE STATISTICSの構文は以下のようになっている。

CREATE STATISTICS [ IF NOT EXISTS ] statistics_name
    [ ( statistics_kind [, ... ] ) ]
    ON column_name, column_name [, ...]
    FROM table_name

パラメータのstatistics_kindには現状、ndistinctまたは、dependenciesを複数指定することができる。つまり、ndistinctとdependenciesの両方を同時に指定することも可能だ。statistics_kindを省略した場合には、サポートされている全ての統計情報の種別が有効になる。これを別の列にしていないのは、おそらくは今後、拡張統計情報の種別を増やしてもスキーマの変更をなくすためなんだろうな。

また、構文上、column_nameは**最低でも2つ指定しなければならない。**重複する列を指定した場合は以下のようなエラーになる。
ERROR: duplicate column name in statistics definition

拡張統計情報の収集

CREATE STATITICSコマンドで拡張統計情報を作成しただけでは、何も変わらない。
拡張統計情報が存在する状態で、統計情報の収集（SQLコマンドのANALYZEの実行、あるいは自動バキューム背景でのANALYZE処理の実行）が必要になる。

統計情報の収集の実行により、拡張統計情報に収集した統計情報が登録される。この情報を使って、プランナはより適切な実行計画を作成する（はずだ）。

PostgreSQL文書での説明。

このわかったようなわからないような機能、幸いにしてPostgreSQL文書で、それなりに説明はされている。

• 14.2.2. Extended Statistics
• 68.2. Multivariate Statistics Examples

検証

PostgreSQL文書にあった説明＋αのモデルを使って、この機能の効果を見てみよう。
(本当はもっと実案件っぽいケースで検証したかっが、自然なモデルを考えるのが難しかった。にゃーん)

検証モデル

テーブル作成

t1, t2という2つのテーブルを作成する。

mcs=# CREATE UNLOGGED TABLE t1 (a INT, b INT, c TEXT);
CREATE TABLE
mcs=# CREATE UNLOGGED TABLE t2 (a INT, b INT, c TEXT);
CREATE TABLE

t1, t2テーブルともにインデックスはあえて設定しない。

データの登録

t1, t2にデータを100万件づつ登録する。

mcs=# INSERT INTO t1 SELECT i % 1000, i % 1000 , repeat(' ', 100) FROM generate_series(1, 1000000) AS s(i);
INSERT 0 1000000
mcs=# INSERT INTO t2 SELECT i % 1000, i % 1000 , repeat(' ', 100) FROM generate_series(1, 1000000) AS s(i);
INSERT 0 1000000

t1, t2 テーブルともに、以下のような値が100万件格納されている。

• a列には、0,1,2,...999 までの一連の数値群が、1000回繰り返し登録される。
• b列も同じ。
• c列は空白100文字。これはレコードサイズのかさ増し用。スキャンや結合時の処理時間にも効いてくるはず。

妥当でない実行計画が生成される例

では、このt1, t2テーブルに対して結合を行うクエリを実行してみる。

結合条件の他に、t1.aにWHERE条件を付与したクエリの場合

mcs=# EXPLAIN SELECT * FROM t1, t2 WHERE (t1.a=1 ) AND t1.b = t2.b;
                                QUERY PLAN
--------------------------------------------------------------------------
 Hash Join  (cost=56344.00..114310.81 rows=965039 width=218)
   Hash Cond: (t1.b = t2.b)
   ->  Seq Scan on t1  (cost=0.00..29742.00 rows=968 width=109)
         Filter: (a = 1)
   ->  Hash  (cost=27242.00..27242.00 rows=1000000 width=109)
         ->  Seq Scan on t2  (cost=0.00..27242.00 rows=1000000 width=109)
(6 rows)

• t1のFilter後の推定行数は968件
• t2はフルスキャンするので1000000件
• この件数同士だと、Hash Joinが良さげだね、とプランナは判断する。

結合条件の他に、t1.aと、t1.bにWHERE条件を付与したクエリの場合

mcs=# EXPLAIN  SELECT * FROM t1, t2 WHERE (t1.a=1 AND t1.b=1 ) AND t1.b = t2.b;
                           QUERY PLAN
----------------------------------------------------------------
 Nested Loop  (cost=0.00..61993.69 rows=969 width=218)
   ->  Seq Scan on t1  (cost=0.00..32242.00 rows=1 width=109)
         Filter: ((a = 1) AND (b = 1))
   ->  Seq Scan on t2  (cost=0.00..29742.00 rows=969 width=109)
         Filter: (b = 1)
(5 rows)

• t1のFilter後の推定行数は1件・・・え！？(★)
• t2はフルスキャンするので1000000件
• この件数同士だと、Nested Loopが良さげだね、とプランナは判断する。→まちがい

★なぜ、こういう推定行数になるのか

• a=1で選択度は1/1000 になる。
• b=1で選択度は1/1000になる。
• aとbの選択度を乗算すると、選択度は1/1000000になる！
• そして推定行数を、全レコード数1000000件/1000000 = 1件と推定してしまう。

aとbの値が全く無関係なら、それは正しい。しかし、今回のデータの場合、aとbの値は、どのレコードでも同じ値なので、実は選択度は1/1000にすぎない。
つまり、1000件と1000000件との結合になるため、Nested Loopは不向き。のはずだ。

実際の検索

それぞれのクエリをEXPLAIN ALNAYZEで動かし、実際の動作時間を見てみる。

結合条件の他に、t1.aにWHERE条件を付与したクエリの場合

mcs=# EXPLAIN ANALYZE SELECT * FROM t1, t2 WHERE (t1.a=1  ) AND t1.b = t2.b;
                                                        QUERY PLAN
---------------------------------------------------------------------------------------------------------------------------
 Hash Join  (cost=56344.00..114310.81 rows=965039 width=218) (actual time=437.351..566.148 rows=1000000 loops=1)
   Hash Cond: (t1.b = t2.b)
   ->  Seq Scan on t1  (cost=0.00..29742.00 rows=968 width=109) (actual time=1.646..95.689 rows=1000 loops=1)
         Filter: (a = 1)
         Rows Removed by Filter: 999000
   ->  Hash  (cost=27242.00..27242.00 rows=1000000 width=109) (actual time=320.710..320.710 rows=1000000 loops=1)
         Buckets: 32768  Batches: 64  Memory Usage: 2735kB
         ->  Seq Scan on t2  (cost=0.00..27242.00 rows=1000000 width=109) (actual time=0.012..99.707 rows=1000000 loops=1)
 Planning time: 0.118 ms
 Execution time: 599.567 ms

• まあ、Hash Joinでも、ほどほどに時間はかかるが・・・(599.567ms)。
• t1の推定行数(rows=968)と実際の取得件数(rows=1000)の間には、それほど乖離はない。

結合条件の他に、t1.aと、t1.bにWHERE条件を付与したクエリの場合

mcs=# EXPLAIN ANALYZE SELECT * FROM t1, t2 WHERE (t1.a=1 AND t1.b=1 ) AND t1.b = t2.b;
                                                   QUERY PLAN
-----------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..61993.69 rows=969 width=218) (actual time=0.039..78900.821 rows=1000000 loops=1)
   ->  Seq Scan on t1  (cost=0.00..32242.00 rows=1 width=109) (actual time=0.032..134.840 rows=1000 loops=1)
         Filter: ((a = 1) AND (b = 1))
         Rows Removed by Filter: 999000
   ->  Seq Scan on t2  (cost=0.00..29742.00 rows=969 width=109) (actual time=0.006..78.594 rows=1000 loops=1000)
         Filter: (b = 1)
         Rows Removed by Filter: 999000
 Planning time: 0.064 ms
 Execution time: 78952.287 ms
(9 rows)

• グワーッ！ 愚直に1000件 × 1000件のNested Loopめいたことをしているためか、遅い、遅い、実際遅い(78952.287ms)
• t1の推定行数(rows=1)と実際の取得件数(rows=1000)に著しい乖離がある。だいたいこいつのせい。

統計情報の追加

上記の「結合条件の他に、t1.aと、t1.bにWHERE条件を付与したクエリ」の問題は、aとbの値の関係が全くない、とPostgreSQLが想定して実行計画を作成したからだ。
だからといって、PostgreSQLを責めるわけにはいかない。
だって、そんな列間の値の関係なんて情報は、どこにもないのだから。

そこで、列間の値の関係を、拡張統計情報として追加してみる。ここで、お待ちかねのCREATE STATITICSの出番である。

さっそく拡張統計情報の枠を作成する。

mcs=# CREATE STATISTICS t1_stts (dependencies) ON a, b FROM t1;
CREATE STATISTICS

t1_sttsという名前の拡張統計情報が作成された。
実際にシステムカタログ上はどうなっているのかというと、

mcs=# TABLE pg_statistic_ext;
 stxrelid | stxname | stxnamespace | stxowner | stxkeys | stxkind | stxndistinct | stxdependencies
----------+---------+--------------+----------+---------+---------+--------------+-----------------
  1043417 | t1_stts |         2200 |       10 | 1 2     | {f}     |              |
(1 row)

こんな感じで登録されている。

• stxkeysの、1,2 というのは、a列とb列の列番号。
• stxkinfの、{f} というのは、依存関係の拡張情報を収集するという意味だ。
• stxndistinctやstxdependenciesの列には、まだ何も入っていない。

ここでANALYZEを実行して統計情報を再収集する。これによって、拡張統計情報が実際に収集される。

mcs=# ANALYZE t1;
ANALYZE
mcs=# TABLE pg_statistic_ext;
 stxrelid | stxname | stxnamespace | stxowner | stxkeys | stxkind | stxndistinct |             stxdependencies
----------+---------+--------------+----------+---------+---------+--------------+------------------------------------------
  1043417 | t1_stts |         2200 |       10 | 1 2     | {f}     |              | {"1 => 2": 1.000000, "2 => 1": 1.000000}
(1 row)

ANALYZEしたことにより、stxdependenciesに値が設定された。この2": 1.000000, "2 => 1": 1.000000の意味は、

• 列番号1から列番号2への対応関係は、1:1.000000
• 列番号2から列番号1への対応関係は、1:1.000000

を示す。

統計情報追加後の実行計画

拡張統計情報が追加されたので、めっさ遅かった、aとbに条件をつけたクエリを実行してみよう。
・・・とその前に、EXPLAINで実行計画を確認してみる。

mcs=# EXPLAIN SELECT * FROM t1, t2 WHERE (t1.a=1 AND t1.b=1 ) AND t1.b = t2.b;
                              QUERY PLAN
----------------------------------------------------------------------
 Nested Loop  (cost=0.00..77332.96 rows=1227723 width=218)
   ->  Seq Scan on t1  (cost=0.00..32242.00 rows=1267 width=109)
         Filter: ((a = 1) AND (b = 1))
   ->  Materialize  (cost=0.00..29746.85 rows=969 width=109)
         ->  Seq Scan on t2  (cost=0.00..29742.00 rows=969 width=109)
               Filter: (b = 1)
(6 rows)

あら？てっきりHash Joinを選択するのかと思いきや、Nested Loopのままだ。
ただし、片側にはMaterializeノードが中間に入っている。
まあいいや、EXPLAIN ANALYZEしてみよう。

mcs=# EXPLAIN ANALYZE SELECT * FROM t1, t2 WHERE (t1.a=1 AND t1.b=1 ) AND t1.b = t2.b;
                                                     QUERY PLAN
--------------------------------------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..77332.96 rows=1227723 width=218) (actual time=0.032..335.023 rows=1000000 loops=1)
   ->  Seq Scan on t1  (cost=0.00..32242.00 rows=1267 width=109) (actual time=0.023..98.260 rows=1000 loops=1)
         Filter: ((a = 1) AND (b = 1))
         Rows Removed by Filter: 999000
   ->  Materialize  (cost=0.00..29746.85 rows=969 width=109) (actual time=0.000..0.131 rows=1000 loops=1000)
         ->  Seq Scan on t2  (cost=0.00..29742.00 rows=969 width=109) (actual time=0.006..89.877 rows=1000 loops=1)
               Filter: (b = 1)
               Rows Removed by Filter: 999000
 Planning time: 0.106 ms
 Execution time: 368.008 ms
(10 rows)

こうかはばつぐんだ！(Execution time: 78952.287 ms → 368.008 ms)

これは単なる自分の推測だが、拡張統計情報の内容から、aとbの値が全て同じだと判断し、かつその値のバリエーションが1000通りしかないので、Materializeにより1000通りのレコードをメモリ上に保持しておいて、再スキャンの処理をスキップするようにしたのだろう。
賢いなさすがPostgreSQLかしこい

n_distinctが有効なパターンについては、別途検証してみよう。今日は時間切れ。

おわりに

• PostgreSQL 10からは、複数の列の相関関係をプランナ向けの統計情報に追加する手段が追加された。
• プランナは追加された統計情報を元に、より適切な実行計画を立てることができるようになった。

参考：該当するリリースノート

本エントリに関連するPostgreSQL 10リリースノートの記載です。

E.2.3.1.4. Optimizer

• Add multi-column optimizer statistics to compute the correlation ratio and number of distinct values (Tomas Vondra, David Rowley, Álvaro Herrera)

PostgreSQL 10全部ぬこ Advent Calendar 2017をやりおえて思ったことなど。

• PostgreSQL 10のマイナーな改善項目を、改めて調査・検証してみると知らなかったことも多く、やってみて損はなかった。
  • 実際に手を動かすことで理解できることもある。
  • 実務に役に立つのかどうかは、知らん。
• コンテンツ力のない弱者なので、それほど「いいね」は集まらなかった。でも、記事への「いいね」はやっぱり励みになる。
  • この場を借りて。自分の書いた各記事に「いいね」をつけてくれた方々に感謝！感謝！
• 11月最終週から6日分先行して書き溜めていたけれど、第3週時点でのバッファは残2日。ここがいちばんしんどかった。12月はPostgreSQLのイベントや、飲み会も多いので、夜に時間が取りづらかったのもきつかった。
• 毎日アウトプットを出すのは、本当にしんどいけど、それはそれで楽しくもあった。ただ、来年も、またやるかどうかはわからない。