BaikalDB技术实现内幕(三)--代价模型实现

原创
11/12 22:47
阅读数 6.2K

本系列文章主要介绍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`)
    ) 

存储模型如下图:

其中倒排索引不适合做列信息的统计,不在本文的讨论范围。全局二级索引和主表数据存储在不同分片上,统计信息使用和局部二级索引类似,只以局部二级索引为例。

索引选择

索引遵循最左前缀匹配原则:只有相等的情况,才会使用下一级索引,如遇范围匹配则不能使用下一级索引。示例:

  1. 索引(a,b),比如where b = 2;则不符合最左前缀原则,无法使用该索引。只有在查询条件中使用了创建索引时的第一个字段,索引才会被使用。
  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 Sketchdistinct count等等。

  1. 列直方图可以用来估计某一区间在整个范围内的占比,用于范围查询;
  2. Count-Min Sketch可以用来估计某一元素的出现频率,用于等值查询;
  3. 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过程中需要根据表的数据量及数据分布调整顺序。
展开阅读全文
打赏
2
5 收藏
分享
加载中
更多评论
打赏
0 评论
5 收藏
2
分享
返回顶部
顶部