Question

使用一个从回归测试数据库拉出来的例子，让我们从一个非常简单的查询开始：

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 很明显在第二个段(970-1943)里，因此，假设每个段里面的分布是线性的，那么就可以计算出选择性：

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

也就是一个段加上第二个段的线性部分，除以总段数。那么估计的行数现在可以用选择性和 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}

选择性只是最常见(MCF)的串，对应第三个 MCV('ATAAAA')：

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 出现的频率累加起来，然后从一里面减去这些，因为的条件数值不是这些值之一，然后用剩下的独立数值来除。请注意这里没有 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

最后将讨论一个同时包含 JOIN 子句和 WHERE 子句的查询：

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

也就是说，把每个表都减去一里面 NULL 的比例，然后除以两个唯一数值的最大值。连接可能选出来的行数是以嵌套循环里的两个结点的笛卡儿积的总行数，乘以选择性计算出来的：

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 里。