X-DB 统计信息管理

X-Man：统计信息管理功能集中收集和存储数据的统计信息，并在SQL优化过程中使用，生成最优的执行计划。实现数据统计信息管理功能有两个出发点：一是为了提升SQL优化的性能，二是为了支持分布式SQL查询处理。本文将深入描述X-DB统计信息管理功能的实现。

统计信息如何提升SQL优化性能

X-DB由AliSQL发展演进而来，AliSQL原生支持代价估算的查询优化方式。代价估算过程中会使用很多统计信息，比如：表的data size、记录总行数、平均记录行长、索引data size、一个range范围内的记录行数等等。作为一个单机数据库，AliSQL的做法是：查询优化过程中，下探到本地存储引擎层获取这些信息。比如要估算一个range范围内的记录行数，以InnoDB的B+树索引为例，具体过程是：1，在B+树上确定每层level的rang start和range end位置；2，在B+树上从上到下扫描每层level的记录总数；3，每层level当数据量小时用精确计算，当数据量很大时用近似估算的方式。如下图所示：

这种方式存在两个问题：一是优化过程中很多地方都需要这些统计信息，因而造成信息重复获取；二是信息收集过程会带来计算和IO开销，导致整体性能下降。统计信息功能的作用是，将优化过程中需要的元信息预先从存储引擎层收集起来，实际使用时只需要读取已经存储的元信息，减少引擎下探开销。

X-DB是shared nothing架构的分布式数据库系统，数据存放在多个不同节点上，单个节点上可能没有全量数据。同时，X-DB提供对称的分布式查询能力，即查询SQL请求发送到任何一个X-DB节点都可以正常执行。这就要求任何接收查询SQL请求的节点都能够生成正确的分布式执行计划。显然，查询优化依靠引擎下探的方式获取统计信息是不可行的，因为查询的数据可能不在本地节点上。所以我们预先收集所有节点数据的统计信息并进行集中管理，某个节点进行SQL优化的时候去查询集中管理的统计信息。

整体框架

统计信息管理功能主要涉及到下面几个模块：

GMS（Global Management Servie）：全局管理服务，负责X-DB集群元数据、集群、用户、Schema以及统计信息等内容管理。其中统计信息的管理包括发起收集统计信息命令、统一存储全局统计信息、刷新各个节点上的统计信息缓存等等。

LMS（Local Management Servie）：节点本地管理服务，是GMS在X-Server节点上的执行代理。LMS在本地缓存了元数据、分区位置信息以及统计信息等内容，目的是为了减少GMS访问的网络开销，提升本地执行性能。

SQL Engine：分布式SQL处理引擎，负责对查询SQL进行优化并生成具体的执行计划，并且负责发起分布式并发查询。优化过程会读取LMS中的统计信息。

X-Engine：数据存储引擎，提供高性能的数据存储服务。负责对存储的数据进行统计并收集统计信息。

统计信息内容

本文所述统计信息分为三个部分：表统计信息、索引统计信息、列统计信息。列统计信息从形式上又可分为两个维度：基本统计信息和直方图信息。表统计信息主要用来做全表扫描的代价估算，索引统计信息主要用来做索引扫描的代价估算，而列统计信息主要用来做范围查询的代价估算。

表统计信息

表统计信息包括下列内容：

全表扫描代价计算分成两部分：数据io代价和cpu代价。计算公式如下

io_cost = (data_size / IO_SIZE + 2) * page_read_cost(1.0)

IO_SIZE 为一次IO的数据大小，默认为一个page大小。

page_read_cost(1.0)为读一个page的代价，与data_in_mem直接相关。

加2为优化器hard code，这么做是为了防止cost为0，2是一个经验值。

cpu_cost = records * row_evaluate_cost()

row_evaluate_cost()为计算一个记录cpu代价，默认0.2。

索引统计信息

索引统计信息包括下列内容：

X-DB基于新一代存储引擎X-Engine，它的架构采用了类似LSM-Tree的思想，将新写入的数据以追加方式写入内存，然后逐渐淘汰并合并到持久化的存储层次中，这个结构在每个层次中采用了与存储相适应的结构，DRAM中使用latch-free的索引结构，持久化存储中使用copy-on-write B-Tree，并进行压缩，辅以FPGA对合并过程进行加速。二级索引可以抽象为一棵B树，记录内容包括键值部分以及主键值部分。索引覆盖扫描的代价包括io代价和cpu代价，计算公式如下：

