Chapter 52. 规划器如何使用统计信息

本章建筑在 Section 13.1Section 13.2 里面讨论的材料上,显示了规划器如何使用系统统计信息来预计一个查询运行的各个阶段可能碰到的行数。 这是规划/优化过程中的一个重要的部分,因为它提供了开销计算中的大部分原始材料。

本章的目的不是给代码写文档 — 代码本身就是文档, 而是给出一个规划器如何使用统计信息的概述。 这样可能可以降低那些想以后阅读这部份代码的人的学习难度。 因此,我们采用的方法是分析一系列逐渐变得复杂的例子。

下面显示的输出和算法是从版本 8.0 里拿出来的。 更早的版本(或者以后的版本)的行为可能会有所变化。

52.1. 行预期的例子

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

EXPLAIN SELECT * FROM tenk1;

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

规划器如何判断 tenk1 里面元组的数目(势)在 Section 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 里,这个例子里,结果是 scalarltselscalarltselpg_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 出现的频率累加起来,然后从一里面减去这些 — 因为我们的条件数值不是这些值之一,然后用剩下的独立数值来除。 请注意这里没有空值,因此我们不用担心这些。估计的行数也用一样的方法计算:

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 |

在这个例子里,没有 unique2MCV 信息, 因为所有数值看上去都是唯一的,因此我们可以使用一个只依赖唯一数值数目和空值数目百分比的算法来给两个表计算(选择性):

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

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

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