The examples shown below use tables in the <productname>PostgreSQL</productname> regression test database. The outputs shown are taken from version 8.3. The behavior of earlier (or later) versions might vary. Note also that since <command>ANALYZE</command> uses random sampling while producing statistics, the results will change slightly after any new <command>ANALYZE</command>. 以下の例はPostgreSQLリグレッションテストデータベース内のテーブルを使用します。 表示される出力はバージョン8.3で取得しました。 以前の（または以降の）バージョンとは動作が変わっているかもしれません。 また、ANALYZEは統計情報を生成する時にランダムなサンプリングを行いますので、結果はANALYZEを新しく行った後に多少変わることに注意してください。

Let's start with a very simple query: 非常に簡単な問い合わせから始めましょう。

EXPLAIN SELECT * FROM tenk1;

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

How the planner determines the cardinality of <structname>tenk1</structname> is covered in <xref linkend="planner-stats"/>, but is repeated here for completeness. The number of pages and rows is looked up in <structname>pg_class</structname>: プランナがどのようにtenk1の濃度を決定するかについては14.2で説明しました。 しかし、ここでは完全を期するために説明を繰り返します。 ページ数および行数はpg_classから検索されます。

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

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

These numbers are current as of the last <command>VACUUM</command> or <command>ANALYZE</command> on the table. The planner then fetches the actual current number of pages in the table (this is a cheap operation, not requiring a table scan). If that is different from <structfield>relpages</structfield> then <structfield>reltuples</structfield> is scaled accordingly to arrive at a current number-of-rows estimate. In the example above, the value of <structfield>relpages</structfield> is up-to-date so the rows estimate is the same as <structfield>reltuples</structfield>. これらの値は最後にそのテーブルをVACUUMまたはANALYZEを行った時点のものです。 プランナはその後、テーブル内の実際のページ数を取り出します（これはテーブルスキャンを行わない安価な操作です）。 それがrelpagesと異なる場合、reltuplesを得られたページ数の割合に応じて変更して現在の推定行数を求めます。 上の例では、relpagesの値は最新のものなので、推定行数はreltuplesと同じです。

Let's move on to an example with a range condition in its <literal>WHERE</literal> clause: 次に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)

The planner examines the <literal>WHERE</literal> clause condition and looks up the selectivity function for the operator <literal>&lt;</literal> in <structname>pg_operator</structname>. This is held in the column <structfield>oprrest</structfield>, and the entry in this case is <function>scalarltsel</function>. The <function>scalarltsel</function> function retrieves the histogram for <structfield>unique1</structfield> from <structname>pg_statistic</structname>. For manual queries it is more convenient to look in the simpler <structname>pg_stats</structname> view: プランナは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}

Next the fraction of the histogram occupied by <quote>&lt; 1000</quote> is worked out. This is the selectivity. The histogram divides the range into equal frequency buckets, so all we have to do is locate the bucket that our value is in and count <emphasis>part</emphasis> of it and <emphasis>all</emphasis> of the ones before. The value 1000 is clearly in the second bucket (993&ndash;1997). Assuming a linear distribution of values inside each bucket, we can calculate the selectivity as: 次に、「< 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

that is, one whole bucket plus a linear fraction of the second, divided by the number of buckets. The estimated number of rows can now be calculated as the product of the selectivity and the cardinality of <structname>tenk1</structname>: つまり、1つのバケット全体に、2番目のバケットとの線形比率を加えたものを、バケット数で割ったものとなります。 ここで、行の推定値は、選択度とtenk1の濃度を掛け合わせたものとして計算されます。

rows = rel_cardinality * selectivity
     = 10000 * 0.100697

     = 1007  (rounding off)

     = 1007  (四捨五入)

Next let's consider an example with an equality condition in its <literal>WHERE</literal> clause: 次に、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)

Again the planner examines the <literal>WHERE</literal> clause condition and looks up the selectivity function for <literal>=</literal>, which is <function>eqsel</function>. For equality estimation the histogram is not useful; instead the list of <firstterm>most common values</firstterm> (<acronym>MCV</acronym>s) is used to determine the selectivity. Let's have a look at the MCVs, with some additional columns that will be useful later: ここでも、プランナは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}

Since <literal>CRAAAA</literal> appears in the list of MCVs, the selectivity is merely the corresponding entry in the list of most common frequencies (<acronym>MCF</acronym>s): CRAAAAがMCVのリスト内にありますので、選択度は単に頻出値の頻度（MCF）のリスト内の対応する項目になります。

selectivity = mcf[3]
            = 0.003

As before, the estimated number of rows is just the product of this with the cardinality of <structname>tenk1</structname>: 前と同様、推定される行数は単に前回同様、この値とtenk1の濃度との積です。

