TiDB 优化器实现的基础:统计信息的收集

2017-01-11 15:24:17来源:oschina作者:zhaiyuan人点击



# TiDB 优化器实现的基础:统计信息的收集
---
> **收集统计信息的意义**
一个 SQL 数据库里,优化器实现的好坏对性能的影响是决定性的。一个未经优化的执行计划和经过充分优化后的执行计划,执行时间的差别往往是成千上万倍。而对一个 SQL 优化器来说,统计信息是必不可少的条件,只有依赖统计信息提供的数据,优化器才可以正确估算不同的执行计划的执行代价,以选择最优的执行计划。就像一个大厨无论多么优秀,没有上等食材也是无法做出美味的饭菜。
###统计信息包含的内容
统计信息有两类,包括 Table 统计信息和 Column 统计信息。
Table 统计信息包含 Row Count 和 Row Size。
Column 统计信息包含 Null Count,Max Value,Min Value,Distinct Count 以及 Histogram。其中 Histogram 用来记录这个 Column 的数据详细分布,可以用来估算大于、小于或等于某个 Value 的 Row Count。
###统计信息采集的步骤
**1)在 TiDB 执行 ANALYZE TABLE 语句,手动触发收集动作。**
我们知道,一个 Table 的数据往往是在不断变化的,我们无法保证统计信息时刻保持在最新状态,总会有一定的误差,如果我们不及时更新,随着时间的推进,这个误差可能会越来越大,影响到优化器的优化效果。
有时我们会需要让统计信息更新的频率低一些来降低系统的压力,因为每次的统计信息收集都是开销很大的操作。有时我们会需要立即更新统计数据,因为我们刚刚向一个表导入了大量的数据,马上就需要查询。
所以定期更新统计信息的功能,我们希望可以用独立的模块,用更灵活的策略来实现,TiDB 本身只需要支持基本的手动触发就可以了。
**2)全表扫描。**
全表扫描的执行过程比较长,整个扫表的任务会被分解为一系列 Region 的小请求,每个 Region 的请求会返回该 Region 包含的 Table 的部分数据。
**3)用扫描得到的数据,记录 Row Count 和 Row Size,并对数据采样。**
扫描得到的数据量有可能会非常大,以至于无法把全部数据保留在内存里进行处理,所以需要进行采样,当采样的概率均匀的时候,计算生成的统计信息的误差是可以接受的。这里我们设定的采样数是 1 万,无论 Table 有多大,最后保留的样本数不会超过 1 万。后面会详细介绍采样时使用到的算法。
**4)采样数据生成 Column 统计信息,并保存到 KV。**
采样得到的数据会进行计算生成 Histogram。
### 采样算法
要得到一个均匀分布的采样池,一个最简单的算法是,当我扫描整个表的时候,读到的每一行,都以一个固定的概率决定是否加入采样池,这个概率 P =(采样池大小/表的行数)。但是由于在扫描之前,我们并不知道一个表总共有多少行,所以如果使用这个算法进行采样,就需要扫描两次,第一次获取整个表的行数,第二次进行真正的采样。
一个更优化的算法,蓄水池算法,可以在表的大小未知的情况下,一次扫描得到均匀分布的采样池。
**算法的实现**
假如我们的样本池大小为 $M = 100$ ,从头开始扫描全表,当我们读到的记录个数 $K < 100$ 时,我们把每一条记录都加入采样池,这样保证了在记录总数小于采样池大小时,所有记录都会被选中。
我们继续扫描,当我们扫描到的第 $K = 101 条$时,我们用概率 $P = (M/K) = (100/101)$ 决定是否把这个新的记录加入采样池,如果加入了采样池,采样池的总数会超过 $M$ 的限制,这时我们需要随机选择一个旧的采样丢掉,保证采样池大小不会超过限制。
执行这样采样算法一直到全表扫描结束,我们可以得到一个均匀分布的采样池。
**算法的证明**
这个算法可以用归纳法来证明,如果表的大小 $N <= K$,所有记录都会放入采样池,满足均匀分布的要求。
现在假设当读取完 K 个元素时,采样池满足均匀分布的要求,采样概率 $P = (M / K)$,当读取第 $K + 1$ 个记录时,我们应用蓄水池算法,以 $P' = M / (K + 1)$ 的概率决定是否加入采样池,这时出现了两种情况,被加入和没有被加入,我们继续分析这两种情况下,这条记录被选中的概率。
如果记录没有被选中,旧样本被保留概率是$Po1 =(1 - P') P = (1 - M / (K + 1)) (M / K)$, 新样本被保留的概率是 Pn1 = 0。
如果记录被选中,采样池中已有的采样有 (M - 1) / M 的概率被保留,旧样本概率是 $Po2 = P' P Po = (M / (K + 1)) (M / K) ( (M -1) / M)$,新样本的整体概率是 $Pn2 = P' = M / (K + 1)$。
把两种情况下的概率相加, 得到旧采样被保留的概率 $Po = Po1 + Po2 = (1 - M / (K + 1)) (M / K) + (M / (K + 1)) (M / K) *( (M -1) / M) = M / (K + 1)$,新采样被保留的概率为 $Pn = Pn1 + Pn2 = 0 + M / (K + 1) = M / (K + 1)$,所有采样被保留的概率都是 $M / (K + 1)$,满足均匀分布的要求。
**Histogram**
Histogram 的类型主要有两种,Frequency Histogram 和 Height-Balanced Histogram。
当 $NDV < Bucket Count$ 时,Frequency 可以包含全部 value 分布信息,每一个 distinct value 占用一个 bucke。
但是当 $NDV > bucket count$ 时,Frequency Histogram 没有足够的 bucket 存放 value,我们就需要用另外的 Histogram 类型,比如 Height-Balanced Histogram。
Height-Balanced Histogram 把所有 value 从小到大排序,平均放到所有 bucket 里,但是缺点是无法记录有哪些 popular value。
Oracle 还实现了一种 Hibrid Histogram,综合了 Frequency Histogram 和 Height-Balanced Histogram 的优点,TiDB 实现的 Histogram 主要参考的就是 Oracle 的 Hibraid Histogram。
Hibrid Histogram 包含 N 个 bucket,我们设定的 N 的默认值是 256,每个 bucket 包含三个字段 `number`,`value` 和 `repeat`,`number` 代表放在这个 bucket 里的最后一个 value 在 table 里排序后的 offset,`value` 就是放在这个 bucket 里的最大的那一个 value,`repeat` 代表最大的 value 的个数。
Hibrid Histogram 在生成的过程中,如果一个 bucket 装满了,遇到下一个 value 的时候,比较一下这个新的 value 和前一个 value 是否相等,如果相等,增加 repeat 值,直到遇到一个更大的 value,换下一个 bucket 存放这个 value,这样保证任何一个 value 只会在 一个 bucket 内存在,相比 Height-Balanced Histogram,可以包含更准确的 value 分布信息。
我们用一个实例来说明 Hibrid Histogram 是如何存储 value 分布信息的。
给定 value 集合 $['a', 'a', 'b', 'c', c', 'c', 'c', 'd', 'd', ‘e’]$ 和 bucket count 3,生成的 histogram 如下:
>[number, value, repeat]
[2, 'b', 0]
[6, 'c', 3]
[9, 'e', 0]
我们可以看到这个集合内, 'c' 的个数有 4 个,在第二个 bucket 里准确记录了 'c' 的 repeat 数量 3,这样我们在查询条件为 `where column = 'c' `的时候,就可以准确的估算执行开销。
统计信息的收集,使 TiDB 的优化器掌握数据分布详情,准确估算执行开销,从而实现高效的 CBO (cost base optimization)。
---
这是对 PingCAP 第 15 期 NewSQL Meetup 中《TiDB 优化器统计信息的采集》这一议题的干货整理。作为一个前沿领域的技术公司,PingCAP 希望能为在国内营造真正关注技术本身的社区和 Meetup 贡献一分力量。自 2016 年 3 月 5 日开始 ,我们在每周六举办 NewSQL Meetup,通过 1-2 个议题与大家交流讨论,并跟大家分享 TiDB 最新的一些进展和我们的思考,希望藉由这个机会让更多人关注到下一代分布式数据库。同时,我们也会定期从 Meetup 分享中筛选议题以文章形式与大家做进一步深度探讨。欢迎感兴趣的小伙伴关注 TiDB 项目,盼望各路大牛加入 PingCAP。

最新文章

123

最新摄影

微信扫一扫

第七城市微信公众平台