本文正在参与炫“库”行动-人大金仓有奖征文
链接 https://marketing.csdn.net/p/98bd30353e7cb998b6070a89e8b91edb
表的基数估算值即优化器预估的查询返回的记录的个数，是KES数据库优化器选择执行计划的一个重要决定因素。以下面的执行计划为例，对表a,表b的基数估算值分别为rows=1和rows=10150，即对表a经过查询条件id=1的过滤，预估能返回一条记录，而表b则返回10150条记录。
TEST=# explain select * from a,b where a.id=b.id and a.id=1; QUERY PLAN ---------------------------------------------------------------------------------- Nested Loop (cost=247.08..4194.46 rows=10150 width=125) -> Seq Scan on a (cost=0.00..2789.00 rows=1 width=89) Filter: (id = 1) -> Bitmap Heap Scan on b (cost=247.08..1303.96 rows=10150 width=36) Recheck Cond: (id = 1) -> Bitmap Index Scan on b_index (cost=0.00..244.54 rows=10150 width=0) Index Cond: (id = 1) (7 rows)
基数估算是否准确对数据库优化器能否选择一个高效的执行计划有重要影响。例如， A,B做join操作， 如果A预估rows=1，很可能会选择执行计划为nestloop(A B), 但如果A 实际10000,而B 是一个耗时的查询，执行会很慢。
通常来说，基数估计的基本公式为：基数估计值 = 表的总行数 * 选择率。其中表的总行数是一个固定的值，而如何得到正确的选择率则成为一个重要的课题。目前主要的数据库论文如SIGMOD,VLDB,ICDE等对选择率的研究主要涉及概率论，数据抽样等领域。即先从数据库中的表中对数据进行抽样，保证抽样数据能尽量接近整个数据集的数据分布，然后将抽样数据组成直方图，MCV图等统计信息，最后在计算选择率时，根据过滤或连接条件等输入信息，和统计信息一起来计算选择率。
在KES中,表的行数保存在系统表sys_class中。对每一个数据表，在sys_class中有对应的一行记录来描述该表，其中reltuples列保存该表的行数的值。该值并非一个精确值，而是根据数据表的大小和每行的大小等值计算的一个近似值。而数据表的统计信息保存在系统表sys_statistic和sys_statistic_ext中。
下面的章节描述不同场景下如何进行选择率的计算。分为三种情况：
- 单列的选择率：如 select * from a where id=1中id=1条件的选择率
- 多列的选择率：如 select * from a where id1=1 and id2=2中id1=1 and id2=2条件的选择率
- 联合查询的选择率：如select * from a,b where a.id=b.id中a.id=b.id的选择率
1.单列查询条件基数估计
基数估计时，KES对查询的条件分别进行基数计算，然后将每个单列的基数估算值合并。对每一列的基数估算采用什么方式取决于操作符。例如对等式(例如select * from a where id=2)会采用MCV图的方式。对比较操作(大于，小于等)会采用直方图和MCV图结合的方式等。
1.1 等值条件的选择率计算与MCV图
作用：
MCV(most common values)相当于顶频直方图。统计信息保存列中频率最高的前K个数值，存储相应的频率 。用于对等式(Var = Const)进行选择率的估算。当数据表中的某一列的数据存在重复值且重复频率不同时，统计信息表sys_statistic中会产生MCV类型的统计信息。在进行基数估算时，公式为：
- 如果常量Const在MCV信息中，则取该值对应的频率
- 如果常量Const不在MCV信息中，取值
除了查询条件中有等式的情况可以用到MCV图。在其他运算符基数估计时也会用到MCV图对其中一些常量值出现的频率进行计算。如比较运算符(例如id>1)，也会用到MCV图得到其中常量1的频率来参与后续的估算
例子：
例如，表b中有10行数据，id列有三个去重值： 1(共5个)，2(共3个)，3(共2个)
则统计信息表sys_statistic中信息为
stakind1 | 1 => 标识该统计信息为MCV
staop1 | 96 => 标识该统计信息的适用的操作符为整数的等于操作符
stavalues1 | {1,2,3} => 最经常出现的值为1,2,3。
stanumbers1 | {0.5,0.3,0.2} => 对应的每个值出现的频率，例如1的频率为 5/10
在实际的执行计划中我们也会看到：
对id=1的基数估计值 = 表中总的数据行数 * 常量1出现的频率 = 10 * 0.5 = 5
TEST=# explain select * from b where id=1; QUERY PLAN ------------------------------------------------- Seq Scan on b (cost=0.00..1.12 rows=5 width=4) Filter: (id = 1) (2 rows)
1.2 比较条件的选择率计算与直方图
作用
直方图通常用于比较运算符(如大于，小于)的基数估计中，用于查询一个范围的值。其计算公式随操作符的不同而不同。
当对某一列已经存在MCV统计信息，则直方图为将出现在MCV中的值去除之后的列值的统计信息。
例子
例如表tenk1有10000行记录。
SELECt relpages, reltuples FROM pg_class WHERe relname = 'tenk1'; relpages | reltuples ----------+----------- 358 | 10000
直方图如下：
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}
执行以下SQL，查询条件unique1<1000。可以看到基数估计值为1007
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)
其计算公式为
selectivity = (1 + (1000 - bucket[2].min)/(bucket[2].max - bucket[2].min))/num_buckets
= (1 + (1000 - 993)/(1997 - 993))/10
= 0.100697
rows = rel_cardinality * selectivity
= 10000 * 0.100697
= 1007
1.3 索引的IO代价与Correlation值
作用
统计信息Correlation为一个介于+1~ -1之间的值，描述的是数据记录保存的物理位置和按照某个属性进行排序时的偏差值。该统计信息不是用于基数估算，而是用于执行代价计算。在计算Btree索引和brin索引的代价时，该值影响磁盘IO的代价值。当该值趋近于0时，优化器会偏向于bitmap扫描
例子
TEST=# select * from d; id1 | id2 | id3 -----+-----+----- 1 | 8 | 3 2 | 7 | 4 3 | 6 | 5 4 | 5 | 1 5 | 4 | 2 6 | 3 | 8 7 | 2 | 7 8 | 1 | 6 (8 rows)
对列 id1：值按升序插入，correlation=1
stakind2 | 3 统计类型为correlation
staop2 | 97 (运算函数为整数小于号：int4lt)
stanumbers2 | {1} correlation=1
对列 id2：值按降序插入，correlation=-1
stakind2 | 3
staop2 | 97
stanumbers2 | {-1}
对列 id3：值按随机插入，correlation=0.54
stakind2 | 3
staop2 | 97
stanumbers2 | {0.54761904}
1.4 数组等值条件的选择率计算与MCELEM信息
作用
MCELEM(most common element)类似于MCV,区别在于其只在数据类型为数组的列上(如tsvector,anyarray,varray,…)生成统计信息,而且是以所有为不为null的行为基数生成统计信息。
例子
TEST=# select * from e;
id | ts
----+-------------
1 | '{1,2,3,4}'
1 | '{1,6,5,4}'
1 | '{1,2,7,8}'
1 | '{1,2,7,8}'
(4 rows)
stakind1 | 4 统计类型为
staop1 | 98 字符串相等运算符texteq
stacoll1 | 100
stanumbers1 | {0.25,0.5,0.25,0.25,0.5} 出现的频率，组成为： MCE值的频率 + 最小频率 + 最大频率
stavalues1 | {"{1,2,3,4}","{1,2,7,8}","{1,6,5,4}"} most common element值
1.5 数组比较条件的选择率计算与数组类型直方图
1.6 Rang类型的长度直方图
作用
对于rang类型的计算进行基数预估
例子
TEST=# select * from a; id | val ----+--------- 1 | [2,10) 2 | [11,21) 2 | [11,21) 2 | [31,41) 2 | [51,91) (5 rows)
统计信息如下
stakind2 | 6 类型为STATISTIC_KIND_RANGE_LENGTH_HISTOGRAM
staop2 | 672 运算符为浮点数的小于： float8lt
stavalues2 | {8,10,10,10,40} 长度的直方图，如第一个值[2,10]长度为8
1.7 Rang类型的边界直方图
例子
对以上的数据表a， 统计信息如下：
stakind1 | 7
stavalues1 | {"[2,10)","[11,21)","[11,21)","[31,41)","[51,91)"}
2. 多列查询条件基数估计
2.1与操作 - AND
多列基数估算指查询条件有多个时，如何将每个条件的选择率进行合并。
2.1.1多列统计信息表
作用
多列统计信息保存在系统表sys_statistic_ext中。当查询条件满足多列信息时，会使用多列信息计算选择率。多列统计能较准确的反映多列的选择率情况。但缺点是需要手动进行创建。
KES的多列统计信息有三种类型
- ndistinct : 适用于语句中有distinct, group的情况
- dependies: 列之间有依赖函数,要使用该类型，操作符要为等号。
Var = Const 或者 Const = Var
- MCV：记录重复的值和选择率，要使用MCV统计信息。
Dependies类型因为列之间有函数关系，所以估值更为准确。但如果多个列之间没有函数依赖关系时，可以使用MCV统计信息。MCV相对于dependies类型准确度欠缺但是可以支持更多的操作类型。支持的操作包括：
(a) (Var op Const), or (Const op Var), Op 包括("=", "<", ">", ">=", "<=")
(b) (Var IS [NOT] NULL)
(c) AND/OR/NOT
dependencies多列统计信息的使用示例
例如，对表t(a int, b int)
插入数据 insert into t select i %100, i %100 from generate_series(1,10000) s(i)
满足条件a=1 and b=1的记录实际100条，但是预估基数值时，估值为1。这是因为KES是按照属性相互独立的假设来估算的。
- 表中10000条记录
- 满足条件a=1的记录100条，选择率1%
- 满足条件b=1的记录100条，选择率1%
- 按照属性独立的假设，满足a=1 and b=1的选择率 = 1% * 1% = 0.01%
- 最终预估计基数 10000 * 0.01% = 1
TEST=# explain select * from t where a=1 and b=1; QUERY PLAN --------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=1 width=8) Filter: ((a = 1) AND (b = 1))
实际上属性a, b是有函数依赖关系的: 每一行中a = b。所以创建依赖关系的多列统计信息
TEST=# create statistics stts(dependencies) on a,b from t; CREATE STATISTICS TEST=# analyze t; ANALYZE
然后再执行查询时，结果估算正确
TEST=# explain select * from t where a=1 and b=1; QUERY PLAN ----------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=100 width=8) Filter: ((a = 1) AND (b = 1)) (2 rows)
N-Distinct多列统计信息的使用示例
注：本节的技术在后面的聚合查询基数估计中使用
TEST=# explain analyze select count(*) from t group by a,b; QUERY PLAN ----------------------------------------------------------------------------------------------------------- HashAggregate (cost=220.00..230.00 rows=1000 width=16) (actual time=47.090..47.139 rows=100 loops=1) Group Key: a, b -> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual time=0.038..3.718 rows=10000 loops=1)
当对列a,b进行分组时，预估值为1000.实际上因为a,b都是从0到99不断循环且值相同，所以应该有100个分组。建立多列统计信息后，基数估算准确。
TEST=# create statistics stts1(ndistinct) on a,b from t; CREATE STATISTICS TEST=# analyze t; ANALYZE TEST=# explain analyze select count(*) from t group by a,b; QUERY PLAN ----------------------------------------------------------------------------------------------------------- HashAggregate (cost=220.00..221.00 rows=100 width=16) (actual time=14.360..14.406 rows=100 loops=1) Group Key: a, b -> Seq Scan on t (cost=0.00..145.00 rows=10000 width=8) (actual time=0.033..3.034 rows=10000 loops=1)
MCV多列统计信息的使用示例
以上的查询也可以使用MCV多列信息来进行基数估计。如下
TEST=# create statistics stts1(mcv) on a,b from t; CREATE STATISTICS TEST=# analyze t; ANALYZE TEST=# explain select * from t where a=1 and b=1; QUERY PLAN ----------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=100 width=8) Filter: ((a = 1) AND (b = 1))
系统表中的统计数据如下
values frequency
--------------------------------------
{0,0} 0.01
{1,1} 0.01 => 对a=1 and b=1，其对应的选择率0.01
…
{99,99} 0.01
2.2.2范围查询
在一个查询中如果有多个比较条件，且涉及同一变量,KES会判断是否为一个范围，如果是其选择率的计算公式是 S = S1 + S2 -1(S1,S2分别为多个条件的选择率)。
2.2.3基于属性值独立性(AVI)假设的估计
当没有多列统计信息且查询条件不是一个范围时，KES会认为各个查询条件相互独立，从而将其选择率相乘做为最终结果的选择率。
2.2或操作 - OR
多个查询条件为或关系时，KES的计算公式为S(x ) + S(y) - S(x) * S(y)。
如以上的表t为例子中,
a=1的选择率为1%
b=1的选择率为1%
a=1 or b=1选择率为1%+1% - 1%*1% = 1.99%
基数估算值 = 10000 % 1.99% = 199
TEST=# explain select * from t where a=1 or b=1; QUERY PLAN ----------------------------------------------------- Seq Scan on t (cost=0.00..195.00 rows=199 width=8) Filter: ((a = 1) OR (b = 1)) (2 rows)
3多表联合查询的基数估计
3.1 概念
KES有三种表的连接方式：nestloop, Hashjoin, mergejoin。表的基数估算值和连接方式无关，而是与内外子表的基数估算值和连接条件有关。在估算时，与连接无关的条件被下推到子表中参与子表基数估算。
如下面的例子，select * from a, b where a.id=b.id and a.val>10;
3.2 公式
一个内联查询的基数估算公式
Selectivity = 左表的基数估算值 * 右表的基数估算值 * join条件的选择率
其中：
- 左右子表可以为简单表，也可以为子查询或联合查询等。
- 当有多个join条件时，KES认为其属性是无关的，所以多个条件是相乘的关系
- 选择率分为两种：当join条件满足外键时，按照外键算法计算选择率。否则按照普通join条件算法计算选择率。
3.3 选择率计算示例
- 外键选择率计算
KES外键的定义可以如下所示 create table a(id int, refid int references b (id))。
其中表b的id属性做为表a的refid属性的外键。按照外键的限制,表b的id属性必须没有重复值，且所有a.refid的值必须在b.id中也存在。
在计算select * from a,b where a.refid=b.id的选择率时，我们可以看到条件a.refid=b.id是外键相关的两个属性的联合。基于以上外键的限制，选择率的公式为
Selective = 1/|R(b)|. 即外键所在表的总行数的倒数。
- 普通Join条件选择率计算
当联合条件不满足外键时，计算公式为
Selective = 1/Max(ndv(a), ndv(b)), 即取a,b 中join使用的属性不重复的个数的倒数。
以下面两个表为例，
表t1基数估算为7，属性id不重复值为7
表t1基数估算为6，属性id不重复值为3
则t1.id=t2.id的选择率为1/max(7,3) = 1/7
则t1 join t2的基数 = 7 * 6 * 1/7 = 6
TEST=# insert into t1 select generate_series(1,7); TEST=# insert into t2 select generate_series(1,3); TEST=# insert into t2 select generate_series(1,3); TEST=# explain select * from t1,t2 where t1.id=t2.id; QUERY PLAN -------------------------------------------------------------- Hash Join (cost=1.14..2.30 rows=6 width=8) Hash Cond: (t1.id = t2.id) -> Seq Scan on t1 (cost=0.00..1.07 rows=7 width=4) -> Hash (cost=1.06..1.06 rows=6 width=4) -> Seq Scan on t2 (cost=0.00..1.06 rows=6 width=4) (5 rows)
本文正在参与炫“库”行动-人大金仓有奖征文
链接 https://marketing.csdn.net/p/98bd30353e7cb998b6070a89e8b91edb
