拡張統計情報とテーブル結合

PostgreSQL Advent Calendar 2018、23日目の記事です。

今更感満載ですが、PostgreSQL 10で導入された拡張統計情報について、直感と異なる挙動だったので調査してみました。小ネタですみません。

TL;DR

PostgresSQLのオプティマイザは、カラム間の関数従属性を考慮しない
拡張統計情報を使えば、テーブル探索で関数従属性を考慮できる
テーブル結合では考慮されない

行数推定の課題

PostgreSQLのオプティマイザはコストベースであり、アクセスパスツリーを生成して最もコストの低いパスを選択します。

このコスト計算において、条件句が複雑な場合に、実体と沿わないコストを算出してしまう場合があります。具体的には、条件句に AND で複数の条件が指定され、かつ両条件に指定されたカラム間に関数従属性がある場合、実際の行数よりも推定行数が少なく見積もられます。

この時点で？？？となった方は、ググるか、恐縮ながら以下をさらっとみてもらえるといいかもしれません。

PostgreSQL：行数推定を読み解く/row-estimation - Speaker Deck

拡張統計情報

任意のテーブルがもつカラム間の相関を取得し、オプティマイザに使わせる事ができる機能です。PostgreSQLのバージョン10で導入されました。

以下ではまず、この機能がどういうものか確認してみます。公式ドキュメントの例を使います。

-- テスト用のテーブルt1を作成する
CREATE TABLE t1 (a int, b int);

-- t1にデータを挿入する
INSERT INTO t1
  SELECT i/100, i/500
  FROM generate_series(1,1000000) s(i);

こうすることにより、t1のデータは以下のようになります。

i	a	b
1	0	0
2	0	0
3	0	0
…	…	…
99	0	0
100	1	0
101	1	0
102	1	0
…	…	…
199	1	0
200	2	0
201	2	0
…	…	…
499	4	0
500	5	1
501	5	1
…	…	…
999	9	1
1000	10	2
1001	10	2
…	…	…

つまり、というかSQLのとおりなんですが、aは100ごとに、bは500ごとに値がインクリメントされます。例えばaが12とわかればbは2と確定しますし、逆にbが2とわかればaは10以上20未満であるとわかります。このとき、カラムaとカラムbは相互に関数従属であるといいます。

この状態で、カラムa、bの両方に対する条件句をもつSQLの実行計画をみてみます。

-- 統計情報を収集する
ANALYZE t1;

-- 実行計画を取得する
EXPLAIN ANALYZE SELECT * FROM t1 WHERE (a = 1) AND (b = 0);

Seq Scan on t1  (cost=0.00..19425.00 rows=1 width=8) (actual time=0.034..113.435 rows=100 loops=1)
  Filter: ((a = 1) AND (b = 0))
  Rows Removed by Filter: 999900
Planning time: 0.155 ms
Execution time: 113.467 ms

t1に対するSeq Scanの実際の結果は100行にもかかわらず、推定行数が1行になっています。これは、カラムaとbの間の関数従属性が考慮されていないためです。つまり、各条件句を独立とみなし、それぞれ別のSQLで取得した結果の和集合としています。

この問題に対する解決策として、拡張統計情報があります。ためしてみます。

-- 拡張統計情報を作成する
CREATE STATISTICS s1 (dependencies) ON a, b FROM t1;

-- 統計情報を収集する
ANALYZE t1;

-- 実行計画を取得する
EXPLAIN ANALYZE SELECT * FROM t1 WHERE (a = 1) AND (b = 0);

Seq Scan on t1  (cost=0.00..19425.00 rows=98 width=8) (actual time=0.020..89.729 rows=100 loops=1)
  Filter: ((a = 1) AND (b = 0))
  Rows Removed by Filter: 999900
Planning time: 0.083 ms
Execution time: 89.750 ms

今度はカラム間の関数従属性が考慮され、行数は正確に見積もられています。

テーブル結合

本題、テーブル結合です。t1と全く同様の方法で、t2とt3という2つのテーブルを作り、これらをクロス結合して実行計画をみてみます。

CREATE TABLE t2 (a2 int, b2 int);
CREATE TABLE t3 (a3 int, b3 int);

INSERT INTO t2 SELECT i/100, i/500 FROM generate_series(1,1000000) s(i);
INSERT INTO t3 SELECT i/100, i/500 FROM generate_series(1,1000000) s(i);

単一条件の場合

まず、t2に対する条件句が単一の場合の実行計画を見てみます。

EXPLAIN ANALYZE SELECT * FROM t2, t3 WHERE (t2.a2 = 1) AND (t2.b2 = t3.b3);

Hash Join  (cost=30832.00..52282.01 rows=48922 width=16) (actual time=614.425..622.979 rows=49900 loops=1)
  Hash Cond: (t2.b2 = t3.b3)
  ->  Seq Scan on t2  (cost=0.00..16925.00 rows=98 width=8) (actual time=0.030..85.213 rows=100 loops=1)
        Filter: (a2 = 1)
        Rows Removed by Filter: 999900
  ->  Hash  (cost=14425.00..14425.00 rows=1000000 width=8) (actual time=475.964..475.965 rows=1000000 loops=1)
        Buckets: 131072  Batches: 16  Memory Usage: 3334kB
        ->  Seq Scan on t3  (cost=0.00..14425.00 rows=1000000 width=8) (actual time=0.024..146.287 rows=1000000 loops=1)
Planning time: 0.331 ms
Execution time: 626.888 ms

t2に対するSeq Scanの推定行数が98となっており、実際には100なので、乖離はありません。結合条件としてはHash Joinが選択されています。

複合条件の場合（拡張統計情報なし）

