他のバージョンの文書 15 | 14 | 13 | 12 | 11 | 10 | 9.6 | 9.5 | 9.4 | 9.3 | 9.2 | 9.1 | 9.0 | 8.4 | 8.3 | 8.2 | 8.1 | 8.0 | 7.4 | 7.3 | 7.2

第 52章プランナが統計情報をどのように使用するか

本章は、項13.1項13.2で扱われている題材を基にしていて、問い合わせの各段階において返される行数を推定するために、プランナがシステムの統計情報をどのように使用するかを説明します。 これは、計画作成および最適化処理の重要な部分で、コスト計算用の多くの生材料を提供します。

本章の目的は、コードを文書化することではありません。このためにはコード自体を参照した方がよいでしょう。 どのように動作するのかに関する概要を表すことが目的です。 これによりおそらく、後にコードを参照するユーザの習得速度が向上するでしょう。 成り行き上、じょじょに複雑化する例を並べて解析するという手法を選びました。

以下で示す出力とアルゴリズムは、バージョン8.0のものを使用しています。 以前(あるいは以降の)のバージョンとは動作が変わっているかもしれません。

52.1. 行推定の例

使用している例は、リグレッションテスト用データベースから抜き出したものです。 非常に簡単な問い合わせから始めましょう。

EXPLAIN SELECT * FROM tenk1;

                         QUERY PLAN
-------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..445.00 rows=10000 width=244)

プランナがどのようにtenk1の濃度を決定するかについては項13.1で説明しました。 しかし、ここで完全になるように繰り返し説明します。 行数はpg_classから検索されます。

SELECT reltuples, relpages FROM pg_class WHERE relname = 'tenk1';

 relpages | reltuples
----------+-----------
      345 |     10000

プランナはrelpages推定値を検査し(これは安価な操作です)、正しくなければ、行推定を得るためにreltuplesを測定します。 この場合は以下のように正しくありませんでした。

rows = 10000

次にWHERE句に範囲条件を持つ例に進みましょう。

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=1031 width=244)
   Filter: (unique1 < 1000)

プランナは、WHERE句条件を検査します。

unique1 < 1000

そして、<演算子用の制限関数をpg_operatorから検索します。 これはoprrest列に保持されており、今回の場合、検索結果はscalarltselとなります。 このscalarltsel関数は、pg_statisticsからunique1用の度数分布を取り出します。 以下のように、これは、より単純化したpg_statsビューを使用して行うことができます。

SELECT histogram_bounds FROM pg_stats 
WHERE tablename='tenk1' AND attname='unique1';

                   histogram_bounds
------------------------------------------------------
 {1,970,1943,2958,3971,5069,6028,7007,7919,8982,9995}

次に、"< 1000"で占められる度数分布率を取り出します。 これが選択度です。 この度数分布は、範囲を等頻度のバケットに分割します。 ですので、行わなければならないことは、値が入るバケットを見つけ、その部分と、その前にあるバケット全体を数えることだけです。 1000という値は明らかに2番目のバケット(970 - 1943)にあります。 従って、値が各バケットの中で線形に分布していると仮定すると、選択度を以下のように計算することができます。

selectivity = (1 + (1000 - bckt[2].min)/(bckt[2].max - bckt[2].min))/num_bckts
            = (1 + (1000 - 970)/(1943 - 970))/10
            = 0.1031

つまり、1つのバケット全体に、2番目のバケットとの線形比率を加えたものを、バケット数で割ったものとなります。 ここで、行の推定値は、選択度とtenk1の濃度を掛け合わせたものとして計算されます。

rows = rel_cardinality * selectivity
     = 10000 * 0.1031
     = 1031

次に、WHERE句に等価条件を持つ例を検討してみましょう。

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'ATAAAA';

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=31 width=244)
   Filter: (stringu1 = 'ATAAAA'::name)

繰り返しますが、プランナはWHERE句の条件を検査します。

stringu1 = 'ATAAAA'

そして、=演算子用の制限関数をから検索します。 結果はeqselとなります。 今回の場合は少し異なり、もっとも一般的な値、MCVが選択度を決定するために使用されます。 他の列も参照しながらこれらを見てみましょう。 ここで参照した列は後で使用します。

SELECT null_frac, n_distinct, most_common_vals, most_common_freqs FROM pg_stats 
WHERE tablename='tenk1' AND attname='stringu1';

null_frac         | 0
n_distinct        | 672
most_common_vals  | {FDAAAA,NHAAAA,ATAAAA,BGAAAA,EBAAAA,MOAAAA,NDAAAA,OWAAAA,BHAAAA,BJAAAA}
most_common_freqs | {0.00333333,0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.00266667,0.00266667}

選択度は、単に3番目のMCV、 'ATAAAA'に対応する、最も一般的な頻度(MCF)となります。

