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

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

相似且存在大量聚合排序(共享机会为完全重叠)的查询.
OMP 执行模式的缺点也是很明显的.
1) 一个Engine 执行完成后,会按照查询的数量将产生的结果发给父算子所在的Engine,这无疑会产生
大量的数据冗余.在极端情况下,数据的冗余是呈指数增长的.因此,该模型对内存的开销极大;
2) 数据需要在各个Engine 之间传递,会产生一定的延迟;
3) 由于某个Engine 接收数据的时间是不确定的,有可能导致各Engine 之间负载不均衡.
对该执行模式主要的优化包括:(1) 在查询编译时对表达式进行预处理,合并公共子表达式,以减少Engine
的负担;(2) 设计协调策略,使Engine 的负载更加均衡.

2.3 小 结
这两种原型系统的优点和缺点都很明显,也从另一方面说明,多查询共享并不适用于所有高并发场景.
2007 年,Johnson 发现:在硬件条件为 32 核 CPU、使用 QPipe [20] 作为查询引擎、运行共享机会较多的工作负载
时,并没有得到很好的吞吐量结果.进一步实验的结果表明:导致共享效率降低的原因有很多,如共享的时机、查
询的种类、硬件条件、查询选择性、负载的并行性等等.因此,目前大多数共享查询系统仅针对某些高并发场
景进行优化.

3 查询编译阶段中的多查询共享技术
多查询优化器的工作是:(1) 寻找共享计算的可能性,对每个运算符采用最优共享算法;(2) 利用优化器搜
索策略找到全局最优计划.以上两项任务都是至关重要的,但它们是正交的.换句话说,搜索策略的细节并不取
决于运算符共享算法的有效程度.本节梳理了近 30 年来主流的多查询共享优化技术.
3.1 多查询计划的表示方法
[9]
1982 年,Finkelstein 将查询用一种无向图来表示,名为查询图(query graph).查询图的实例如图 6 所示,与查
询树不同的是,该查询图的节点中存储了除连接关系以外的所有信息,包括所属关系、谓词、投影等信息,而连
接关系则用边来表示.这种用图来表示查询的方法有利于查询之间的合并,文献[9]中给出的共享策略为:将多个
相似的查询图合并为临时查询图,并为每个查询图产生一个快照.当不可预知的连续查询对数据库进行访问时,
可以先访问查询图,从而共享查询图所对应的快照中的数据.

USER USER
ITEM
COUNTRY=‘CHINA’ OR COUNTRY =‘CHINA’ ITEM I.CATEGORY=?
COUNTRY=‘USA’ OR AND I.AVAILABLE<? OR SORT:PRICE
USERNAME=? AGE >? AND AGE<? I.CATEGORY=?

RESULT ORDER RESULT
U.USER_ID=O.USER_ID STATUS=‘OK’ OR O.ITEM_ID=I.ITEM_ID
O.DATE>?

Fig.6 An example of query graph
图 6 查询图实例

随着研究的深入,图数据结构逐渐被用来表示多查询计划,查询引擎将多个公共运算符节点合并,从而生成
一个包含多个查询的图结构.2000 年,Prasan [42] 将查询用一种有向无环图来表示,名为 and-or DAG.该 DAG 的起
始节点表示关系,其他节点则表示运算符(包括扫描、选择、连接、排序等).而 2003 年,Nilesh [17] 提出的 plan-
DAG(如图 7 所示)则是对 and-or DAG 的改进.plan-DAG 的实线边表示数据以流水线的方式从一个节点(运算