io_cost = ceiling(records / keys_per_block) * page_read_cost(1.0)

ceiling(records / keys_per_block) = (records + keys_per_block - 1)/keys_per_block

keys_per_block = (block_size/2) / (key_length + ref_length) + 1;

计算每个block包含的键值个数时做了一个假设，认为每个索引block只使用了一半的空间，所以有block_size/2。

cpu_cost = records * row_evaluate_cost()

列统计信息

列的统计信息分两部分：基本统计信息和直方图信息。列统计信息的作用是做filter factor的估算，从而计算一个给定range内的行数。基本统计信息可以满足简单场景下的行估算，而直方图信息可以做复杂场景下的行估算。

基本统计信息包括下列内容：

基本统计信息可用来对数值型数据的range做行估算，并且假定数据是均匀分布的。下图代表了range查询的四种情况。

情况1代表range查询完全落在数据范围内，该情况下行估算公式如下，根据区间的开闭情况，决定是否需要加density。

cardinality = (records - null number) ( (range end - range start) / (max - min) [ + [2 *] density] )

情况4代表range查询完全不在数据范围内，该情况下行数估算结果为一个很小的值，公式如下：

cardinality = (records - null number) * density

情况2、3是上面两种情况的中间状态，计算公式如下：

情况2：cardinality = (records - null number)*( (range end - min) / (max - min) [+ density] + density )

情况3：cardinality = (records - null number)*( (max - range start) / (max - min) [+ density] + density )

直方图

列的基本统计信息的计算公式有一个假设：认为数据是均匀分布的，并且只能对数字型数据进行计算。对于非数字型数据，以及数据偏移分布的情况，为了达到更高的估算精度，使用直方图信息。X-DB使用了两种类型的直方图，分别是singleton类型和equivalent height类型。singleton类型是一个宽度为1的等宽直方图，每个bucket只包含一个value信息，而equivalent height类型是每个bucket的frequency大致相等的等高直方图。选择的逻辑是：列数据NDV（Number of Distinct Value）不大于直方图buckets number时选择singleton类型直方图，否则选择equivalent height类型直方图。

singleton类型直方图包含下列内容：

1.buckets number

2.bucket

Key Value

Cumulative frequency

图中singleton直方图包含4个buckets，所以buckets number为4。每个buket的Key Value分别是val1、val2、val3、val4。

上图中一个range范围查询包含了vol2和vol3两个bucket，行估算计算公式如下：

cardinality = (records - null number) * (Cumulative frequency(vol3) - Cumulative frequency(vol1) )

equivalent height类型直方图包含下列内容：

1.buckets number

2.bucket

min/max

NDV

Cumulative frequency

equivalent height类型直方图一个bucket内可以包含若干个Key value，并且认为bucket的数据是均匀分布的。下图中包含3个buckets，每个bucket表示一个区间(min, max)。

上图所示，查询range范围包含了bukcet2和部分bucket3的内容，行估算计算公式如下所示：

cardinality = (records - null number) * ( frequency(bucket2) + frequency(bucket3) * distance)

distance = (range end - min) / (max - min)

计算distance过程中，如果是数字类型数据可以直接计算，如果是字符类型则我们通过一个特殊的哈希函数将它变成一个哈希数，然后再进行计算。该哈希函数的特点是：计算的哈希数能够保持字符数据间的大小关系，既如果str1 > str2则hash(str1) > hash(str2)。

示例说明

有一张员工信息表结构如下：

Create Table: CREATE TABLE `worker` (

`id` int(11) NOT NULL AUTO_INCREMENT,

`name` varchar(32) DEFAULT NULL,

`dep_no` int(11) DEFAULT NULL,

`group_no` int(11) DEFAULT NULL,

PRIMARY KEY (`id`),

KEY `idx_dep_group` (`dep_no`,`group_no`, `name`)

) ENGINE=InnoDB DEFAULT CHARSET=utf8

共4个字段，两个索引。员工号id为主键，name是员工姓名，dep_no为部门number，group_no为小组number。假设共10万条员工信息，30个部门，每个部门下的小组数量不等。分析下面的查询SQL优化过程：

select name from worker where id > 10001 and id

优化器分析过程中会发现有两个索引可以使用：主键PK和二级索引idx_dep_group，分别对应的字段是id、dep_no，会分别对两个索引访问做代价估算。计算PK访问代价时用到字段id的列统计信息，由列基本统计信息可以估算输出cardinality为大概1000。根据列dep_no的基本统计信息可以估算出cardinality大概为3300（10w/30），因此会选择走PK主键扫描。如果dep_no字段上有直方图信息，且直方图有64个bucket。则可以清楚的知道`dep_no=15`的部门共有多少员工，假如只有300名员工，则最终会选择走idx_dep_group索引。

