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

危剑豪 等:多查询共享技术研究综述 3193

方式将每个运算符放置并部署到物理执行计划中.在利用共享机会时,调度程序将优先利用“输入-运算符共享”
的机会,从而创建从共享顶点到两个顶点未共享的任何其他下游顶点的附加边来更新现有执行.当某个运算节
点需要参与其他共享节点时,则作业调度程序无需部署该节点.另一方面,具有“输入共享”的节点将与其对应的
共享节点部署在同一站点上,以减轻广域网络上的冗余数据传输.
4.3 小 结

在多查询系统中,数据的利用率与数据的共享性往往成正相关,这使得多查询缓存的管理相较单查询而言
更为复杂.此外,在大多数多查询系统中,数据通常以 push 的方式自底向上推入各个运算符,一方面增加了数据
之间的共享机会,但另一方面也导致较大的内存开销.因此,一个良好的多查询缓存策略还需考虑大量中间结果
所带来的内存消耗问题.
由于 OMP 的执行引擎比较特殊,如第 2 节所述,其执行引擎的内部由若干个-engine 组成,不同-engine 分
别执行不同的计算,相互之间通过 packet 传递数据.因此,多个-engine 之间保持良好的通信,相互之间协调地传
递数据,是 OMP 执行效率的关键.

5 多查询共享技术的应用

在多查询共享技术研究伊始,就有不少基于该技术的系统问世,这些系统基本上是用来解决数据仓库并发
查询激增而带来的资源争用问题,能够处理的共享运算符非常有限,也没有较好的方案生成多查询计划.随着多
查询优化技术的不断发展——多查询计划的优化方法日趋成熟,各种运算符的共享算法愈来愈完备,包括图数
据库、Map-Reduce、半结构化数据库等多个领域开始尝试应用多查询共享技术来解决查询并发的问题.本节将
梳理多查询共享技术在这些领域中的应用.
5.1 关系型数据库系统中的应用
5.1.1 OLAP 数据库中的多查询共享
在多查询共享技术的研究历史中,大部分技术都应用于处理 OLAP 负载的系统.2000 年,Chen 等人设计了
NiagaraCQ [11] ,一个连续查询处理引擎,旨在处理 Web 查询场景下数百万并发查询.NiagaraCQ 通过归纳 Web 查
询中的相似结构,对查询进行分组,将通用的计算放入内存中加以共享,从而极大地降低了 I/O 成本.此外,对选择
谓词进行分组,可以消除大量不必要的查询调用.NiagaraCQ 在之前的分组优化技术的基础上加以改进:首先,使
用具有动态重新分组功能的增量分组优化策略,新查询将添加到现有查询组中,而无需重新分组已安装的查询;
其次,使用查询拆分方案,该方案只需对通用查询引擎进行最少的更改;第三,NiagaraCQ 以统一的方式对基于更
改的查询和基于计时器的查询进行分组.为了确保 NiagaraCQ 具有可伸缩性,中文采用了其他技术,包括连续查
询的增量评估,同时使用 pull 模型和 push 模型来检测异构数据源的变化以及内存缓存.
实验结果表明:虽然 NiagaraCQ 的适用场景存在着局限性,不过对于高并发的 Web 查询场景,NiagaraCQ 的
吞吐量要明显优于同类系统.
2007 年,Zukowski 等人将协作扫描技术和多查询缓存管理技术应用到了数据仓库中,他们描述了一个“协
作扫描”框架 [23] ,该框架由传统的(索引)扫描运算符的协作变体(称为 CScan)和活动缓冲区管理器(ABM)组成:
CScan 声明所需要扫描的数据范围或聚集索引的范围,初始化后的 CScan 算子被放入 ABM 中;ABM 负责协调
多 CScan 算子的执行,以最大程度地提高 I/O 带宽重用,同时确保良好的查询延迟.Zukowski 等人的关注点在于
实现一个良好的算子调度策略,使平均查询成本最小化,同时使最大查询执行成本保持稳定(即确保对所有查询
的“公平”对待).
2009 年,Candea 等人设计了 CJoin 查询流水线模型 [22] ,可以有效地评估星型设计下的并发连接查询.CJoin
应用了共享扫描技术,优化了多查询连接算法,其执行流程如图 13 所示.
该模型专为星型查询所设计,星型查询模式如图 14 所示.F 为事实表,D 为维度表.CJoin 引擎采用“始终在
线”的单个物理计划,该查询将事实表 F 与维度表 D i 进行连接,最后以属性 B 分组并做聚合运算.在图 13 中,系