selectivity = mcf[3]
            = 0.003

推定される行数は単に前回同様、この値とtenk1の積です。

rows = 10000 * 0.003
     = 30

この後に行われる推定検査のため、EXPLAINで出力される値はこれより多少大きくなっています。

ここで、同じ問い合わせを見てみます。 ただし、今回は定数がMCV内にありません。

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 = 'xxx';

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..470.00 rows=15 width=244)
   Filter: (stringu1 = 'xxx'::name)

値がMCVの一覧にない場合、選択度をどのように推定するかは大きく異なります。 値が一覧にない場合に使用される方法は、MCVすべての頻度に関する知識を組み合わせたものです。

selectivity = (1 - sum(mvf))/(num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.00333333 + 0.003 + 0.003 + 0.003 
            + 0.003 + 0.003 + 0.003 + 0.00266667 + 0.00266667))/(672 - 10)
            = 0.001465

つまり、全てのMCVの頻度を足し合わせ、MCVの中にはありませんので、その結果を1から差し引き、そして、残りの個別値数で割ります。 NULL値が含まれていないので、NULL値を考慮する必要がない点に注意してください。 行数の推定値はこれまで通りに計算されます。

rows = 10000 * 0.001465
     = 15

複雑さを増して、WHERE句に複数の条件を持つ場合を検討しましょう。

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000 AND stringu1 = 'xxx';

                       QUERY PLAN
-----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..495.00 rows=2 width=244)
   Filter: ((unique1 < 1000) AND (stringu1 = 'xxx'::name))

独立であることが仮定され、個々の制限の選択度が掛け合わせられます。

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.1031 * 0.001465
            = 0.00015104

行数の推定値はこれまで通りに計算されます。

rows = 10000 * 0.00015104
     = 2

最後に、WHERE句で互いへのJOINを持つ問い合わせを見てみましょう。

EXPLAIN SELECT *  FROM tenk1 t1, tenk2 t2 
WHERE t1.unique1 < 50 AND t1.unique2 = t2.unique2;

                                      QUERY PLAN
-----------------------------------------------------------------------------------------
 Nested Loop  (cost=0.00..346.90 rows=51 width=488)
   ->  Index Scan using tenk1_unique1 on tenk1 t1  (cost=0.00..192.57 rows=51 width=244)
         Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..3.01 rows=1 width=244)
         Index Cond: ("outer".unique2 = t2.unique2)

tenk1 "unique1 < 50"に関する制限が、入れ子状ループ結合の前に評価されます。 これは、前の範囲に関する例と同様に扱われます。 前例と同様、<用の制限演算子はscalarlteqselです。 しかし、今回の値50はunique1 度数分布の最初のバケットにありますので、以下のようになります。

selectivity = (0 + (50 - bckt[1].min)/(bckt[1].max - bckt[1].min))/num_bckts
            = (0 + (50 - 1)/(970 - 1))/10
            = 0.005057

rows        = 10000 * 0.005057
            = 51

結合用の制限は以下の通りです。

t2.unique2 = t1.unique2

これは、tenk1を外側のループとする、入れ子状ループ結合方法が使用されているためです。 演算子は、よく知られた、単なる=ですが、制限関数はpg_operatoroprjoin列から取り出されます。 この制限関数はeqjoinselとなります。 さらに、以下のように、tenk2tenk1の両方の統計情報を使用します。

SELECT tablename, null_frac,n_distinct, most_common_vals FROM pg_stats 
WHERE tablename IN ('tenk1', 'tenk2') AND attname='unique2';  

tablename  | null_frac | n_distinct | most_common_vals
-----------+-----------+------------+------------------
 tenk1     |         0 |         -1 |
 tenk2     |         0 |         -1 |

今回の場合、すべての値が一意であるため、unique2に関するMCV情報がありません。 ですので、両リレーションの個別値数とNULL値の部分のみに依存したアルゴリズムを使用することができます。

selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
            = (1 - 0) * (1 - 0) * min(1/10000, 1/1000)
            = 0.0001

これは、各リレーションにおいて、1からNULL部分を差し引き、個別値数の小さい方の値で割った値です。 この結合が生成するはずの行数は、入れ子状ループ内の2つのノードのデカルト積の濃度に、この選択度を掛けたものとして計算されます。

rows = (outer_cardinality * inner_cardinality) * selectivity
     = (51 * 10000) * 0.0001
     = 51

詳細に興味を持った方向けに、リレーション内の行数の推定はsrc/backend/optimizer/util/plancat.cで説明されています。 句の選択度に関する計算ロジックについてはsrc/backend/optimizer/path/clausesel.cにあります。 演算子と結合に関する制限関数の実際の実装についてはsrc/backend/utils/adt/selfuncs.c内にあります。