rows = 10000 * 0.003
     = 30

Now consider the same query, but with a constant that is not in the <acronym>MCV</acronym> list: ここで、同じ問い合わせを見てみます。 ただし、今回は定数が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)

This is quite a different problem: how to estimate the selectivity when the value is <emphasis>not</emphasis> in the <acronym>MCV</acronym> list. The approach is to use the fact that the value is not in the list, combined with the knowledge of the frequencies for all of the <acronym>MCV</acronym>s: 値がMCVの一覧にない場合、選択度をどのように推定するかは大きく異なります。 値が一覧にない場合に使用される方法は、MCVすべての頻度に関する知識を組み合わせたものです。

selectivity = (1 - sum(mcv_freqs))/(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

That is, add up all the frequencies for the <acronym>MCV</acronym>s and subtract them from one, then divide by the number of <emphasis>other</emphasis> distinct values. This amounts to assuming that the fraction of the column that is not any of the MCVs is evenly distributed among all the other distinct values. Notice that there are no null values so we don't have to worry about those (otherwise we'd subtract the null fraction from the numerator as well). The estimated number of rows is then calculated as usual: つまり、MCVの頻度をすべて足し合わせたものを1から差し引き、そして、この他の個別値の数で除算します。 これは、MCV以外の列の割合は、この他の個別値すべてに渡って一様に分布していることを前提としていることになります。 NULL値が存在しないため、これを考慮する必要がないことに注意してください。 （さもなくば、分子から同様にNULLの割合を差し引くことになります。） 推定行数は以下のように普通に計算されます。

rows = 10000 * 0.0014559

     = 15  (rounding off)

     = 15  (四捨五入)

The previous example with <literal>unique1 &lt; 1000</literal> was an oversimplification of what <function>scalarltsel</function> really does; now that we have seen an example of the use of MCVs, we can fill in some more detail. The example was correct as far as it went, because since <structfield>unique1</structfield> is a unique column it has no MCVs (obviously, no value is any more common than any other value). For a non-unique column, there will normally be both a histogram and an MCV list, and <emphasis>the histogram does not include the portion of the column population represented by the MCVs</emphasis>. We do things this way because it allows more precise estimation. In this situation <function>scalarltsel</function> directly applies the condition (e.g., <quote>&lt; 1000</quote>) to each value of the MCV list, and adds up the frequencies of the MCVs for which the condition is true. This gives an exact estimate of the selectivity within the portion of the table that is MCVs. The histogram is then used in the same way as above to estimate the selectivity in the portion of the table that is not MCVs, and then the two numbers are combined to estimate the overall selectivity. For example, consider 前述の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)

We already saw the MCV information for <structfield>stringu1</structfield>, and here is its histogram: すでに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}

Checking the MCV list, we find that the condition <literal>stringu1 &lt; 'IAAAAA'</literal> is satisfied by the first six entries and not the last four, so the selectivity within the MCV part of the population is MCVリストを検査すると、stringu1 < 'IAAAAA'条件は先頭の6項目で満たされ、最後の4項目で満たされないことがわかります。 ですので、母集団のMCV部分における選択度は以下のようになります。

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

Summing all the MCFs also tells us that the total fraction of the population represented by MCVs is 0.03033333, and therefore the fraction represented by the histogram is 0.96966667 (again, there are no nulls, else we'd have to exclude them here). We can see that the value <literal>IAAAAA</literal> falls nearly at the end of the third histogram bucket. Using some rather cheesy assumptions about the frequency of different characters, the planner arrives at the estimate 0.298387 for the portion of the histogram population that is less than <literal>IAAAAA</literal>. We then combine the estimates for the MCV and non-MCV populations: 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  (rounding off)

            = 3077  (四捨五入)

In this particular example, the correction from the MCV list is fairly small, because the column distribution is actually quite flat (the statistics showing these particular values as being more common than others are mostly due to sampling error). In a more typical case where some values are significantly more common than others, this complicated process gives a useful improvement in accuracy because the selectivity for the most common values is found exactly. 列の分布がかなり平坦ですので、この特定の例におけるMCVリストによる訂正はかなり小さなものです。 （これらの特定の値が他より頻出するものと示す統計情報はほとんどサンプリングエラーによります。） より一般的な、一部の値が他より非常に多く頻出する場合では、頻出値に対する選択度が正確に検出されますので、この複雑な処理により精度が改良されます。

Now let's consider a case with more than one condition in the <literal>WHERE</literal> clause: 次に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)

The planner assumes that the two conditions are independent, so that the individual selectivities of the clauses can be multiplied together: プランナは2つの条件が独立していると仮定します。 このため、個々の句の選択度が掛け合わされます。

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

rows        = 10000 * 0.0001466

            = 1  (rounding off)

            = 1  (四捨五入)

Notice that the number of rows estimated to be returned from the bitmap index scan reflects only the condition used with the index; this is important since it affects the cost estimate for the subsequent heap fetches. ビットマップインデックススキャンにより返されるものと推定される行数は、インデックスで使用される条件のみを反映することに注意してください。 後続のヒープ取り出しのコスト推定に影響しますので、これは重要です。

Finally we will examine a query that involves a join: 最後に、結合を含む問い合わせを見てみましょう。

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)

