开务数据库 (原：云溪数据库) 始终保持在产学研单干畛域的翻新倒退，通过建设校企联结实验室，针对国家和行业的重大需要，致力于攻克数据库技术难题。
如果你对数据库核心技术、前沿科学钻研等感兴趣，并心愿能够扎根于数据库畛域，那诚邀大家关注“Paper Reading”文章专栏。
咱们会邀请寰球顶尖的数据库专家，深入浅出地率领大家走进学术世界，学习实践，翻新实际！
论文题目
An Adaptive Strategy for Statistics Collecting in Distributed Database（该论文被收录于 Front.Comput.SCI）论文地址
https://link.springer.com/art…
01. 导入语
在数据库系统中，统计信息对于查问优化至关重要，谬误的统计信息将重大影响到查问优化的品质。因为统计信息存在缺失、过期或不充沛的状况，优化器常常会抉择次优的执行打算，但现在已有很多策略可能保障统计信息的正确性。
然而在分布式系统下，咱们不能疏忽统计信息收集时的效率问题以及对系统的影响。从统计信息的收集形式来看，一些零碎在各节点上收集统计信息，记为局部统计信息。
当优化器须要应用统计信息时，局部统计信息须要聚合为全局统计信息。这种策略能够充分利用并行计算资源来进步收集效率，然而没有思考聚合时统计信息正确性的损失以及对系统性能的负面影响（统计信息收集时占据大量系统资源，将影响零碎失常运行）。
从统计信息收集的频率来看，收集统计信息的周期短，可能更加及时地修改谬误的统计信息。然而这会使统计信息收集的频率减少，耗费大量系统资源。
综上所述，统计信息的收集是一个费时费力的操作。在分布式数据库中，要想实现无效地收集统计信息且不影响零碎性能和统计信息的正确性这一想法，具备很高的挑战性。目前往往只能从单维度思考统计信息的收集，疏忽了多种相干因素。
因而此篇论文提出了一种自适应收集策略（Adaptive Statistics Collecting），记为 ASC，无效地均衡了收集效率、统计信息的正确性以及对系统性能的影响。通过本篇论文，大家能够理解到：
- 如何将统计信息收集流程形式化，并剖析与统计信息收集无关的因素间的互相关系；
- 自适应组件为统计信息收集提供鲁棒性的策略，均衡与统计信息收集无关的因素关系；
- 剖析传统算法的问题并论述本文提出的算法如何解决这些问题；
- 在分布式环境下，从收集效率，统计信息的正确性、对系统性能的影响这三个方面评估本文算法。
02. 准备常识
一、收集流程
统计信息的收集流程往往能划分为 3 个阶段：When、Where 和 How。
When：统计信息的收集是一个被动的操作，意味着它的执行须要被某些事件触发，通常是增量数据达到某个阈值；
Where：统计信息的收集与利用是离开的，意味着咱们须要抉择适合的地位去存储它们；
How：统计信息收集的执行形式分为 3 种，如下表所示：
将以上三个阶段联合，能够失去传统的统计信息收集流程，如下图所示：
二、与统计信息收集相干的因素及互相关系
和统计信息收集相干的因素，如下表所示：
依据一些启发式规定，给出各因素之间的关系，如下表所示：
注：零碎性能的高下能够了解为零碎是否可能失常维持原有的性能。
三、指标函数
对于 Collecting Efficiency（E）、Correctness of Statistics（C）、Negative Effect To System Performance（NEP）3 个因素，函数最终目标是在保障对系统性能 P 影响较低的条件下，尽可能进步统计信息的收集效率 E 和统计信息的准确性 C。
03. 自适应统计信息收集
一、ASC 流程
自适应统计信息收集 ASC 是用三个自适应组件 Adaptive Triggering、Adaptive Tcheduling、Adaptive Executing 实现目标函数。ASC 的流程图如下：
对流程图的解读如下：
- 基于事件造成 ESI（能够存储必要信息的一个架构），在不同阶段之间传递，并且动静扩大，满足不同的需要；
- Adaptive Triggering 组件依据 ESI 决定触发工夫（是否触发统计信息的收集），并且产生收集工作，存储在 ESI 中，传递给 Adaptive Scheduling 组件；
- Adaptive Scheduling 组件为收集工作决定适合的执行模型、执行地位与存储地位；
- Adaptive Scheduling 组件能够判断以后零碎状态是否能够执行收集工作，如果能够，利用对应的执行模型执行收集工作，并将后果存储在相应地位。
二、ESI
所有的自适应决策须要基于一些信息，在不同阶段这些信息不同。ESI 存储这些信息并依据不同阶段动静扩大，ESI 的表达式和变量的具体含意如下：
三、Adaptive Triggering
何时收集统计信息会影响统计信息的准确性和零碎状态，Adaptive Triggering 组件综合思考丰盛的信息，依据 3 个阈值判断是否触发收集工作：
WT 为增量数据阈值，与 PostgreSQL 的阈值设置类似，其中 b 代表根底阈值，默认为 50；X 是元组数量；Θ 为系数因子，默认为 0.1，代表增量的百分比。
HT 代表一张表的重要性，是查问这张表的频数，用英文表白是 Query Heat Threshold，σ 的表达式如下，示意 N 张表的均匀 Query Heat。
ST 代表着状态阈值，State Threshold 示意比均匀可用内存数高的节点数量，即衰弱节点数，K 示意总节点数。
基于以上 3 个阈值，算法 1 如下：
对算法的解读如下：
当零碎处于衰弱状态时，意味着衰弱节点数的 25% 大于收集工作数（Line 3），而后咱们能够假如零碎可能解决这些收集工作同时放弃对系统性能较低的负面影响，因而能够触发所有的收集工作（Line 4）。
如果不满足 1 中的条件，对于每个工作，如果它增量元组的数量和重要性（Query Heat）都大于阈值（Line 8），则能够触发这个工作。
如果 1 和 2 都不满足，咱们能够放宽束缚，只判断是否满足其中一个阈值条件。然而阈值自身会进步（Line 10），这一判断可能确保较为重要的工作或增量数据较多的工作能够被触发。
最初，如果存在须要被触发的工作，保留它们并触发（Line 14-16）。
注：局部常量值，例如算法 1 Line 10 的 1.5 和 2 通过试验剖析失去。
四、Adaptive Scheduling
Adaptive Scheduling 为每一个收集任务分配适合的执行模型，并确定执行地位和存储地位。
回顾在后面 How 中提到过的 3 种模型：PCM，PmCM，GCM，存在以下特点：
传统办法个别只能指定一个模型，不足通用性。为解决这个问题，利用一个函数，记为 DM，为每个工作基于它所占据的节点数决定它的执行模型。DM 函数如下：
其中 Θ 是一个阈值，其表达式为 ε*log2(K/2)，其中 K 为分布式系统的总节点数，ε 为系数因子，默认为 2。这样的设置基于启发式的理由：大型工作更须要效率，小型工作更须要准确性。
因为 PmCM 与 PCM 比拟类似，但 PmCM 的效率低于 PCM，所以作者只思考从 PCM 和 GCM 两种执行模型中抉择。
对于 PCM，执行地位和存储地位都为要收集的对象（表）所在位置；对于 GCM，执行地位只有一个：蕴含最多要收集表内容的节点，这使得网络传输最小；存储地位由用户定义。具体算法如下：
五、Adaptive Executing
对于一个收集工作，它的执行地位的状态可能并不容许间接解决这些工作，Adaptive Executing 决定以后收集工作何时执行。具体算法如下：
算法 3 中的输出是收集工作以及它的存储地位，当检测到以后节点的状态（F 代表内存利用率）低于某个阈值时（默认为 55%，由教训所得），才能够执行此工作，执行后果将存储到对应的存储地位中（Line 2-9）。
六、算法总结
传统的统计信息收集存在一些共性问题：对于收集统计信息的工夫（触发条件）判断简略，个别只看增量数据，没有综合思考多种因素；执行和存储模型不通用，不能适应各种情景；收集工作的执行不能自适应地管制。
ASC 用三个组件解决以上问题：Adaptive Triggering 利用更加丰盛的信息判断何时触发；Adaptive Scheduling 为每个工作抉择最合适的执行模型和执行地位；Adaptive Executing 自适应地管制工作的执行工夫。
下图为 ASC 的一个例子，比拟直观易懂：
04. 试验评估
本文作者利用 OceanBase 与 TPC-H 数据集，别离对收集效率，收集准确性和对系统性能影响三个方面进行算法评估，同时和传统办法进行了比照。
在前面的试验后果中，本文提出的算法记为 CS-AP。传统办法别离记为 CS-PP、CS-PG、CS-GG。其含意和算法如下：
- CS-PP：partial collecting and partial storing algorithm
- CS-PG：partial collecting and global storing algorithm
- CS-GG：global collecting and global storing algorithm
注：在传统算法中，用 WT 示意触发统计信息收集的阈值。
一、收集效率
统计不同节点数、不同数据量下的执行工夫。
二、收集正确性
本试验的目标是证实用 ASC，可能更加正当的利用系统资源，及时为更加重要的工作和增量数据较多的工作触发统计信息的收集。
三、对系统性能的影响
其中，MRU 为 Memory Utilization Rate，即内存利用率；Q 为只执行查问但不执行收集工作时的零碎；O 为初始状态的 MUR。