テーブルt2のカラムa2、b2それぞれに対して条件句を指定します。関数従属性により、実行計画が狂ってしまうのを確認します。

EXPLAIN ANALYZE SELECT * FROM t2, t3 WHERE (t2.a2 = 1) AND (t2.b2 = 0) AND (t2.b2 = t3.b3);

Nested Loop  (cost=0.00..36354.86 rows=486 width=16) (actual time=0.056..8576.923 rows=49900 loops=1)
  ->  Seq Scan on t2  (cost=0.00..19425.00 rows=1 width=8) (actual time=0.032..79.398 rows=100 loops=1)
        Filter: ((a2 = 1) AND (b2 = 0))
        Rows Removed by Filter: 999900
  ->  Seq Scan on t3  (cost=0.00..16925.00 rows=486 width=8) (actual time=0.007..84.883 rows=499 loops=100)
        Filter: (b3 = 0)
        Rows Removed by Filter: 999501
Planning time: 0.113 ms
Execution time: 8580.450 ms

前項のt1と同じく、t2は推定行数が大きくずれ、Seq Scanとなっています。結合に関しては、t2が1行となる予測なので、Nested Loopが選択されています。

複合条件の場合（拡張統計情報あり）

テーブルt2のカラムa2、b2に対して、拡張統計情報を作成します。

CREATE STATISTICS s2 (dependencies) ON a2, b2 FROM t2;
ANALYZE t2;
EXPLAIN ANALYZE SELECT * FROM t2, t3 WHERE (t2.a2 = 1) AND (t2.b2 = 0) AND (t2.b2 = t3.b3);

Nested Loop  (cost=0.00..36945.60 rows=47628 width=16) (actual time=0.045..231.646 rows=49900 loops=1)
  ->  Seq Scan on t3  (cost=0.00..16925.00 rows=486 width=8) (actual time=0.019..119.208 rows=499 loops=1)
        Filter: (b3 = 0)
        Rows Removed by Filter: 999501
  ->  Materialize  (cost=0.00..19425.49 rows=98 width=8) (actual time=0.000..0.205 rows=100 loops=499)
        ->  Seq Scan on t2  (cost=0.00..19425.00 rows=98 width=8) (actual time=0.022..97.727 rows=100 loops=1)
              Filter: ((a2 = 1) AND (b2 = 0))
              Rows Removed by Filter: 999900
Planning time: 0.194 ms
Execution time: 235.587 ms

実行時間が8580msから246msに改善しました。実行計画の中身をみてみると、t2の推定行数が98になっており、実行結果の100行と僅差になっています。それにより、Materializeされるようになりました。Materializeは、t2をSeq Scanした結果をメモリにのせます。これにより、t3とのNested Loopにおいてt2の再スキャンを高速化します。

考察

拡張統計情報によって見事に実行速度が改善したわけですが、Nested Loopではなく単一条件の場合と同じくHash Joinが選択されてもよさそうです。なぜNested Loopのままなのか、PostgreSQLのコードを見てみます。

拡張統計情報を参照するのは clauselist_selectivity() の以下の箇所です。該当コードはここ。

 /*
    * Determine if these clauses reference a single relation.  If so, and if
    * it has extended statistics, try to apply those.
    */
    rel = find_single_rel_for_clauses(root, clauses);
    if (rel && rel->rtekind == RTE_RELATION && rel->statlist != NIL)
    {
        /*
        * Perform selectivity estimations on any clauses found applicable by
        * dependencies_clauselist_selectivity.  'estimatedclauses' will be
        * filled with the 0-based list positions of clauses used that way, so
        * that we can ignore them below.
        */
        s1 *= dependencies_clauselist_selectivity(root, clauses, varRelid,
                                                  jointype, sjinfo, rel,
                                                  &estimatedclauses);

        /*
        * This would be the place to apply any other types of extended
        * statistics selectivity estimations for remaining clauses.
        */
    }

    /*
    * Apply normal selectivity estimates for remaining clauses. We'll be
    * careful to skip any clauses which were already estimated above.

スキャン方法の選択時、 src/backend/optimizer/path/costsize.c がこのコードを使っています。

void
set_baserel_size_estimates(PlannerInfo *root, RelOptInfo *rel)
{
    double     nrows;

    /* Should only be applied to base relations */
    Assert(rel->relid > 0);

    nrows = rel->tuples *
        clauselist_selectivity(root,
                               rel->baserestrictinfo,
                               0,
                               JOIN_INNER,
                               NULL);

一方、結合条件について。PostgreSQLのオプティマイザはデフォルトでNested Loopのパスを作り、そのあとにMerge Join、Hash Joinとそれぞれを検討して、そっちのほうが速そうならそっちに置き換えます。このへんでHash Joinを選択するか判断しているのですが、この段階で上記コードを参照していません。つまり、結合条件の選択に、拡張統計情報はつかわれません。

改めて問題

何が困るかというと、まあそのままなのですが、「巨大なテーブル同士をNested Loopでジョインしてしまう」ことです。これについては、バージョン10以前と同様にpg_hint_planをつかって結合ルールを手動制御せざるを得なさそうです。

そんな人はいないと思いますが、「関数従属な複数カラムに対する条件句」と「テーブル結合」の両方を持つSQLがたくさんあり、pg_hint_planでがんじがらめになっているサービスを運用しており、拡張統計情報をメシア視している方がもし仮に存在するなら、要注意です。

まとめ

普通に結合条件でも考慮されてほしいと思いました。拡張統計情報という壮大な名前なので、今後さらに賢くなっていくことが期待できます。と思っていたらバージョン11では特にアップデートがなかったです。悲しいです。以降、「文句言ってないでOSSなんだから自分でなおせよ」禁止。

夜は寝る