★PostgreSQLカンファレンス2024 12月6日開催/チケット販売中★
他のバージョンの文書 16 | 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

70.1. 行数推定の例

以下の例はPostgreSQLリグレッションテストデータベース内のテーブルを使用します。 表示される出力はバージョン8.3で取得しました。 以前の(または以降の)バージョンとは動作が変わっているかもしれません。 また、ANALYZEは統計情報を生成する時にランダムなサンプリングを行いますので、結果はANALYZEを新しく行った後に多少変わることに注意してください。

非常に簡単な問い合わせから始めましょう。

EXPLAIN SELECT * FROM tenk1;

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

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

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

 relpages | reltuples
----------+-----------
      358 |     10000

これらの値は最後にそのテーブルをVACUUMまたはANALYZEを行った時点のものです。 プランナはその後、テーブル内の実際のページ数を取り出します(これはテーブルスキャンを行わない安価な操作です)。 それがrelpagesと異なる場合、reltuplesを得られたページ数の割合に応じて変更して現在の推定行数を求めます。 上の例では、relpagesの値は最新のものなので、推定行数はreltuplesと同じです。

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

EXPLAIN SELECT * FROM tenk1 WHERE unique1 < 1000;

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=24.06..394.64 rows=1007 width=244)
   Recheck Cond: (unique1 < 1000)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

プランナはWHERE句の条件を検査し、pg_operator内の<演算子用の選択度関数を検索します。 これはoprrest列に保持されます。 今回の例ではこの項はscalarltselです。 scalarltsel関数は、pg_statisticからunique1の度数分布を取り出します。 手作業で問い合わせる場合は、より単純なpg_statsビューを検索した方が簡単です。

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

                   histogram_bounds
------------------------------------------------------
 {0,993,1997,3050,4040,5036,5957,7057,8029,9016,9995}

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

selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
            = (1 + (1000 - 993)/(1997 - 993))/10
            = 0.100697

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

rows = rel_cardinality * selectivity
     = 10000 * 0.100697

     = 1007  (四捨五入)

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

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

                        QUERY PLAN
----------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=30 width=244)
   Filter: (stringu1 = 'CRAAAA'::name)

ここでも、プランナはWHERE句の条件を検査し、=用の選択度関数、この場合はeqselを検索します。 等価性の推定では、度数分布は役に立ちません。 代わりに、選択度の決定には頻出値MCV)のリストが使用されます。 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        | 676
most_common_vals  | {EJAAAA,BBAAAA,CRAAAA,FCAAAA,FEAAAA,GSAAAA,JOAAAA,MCAAAA,NAAAAA,WGAAAA}
most_common_freqs | {0.00333333,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003,0.003}

CRAAAAがMCVのリスト内にありますので、選択度は単に頻出値の頻度(MCF)のリスト内の対応する項目になります。

selectivity = mcf[3]
            = 0.003

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

rows = 10000 * 0.003
     = 30

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

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

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

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

selectivity = (1 - sum(mvf))/(num_distinct - num_mcv)
            = (1 - (0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003 +
                    0.003 + 0.003 + 0.003 + 0.003))/(676 - 10)
            = 0.0014559

つまり、MCVの頻度をすべて足し合わせたものを1から差し引き、そして、この他の個別値の数で除算します。 これは、MCV以外の列の割合は、この他の個別値すべてに渡って一様に分布していることを前提としていることになります。 NULL値が存在しないため、これを考慮する必要がないことに注意してください。 (さもなくば、分子から同様にNULLの割合を差し引くことになります。) 推定行数は以下のように普通に計算されます。

rows = 10000 * 0.0014559

     = 15  (四捨五入)

前述のunique1 < 1000を使用した例はscalarltselが本当は何を行うかについて、単純化しすぎたものでした。 ここまでで、MCVを使用した例を見てきましたので、多少詳細に補てんすることができます。 unique1は一意な列であるため、MCVが存在しません(ある値が他の値と同じとなることがないことは明確です)ので、例は計算自体は正確なものでした。 一意ではない列では、通常度数分布とMCVリストの両方が存在します。 そして、度数分布は、MCVで表される列母集団の位置を含みません。 より正確な推定を行うことができるため、この方法を行います。 この状況では、scalarltselは直接条件(例えば< 1000)をMCVリストの各値に適用し、条件を満たすMCVの頻度を足し合わせます。 これがMCVのテーブル部分における正確な推定選択度です。 その後度数分布が上と同様に使われ、MCV以外のテーブル部分における選択度を推定します。 そしてこの2つの値を組み合わせて、全体の選択度を推定します。 例えば、以下を検討します。

EXPLAIN SELECT * FROM tenk1 WHERE stringu1 < 'IAAAAA';

                         QUERY PLAN
------------------------------------------------------------
 Seq Scan on tenk1  (cost=0.00..483.00 rows=3077 width=244)
   Filter: (stringu1 < 'IAAAAA'::name)

すでにstringu1のMCV情報は確認していますので、ここでは度数分布を見てみます。

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

                                histogram_bounds
