68.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
的基数已在Section 14.2中介绍,但在此重复以确保完整性。在pg_class
中查找页数和行数:
SELECT relpages, reltuples FROM pg_class WHERE relname = 'tenk1';
relpages | reltuples
----------+-----------
358 | 10000
这些数字是表格中最后VACUUM
或ANALYZE
的当前数字。然后,计划者将获取表中当前的实际页面数(这是一项廉价的操作,不需要进行表扫描)。如果与relpages
不同,则对reltuples
进行相应缩放,以得出当前行数估计。在上面的示例中,relpages
的值是最新的,因此行估计与reltuples
相同。
让我们 continue 一个示例,该示例的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”所占据的直方图分数。这就是选择性。直方图将范围划分为相等频率的存储桶,因此我们要做的就是找到我们的值所在的存储桶,并对其部分和所有进行计数。值 1000 显然在第二个存储桶(993-1997)中。假设每个值在每个存储桶中呈线性分布,我们可以将选择性计算为:
selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
= (1 + (1000 - 993)/(1997 - 993))/10
= 0.100697
也就是说,一个完整的存储桶加上第二个存储桶的线性分数除以存储桶的数量。现在可以将估计的行数计算为tenk1
的选择性和基数的乘积:
rows = rel_cardinality * selectivity
= 10000 * 0.100697
= 1007 (rounding off)
接下来,让我们考虑一个在其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 列表中的值为* not *时,如何估算选择性。该方法是利用该值不在列表中的事实,结合所有 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 的所有频率相加并从一个频率中减去,然后除以“其他”不同值的数量。这相当于假设不是所有 MCV 的列部分在所有其他不同值之间均匀分布。请注意,没有 null 值,因此我们不必担心这些值(否则我们也将从分子中减去 null 分数)。然后像往常一样计算估计的行数:
rows = 10000 * 0.0014559
= 15 (rounding off)
上一个关于unique1 < 1000
的示例是对scalarltsel
实际功能的简化。既然我们已经看到了使用 MCV 的示例,那么我们可以填写更多细节。该示例就目前而言是正确的,因为unique1
是唯一列,因此它没有 MCV(很明显,没有任何其他值比任何其他值更通用)。对于非唯一列,通常将同时具有直方图和 MCV 列表,并且直方图不包括由 MCV 表示的列总体的一部分。我们这样做是因为它可以进行更精确的估算。在这种情况下,scalarltsel
直接将条件(例如,“ <1000”)应用于 MCV 列表的每个值,并且将满足条件的 MCV 的频率相加。这样可以在表中的 MCV 部分中准确估算出选择性。然后,以与上述相同的方式使用直方图来估计表格中非 MCV 部分的选择性,然后将这两个数字组合起来以估计总体选择性。例如,考虑
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'
由前六个条目而不是后四个条目满足,因此总体 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
几乎落在第三个直方图桶的末尾。使用一些关于不同字符出现频率的粗俗假设,计划者针对直方图总体中小于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)
在此特定示例中,来自 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)
计划者假定这两个条件是独立的,因此子句的各个选择性可以相乘在一起:
selectivity = selectivity(unique1 < 1000) * selectivity(stringu1 = 'xxx')
= 0.100697 * 0.0014559
= 0.0001466
rows = 10000 * 0.0001466
= 1 (rounding off)
注意,估计从位图索引扫描返回的行数仅反映与索引一起使用的条件。这很重要,因为它会影响后续堆提取的成本估算。
最后,我们将检查一个涉及联接的查询:
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 (rounding off)
加入的限制为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 |
在这种情况下,没有unique2
的 MCV 信息,因为所有值似乎都是唯一的,因此我们使用的算法仅依赖于两个关系的不同值的数量及其空分数:
selectivity = (1 - null_frac1) * (1 - null_frac2) * min(1/num_distinct1, 1/num_distinct2)
= (1 - 0) * (1 - 0) / max(10000, 10000)
= 0.0001
这是,从每个关系中减去一个零分数,然后除以不同值的最大数量。联接可能发出的行数计算为两个 Importing 的笛卡尔乘积的基数乘以选择性:
rows = (outer_cardinality * inner_cardinality) * selectivity
= (50 * 10000) * 0.0001
= 50
如果两列都有 MCV 列表,eqjoinsel
将使用 MCV 列表的直接比较来确定由 MCV 表示的部分列总体内的连接选择性。其余人口的估计数采用此处所示的相同方法。
请注意,我们显示inner_cardinality
为 10000,即未修改的tenk2
大小。通过检查EXPLAIN
输出,可能会发现联接行的估计值来自 50 * 1,即,外部行数乘以tenk2
上的每个内部索引扫描获得的估计行数。但是事实并非如此:在考虑任何特定的连接计划之前,就估计了连接关系大小。如果一切运行良好,则两种估算联接大小的方法将得出大致相同的答案,但是由于舍入误差和其他因素,它们有时会大相径庭。
对于那些对更多细节感兴趣的人,可以在src/backend/optimizer/util/plancat.c
中估算表的大小(在任何WHERE
子句之前)。子句选择性的通用逻辑在src/backend/optimizer/path/clausesel.c
中。特定于运算符的选择性函数主要在src/backend/utils/adt/selfuncs.c
中找到。