The restriction on <structname>tenk1</structname>, <literal>unique1 &lt; 50</literal>, is evaluated before the nested-loop join. This is handled analogously to the previous range example. This time the value 50 falls into the first bucket of the <structfield>unique1</structfield> histogram: 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  (rounding off)

            = 50  (四捨五入)

The restriction for the join is <literal>t2.unique2 = t1.unique2</literal>. The operator is just our familiar <literal>=</literal>, however the selectivity function is obtained from the <structfield>oprjoin</structfield> column of <structname>pg_operator</structname>, and is <function>eqjoinsel</function>. <function>eqjoinsel</function> looks up the statistical information for both <structname>tenk2</structname> and <structname>tenk1</structname>: 結合の制限はt2.unique2 = t1.unique2です。 演算子はよく使用する単なる=ですが、選択度関数はpg_operatorのoprjoin列から入手され、eqjoinselとなります。 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 |

In this case there is no <acronym>MCV</acronym> information for <structfield>unique2</structfield> because all the values appear to be unique, so we use an algorithm that relies only on the number of distinct values for both relations together with their null fractions: 今回の場合、すべての値が一意であるため、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

This is, subtract the null fraction from one for each of the relations, and divide by the maximum of the numbers of distinct values. The number of rows that the join is likely to emit is calculated as the cardinality of the Cartesian product of the two inputs, multiplied by the selectivity: これは、各リレーションにおいて、1からNULL部分を差し引き、個別値数の最大値で割った値です。 この結合が生成するはずの行数は、2つの入力のデカルト積の濃度に、この選択度を掛けたものとして計算されます。

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

Had there been MCV lists for the two columns, <function>eqjoinsel</function> would have used direct comparison of the MCV lists to determine the join selectivity within the part of the column populations represented by the MCVs. The estimate for the remainder of the populations follows the same approach shown here. 2つの列に対するMCVリストがありますので、eqjoinselはMCVで表される列母集団部分の結合選択度を決めるために、MCVリストを直接比較します。 残りの母集団に対する推定はここで示した同じ手法に従います。

Notice that we showed <literal>inner_cardinality</literal> as 10000, that is, the unmodified size of <structname>tenk2</structname>. It might appear from inspection of the <command>EXPLAIN</command> output that the estimate of join rows comes from 50 * 1, that is, the number of outer rows times the estimated number of rows obtained by each inner index scan on <structname>tenk2</structname>. But this is not the case: the join relation size is estimated before any particular join plan has been considered. If everything is working well then the two ways of estimating the join size will produce about the same answer, but due to round-off error and other factors they sometimes diverge significantly. inner_cardinalityを10000、つまりtenk2の変更がないサイズと示していることに注意してください。 EXPLAINの出力を検査すると、結合行の推定が50 * 1、つまり、外側の行数とtenk2上の内側のインデックススキャン毎に得られる推定行数を掛けた数から来ていると思うかもしれません。 しかし、実際はそうではありません。 結合リレーションサイズは、具体的な結合計画が検討される前に推定されます。 もしすべてがうまくいけば、結合サイズを推定する2つの方法は同じ答えを導きます。 しかし、四捨五入誤差などの要因により多少異なる場合があります。

For those interested in further details, estimation of the size of a table (before any <literal>WHERE</literal> clauses) is done in <filename>src/backend/optimizer/util/plancat.c</filename>. The generic logic for clause selectivities is in <filename>src/backend/optimizer/path/clausesel.c</filename>. The operator-specific selectivity functions are mostly found in <filename>src/backend/utils/adt/selfuncs.c</filename>. 詳細に興味を持った方向けに、テーブル（すべてのWHERE句の前にあるもの）のサイズ推定はsrc/backend/optimizer/util/plancat.cで行われます。 句の選択度に関する一般的なロジックについてはsrc/backend/optimizer/path/clausesel.cにあります。 演算子固有の選択度関数についてはたいていsrc/backend/utils/adt/selfuncs.c内にあります。