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

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

理、执行模块之间的调度;(3) 不同类型数据库系统中的多查询共享技术.
(1) 两种原型系统
a) 基于全局查询计划的多查询原型(GQP)系统:GQP 系统应用广泛,大部分支持多查询共享的系统均采
用该系统的设计模式.GQP 系统将来自多个客户端的多个查询解析树进行合并,之后生成全局查询计
划,最后执行该全局计划并返回结果给相应的客户端.该系统的共享时机是在生成全局查询计划时产
生的;
b) 以运算符为中心的多查询原型系统(OMP):针对 GQP 设计上的不足,文献[20]设计了 OMP,该系统以运
算符(算子)为中心,在查询解析与转换时与 GQP 类似,之后生成的解析树通过包分派器(packet
dispatcher)将查询拆分为不同的运算符,并发送给若干个执行器,每个执行器执行特定的运算符,生成
的结果发送给其他执行器或返回给用户.该系统的共享时机是在执行器执行相同或相似运算符时产
生的.
(2) 查询编译阶段的多查询共享技术
a) 多查询计划的表示方法:该技术主要为 GQP 模式的系统提供全局查询计划.在 GQP 模式下,当查询语
句进入查询分析和重写阶段时,查询引擎会对多个查询语句解析,通过词法分析和语义分析生成多查
[9]
询计划图 .在该阶段,主要研究内容是设计有效的数据结构将多查询计划抽象出来.目前,主流的多
查询计划表示方式是基于图的数据结构.一个良好的多查询抽象方法,一方面要清楚地表示出查询中
共享的算子,另一方面还要能够适应查询数量和种类的变化;
b) 多查询表达式合并:该研究主要是根据特定的规则,在不同的场景下,通过签名、哈希等技术快速识别
多个查询的公共表达式,并将其合并 [11] .如上节所述,GQP 和 OMP 模式均包含合并模块(merger),因此,
多数多查询表达式合并的研究均适用于以上两种模式;
c) 多查询共享算法:该阶段为最优查询计划树中的每个运算符节点选择最佳多查询算法,将逻辑多查询
计划翻译为物理多查询计划.主要的研究内容即为各个运算符(扫描、选择、连接、排序、分组等)
设计共享查询算法.扫描和选择运算符逻辑较为简单,共享算法较为单一.连接和排序等运算符逻辑
较为复杂,算法种类繁多,兼之其具有使用频繁、开销较大等特点,因此更多的文献集中于研究这些运
算符的共享算法.由于 GQP 和 OMP 两种模式的算子存在差异,因此一种算法往往只能适应一种执行
模式;
d) 多查询优化:与单查询优化相似,多查询优化的目的是为了产生多查询计划.早期的多查询共享系统
通常在查询重写之后跳过最佳查询路径搜索阶段,直接将逻辑查询计划转化为物理查询计划,这导致
了大量运算符和中间结果无法共享.2000 年之后,基于成本的启发式多查询优化在一些场景下取得成
功 [11,42] ,吸引了更多学者从事关于多查询路径搜索的研究.良好的多查询计划方案通常包括以下几
点:一是多查询计划的代价模型,该模型必须准确地估计出多查询计划的开销并具有较强的健壮性;
其二是多查询计划的生成算法,该算法利用上述代价模型,快速地选出一个多查询计划,同时保证查
询计划的高效性.近年来,多查询共享技术被广泛应用到图查询引擎、MapReduce 执行引擎等多种领
域,几乎所有的文章中都会提到多查询计划的优化方案.目前,大多数的多查询优化方案都是基于
GQP 模式,而针对 OMP 的查询优化研究得较少,主要是受执行模式所限:由于 GQP 模式存在优化器
(optimizer)模块,因此相关研究可以很好地在该模块中进行;而 OMP 在查询合并之后就立即进入执行
阶段,因此该模式不存在传统意义上的查询优化阶段.
(3) 查询执行阶段的多查询共享优化
a) 多查询缓存管理:在查询执行的过程中,由于多查询的运算符一次处理的元组要比单查询要多出许
多,这就需要消耗更多的内存.也有不少文献研究多查询的缓存管理技术,旨在提高查询中间结果的
利用率;
b) 多查询执行模块之间的调度:该研究方向大多基于 OMP 系统.该系统的执行模块由若干个运算符执