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

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

划的多查询执行模式,其性能稳定,可扩展性强,应用范围更广,依赖于良好的全局查询搜索算法;以运算符为中
心的多查询执行模式,其共享机会更多,但可扩展性、Engine 之间的调度还有待优化.
5.2 非关系型数据库系统中的应用
5.2.1 图数据库中的多查询共享
2012 年,Wang [26] 将多查询优化的场景搬入到 RDF/SPARQL 中,他们指出,SPARQL 的多查询优化是一个
NP-hard 问题.在总结了 SPARQL 查询的结构相似性,并考虑了 SPARQL 的独特属性之后,他们提出了一种启发
式多查询优化算法:将输入的查询分为若干组,以便可以一起优化每组查询.该优化的重要组成部分包括一个基
于查找常见子查询结构的算法以发现多个 SPARQL 查询的通用子结构,以及一个有效的成本模型来比较候选
执行计划.算法的基本思想是:(1) 将输入的查询划分为多个组,同一组中的查询更有可能通过查询重写而共享
公共子表达式;(2) 将每组中的类型 1 [66] 查询重写为其对应的具有成本效益的类型 2 [66] 查询;(3) 执行重写的查
询,并分发查询结果返回到原始输入查询.Wang 等人的实验结果显示,带有多查询共享的 SPARQL 查询系统要
比没有多查询共享的吞吐量高出 40%~75%.
2016 年,Ren [28] 指出,现有的子图同构搜索算法不能很好地支持多查询.在其论文中,他们介绍了 Tri-vertex
标签序列的概念,并提出了两个查询图之间的新颖分组因子,可用于有效滤除不共享的子图.文献[28]中还提出
了新型的图分区及构建该分区的启发式算法,在此基础上,Ren 等人设计了一种结构来将常见子图的查询结果
存储在内存中,从而共享这些结果.
2019 年,Guo [27] 指出,现有的基于 SPARQL 的查询优化方案存在诸多问题:首先,这些方法主要依靠子图同
构算法来检测常见的子查询,这增加了计算的复杂性,使得单个查询的响应时间大为增多;此外,由于数据集越
来越大,可伸缩性问题也变得越来越严重.Guo 等人构建了一种支持多查询优化的分布式 RDF [67] 引擎,该引擎使
用特征集来探测公共子表达式,并且沿用了文献[28]中的成本模型.
5.2.2 以 GPU 为计算核心的数据库中的多查询共享
2013 年,Wang 对具有复杂软件优化和硬件配置的数据库查询进行了全面研究,他们指出:在当前的 GPU 数
据库中,系统使用专用的优化器来处理每个单独的查询,并不支持在并发查询之间共享 GPU 资源.在开源 GPU
查询引擎 [31] 上运行 OLAP 负载并进行性能分析后,他们观察到,主要 GPU 资源的利用率仅为 25%.于是,该团队
在文献[30]中提出了一个原型系统,该系统可以在多个查询之间共享 GPU 资源.该系统主要依靠 GPU 查询调度
策略来实现多查询共享,该调度的实现策略类似全局查询计划.另外,Wang 等人还提出了一个衡量指标,通过该
指标可以量化 GPU 查询的资源需求,从而动态控制批处理查询的数量.实验结果表明:通过同时执行多个 GPU
查询,与专用处理相比,系统吞吐量最多可提高 55%.
5.2.3 Map-Reduce 中的多查询共享
2008 年,Parag 等人把共享查询的场景搬到了 Map-Reduce 中,他们在文献[34]中指出,现有的以短工作优先
的常规调度技术无法满足多任务工作负载的调度.对此,该团队专门针对如何共享工作负载提出了新的调度策
略.该调度策略是一种在线算法,每次执行者空闲时都会被调用,然后从输入队列中删除非空的作业子集,将其
打包为一个执行批处理,然后将该批处理提交给执行程序.策略仅有的共享时机是 Map 阶段多个作业对相同文
件的扫描操作,对到达作业的类型有着较高的要求.实验结果表明:该策略在处理共享率不高的工作负载时,性
能明显不如非共享的调度策略.
2010 年,Tomasz [33] 提出了一种针对 MR 的共享框架,名为 MRShare,该框架可以自动地在 MR 中进行工作共
享.他们总结了 MR 工作中的 3 种共享时机,分别是共享扫描、共享 Map 阶段的输出和共享 Map 阶段的计算.MR
的核心组件是 grouping layer,该组件使用基于 I/O 的代价模型,将批量工作负载作为输出,并根据 3 种共享时机
实现多查询的调度.值得一提的是,通过代价模型找出最佳计划的方法被证明为 NP-hard 问题.因此,文献[33]中
所提到的 grouping layer 在实现中降低了优化标准.实验结果表明:相对于传统的 MR 执行引擎,MRShare 的性能
无论从批处理的整体响应时间上,还是吞吐量上,都有了明显的提升.
2011 年,Wang [32] 提出了 Map-Reduce(MR)多任务调度方案,名为 CoScan,它消除了在 MR 计算环境中扫描大