Page 216 - 《软件学报》2021年第10期

3188 Journal of Software 软件学报 Vol.32, No.10, October 2021

而 Att={a 1 ,a 2 ,…,a m }=   s 为 S 中包含的所有属性的集合.Duy-Hung 构建了一个名为搜索 DAG 的有向无
i 1 i
环图 G=(V,E)来表示该多查询实例.V 是集合 S 再加上根节点 T 的集合,根节点(root node)为潜在的数据输入节
点,其他节点则称为终端节点(terminal node).从节点 u 到节点 v 的边 e=(u,v)E 表示分组查询的执行路径.该分
组多查询图的实例如图 10 所示.

Fig.10 An example of a search DAG
图 10 搜索 DAG 实例

该算法的基本思想如下.
 第 1 步是构建仅由终端节点和根节点组成的初步方案树.文献[49]中以终端节点的基数降序对终端节
点进行排序,在遍历终端节点的过程中,将它们添加到初步解决方案树 G中.添加所有终端节点后,系统
将更新节点 u 及其子节点中扫描/排序之间的关系.本质上,该过程可以找到 u 的子节点,并对相同的扫
描和排序算子进行预合并处理;
 第 2 步以该初步方案树为输入,从根节点自顶向下地递归寻找子节点的最优化方案,然后生成全局逻
辑查询计划,最后生成全局物理查询计划并执行.
Duy-Hung 的实验结果表明:与未优化的计划相比,该算法最多可将查询执行时间减少 34%.
2017 年,Sun [16] 提出了一种分批分组和共享中间结果的技术,类似思路也在文献[5052]中提及.该技术利用
分组查询中计算的重叠,从而达到中间结果的共享,以减少大数据做分组操作,I/O 开销过大的问题.设 R(A,B,C,
D),现对 A 和 D 的属性排序或分组,当属性 D 有序时,属性 A 部分有序,这时,若利用该结果对 A 属性进行排序或
者分组,则可以减少相当一部分计算.而在批处理分组设置中,不同的分组顺序可能出现更多的计算重叠.根据
分组键之间的不同关系,Sun 等人提出了 3 种不同的共享级别,分别是完全共享、部分共享和常规共享.为了最
小化 I/O 成本,他们将组顺序调度问题形式化为一个可以在 NP-hard 中证明的优化问题,然后提出一种启发式算
法——HEGOS(启发式分组调度)算法.该 HEGOS 算法的核心思想是:由于完全共享减少了后续任务的整个工
作量,因此他们可以尽可能地充分利用完全共享,然后以贪心的方法逐一安排其余类型的共享.Sun 等人并未在
真实的数据库系统下进行实验,而是编写程序模拟了数据库分组计算的过程.因此,他们所提出的算法是否能适
用于真实的系统环境还有待商榷.
2018 年,Makreshanski 等人 [15] 提出了一种针对哈希连接运算符的共享算法,名为 MQJoin.该算法的思路大
致如下:首先将关于左表的 where 子语句筛选出来设为组 A,再将剩下的右表的 where 子语句设为组 B,分别对左
右两表进行扫描,过滤出满足条件 A 和 B 的左右表元组集合;然后对两组元组集合进行哈希连接.该算法为每个
中间结果添加长度为查询数量的位图向量,用来识别每个元组所对应的查询.该算法的缺点在于每个中间结果
均包含一个冗余的位图向量,该向量的大小与查询数量成正比,性能往往受 CPU 高速缓存大小的限制.为了提升
算法的连接效率,Makreshanski 等人采用 12 核 AMD Opteron 6174 ‘Magny-Cours’处理器,使得带有位图向量的
元组可以一次性读入 CPU 缓存中以增加连接探测的效率.他们在 Crescando 上实现了 MQJoin,对于基于 TPC-
H [53] 的工作负载,该系统的吞吐量要比 Vectorwise [54] 高出 2~5 倍,并且,相应时间也更稳定.
3.4 多查询优化
1988 年,Timos [55] 提出了识别正在运行的查询集中的常见子表达式,生成有效的多查询执行计划.他的关注
点在于构建最佳的访问路径 [56] ,文献[55]提出了两种多查询访问路径的优化方案.