统计信息收集

统计信息收集的命令在GMS节点上发起，并根据表的location信息转发到相应的节点上执行。收集的统计信息不但要更新本地LMS缓存，还要回传到GMS节点上存储，同时还要通知其它节点更新相关缓存信息。整个过程如下图所示：

统计信息收集命令发送到GMS节点上后，整个收集过程分下面几个步骤：

1.GMS节点将信息收集命令转发送到目标表所在的节点上，目标节点的SQL Engine通知X-Engine层进行信息收集；

2.X-Engine将收集的信息返回给SQL Engine，SQL Engine进行相应计算后交付给本地LMS模块进行处理；

3.LMS接收统计信息结果后更新本地cache，然后回传给GMS节点；

4.GMS节点接收统计信息结果将其存储到全局系统表中，并且向其它节点广播相关统计信息的失效消息；

5.其它节点LMS模块收到统计信息失效消息后删除本地缓存相关的统计信息。

异常情况处理：

1.collection msg网络发送失败时进行重试，最多重试3次，若还是失败则收集命令返回给用户失败信息。

2.统计信息收集执行过程中会记录当前执行的状态，GMS会轮询命令执行状态。当发现命令状态失败或者出现网络隔离的情况下，GMS认为命令失败并返回给用户。

3.GMS将统计信息失效命令广播给其它节点时，如果出现发送失败则进行重试，最多重试3次。如果重试3次依然失败则通过LMS缓存中的过期机制做统计信息失效。

X-Engine信息收集

表基本信息

表基本信息主要包括表的行数和存储空间的大小，X-Engine在磁盘的数据是按EXTENT进行管理的，将数据文件划分为相同大小的EXTENT，通过内存结构控制EXTENT的分配和回收，通过日志保证一致性，同时定期的CHECKPOINT保证外存恢复时间可控。引擎将表的数据按聚簇索引存储, 主键包含所有列数据，为了减少每次数据写操作都更新SQL层的统计信息影响性能，采用将EXTENT上对数据信息聚合结果在EXTENT分配和回收时上报给上层，从而高效的完成表信息的统计。过程如下图所示：

索引基本信息

对于具体key的信息，通过扫描索引能够得到精确值，而叶子块的数量扫描EXTENT内存管理结构可以高效的获取，EXTENT内部结构如下：

列基本信息

列信息除了一些通过扫描得到的基本信息外，最主要的是NDV的统计，NDV统计如果要做到精确，需要消耗过多的系统资源，同时统计时间也不可接受。我们使用了目前比较流行的计算NDV的算法HyperLogLog，经测试它在1亿的数据量时偏差控制在2%以内，而O(n)的时间复杂度完全能够满足优化器和搜集的需求。

HyperLogLog是基于LogLog算法的改进版，LogLog算法的思想是将一个value进行hash计算并记录hash值中1的位置，根据所有hash值中1的最大位置数反算出数据value的NDV。公式是：n=2^k，n是数据NDV，K是1的最大位置。HyperLogLog的做法是增加了多个bucket，每个value计算hash后落在其中一个bucket中，并对每个bucket做LogLog算法计算。最后求所有bucket中n值的调和平均数。算法示意图如下：

图中共4个bucket，一个数据经过hash计算后得到一个二进制数，根据最低2位确定bucket（2^2 = 4）。上面最低2位是"10"，因此bucket的位置offset=2。根据二进制其它的位确定register_count，上图"1000"中1出现在位置4，所以register_count=4（bucket中只记录最大的register_count）。最终NDV是对所有register_count取调和平均值。HyperLogLog算法bucket的数量越多精确度越高，当然会消耗更多的资源，通过实际测试64K的桶数是个比较好的折中。

抽样扫描

基本信息搜集除了表以外，索引和列都是通过扫描EXTENT来实现的，若表的数据量很大时，全表扫描执行时间就会相当长，这会导致功能基本不可用。为了把搜集时间控制在有效的范围内（比如分钟级别），同时又不丢失表的数据特征，需要在统计的过程中进行抽样，通过配置需要扫描的数据块的量和总的表的数据量决定抽样比例：

抽样比例=配置读取数据量/表总数据量

