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

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

结果根据元组标记算法返回给各客户端.我们为表 2 中的查询构建一个全局查询计划,如图 4 所示.Q1、Q2、Q3
共享对用户表的选择运算,Q5 先与 Q6 共享对订单表和项目表的连接运算,然后再与 Q4 共享对用户表和订单表
的连接运算.Q6 与 Q5 共享之后,再与 Q7 共享排序运算.

Fig.4 Global query plan tree
图 4 全局查询计划树

GQP 的优点在于查询执行流程较为简单、易于扩展,使其能够很好地兼容各种多查询共享技术,因此大部
分多查询共享技术均基于该模式.适用场景一般为高并发下的 OLAP 查询,对于运算符的相似度、类型则没有
具体的限制.GQP 的缺点在于:(1) 查询往往需要等待,单个查询延迟高;(2) 生成全局查询计划开销较大.
经过多年的研究,GQP 执行模式也在不断的发展和完善,早期的 GQP 手动生成全局查询计划,当查询提交
进来时直接执行,计算后的结果通过标记的 queryId 返回,因此适用的场景非常有限.随着多查询共享技术的发
展,之后基于 GQP 的系统大多实现多查询路径搜索算法,使得多个查询可以动态地生成全局查询计划.目前,主
要的优化方向是更多地利用直接的共享机会,尽量缩短查询的等待时间以及多查询计划的搜索时间.类似的系
统 [21] 在内存中维护着一个全局查询计划,当有 query 提交时无需等待,直接将该 query 拆分为若干个算子,将该算
子与查询计划中存在的共享算子合并.若系统中不存在该算子的共享算子,则系统将会为该算子创建新的计划
树节点.
2.2 以运算符为中心的多查询原型系统

由于上述查询模式存在着不足,人们开始寻求一个共享机会更多且更易捕捉,同时能够避免复杂的多查询
计划路径搜索带来的额外开销的多查询执行架构.2005 年,Stavros [20] 奠定了以运算符为中心的多查询原型系统
OMP 的基础.
对于 OMP 系统来说,如果两个或多个并发查询在其查询计划中包含相同的关系运算符,并且该运算符对于
所有的查询来说都输出相同的元组(或元组的投影),则称这些运算符为“可共享运算符”.当查询运行时,系统动
态地利用这些共享运算符,每一个共享运算符将执行一次,并且其输出的数据将同时通过流水线管道传输到所
有父算子节点.该系统的查询执行流程如图 5 所示,不同的颜色代表不同的线程.
在该系统中,每个运算符都被提升为一个独立的微型引擎(Engine).系统输入的是一个个预编译的单查询
计划.查询计划通过 packet 分派器(该分派器会创建与查询树中的节点一样多的 packet)分配给相应的Engines,
每个Engine 都有一个 packet 请求队列.属于该Engine 的辅助线程从队列中取出 packet 并加以执行.Packet 里
包含输入和输出元组缓冲区位置以及关系运算符的参数(例如排序属性、谓词等).所有Engine 并行处理以评
[8]
估查询.评估模型类似于基于 push 式的执行设计 ,其中,每个运算符独立生成元组,直到填满父级缓冲区为止.
例如,排序Engine 仅接受对元组进行排序的请求.请求本身必须指定需要排序的内容以及需要将结果放入哪