--------------------------------------------------------------------------------
 {AAAAAA,CQAAAA,FRAAAA,IBAAAA,KRAAAA,NFAAAA,PSAAAA,SGAAAA,VAAAAA,XLAAAA,ZZAAAA}

MCVリストを検査すると、stringu1 < 'IAAAAA'条件は先頭の6項目で満たされ、最後の4項目で満たされないことがわかります。 ですので、母集団のMCV部分における選択度は以下のようになります。

selectivity = sum(relevant mvfs)
            = 0.00333333 + 0.003 + 0.003 + 0.003 + 0.003 + 0.003
            = 0.01833333

MCFの総和はまた、MCVで表される母集団の合計割合が0.03033333であり、したがって度数分布で表される割合が0.96966667であることがわかります。 (この場合もNULLは存在しません。もし存在する場合はここで除外しなければなりません。) IAAAAAという値は3番目のバケットの終端近辺になることを確認することができます。 異なる文字の頻度について多少安っぽい仮定を使用すると、プランナはIAAAAAより小さい母集団の度数分布の部分の推定値は0.298387になります。 そしてMCVと非MCV母集団についての推定値を組み合わせます。

selectivity = mcv_selectivity + histogram_selectivity * histogram_fraction
            = 0.01833333 + 0.298387 * 0.96966667
            = 0.307669

rows        = 10000 * 0.307669

            = 3077  (四捨五入)

列の分布がかなり平坦ですので、この特定の例におけるMCVリストによる訂正はかなり小さなものです。 (これらの特定の値が他より頻出するものと示す統計情報はほとんどサンプリングエラーによります。) より一般的な、一部の値が他より非常に多く頻出する場合では、頻出値に対する選択度が正確に検出されますので、この複雑な処理により精度が改良されます。

次にWHERE句に複数の条件を持つ場合を検討しましょう。

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

                                   QUERY PLAN
--------------------------------------------------------------------------------
 Bitmap Heap Scan on tenk1  (cost=23.80..396.91 rows=1 width=244)
   Recheck Cond: (unique1 < 1000)
   Filter: (stringu1 = 'xxx'::name)
   ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..23.80 rows=1007 width=0)
         Index Cond: (unique1 < 1000)

プランナは2つの条件が独立していると仮定します。 このため、個々の句の選択度が掛け合わされます。

selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
            = 0.100697 * 0.0014559
            = 0.0001466

rows        = 10000 * 0.0001466

            = 1  (四捨五入)

ビットマップインデックススキャンにより返されるものと推定される行数は、インデックスで使用される条件のみを反映することに注意してください。 後続のヒープ取り出しのコスト推定に影響しますので、これは重要です。

最後に、結合を含む問い合わせを見てみましょう。

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

                                      QUERY PLAN
--------------------------------------------------------------------------------------
 Nested Loop  (cost=4.64..456.23 rows=50 width=488)
   ->  Bitmap Heap Scan on tenk1 t1  (cost=4.64..142.17 rows=50 width=244)
         Recheck Cond: (unique1 < 50)
         ->  Bitmap Index Scan on tenk1_unique1  (cost=0.00..4.63 rows=50 width=0)
               Index Cond: (unique1 < 50)
   ->  Index Scan using tenk2_unique2 on tenk2 t2  (cost=0.00..6.27 rows=1 width=244)
         Index Cond: (unique2 = t1.unique2)

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

selectivity = (0 + (50 - bucket[1].min)/(bucket[1].max - bucket[1].min))/num_buckets
            = (0 + (50 - 0)/(993 - 0))/10
            = 0.005035

rows        = 10000 * 0.005035

            = 50  (四捨五入)

結合の制限はt2.unique2 = t1.unique2です。 演算子はよく使用する単なる=ですが、選択度関数はpg_operatoroprjoin列から入手され、eqjoinselとなります。 eqjoinseltenk2および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) / max(10000, 10000)
            = 0.0001

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

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

2つの列に対するMCVリストがありますので、eqjoinselはMCVで表される列母集団部分の結合選択度を決めるために、MCVリストを直接比較します。 残りの母集団に対する推定はここで示した同じ手法に従います。

inner_cardinalityを10000、つまりtenk2の変更がないサイズと示していることに注意してください。 EXPLAINの出力を検査すると、結合行の推定が50 * 1、つまり、外側の行数とtenk2上の内側のインデックススキャン毎に得られる推定行数を掛けた数から来ていると思うかもしれません。 しかし、実際はそうではありません。 結合リレーションサイズは、具体的な結合計画が検討される前に推定されます。 もしすべてがうまくいけば、結合サイズを推定する2つの方法は同じ答えを導きます。 しかし、四捨五入誤差などの要因により多少異なる場合があります。

詳細に興味を持った方向けに、テーブル(すべてのWHERE句の前にあるもの)のサイズ推定はsrc/backend/optimizer/util/plancat.cで行われます。 句の選択度に関する一般的なロジックについてはsrc/backend/optimizer/path/clausesel.cにあります。 演算子固有の選択度関数についてはたいていsrc/backend/utils/adt/selfuncs.c内にあります。