扫描数据块的过程中，每次计算一个0-1的随机值，如果这个值比抽样比例大，就跳过这个EXTENT而扫描下一个，抽样扫描的流程图如下：

直方图创建

构造一个列的直方图过程主要有两个阶段，首先从存储引擎层扫描收集该列的value值，并构造一个value map对象，value map的内容是(Key value，count)，表示每个不同Key value的个数。数据收集过程中需指定最大扫描空间，当扫描空间大于等于表空间则进行全表扫描，否则进行样本空间数据扫描。value map对象收集完成后使用它来构造直方图，若Key value number

对下列value map构造一个直方图，map中共包含5个key value。如果指定直方图有5个buckets，则会选择构造singleton类型的直方图。构造的直方图结果如下：

[value map]

key value count

----------------------------------

‘a’ 4

'b' 2

'c' 7

'd' 9

'e' 11

total number 33

[singleTon histogram]

buckets number= 5

key value cumulative frequency

-----------------------------------------

'a' 4/33

'b' (4+2)/33

'c' (4+2+7)/33

'd' (4+2+7+9)/33

'e' (4+2+7+9+11)/33

对同样的value map，如果指定直方图有4个buckets，则会选择构造equivalent height的直方图。构造的直方图结果如下：

[value map]

key value count

----------------------------------

‘a’ 4

'b' 2

'c' 7

'd' 9

'e' 11

total number 33

threshold = 33/4 = 8 -- 每个bucket应该包含的平均value count

[Equi_height histogram]

bucket number=4

buckets cumulative frequency (threshold) distinct values

('a', 'b') 6(8)/33 2

('c', 'c') 13(16)/33 3

('d', 'd') 22(24)/33 4

('e', 'e') 33(32)/33 5

构造equivalent height直方图过程中，每个bucket包含的value count应该尽量接近threshold的值。

统计信息缓存同步

LMS缓存

LMS统计信息缓存模块负责缓存表、列、索引统计信息以及直方图统计信息，所有节点启动时都会初始化统计信息缓存管理模块。SQL层获取统计信息时，首先访问LMS统计信息缓存管理模块，如果缓存命中则直接使用缓存的统计信息，否则LMS缓存管理模块会发起异步刷新本地统计信息的任务，从系统表中获取缺失的统计信息并刷新缓存。对于本地表遇到LMS统计信息缓存不命中时走原先通过下探引擎获取统计信息的逻辑，否则报错处理。统计信息缓存管理模块通过4个独立的KV Cache分别管理表、列、索引以及直方图统计信息，这些Cache通过分区hash_map和LRU技术减少高并发时的锁冲突以及内存淘汰等问题。

GMS同步刷新

数据节点在本地执行完统计信息收集命令后，将变化的统计信息项通过RPC message发送回GMS节点，GMS节点以广播的方式将这些统计项发送到集群中的其他节点, 这些节点接受到刷新统计信息缓存的RPC后，将本地缓存的对应统计信息项删除，同时触发从系统表中异步拉取新统计信息内容的任务。

对于X-DB这样的分布式系统，不可避免地会出现网络分区或RPC丢包的问题，如何保证集群中各节点的统计信息缓存保存一致？X-DB采用触发更新和定期淘汰结合的方式更新本地缓存，如果刷新统计信息的任务失败，GMS节点会将失败的任务投放到消息队列中，异步执行框架会不断的从消息队列中取出任务，直到执行成功为止。LMS的统计信息缓存会设置一个有效时间（TTL），假设有效的时间为10分钟，当查询访问缓存时，如果缓存命中且缓存项的上次更新时间距离当前时间的间隔在10分钟内，则直接返回缓存内容。如果缓存TTL时间超过10分钟，则触发异步刷新cache的任务。异步刷新cache的任务通过无锁队列和异步执行框架进行调度，确保前台线程不受影响。

未来规划

目前存储引擎通过数据扫描的方式收集统计信息，会带来性能开销和估算不准的问题。未来将统计信息收集过程做到与X-Engine Compaction过程相结合，提高统计信息准确性和减少收集过程性能开销。对于分区表的情况，一个表的多个分区可能分布在多个物理节点上。将涉及到分区级别统计信息的收集管理和聚合操作，既要有分区级别统计信息也要有表级别统计信息，这方面将有很多工作改进的空间。对于过滤条件中涉及多个不同列，或者联合索引键，当前我们假设它们之间是独立的关系。实际上有些场景下，它们之间可能存在相关性。为进一步提升统计信息的精度，将会考虑创建基于column group的信息。

- end -