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

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

个元组缓冲区.系统通过将一个Engine 的输出链接到另一个Engine 的输入来完成查询,从而在参与的Engine
之间建立生产者-消费者关系.

Fig.5 Query execution process based on OMP system
图 5 基于 OMP 系统的查询执行流程
查询 packet 表示查询在给定的Engine 上需要执行的工作.每当新的 packet 在Engine 中排队时,系统都会
扫描队列中的 packet,以检查是否有重叠的工作,即对每个 packet 编码参数列表(在查询通过 packet 分派器时产
生的)的快速检查.找到重叠的 packet 后,检查当前算子的哪个阶段可以重用.每个Engine 都采用不同的共享机
制,具体取决于算子的共享时机.Engine 包含 OMP 协调器和死锁检测器.OMP 协调器负责将新的 packet 与正
在执行或未执行的 packet 进行合并,并将输出的元组同时通过管道传递给所有参与的查询.OMP 协调器还可以
对原始查询的评估策略作一些必要的调整,如创建一个附加数据包来完成算子非重叠部分.死锁检测器则是确
保同时执行流水线的调度时实现无死锁.
OMP 的共享机会主要有以下 4 种.
(1) 线性重叠:表示可以始终能够利用正在进行的相同操作的未完成部分,其成本节省从 0 到 100%不等,
具体取决于 Q2 加入 Q1 的时间,对应的操作有文件扫描、索引扫描;
(2) 步骤重叠:只要尚未生成第 1 个输出元组,则可以完全相互利用的并发操作(节省 100%的成本),对应的
操作有嵌套循环连接、排序合并连接的合并阶段、hash 连接的探测阶段;
(3) 完全重叠:正在进行中的操作的整个生命周期内,始终可以节省 100%的成本.相应的扫描有排序、聚
合、排序合并 join 的排序阶段、hash 连接的构建阶段;
(4) 尖峰重叠:只有在同一时间开始才能重叠的操作.相应的操作有文件和索引的顺序扫描.
OMP 执行模式的好处在于它无需指定复杂的多查询计划,共享机会较多,可以充分利用查询之间重叠的计
算及数据,查询无需等待,到达的查询可以立即执行.适用的场景主要具有如下特征:高并发环境下,查询选择性