54.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内にあります。