使用している例は、リグレッションテスト用データベースから抜き出したものです。 非常に簡単な問い合わせから始めましょう。
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_operatorのoprjoin列から取り出されます。
この制限関数はeqjoinselとなります。
さらに、以下のように、tenk2とtenk1の両方の統計情報を使用します。
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内にあります。