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

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

对于一个数据库管理系统来说,长期以来都是采取一次执行一个查询(one-query-at-a-time,以下称“单次查
[1]
询”) 的执行模式,即:系统在处理单次查询时,为该查询创建一个线程,各个查询线程之间互不影响.各查询从查
询编译、生成查询计划、检查缓存、执行查询计划到返回结果等各个步骤,均独立完成.当多个查询同时执行
时,各个物理计划之间会竞争相应的磁盘 I/O 访问资源和 CPU 计算资源,这导致尽管现代系统可以有效地优化
[2]
[3]
和执行单个复杂 OLAP(on line transaction processing) 或 OLTP(on line transaction processing) 查询,但当多个
[4]
复杂查询同时运行时,它们的性能将显著下降 .为了提高并发环境下的性能(其核心是提高资源利用率以减少
[5]
资源争用),解决方案通常包含 3 种:(1) 构建缓存池以共享部分数据 ,这种数据被动的共享模式往往存在缓存
命中率低的问题;(2) 利用不同查询之间访问数据重叠的特性构建物化视图 [6,7] ,物化视图利用了不同查询之间
的共性,但却潜在着大量维护视图成本的问题;(3) 针对相似的查询缓存查询结果和查询计划,这类方法适用的
场景较窄,可扩展性不高,仅适合于查询语句单一、查询结果变化较小的场景.
由于单查询模式的局限性,不同查询在执行过程中相互隔离,使得很多显而易见的优化机会无法实现 [4,8] .
并发查询往往会存在很多重复的算子,例如多个查询扫描同一个数据集、多个查询对同一个中间结果进行排序
等等.这些可以共同执行的机会在单查询模式下只能被冗余执行,导致系统的吞吐量降低.基于该瓶颈,很多学
者开始研究一次执行多个查询(multi-query-at-a-time,以下称为多查询)的模式.
 多查询共享技术的发展历史
早在 20 世纪 80 年代,就有团队开始研究多查询共享技术.早期的多查询共享技术主要集中于查询编译中
的查询重写阶段 [9,10] ,即对并发查询的公共子表达式进行检测与合并,从而减少多个查询之间的冗余计算.2000
年,Chen 提出了一种多查询计划的概念 [11] ,即在查询编译中的查询优化阶段将并发查询下的多个查询计划合并
为一个全局查询计划,查询引擎只需执行 1 次,该全局计划就能得到多个查询结果.陆续的研究表明,最优全局查
询计划问题为 NP-hard 问题 [12] .因此,之后对于多查询计划的研究主要集中在根据不同的场景设计启发式的全
局查询优化方案.到 2012 年,Giannikis 结合之前的研究,提出了一种通用的全局查询计划的生成方案 [12] .该方案
[4]
2
能够适应场景的变化,确保查询执行的时间复杂度为 O(n ).该方案在 SharedDB 上实现,能够为上千并发查询
生成全局查询计划,大大提高了系统的吞吐量.在查询优化阶段的另一个研究方向是对各运算符共享算法的优
化,该方向的研究贯穿整个多查询共享研究的历史,主要集中在常用且开销较大的运算符上,如顺序扫描 [12,13] 、
连接 [14,15] 、分组 [16] 、排序 [17,18] 等.多查询共享技术虽然能够显著提高系统的吞吐量,但其并非在任何场景下均
适用:首先,多个查询在共享某一运算符或中间结果时,往往会导致单个查询的响应时间受到影响;其次,文献
[19]中的研究结果表明,即便是在高并发且查询较为相似的所谓“高共享”场景下,多查询的吞吐量依然受到硬
件环境、查询选择性、查询的语义等因素的影响.
随着多查询共享研究工作的不断展开,支持多查询的数据库系统相继问世,包括 QPipe [20] 、Datapath [21] 、
[4]
CJoin [22] 、SharedDB 等.这些系统的实现不尽相同,对于各种并发环境的优化也是各有所长.随着这些系统的问
世,多查询共享技术的应用领域也逐渐拓宽.经过 30 多年的发展,多查询共享技术也从最开始应用于数据仓库
和连续查询系统 [11,2125] 拓展到了图数据库系统 [2629] 、以 GPU 计算的查询系统 [30,31] 、基于 Map-Reduce 计算框
架的批处理系统 [3237] 以及数据流分析查询系统 [3840] 等多个领域.本文根据查询的执行流程将多查询共享技术
分为两类,分别为查询编译阶段的多查询共享以及查询执行阶段的多查询共享,并对这两类技术的相关文献进
行了梳理与评价.本文还总结了两种经典的支持多查询共享的原型系统,并且分析了它们的优势与不足.
本文第 1 节介绍多查询共享的相关概念并对多查询共享技术的研究方向加以总结.第 2 节介绍两种支持多
查询的原型系统.第 3 节梳理查询编译阶段中的多查询共享技术.第 4 节梳理查询执行阶段中的多查询共享技
术.第 5 节梳理多查询共享技术在各个领域的应用.第 6 节进行总结和展望.

1 多查询共享描述
1.1 相关概念

通常,数据库处理一条查询语句包含查询编译和查询执行两个阶段.查询编译阶段又可分为查询分析、查