刘鹏举(1997-), 男, 博士生, 主要研究领域为智能数据分区, 组合优化, 负载预测, 强化学习
李好洋(1999-), 男, 博士生, 主要研究领域为数据库分区优化, 自然语言处理
王天一(1999-), 女, 硕士生, 主要研究领域为数据库分区与布局, 机器学习
刘欢(1997-), 男, 硕士生, 主要研究领域为数据分区, 机器学习, 图神经网络
孙路明(1994-), 男, 博士生, 主要研究领域为机器学习, 数据库系统
任逸飞(1987-), 男, 高级工程师, 主要研究领域为NoSQL数据库, 主存数据库, 分布式键值存储引擎
李翠平(1971-), 女, 博士, 教授, 博士生导师, CCF杰出会员, 主要研究领域为社交网络分析, 社会推荐, 大数据分析及挖掘
陈红(1965-), 女, 博士, 教授, 博士生导师, CCF杰出会员, 主要研究领域为数据库技术, 新硬件平台下的高性能计算
垂直数据分区技术从逻辑上将满足一定语义条件的数据库表属性存放在同一个物理块中, 进而降低数据访问成本, 提高查询效率. 数据库查询负载中的每条查询通常只与数据库表中的部分属性有关, 因此只需使用数据库表的某个属性子集便可以得到准确的查询结果. 合理的垂直数据分区方式可以使大多数查询负载不需要扫描完整数据库就可以完成查询任务, 从而达到减少数据访问量, 提高查询处理效率的目的. 传统的数据库垂直分区方法主要基于专家设置的启发式规则, 分区策略粒度较粗, 且不能根据负载的特征进行有针对性的分区优化. 同时, 当负载规模较大或者属性个数较多时, 现有垂直分区方法执行时间过长, 尤其无法满足数据库在线实时调优的性能需求. 为此, 提出在线环境下基于谱聚类的垂直数据分区方法(spectral clustering based vertical partitioning, SCVP), 采用分阶段求解的思想, 减少算法时间复杂度, 加快分区执行速度. 首先通过增加约束条件缩小解空间(即根据谱聚类生成初始分区), 然后对解空间设计算法进行精细的搜索(即采用频繁项集和贪心搜索相结合的策略对初始分区进行优化). 为了进一步提升SCVP在高维属性下的性能, 提出了SCVP的改进版本SCVP-R (spectral clustering based vertical partitioning redesign). SCVP-R通过引入同域竞争机制、双败淘汰机制和循环机制, 对SCVP在分区优化过程中的合并方案进行了进一步优化. 在不同数据集上的实验结果表明, 相比于目前最好的垂直分区方法, SCVP和SCVP-R有着更快的执行时间和更好的性能表现.
Vertical data partitioning technology logically stores database table attributes satisfying certain semantic conditions in the same physical block, so as to reduce the cost of data accessing and improve the efficiency of query processing. Every query is usually related only to the table’s some attributes in the database, so a subset of the table’s attributes can be used to get the accurate query results. Reasonable vertical data partitioning can make most queries answered without scanning the whole table, so as to reduce the amount of data accessing and improve the efficiency of query processing. Traditional database vertical partitioning methods are mainly based on heuristic rules set by experts. The granularity of partitioning is coarse, and it can not provide different partition optimizations according to the characteristics of workload. Besides, when the scale of workload or the number of attributes becomes large, the execution time of the existing methods are too long to meet the performance requirements of online real-time tuning of database. Therefore, a method called spectral clustering based vertical partitioning (SCVP) is proposed for the online environment. The idea of phased solution is adapted to reduce the time complexity of the algorithm and speed up partitioning. Firstly, SCVP reduces the solution space by increasing the constraint conditions, that is, generating initial partitions by spectral clustering. Secondly, SCVP designs the algorithm to search solution space, that is, the initial partitions are optimized by combining frequent itemset mining and greedy search. In order to further improve the performance of SCVP under high-dimensional attributes, a new method called special clustering based vertical partitioning redesign (SCVP-R) is proposed which is an improved version of SCVP. SCVP-R optimizes the partitions combiner component of SCVP by introducing sympatric-competition mechanism, double-elimination mechanism, and loop mechanism. The experimental results on different datasets show that SCVP and SCVP-R have faster execution time and better performance than the current state-of-the-art vertical partitioning method.
垂直分区是数据库物理设计中的经典技术. 它将一个表或多个表纵向切分成不相交的多个列组, 每个列组拥有相同数量的元组. 其形式化定义为: 给定关系表
例如, 给定某关系表
查询
求解最优垂直分区方案的最直接方法是暴力枚举法, 即枚举所有可能的分区方案, 并为每个方案计算执行所有工作负载的预期访问成本, 选择成本最小的方案. Bell数是指使用暴力枚举的方式求出垂直分区所有可能组合数. 对于含有
暴力枚举法的时间复杂度为
在线分区系统[
本文提出一个具有较低时间复杂度的垂直分区方法SCVP. 首先根据工作负载, 提取属性的亲和度矩阵, 生成表属性的关系图并在该关系图上进行谱聚类, 得到属性聚簇, 作为初步的分区方案; 然后对初始方案进一步优化, 包括分区的分割和合并两个过程, 首先对工作负载进行频繁项集挖掘, 利用得到的频繁模式作为先验信息, 将属性聚簇拆分成最小粒度的分区单元, 再根据先验信息, 将分区单元进行组合, 形成最终的分区方案并在数据库中部署. 同时本文也提出新的成本模型HDD-I (hard disk imputed cost model)和SCVP的改进算法SCVP-R, 该算法主要对SCVP的合并过程进行优化, 使性能发挥到最佳. 本文提出的方法将分区求解过程划分为两个优化阶段, 以减少每个阶段所面临的解空间, 因此更适用于高维属性; 其次, 由于第1阶段只利用了亲和度的普适性, 仅在第2阶段需要计算负载的执行成本, 从而减少了计算分区方案成本的总次数, 更适合于高负载. 实验证明, 在8个不同属性维度的数据集测试, SCVP和SCVP-R分别达到HillsClimb性能的92%、100.5%, 在执行时间上仅为Hills-Climb的1/226、1/17. 在8个不同负载规模的数据集中测试, SCVP和SCVP-R分别达到HillsClimb性能的97.6%和100%, 执行时间缩减到1/35、1/16.
本文第1节介绍了垂直分区的相关研究工作. 第2节介绍了SCVP、SCVP-R算法的原理. 第3节按照分区特性进行分类, 并给出了成本模型HDD-I. 第4节提出一种切割收益函数对SCVP和SCVP-R的执行时间进行优化. 第5节进行实验分析. 第6节对全文进行总结.
从1975年发展至今, 数据库垂直分区技术的研究可从两个角度进行归纳: (1)根据评价指标的演变将垂直分区研究划分为基于亲和度矩阵和基于成本模型两个阶段: 早期基于亲和度矩阵的方法认为如果将尽可能多的被共同访问的属性放在同一分区中, 这种划分就是有效的; 近年来的研究则提出采用模拟数据库实际环境的成本模型, 来作为评价分区方案优劣的标准. (2)根据分区的生成策略, 可分为自底向上、自顶向下、基于数据挖掘技术的垂直分区生成方法这3类. 本文主要从分区生成策略的角度对垂直分区研究进行介绍.
(1) 自底向上的垂直分区生成方法
对暴力枚举法的一种改进思路是采用自底向上的方法来生成垂直分区. 算法开始时, 首先得到一个初始化分区, 随后逐步迭代, 在每一次迭代中分区数减少一个或多个, 并设置停止条件. 例如HillsClimb就是典型的从单列布局开始自底向上迭代的算法.
AutoPart[
Hyrise[
Trojan[
(2) 自顶向下的垂直分区生成方法
对暴力枚举法的另一种改进思路是采用自顶向下的方法把整个表作为单个分区, 随后逐步迭代, 在每一次迭代中分区数增加一个或多个, 并设置停止条件.
Navathe等人[
Navathe等人[
O2P[
(3) 基于数据挖掘技术的垂直分区生成方法
Hoffer[
上述是垂直分区的研究现状, 整体来看, 算法以何种角度、分几个阶段生成分区其实并不决定性能优劣, 关键在算法逼近于暴力枚举法的程度与迭代复杂度之间的权衡. 文献[
本文提出的SCVP和SCVP-R方法解决了现有不足, 具体如下: (1)在切割过程中使用了自顶向下的分区生成方法, 使用图聚类方法进行分区初始化, 然后依据频繁模式进行更细致的分区修剪, 且目标并非是试图找到最终的分区方案, 而是得到该成本模型环境下, 粒度最小的分区单元, 便于多阶段处理的衔接. (2)在分区单元的合并过程中使用了自底向上的分区生成方法, 利用频繁模式指导合并, 而不是随机组合, 然后通过贪心策略确定分区单元合并的顺序, 通过降低组合空间最大程度减少迭代时间.
为了应对高维属性的复杂组合空间, 同时减少对成本模型的调用次数, 本文提出两阶段的垂直分区求解方法SCVP. 第1阶段, 从负载流中提取属性结点的亲和度矩阵, 使用谱聚类提取各个属性结点的特征向量, 经特征向量得到的聚簇结果作为初始分区方案. 第2阶段, 在初始方案的基础上依据成本模型HDD-I (见第3.2节), 通过切割和合并两个修剪过程, 得到最终的垂直分区方案.
SCVP算法的核心思想是通过分阶段求解, 减少算法时间复杂度, 加快分区执行速度. 首先通过增加约束条件缩小解空间(即根据谱聚类生成初始分区), 然后对解空间设计算法进行精细的搜索(即采用频繁项集和贪心搜索相结合的策略对初始分区进行优化). SCVP算法的整体架构如
SCVP架构
(1) 负载收集器(workload collector): 模型外部组件, 用于接收软件系统用户端的负载信息流, 将其处理为批量batch数据, 这些batch将会分配到线程池的processor类, 待软件系统发送分区信号后, processor生成亲和度矩阵和负载数据发送到属性聚类器.
(2) 属性聚类器(attributes clusterer): 将亲和度矩阵转化为属性的无向带权图, 对图进行切割得到聚簇, 作为初始分区方案交由优化器处理.
(3) 分区优化器(partitions analyzer): 依据负载数据生成的频繁模式作为先验信息, 使用测量分区方案性能的成本模型作为指导信息, 对初始分区方案分为两个阶段处理. 第1阶段由分区切割器(partitions splitter)完成, 使用自顶向下的策略对初始分区方案进行切割, 生成分区单元; 第2阶段由分区聚合器(partitions combiner)完成, 使用自底向上的策略对分区单元合并, 形成最终分区方案.
(4) 分区生成器(partitions generator): 根据分区优化器产生的最终分区方案生成DDL/DML语句部署到DBMS中.
本节对SCVP模型的4个组件执行原理进行更加详细的介绍. 为便于读者理解, 以如下的含有6个属性的关系表
关系表:
工作负载:
负载收集器对软件驱动程序(通常是ODBC与JDBC)发送的查询流进行批处理, 如
负载收集器的执行过程
(1) Batch结构与分配规则
Batch是一个字典结构, 包括时间片和容量为8的查询负载. 每个batch都被分配一个时间片, 它需要对复杂查询语句进行特征提取, 如多表查询需要拆分到多个单表的查询、对嵌套子查询进行合并、识别系统函数等, 最终形成的负载见
Batch的分配规则主要解决两个问题: (1) 到达的每一个查询应分配到哪个batch中. (2) Batch如何分配给processor. 首先, 所有的batch将被分组, 保证不同组的batch内不允许出现重合属性的查询. 然后, 当到来一个新的查询时, 检测目前未装满的batch, 将其添加到含有重合属性的组中, 如果出现多个组含有重合属性, 则将这些组合并成一个batch组, 以此来解决问题1. 当负载收集器接收到软件系统发送的分区信号时, 所有batch将所分配查询的始末时间作为时间片, 每个batch组分配一个processor, 以此解决问题2.
(2) 从batch中提取亲和度矩阵
Processor将batch组中的负载特征转化为亲和度矩阵记为
亲和度反映两个或多个对象共同出现的概率程度, 通常用共同访问频率来表示. 这里以第2.2节的例子1为例进行说明, 根据例子1可提取负载数据下属性的使用矩阵(attribute usage matrix, AUM)见
属性使用矩阵
Queries |
|
|
|
|
|
|
|
|
1 | 0 | 0 | 1 | 1 | 0 |
|
|
0 | 0 | 0 | 0 | 1 | 1 |
|
|
1 | 1 | 0 | 0 | 0 | 0 |
|
|
0 | 0 | 0 | 1 | 1 | 1 |
|
按照公式(2), 代入具体的数值, 则
在亲和度矩阵
(3) Processor的并行处理
由于不同processor中的负载特征是不关联的, 对于拥有独立分区特点(见第3.1节)的数据库环境, 属性聚类器及其后续组件均可并行处理, 否则, 只能串行处理.
在得到processor的亲和度矩阵后, 可以基于亲和度得到一个粗略的分区方案. 这样做有两个原因: 第一, 分区内的亲和度越大并不代表最终的分区成本低, 因此只能得到粗略的分区结果, 并非最优解. 第二, 算法初始状态下面临的解空间很大, 如果直接依据成本模型设计精细的算法, 时间复杂度很高.
SCVP使用图分割算法谱聚类生成初始分区. 谱聚类[
对于无向图
定义
其中,
定义
谱聚类有两种流行的切图算法: (1) RatioCut切图: 对每个切图, 不光考虑最小化
谱聚类的执行流程为: ① 根据邻接矩阵
下面从对谱聚类算法关键参数的设置进行分析, 包括3个方面.
(1) 邻接矩阵的选择和优化
将亲和度矩阵直接作为邻接矩阵, 此时属性的亲和度为边的权重. 如果processor被并行处理, 它的负载数据中将存在大量属性未访问, 这常常发生, 此时亲和度矩阵是一个稀疏矩阵. 为此, SCVP采取三元组顺序表压缩亲和度矩阵, 减少存储空间, 在由三元组映射为邻接矩阵时, 只将被访问属性写入邻接矩阵中.
(2) 切割方式和聚类算法的选择
选择切割效果更好的NCut作为切割目标, 谱聚类第4步对属性特征矩阵
(3) 聚簇数
谱聚类需要预先指定聚簇数
设
其中, 类
根据例子1的数据, 得到最佳的
分区优化器主要采用频繁项集挖掘和贪婪搜索相结合的方法来指导初始分区的更新过程, 包括分区的修剪、以及多个分区的合并和交叉等过程. 首先由FP-Growth算法[
分区切割器的功能是分区修剪, 将初始分区切分成具有原子性的分区单元. 原因在于: 初始分区方案是依据亲和度矩阵生成, 存在部分分区亲和度很高但由成本模型计算的代价成本很高, 需要对其进行切割降低成本, 每次切割只切一次, 即单个分区只能被切分两个分区, 新产生的所有分区将作为新的独立分区继续被分区切割器修剪. 分区修剪主要分为6个步骤.
步骤1. 将属性聚类器得到的聚簇作为初始分区, 首先判断当前数据库环境是否拥有独立分区特点(见第3.1节), 如果是, 则将每个分区交由线程池分发给指定的线程处理. 如果不是, 则由单个线程对所有分区顺序处理.
步骤2. 线程将待切割的分区放入到队列中, 并创建一个空的待分配列表. 从工作负载提取最小支持度为
步骤3. 从队列中pull一个待切割分区元素, 首先进行异常检测, 如果属性数小于2, 则直接将其添加到分区单元集合中, 否则对其进行切割操作.
步骤4. 从待分配列表中取出该待切割分区属性子集的所有频繁模式(若待分配列表为空, 则从Hash表中取出), 根据频繁模式将分区切为两段, 代入成本模型中计算按此频繁模式切割该分区的收益, 即
步骤5. 如果待分配列表不为空, 从待分配列表中取出第1个频繁模式, 即奖励最大的频繁模式作为切割点, 将该频繁模式push到队列中, 然后删除待分配列表中所有与该切割点有交集的频繁模式, 将分割后剩余的另一半分区作为待切割分区, 执行步骤4; 如果待分配列表为空, 则将该待切割分区加入到分区单元集合中, 此时检测队列中是否有元素, 如果有, 转入步骤3, 否则执行步骤6.
步骤6. 输出分区单元集合, 结束.
以例子1说明分区切割器的运行机理, 如
分区切割器的执行过程
算法
Input: 初始分区集合
Output: 分区单元集合
1
2 Initialize(Queue) //存放切割点的队列, 初始为空
3 Initialize(Set) //待分配列表: 存放临时的频繁模式, 初始为空
4
5 push(Queue,
6
7
8
9 continue
10
11
12
13
14
15 reward=costmodel(
16 //将每个切割点和其切割收益, 按照收益大小添加到待分配列表Set指定的位置
17 add(Set, (
18
19
20
21 push(Queue,
22
23 delete(Set, Unallocate_P) //删除Set中不属于分区Unallocate_P范围下的频繁模式
24 //更新待分配列表Set中在新的分区Unallocate_P下的切割收益
25 updateCutReward(Set, Unallocate_P)
26 sortByReward(Set) //按照切割收益对待分配列表降序排列
27
28 //待分配列表中无正向收益的频繁模式时, 将剩余分区加入到分区单元列表中
29
30
31
32
分区聚合器负责对分区切割器得到的分区单元进行组合. 分区聚合器放在分区切割器之后执行有两个原因: 第一, 分区单元作为粒度最小的单元, 在这个条件下进行合并操作, 能提供更多的组合方案, 便于找到最优解. 第二, 没有像HillsClimb算法一样选择从单个属性开始进行合并, 主要考虑到高维度下单个属性的组合规模太大, 显著影响执行时长.
关于分区聚合器中组合方法的设计, 一种朴素的方案是任意两个分区单元进行组合, 取出组合后收益最大的方案, 但导致的后果是, 每轮选择时都要列出所有的组合方案, 计算所有方案的成本, 并逐个选择成本最小的一种, 整个过程需要计算所有的组合方案. 分区聚合器采取了另外一种思路, 依据频繁模式这个先验信息, 进行分区单元的合并. 后续的实验证明这种思路带来的收益略低于朴素的方案, 但在高维属性下节约了将近200倍的时间成本. 分区的合并过程主要分为5个步骤.
步骤1. 从工作负载提取最小支持度为
步骤2. 从Hash表中依次取出每个频繁模式, 找到其所含属性涉及到的所有分区单元, 如果该分区单元组合被之前的频繁模式使用过, 则直接跳过该频繁模式, 如果未使用过, 则将其合并为一个分区, 计算合并前后的收益, 即
步骤3. 从待分配列表中取出第1个频繁模式, 即收益最大的频繁模式作为合并点. 然后删除待分配列表中所有与该合并点有交集的频繁模式(这里的交集指的是合并点与频繁模式所对应的分区单元组合是否有交集), 并将该合并点所对应的合并分区加入到最优分区方案中, 同时从分区单元集合中删除已被合并的分区单元, 如果待分配列表不为空, 执行步骤4, 否则执行步骤5.
步骤4. 由于有新的合并分区产生, 需要重新更新待分配列表中所有频繁模式的合并奖励收益, 并对待分配列表进行降序排列, 执行步骤3.
步骤5. 将分区单元集合中未合并的分区单元添加到最优分区方案, 结束.
以例子1说明分区聚合器的运行机理, 如
分区聚合器的执行过程
算法
Input: 分区单元集合
Output: 最终分区方案
1 Initialize(UnitsMap) //存放已被合并过的分区单元组合, 初始为空
2 Initialize(Queue) //存放切割点的队列, 初始为空
3 Initialize(Set) //待分配列表: 存放临时的频繁模式, 初始为空
4
5
6 //判断该分区单元组合是否被使用, 若是处理下个循环, 否则, 将该组合添加到UnitsMap中
7
8 continue
9
10 put(UnitsMap,
11
12
13 reward= costmodel
14 // 将每个合并点、合并分区及其合并收益, 按照收益大小添加到待分配列表Set指定的位置
15 add(Set,
16
17
18
19 push(Queue,
20 delete
21 delete(Set,
22 updateMergeReward(Set,
23 sortByReward(Set) //按照合并收益对待分配列表降序排列
24
25
26
分区生成器负责将垂直分区方案在数据库中在线部署, SCVP提供了两种部署方法, 第1种是根据分区方案由程序自动拼接分区的DDL/DML语句通过PDBC在数据库中执行, 第2种是创建数据库自定义函数, 设置触发器条件, 根据输入的分区方案在线建立分区. SCVP参考KingBase、达梦(DM)数据库文档, 对部署过程中作如下约束.
(1) 垂直分区算法需要根据原表结构数据及分区方案, 自动创建多个子表以及所有子表连接的分区基表.
(2) 分区基表不保存实际数据, 只保存表定义、分区信息, 实际数据保存在分区子表中.
(3) 建立垂直分区的表必须对主键建立聚集索引, 即CLUSTER PK, 并且此聚集索引不允许删除. 一般对原表的主键建立聚集索引, 并复制到各个子表中.
(4) 不支持任何列同时出现在多个分区子表中, 即不支持列重复.
从第2.2节可以看出, SCVP中分区聚合器组件对分区单元的合并思想设计很简单, 因为SCVP旨在考虑降低时间复杂度. 但同时也暴露出合并过程中的一些明显问题.
问题1. 如果一个分区单元组合被选中合并, 则后续关联该组合的频繁模式将不会被考虑, 这是因为不同频繁模式的分区单元组合如果相同, 则对应的合并分区也相同, 属于互斥关系, 只选择一个即可. 但与此同时带来的问题是, 多个不同的频繁模式被当做一种情况处理, 分区单元组合就不能完全反映频繁模式的特征.
问题2. 待分配列表中的频繁模式一旦被选中作为合并项, 其分区单元将被使用, 则后续含有该分区单元的频繁模式将被删除, 但如果存在多个频繁模式属于合并项的互不重叠的子集, 它们的合并收益之和大于排序靠前的频繁模式的合并收益, 则理应选择前者作为合并项.
问题3. SCVP仅在分区单元的基础上进行合并, 合并后的分区方案即作为最终分区. 由于贪心机制, 第1轮合并过程中, 部分收益小的频繁模式被忽略, 因此合并后的分区方案, 仍有继续合并的可能性.
为此, 本节将针对这些问题, 提出了新的分区聚合器-R (partitions combiner-R)组件, 替换原有的分区聚合器组件, 以此构建基于SCVP的性能优化模型: SCVP-R, 它的目标就是提升目前垂直分区方法在高维属性下的性能瓶颈问题, 同时保证时间复杂度在可控的范围内(非指数级)增长. 分区聚合器-R通过引入3种机制: 同域竞争机制、双败淘汰机制、循环机制来解决分区聚合器存在的3个问题, 具体解决思路如下.
(1) 同域竞争机制(sympatric-competition mechanism)
在构建待分配列表时, 每个频繁模式关联的分区单元组合, 将合并为两个分区: 频繁模式本身、剩余属性组成的分区, 替换原先只合并为单个分区的思路. 例如[a, c]关联的分区单元组合为{{a, b}、{c}}, 则该组合最终合并为{a, c}、{b}两个分区, 但这样做也将导致了大量的候选频繁模式, 为了降低复杂度, 分区聚合器-R在待分配列表的构建时, 引入同域竞争机制, 关联相同分区单元组合的多个频繁模式只保留合并收益较大的一方, 如
分区聚合器-R的3种机制
(2) 双败淘汰机制(double-elimination mechanism)
在构建待分配列表时, 会按照合并收益排序, 目的是选择收益最大的合并项, 并及时淘汰与之属性域有冲突的频繁模式, 此为单败制. 引入双败制后, 从待分配列表中取出的第1个元素, 原本应作为合并项, 但由于双败的考虑, 还会进一步比较, 如果发现列表中存在该合并项的多个不重叠的子项, 它们的合并收益总和大于原始合并项, 则淘汰原始合并项, 将其子项作为第1次合并项. 如
(3) 循环机制(loop mechanism)
如
本节将按照分区间的特性对分区进行分类, 包括独立分区与耦合分区的概念, 并介绍后续实验所使用的基于磁盘数据库的分区成本模型HDD-I.
根据数据库实际运行环境的不同, 可以将分区间的关系划分为独立分区与耦合分区.
(1) 独立分区: 如果某个分区的内部划分(即一个分区可能被拆解成多个分区)如何改变, 都不影响其他分区的现有收益.
(2) 耦合分区: 一个分区内部划分的改变会影响到其他分区的当前收益情况, 但收益变化未知. 其中, 耦合分区又根据某个分区结构改变后其他分区的收益变化趋势是否相同, 划分为耦合反馈分区和耦合相对反馈分区.
• 耦合反馈分区: 如果该分区划分后的收益变化趋势与其他分区的收益变化相同, 则称分区为耦合正反馈分区; 若变化趋势相反, 则分区为耦合负反馈分区. 易知, 独立分区是典型的耦合正反馈分区.
• 耦合相对反馈分区: 如果一个分区改变后, 其他分区的收益变化趋势不相同, 有的收益增加, 有的收益减少, 但收益值排序的相对顺序不变, 则称该分区为耦合相对正反馈分区, 如果相对顺序完全相反, 则称该分区为耦合相对负反馈分区.
根据目前垂直分区领域的已有的成本函数[
结论1: 单机数据库的分区属于独立分区或耦合正反馈分区.
结论2: 分布式数据库的分区属于耦合正反馈分区或耦合相对正反馈分区.
HDD (hard disk cost model)成本模型[
查询
聚集索引下扫描成本:
非聚集索引下的扫描成本:
顺序扫描成本:
其中, MF是主分区(main fragments)的缩写,
查询
其中, SF是次分区(secondary fragments)的缩写,
HDD存在一些不足, 如:
(1) 次分区的成本计算没有考虑到分区的长度.
(2) 没有考虑分区之间的连接成本, 导致生成次分区的优先级显著高于主分区.
(3) 查询的扫描键只考虑到一个属性, 而现实的查询往往是多个.
为此, 本文对HDD进行简化和改进, 提出新的成本模型HDD-I, 包括改进了主分区和次分区访问成本
对于查询
其中, MF、SF分别是主分区和次分区的缩写,
本节介绍一种切割收益更新函数用于对SCVP和SCVP-R算法加速, 并将其应用于成本模型HDD-I.
在分区切割器中, 对单个分区通常要进行多次切割, 每次切割都要重新计算所有频繁模式的切割收益, 重新代入成本函数计算切割前和切割后的成本变化, 成本函数至少达到O(分区数
设访问分区
进行第1轮切割后, 如果待分配列表中存在收益大于0的切割点, 则进行第2轮切割, 此时需要重新计算列表中所有频繁模式的切割收益, 例如取
以频繁项
下面以情形1为例, 探究如何计算
将参数
其中,
下面以成本模型HDD-I为例, 应用切割奖励更新函数
假设分区
对分区
因此, 切割后次分区各类查询的总切割收益为:
同理
分区
经过第1轮切割后, 在后续切割点的选择时, 需要重新计算频繁模式的收益, 根据公式(21)可知, 如果能根据切割后分区属性范围的缩小情况, 计算出关键参数
对某个频繁模式例如
第2轮切割
首先计算参数
然后依据公式(17)–公式(19), 计算参数
同理, 计算参数
最后计算参数
其中,
如果得到
将计算的所有参数包括
本节首先介绍数据集、实验环境及对比的基准算法, 然后在数据集上分析不同算法的性能差异由哪些因素引起, 最后从分区性能、执行时间两个指标对比不同分区算法的特点.
SCVP算法适用于各种类型的成本模型, 算法能够根据成本模型的设计得出适应不同环境的分区方案, 本节将以HDD-I作为成本模型. 下面介绍实验中使用的模型运行环境、数据库环境和数据导入方式.
(1) 模型运行环境: SCVP和SCVP-R基于Python实现, 不依赖于预训练模型和GPU, 引用Pandas、Numpy、Scikit-learn等常见的数据处理和机器学习包, 能够被打包成轻量级的Python库, 方便调用.
(2) 数据库环境: PostgresSQL 13.3 (Ubuntu 18.04).
(3) 数据导入方式: 为不同数据集建立独立的模式, 编写shell脚本根据预先定义好的表结构(DDL)和Insert语句, 建立原表, 并导入表数据, 同时, 将负载集中存放到Workload表.
本文在以下3个数据集上进行实验.
(1) TPC-H
TPC-H是决策支持的基准测试, 提供了22个复杂的查询, 共有customer、lineitem、nation、orders、part、partsupp、region、supplier这8张表. 本实验使用DBGEN产生了规模系数(scale factor, SF)为1的表数据, 每张表约含
(2) SSB (star schema benchmark)
和TPC-H类似, SSB也是一种基于现实商业应用的数据模型来模拟决策支持的基准测试, 包括1个事实表lineorder和4个维表customer、part、date、supplier, 以及13条标准SQL查询测试语句, 包括统计查询、多表关联、复杂条件、group by、order by等组合方式, 拆分到5个表的负载规模分别为13、7、6、13、10. 在实验中我们生成了规模系数SF为1的数据集.
(3) 随机数据集
为了测试算法在大规模负载下的性能表现, 额外增加了两组随机数据集, 数据集中每张表均含有
• randomAttr: 表的维度不同, 分别在属性数为30、50、100、200、500的关系表上生成1 000条查询.
• randomQue: 负载规模不同, 分别在50个属性的关系表上生成50、200、500、1 000、5 000个查询.
在随机数据集上进行实验时, 通常会设置多份数据集, 每份数据集包括randomAttr、randomQue两组数据, 取所有数据集的平均值作为最终的测试值. 下面介绍随机数据集的生成策略: 为了能够让算法划分尽可能多的列组, 对查询的随机生成制定如下规则.
• 设置具有明显特征的查询: 少部分查询作为高频查询, 其
• 获得较多的分区数: 将给定的属性范围划分为等分的4–6个区间, 并对每个区间适当延长, 使彼此有重叠部分, 如设置重叠比例为10%. 随机产生一个分布在[4, 6]的整数, 则下一个查询访问的属性范围需位于该整数对应的区间内.
• 查询的其他参数的生成策略:
模拟软件系统发送查询请求, 计划从workload表中, 依次读取对应测试数据集的查询, 并将读取时间作为查询到达时间, 待所有查询读取完毕, 向负载收集器发送分区信号, 执行分区操作.
本文选取了 10 个经典的垂直分区算法用于对比实验, 其中前 3个不基于成本模型生成垂直分区, 而后 7 个基于成本模型生成垂直分区. 基于成本模型的算法一般比不基于成本模型的算法效果要好.
• Pure_NSM: 将原表单独作为一个分区, 分区数为1.
• Pure_DSM: 每个属性都作为一个单独的分区, 分区数为属性数.
• Rodriguez[
• HillsClimb[
• HYF[
• NAVATHE[
• AutoPart[
• Trojan[
• O2P[
• Hyrise[
在基准数据集TPC-H、SSB上进行实验, 首先从HDD-I成本模型计算的磁盘I/O访问成本来比较各类算法的性能, 然后通过引入另外两个分区指标: 不必要数据的读比例和元组重建平均次数来测量各类算法的分区特性.
(1) 磁盘I/O访问成本
TPC-H数据集的算法性能比较 (cost model: HDD-I, benchmark: TPC-H)
TPC-H数据集各算法的平均I/O成本比较
算法 | Pure_NSM | Pure_DSM | HillsClimb | Rodriguez | HYF | SCVP/SCVP-R | O2P | AutoPart | Hyrise | Trojan | NAVATHE |
Avg. I/O (块) | 33700 | 8 645 | 19050 | 8 288 | 10311 | 8 179 | 8 109 | 8 171 | 10241 |
SSB数据集的算法性能比较(cost model: HDD-I, benchmark: SSB)
SSB数据集各算法的平均I/O成本比较
算法 | Pure_NSM | Pure_DSM | HillsClimb | Rodriguez | HYF | SCVP/SCVP-R | O2P | AutoPart | Hyrise | Trojan | NAVATHE |
Avg. I/O (块) | 19 568 | 6 884 | 6 880 | 5 568 | 5 536/
|
6 488 | 5 536 | 6 212 | 5 772 | 6 424 |
(2) 不必要数据的平均读比例
Agrawal等人[
其中,
本文使用不必要数据的平均读比例测量不同算法分区方案的特性, 分析该指标与算法性能的关系.
基准数据集上算法不必要数据的平均读比例比较
(3) 元组平均重建次数
分区数量越多, 元组重建的次数也会增多, 元组重建平均次数能很好地评判算法给出的优化方案中分区数量的大小, 计算公式如下:
本文主要探究不同算法的性能是否和分区数量有关系.
基准数据集中不同算法的元组平均重建次数比较
本小节将在randomAttr、randomQue两组随机数据集进行实验, 为了减少数据集的随机性对结果造成影响, 每次实验都对两组数据集随机生成5份, 取5次测试的平均值作为最终的指标值.
在randomAttr数据集中不同算法的平均性能比较(cost model: HDD-I, benchmark: randomAttr)
randomAttr数据集各算法的平均I/O成本比较
算法 | Pure_DSM | Rodriguez | HYF | HillsClimb | SCVP | SCVP-R | O2P | AutoPart |
Avg. I/O (块) | 451597 | 548223 | 417656 | 356447 | 364047 | 452418 | 434414 |
下面对性能接近的3种算法HillsClimb、SCVP和SCVP-R进一步比较, 通过对属性的维度进一步细化, 探究它们的性能和优化时间的差异.
randomAttr数据集扩大到8维时, 4种算法的平均性能比较
在randomAttr数据集中HillsClimb、SCVP和SCVP-R算法的平均优化时间比较
在randomAttr数据集中HillsClimb、SCVP和SCVP-R算法的平均优化时间(s)
算法 | 30 attr | 50 attr | 65 attr | 80 attr | 100 attr | 125 attr | 150 attr | 175 attr |
HillsClimb | 1.20 | 9.00 | 29.20 | 68.20 | 178.00 | 506.40 | 1106.80 | 2020.00 |
SCVP | 0.16 | 0.28 | 0.50 | 0.56 | 1.08 | 2.33 | 3.52 | 8.91 |
SCVP-R | 0.16 | 0.47 | 1.29 | 1.56 | 5.66 | 19.29 | 59.75 | 136.11 |
在randomQue数据集中不同算法的平均性能比较(cost model: HDD-I, benchmark: randomQue)
下面对性能最好的3类算法HillsClimb、SCVP和SCVP-R进一步比较, 通过对增加更多负载的规模, 探究它们的性能和优化时间的差异.
randomQue数据集各算法的平均I/O成本比较
算法 | Pure_DSM | Rodriguez | HYF | HillsClimb | SCVP | SCVP-R | O2P | Auto
|
Hyrise |
Avg. I/O (块) | 633362 | 766846 | 609598 | 564101 | 628358 | 619215 | 628365 |
randomQue数据集扩大到8种规模, 4种算法的平均性能比较
如
在randQue数据集中HillsClimb、SCVP和SCVP-R算法的平均优化时间比较
在randQue数据集中HillsClimb、SCVP和SCVP-R算法的平均优化时间(s)
算法 | 200 query | 500 query | 1 000 query | 1 500 query | 2 000 query | 3 000 query | 4 000 query | 5 000 query |
HillsClimb | 3.82 | 5.67 | 10.40 | 12.37 | 19.98 | 23.99 | 24.15 | 38.46 |
SCVP | 0.15 | 0.17 | 0.26 | 0.32 | 0.44 | 0.64 | 0.79 | 1.13 |
SCVP-R | 0.19 | 0.27 | 0.52 | 0.60 | 0.87 | 1.64 | 1.71 | 2.61 |
为了解决现有垂直分区算法应用于在线环境时, 存在执行时间过长、性能差等无法满足实时应用需求的难题, 本文提出一个基于谱聚类的在线垂直分区算法SCVP. 它首先通过增加约束条件缩小解空间, 然后对解空间设计算法进行精细的搜索. 为了进一步提升SCVP在高维属性下的性能, 进一步提出了SCVP的改进版本SCVP-R. SCVP-R通过引入同域竞争机制、双败淘汰机制和循环机制, 对SCVP在分区优化过程中的合并方案进行了优化. 在不同数据集上的实验结果表明, 相比于目前最好的垂直分区方法, SCVP和SCVP-R有着更快的执行时间和更好的性能表现. 目前SCVP基于传统机器学习方法, 未来将尝试使用图神经网络以及深度强化学习技术[
Grund M, Krüger J, Plattner H, Zeier A, Cudre-Mauroux P, Madden S. Hyrise: A main memory hybrid storage engine. Proc. of the VLDB Endowment, 2010, 4(2): 105–116.
Navathe S, Ceri S, Wiederhold G, Dou JL. Vertical partitioning algorithms for database design. ACM Trans. on Database Systems, 1984, 9(4): 680–710.
McCormick Jr WT, Schweitzer PJ, White TW. Problem decomposition and data reorganization by a clustering technique. Operations Research, 1972, 20(5): 993–1009.
Hoffer JA. An integer programming formulation of computer data base design problems. Information Sciences, 1976, 11(1): 29–48.
Cornell DW, Yu PS. An effective approach to vertical partitioning for physical design of relational databases. IEEE Trans. on Software Engineering, 1990, 16(2): 248–258.
Cheng CH, Lee WK, Wong KF. A genetic algorithm-based clustering approach for database partitioning. IEEE Trans. on Systems, Man, and Cybernetics, Part C (Applications and Reviews), 2002, 32(3): 215–230.
Song SK, Gorla N. A genetic algorithm for vertical fragmentation and access path selection. The Computer Journal, 2000, 43(1): 81–93.
Gorla N, Betty PWY. Vertical fragmentation in databases using data-mining technique. Int’l Journal of Data Warehousing and Mining (IJDWM), 2008, 4(3): 35–53.
Huang YF, Lai CJ. Integrating frequent pattern clustering and branch-and-bound approaches for data partitioning. Information Sciences, 2016, 328: 288–301.
Shukla S, Naganna S. A review on K-means data clustering approach. Int’l Journal of Information & Computation Technology, 2014, 4(17): 1847–1860.
Von Luxburg U. A tutorial on spectral clustering. Statistics and Computing, 2007, 17(4): 395–416.
Caliński T, Harabasz J. A dendrite method for cluster analysis. Communications in Statistics, 1974, 3(1): 1–27.
Han JW, Pei J, Yin YW, Mao RY. Mining frequent patterns without candidate generation: A frequent-pattern tree approach. Data Mining and Knowledge Discovery, 2004, 8(1): 53–87.
Son JH, Kim MH. An adaptable vertical partitioning method in distributed systems. Journal of Systems and Software, 2004, 73(3): 551–561.
Lewis FL, Vrabie D, Vamvoudakis KG. Reinforcement learning and feedback control: Using natural decision methods to design optimal adaptive controllers. IEEE Control Systems Magazine, 2012, 32(6): 76–105.