BaikalDB技术实现内幕（三）--代价模型实现
本系列文章主要介绍HTAP数据库BaikalDB的技术实现细节
作者简介：于正泉，百度商业平台研发部高级研发工程师。主要从事分布式存储、分布式数据库等领域的工作，现主要负责BaikalDB SQL 性能优化，稳定性相关方向的研发工作。
欢迎关注 Star github.com/baidu/BaikalDB 国内加速镜像库gitee
BaikalDB系统简介
BaikalDB是一个分布式可扩展的存储系统，兼容MySQL协议，整个系统的架构如下图所示： 
- BaikalStore 负责数据存储，数据分区按region组织，三个Store的三个region形成一个 Raft-group 实现三副本，多实例部署，Store实例宕机可以自动迁移 Region数据；
- BaikalMeta 负责元信息管理，包括分区，容量，权限，均衡等， Raft 保障的3副本部署，Meta 宕机只影响数据无法扩容迁移，不影响数据读写；
- BaikalDB 负责前端SQL解析，查询计划生成执行，无状态全同构多实例部署，宕机实例数不超过 qps 承载极限即可。
索引介绍
本文只介绍BaikalDB是怎样基于代价进行索引选择的。首先简单回顾下BaikalDB的索引。 BaikalDB索引类型包括，主键索引，局部索引，局部唯一索引，全局二级索引和倒排索引。主键索引是 BaikalDB 针对主键创建的索引，主键 key 值必须唯一。BaikalDB 使用主键值将整个表进行 range 划分为多个 region 分区。 示例：
CREATE TABLE `t` (
`a` INT(10) NOT NULL,
`b` DATETIME NOT NULL,
`c` BIGINT(20) UNSIGNED NOT NULL,
`d` TINYINT(3) NOT NULL,
`e` VARCHAR(100)NO NULL,
PRIMARY KEY (`a`),
KEY b_c_key (`b`, `c`),
UNIQ KEY c_d_uniq (`c`, `d`)
)
存储模型如下图：
其中倒排索引不适合做列信息的统计，不在本文的讨论范围。全局二级索引和主表数据存储在不同分片上，统计信息使用和局部二级索引类似，只以局部二级索引为例。
索引选择
索引遵循最左前缀匹配原则：只有相等的情况，才会使用下一级索引，如遇范围匹配则不能使用下一级索引。示例：
- 索引(a,b)，比如where b = 2；则不符合最左前缀原则，无法使用该索引。只有在查询条件中使用了创建索引时的第一个字段，索引才会被使用。
- 索引(a,b,c,d)，比如where a = 1 and b = 2 and c > 3 and d = 4；范围查询条件命中索引时无法继续使用下一级，例子中c为范围查询，则d用不到索引，只能作为普通条件过滤。如果索引是(a,b,d,c)，则可以用到全部索引列。
基于代价优选索引
对于能匹配到多个索引的SQL，需要选择一个最优的代价最小的去执行。何为最优索引，检索量是个很重要的指标，一条SQL获取的数据量固定，检索量越少说明该索引越高效，为了选出最优的索引，需要预估出使用某个索引的检索量，那么我们就需要一些统计信息。 BaikalDB维护的统计信息包括列直方图、Count-Min Sketch、distinct count等等。
- 列直方图可以用来估计某一区间在整个范围内的占比，用于范围查询；
- Count-Min Sketch可以用来估计某一元素的出现频率，用于等值查询；
- distinct count可以用来评估该列的区分度。
查询条件（范围，等值，IN）在采样数据中的占比我们称之为选择率，再乘以表的总行数可以预估该条件需要检索的行数。对于单列索引可以直接计算出索引的检索行数，对于联合索引涉及多列，假设每列是相互独立的，那么将每一列的选择率相乘即可得到联合索引的选择率，进而可以预估联合索引的检索行数。统计信息的生成和使用如下图
接下来，我们将详细介绍直方图和Count-Min Sketch的实现和使用。
统计信息
列直方图
直方图是一种对数据分布情况的图形表示，是一种二维统计图表，它的两个坐标分别是统计样本和该样本对应的某个属性的度量， 我们用直方图描述列数据的分布情况。 直方图分为等宽直方图和等深直方图，在对统计数据进行分桶时，等宽直方图比较难估计桶边界，在数据倾斜较大时等深直方图有较小的误差，所以我们使用等深直方图。直方图横坐标表示列区间，纵坐标表示落入该桶内的列采样个数。如下图，数据集合{1,1.5,2,3,4,6,7,8,9}，生成三个桶[1,2]，[3,6]，[7,9]，桶深均为3。
Count-Min Sketch
Count-Min Sketch 是一种可以处理等值查询的数据结构。Count-Min Sketch维护了一个d*w的二维数组，对于每个值，用d个独立的hash函数映射到每一行的每一列中，并对应修改这d个位置的计数值。查询一个值出现了多少次，依旧用这d个hash函数找到每一行中被映射到的位置，取这d个值的最小值作为估计值。如下图： 
统计信息的构建
统计信息总体构建流程
analyze 复用select查询计划，这样只需要增加baikaldb的排序功能和baikalStore的抽样功能
蓄水池抽样
在构建直方图的时候，无法将所有数据都读出来进行排序，因此我们采用蓄水池抽样算法，用于生成均匀抽样集合。蓄水池抽样算法用于从包含n个项目的集合S中选取k个样本，其中n为一很大或未知的数量，尤其适用于不能把所有n个项目都存放到内存的情况。证明过程可以参考维基百科。
列直方图的构建
通过执行analyze语句，将抽样请求下推到每个region上执行，然后将每一个region上的结果归并排序。我们会根据表的总行数以及region的行数预估每个region的采样行数，假设需要采样S行，表的行数为T，region的行数为R，那么预估这个region需要采样 S * (T/R)行。 由于提前已经知道采样总行数和直方图桶个数，因此可以知道每个桶的深度。顺序遍历每个值V：如果V值等于上一个值，那么将V放在与上一个值同一个桶里，这样保证每个值都只存在于同一个桶中。如果不等则判断当前桶是否已满，如果不是直接放入当前桶，否则开辟新桶。对于数据比较倾斜的场景，例如相同值个数大于平均桶深的某个阈值则单独为该值开辟新桶。
Count-Min Sketch的构建
Count-Min Sketch相对比较简单，每个region构建自己的Count-Min Sketch，然后再baikaldb聚合，二维数组对应位置的值相加即可。
统计信息的应用
索引代价计算
在查询语句中，通常一条select语句会命中多个索引，上面讲到我们会通过统计信息来预估索引的检索行数，接下来我们通过具体的例子来介绍使用统计信息来计算索引的代价。 根据不同条件，一般分为等值查询、多列查询、范围查询。 以如下 schema 为例：
CREATE TABLE table (
field0 bigint(20) NOT NULL DEFAULT '0' ,
field1 bigint(20) NOT NULL DEFAULT '0' ,
field2 bigint(20) NOT NULL DEFAULT '0' ,
field3 bigint(20) NOT NULL DEFAULT '0' ,
field4 bigint(20) NOT NULL DEFAULT '0' ,
field5 bigint(20) NOT NULL DEFAULT '0',
PRIMARY KEY (field0),
KEY field1_idx (field1),
KEY field2_idx (field2),
KEY field3_field4_idx (field3,field4)
)
例如：select * from table where field0 > a1 and field0 < a2 and field1 = b and field3 = c and field4 < d;
该条SQL可以命中_primary_key_、field1_idx、_field3_field4_idx_这三个索引。关于BaikalDB索引的使用可以参考之前的文章，本文不做过多赘述。
-
等值查询 对于索引field1_idx，可以使用Count-Min Sketch 获取 field1等于a值的个数N，N除以采样行数得出选择率，再乘以表行数预估检索行数即为该索引的代价。
-
范围查询 对于索引primay_key，可以使用直方图估计区间(a1,a2)的占比。具体算法如下： 在前面介绍等深直方图时，直方图为三个桶，分别为[1,2]，[3,6]，[7,9]，桶深均为3。如果我们想预估落在[1.2,8]这个区间内的行数，对应到直方图上可以看到[3,6]这个区间是完全被覆盖的，[1,2]和[7,9]各被覆盖一部分。完全覆盖很好理解，那么覆盖一部分怎么计算呢？我们假设桶内数据是连续均匀分布的，那么可以通过比例去估算，(2-1.2) / (2 - 1) * 3 = 2，(8-7) / (9-7) = 1。
-
多值查询 对于索引_field3_field4_idx_，如何计算这个联合索引的检索行数，通常我们认为不同列之间是相互独立的，因此把每列的选择率相乘就能得到该联合索引的选择率。
使用主键和二级索引的区别，对于使用二级索引并且没有索引覆盖的查询SQL，需要回表，回表的代价和顺序扫描的代价是不同的，对于RocksDB来说回表的性能更差，所以在计算索引代价时需要回表的索引要乘以一个系数。
索引推荐
一些无索引/索引区分度低等原因导致检索行数多、性能差的SQL，容易导致主机及DB资源消耗大，还可能影响同实例其他SQL，使DB吞吐能力降低，存在很大的风险。对于这种低效SQL，我们希望能给出建议索引，协助用户优化性能。 首先对真实SQL模糊、抽象，生成SQL指纹，对SQL进行归类，对每一类SQL进行统计，包括扫描行数、过滤行数，计算过滤率(过滤行数/扫描行数)，筛选出过滤率加大的低效SQL。
抽象出来的SQL查询条件没有具体的值，所以使用distinct count信息推荐索引，结合最左匹配规则，等值条件优先，其次是多值条件，最后是范围查询条件。为了提高索引的区分度，distinct count较大优先靠左排列。
后续工作
目前BaikalDB代价模型只实现了索引选择，正在进一步完善中，主要工作如下:
- 索引直方图
在联合索引的代价计算是在假设不同列相互独立的前提下计算的，如果联合索引列之间相关性比较高，利用列直方图计算出的索引代价误差较高。我们将直接对联合索引数据进行采样生成索引直方图，来降低索引列相关性的影响。 - 统计信息动态更新
目前代价计算使用的统计信息没有实现动态更新，如果表的写入或更新量较大可能造成统计信息不准确。 - Join Reorder
在实际的业务场景中，多个表的 Join 语句是很常见的，而 Join 的执行效率和各个表参与 Join 的顺序有关系。Join Reorder过程中需要根据表的数据量及数据分布调整顺序。
