传统的数据库系统围绕单次查询的模型构建,独立地执行并发查询.由于该模型的限制,传统数据库无法一次对多个查询进行优化.多查询共享技术旨在共享查询之间的公共部分,从而达到提高系统整体响应时间和吞吐量的目的.将多查询执行模式分为两类,介绍了各自的原型系统——基于全局查询计划的多查询原型系统和以运算符为中心的多查询原型系统,并且讨论了两种系统的优势以及所适用场景.在之后的内容中,将多查询共享技术按照查询的各个阶段分为查询编译阶段中的多查询共享技术以及查询执行阶段中的多查询共享技术两大类.以这两个方向为线索,梳理了多查询计划的表示方法、多查询表达式合并、多查询共享算法、多查询优化等各种方向的研究成果.在此基础上,还介绍了共享查询技术在关系数据库和非关系数据库中的应用.最后,分析了共享查询技术面临的机遇和挑战.
Traditional database systems are built around a model of query-at-a-time, and concurrent queries in the context are executed independently. Due to the limitations of this model, traditional databases cannot optimize multiple queries at a time. Multi-query sharing technology is designed to share the common part between queries to improve the overall response time and throughput of the system. This study divides the multi-query execution mode into two categories and introduces their respective prototype systems: the multi-query prototype system based on the global query plan and on demand simultaneous pipelining. Also, the advantages of the two systems and the applicable scenarios are discussed. In the following content, the multi-query sharing technology is divided into multiple query sharing technologies in the query compilation phase and query execution phase according to the various stages of the query. There are two major types of multi-query sharing technologies. Taking these two directions as clues, the research results in various directions such as the multi-query plan representation method, multi-query expression combination, multi-query sharing algorithm, and multi-query optimization are reviewed here. On this basis, the applications of shared query technology in relational database and non-relational database are also introduced. Finally, it analyzes the opportunities and challenges faced by shared query technology.
对于一个数据库管理系统来说, 长期以来都是采取一次执行一个查询(one-query-at-a-time, 以下称“单次查询”)[
由于单查询模式的局限性, 不同查询在执行过程中相互隔离, 使得很多显而易见的优化机会无法实现[
● 多查询共享技术的发展历史
早在20世纪80年代, 就有团队开始研究多查询共享技术.早期的多查询共享技术主要集中于查询编译中的查询重写阶段[
随着多查询共享研究工作的不断展开, 支持多查询的数据库系统相继问世, 包括QPipe[
本文第1节介绍多查询共享的相关概念并对多查询共享技术的研究方向加以总结.第2节介绍两种支持多查询的原型系统.第3节梳理查询编译阶段中的多查询共享技术.第4节梳理查询执行阶段中的多查询共享技术.第5节梳理多查询共享技术在各个领域的应用.第6节进行总结和展望.
通常, 数据库处理一条查询语句包含查询编译和查询执行两个阶段.查询编译阶段又可分为查询分析、查询重写、查询优化这3个步骤, 最终生成物理查询计划.查询执行阶段则是执行查询编译生成的物理查询计划.我们以关系数据库为例, 关系数据库引擎[
关系数据库引擎下的查询执行流程
Query execution process of relational database engine
数据库中的并发通常是指当前时刻正在执行的工作单元, 比如当前时刻正在执行10个查询, 则并发量为10.并发是数据库系统中非常重要的属性, 是最通用的负载定义.吞吐量即单位时间能够处理的查询数量.响应时间即查询的处理时间与等待时间之和.并发的高低直接影响了一个数据库系统的吞吐量和平均响应时间.随着系统并发量的提升, 吞吐量和平均响应时间均逐渐增加而达到瓶颈.传统数据库由于受限于单次查询的执行模式, 其性能受到并发的严重制约.而本文所提到的多查询的执行模式, 旨在减少高并发对数据库系统所带来的负面影响.
为了后文讨论方便, 我们将数据库系统中的查询语句称为查询表达式, 查询表达式中的一部分被称为子表达式, 被多个查询表达式所共有的查询表达式称为公共查询子表达式.查询语句的树结构表达方式称为查询树, 又称为查询计划树.在查询优化阶段, 通过查询搜索算法找出的代价最小的查询计划树称为最优查询路径.将最优查询路径中的节点替换为物理运算符后, 生成的查询计划树即为物理查询计划.
多查询共享是指多个并发查询在查询执行的各个阶段, 合并相似的子表达式, 共用相同的查询计划, 共享相同的访问数据或者相同的计算过程.通常, 查询共享、共享查询、多查询优化在无特别说明的情况下都指的是多查询共享.从计算机程序的角度来说, 多查询共享是指多个查询或者多个查询的子表达式在一个线程执行, 这与“单次查询”有着本质的不同.
接下来描述一个多查询共享实例, 3个常见关系分别是用户(user)、订单(order)、产品(item)表示, 见
常见的用户-订单-产品的关系
Relation of user, order and product
关系 | 属性 |
用户(user) | 用户编号(user_id), 名字(username), 年龄(age), 国籍(country) |
订单(order) | 订单编号(order_id), 产品编号(item_id), 用户编号(user_id), 状态(status), 交易日期(date) |
产品(item) | 产品编号(item_id), 库存(available), 价格(price), 类别(category) |
常见的7个查询
Seven ordinary queries
查询 | 语句 |
Q1 | SELECT COUNTRY, COUNT(*) FROM |
Q2 | SELECT USERNAME, COUNTRY FROM USERS |
Q3 | SELECT USERNAME FROM USERS WHERE |
Q4 | SELECT * FROM USERS U, ORDERS O WHERE |
Q5 | SELECT * FROM USERS U, ORDERS O, ITEMS I WHERE |
Q6 | SELECT * FROM ORDERS O, ITEMS I WHERE |
Q7 | SELECT * FROM ITEMS I WHERE I.CATEGORY=? ORDER BY I.PRICE; |
Q1、Q2、Q3的多查询计划树
A multiple query plan tree for Q1, Q2, Q3
目前, 所有关于多查询共享的研究都围绕着两种原型系统展开, 即基于全局查询计划的多查询原型系统(multi-query prototype system based on global query plan, 简称GQP系统)和以运算符为中心的多查询原型系统(operator-centric multi-query prototype system, 简称OMP系统), 我们将在下一节对它们进行详细的描述.基于这两种多查询系统架构, 研究内容主要可以分为: (1) 查询编译阶段的多查询共享技术, 包括多查询计划的表示方法、合并规则、路径搜索以及运算符的共享算法等研究内容; (2) 查询执行阶段中的共享查询技术, 包括缓存管理、执行模块之间的调度; (3) 不同类型数据库系统中的多查询共享技术.
(1) 两种原型系统
a) 基于全局查询计划的多查询原型(GQP)系统: GQP系统应用广泛, 大部分支持多查询共享的系统均采用该系统的设计模式.GQP系统将来自多个客户端的多个查询解析树进行合并, 之后生成全局查询计划, 最后执行该全局计划并返回结果给相应的客户端.该系统的共享时机是在生成全局查询计划时产生的;
b) 以运算符为中心的多查询原型系统(OMP): 针对GQP设计上的不足, 文献[
(2) 查询编译阶段的多查询共享技术
a) 多查询计划的表示方法: 该技术主要为GQP模式的系统提供全局查询计划.在GQP模式下, 当查询语句进入查询分析和重写阶段时, 查询引擎会对多个查询语句解析, 通过词法分析和语义分析生成多查询计划图[
b) 多查询表达式合并: 该研究主要是根据特定的规则, 在不同的场景下, 通过签名、哈希等技术快速识别多个查询的公共表达式, 并将其合并[
c) 多查询共享算法: 该阶段为最优查询计划树中的每个运算符节点选择最佳多查询算法, 将逻辑多查询计划翻译为物理多查询计划.主要的研究内容即为各个运算符(扫描、选择、连接、排序、分组等)设计共享查询算法.扫描和选择运算符逻辑较为简单, 共享算法较为单一.连接和排序等运算符逻辑较为复杂, 算法种类繁多, 兼之其具有使用频繁、开销较大等特点, 因此更多的文献集中于研究这些运算符的共享算法.由于GQP和OMP两种模式的算子存在差异, 因此一种算法往往只能适应一种执行模式;
d) 多查询优化: 与单查询优化相似, 多查询优化的目的是为了产生多查询计划.早期的多查询共享系统通常在查询重写之后跳过最佳查询路径搜索阶段, 直接将逻辑查询计划转化为物理查询计划, 这导致了大量运算符和中间结果无法共享.2000年之后, 基于成本的启发式多查询优化在一些场景下取得成功[
(3) 查询执行阶段的多查询共享优化
a) 多查询缓存管理: 在查询执行的过程中, 由于多查询的运算符一次处理的元组要比单查询要多出许多, 这就需要消耗更多的内存.也有不少文献研究多查询的缓存管理技术, 旨在提高查询中间结果的利用率;
b) 多查询执行模块之间的调度: 该研究方向大多基于OMP系统.该系统的执行模块由若干个运算符执行器构成, 数据在各执行器之间相互传递, 这就需要良好的调度机制以使得各执行器之间能够合理地分配资源, 减少阻塞, 保证程序的正常运行.因此, 也有相关文章对该方向进行了探讨.
(4) 多查询共享技术的应用
目前, 多查询共享技术应用较多的领域有数据仓库、连续查询、MapReduce[
在关系数据模型之下, 几乎所有的多查询共享技术都围绕着以下两种原型系统进行设计.在本节中, 我们将详细介绍这两种原型系统的架构以及它们各自的优缺点.
基于全局查询计划的多查询原型系统GQP目前较为主流, 大部分支持多查询共享的系统均采用该原型系统的设计模式, 例如早期的CScan[
GQP的核心思想如下: 首先, 将多个并发查询根据表达式合并规则进行合并, 生成多查询解析树; 之后, 通过多查询优化生成全局查询计划; 最后执行该全局查询计划, 并将结果返回给相应的客户端.该系统的查询执行流程如
基于GQP系统的查询执行流程
Query execution process based on GQP system
在该系统中, 多个查询语句首先在查询分析和重写阶段进行公共子表达式的合并, 生成一个全局查询计划图, 在查询路径选择过程生成一个最优或次优全局查询计划图.查询执行器执行该计划中的每个运算符.生成的结果根据元组标记算法返回给各客户端.我们为
全局查询计划树
Global query plan tree
GQP的优点在于查询执行流程较为简单、易于扩展, 使其能够很好地兼容各种多查询共享技术, 因此大部分多查询共享技术均基于该模式.适用场景一般为高并发下的OLAP查询, 对于运算符的相似度、类型则没有具体的限制.GQP的缺点在于: (1) 查询往往需要等待, 单个查询延迟高; (2) 生成全局查询计划开销较大.
经过多年的研究, GQP执行模式也在不断的发展和完善, 早期的GQP手动生成全局查询计划, 当查询提交进来时直接执行, 计算后的结果通过标记的queryId返回, 因此适用的场景非常有限.随着多查询共享技术的发展, 之后基于GQP的系统大多实现多查询路径搜索算法, 使得多个查询可以动态地生成全局查询计划.目前, 主要的优化方向是更多地利用直接的共享机会, 尽量缩短查询的等待时间以及多查询计划的搜索时间.类似的系统[
由于上述查询模式存在着不足, 人们开始寻求一个共享机会更多且更易捕捉, 同时能够避免复杂的多查询计划路径搜索带来的额外开销的多查询执行架构.2005年, Stavros[
对于OMP系统来说, 如果两个或多个并发查询在其查询计划中包含相同的关系运算符, 并且该运算符对于所有的查询来说都输出相同的元组(或元组的投影), 则称这些运算符为“可共享运算符”.当查询运行时, 系统动态地利用这些共享运算符, 每一个共享运算符将执行一次, 并且其输出的数据将同时通过流水线管道传输到所有父算子节点.该系统的查询执行流程如
基于OMP系统的查询执行流程
Query execution process based on OMP system
在该系统中, 每个运算符都被提升为一个独立的微型引擎(μEngine).系统输入的是一个个预编译的单查询计划.查询计划通过packet分派器(该分派器会创建与查询树中的节点一样多的packet)分配给相应的μEngines, 每个μEngine都有一个packet请求队列.属于该μEngine的辅助线程从队列中取出packet并加以执行.Packet里包含输入和输出元组缓冲区位置以及关系运算符的参数(例如排序属性、谓词等).所有μEngine并行处理以评估查询.评估模型类似于基于push式的执行设计[
查询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执行模式的好处在于它无需指定复杂的多查询计划, 共享机会较多, 可以充分利用查询之间重叠的计算及数据, 查询无需等待, 到达的查询可以立即执行.适用的场景主要具有如下特征: 高并发环境下, 查询选择性相似且存在大量聚合排序(共享机会为完全重叠)的查询.
OMP执行模式的缺点也是很明显的.
1) 一个μEngine执行完成后, 会按照查询的数量将产生的结果发给父算子所在的μEngine, 这无疑会产生大量的数据冗余.在极端情况下, 数据的冗余是呈指数增长的.因此, 该模型对内存的开销极大;
2) 数据需要在各个μEngine之间传递, 会产生一定的延迟;
3) 由于某个μEngine接收数据的时间是不确定的, 有可能导致各μEngine之间负载不均衡.
对该执行模式主要的优化包括: (1) 在查询编译时对表达式进行预处理, 合并公共子表达式, 以减少μEngine的负担; (2) 设计协调策略, 使μEngine的负载更加均衡.
这两种原型系统的优点和缺点都很明显, 也从另一方面说明, 多查询共享并不适用于所有高并发场景. 2007年, Johnson发现: 在硬件条件为32核CPU、使用QPipe[
多查询优化器的工作是: (1) 寻找共享计算的可能性, 对每个运算符采用最优共享算法; (2) 利用优化器搜索策略找到全局最优计划.以上两项任务都是至关重要的, 但它们是正交的.换句话说, 搜索策略的细节并不取决于运算符共享算法的有效程度.本节梳理了近30年来主流的多查询共享优化技术.
1982年, Finkelstein[
查询图实例
An example of query graph
随着研究的深入, 图数据结构逐渐被用来表示多查询计划, 查询引擎将多个公共运算符节点合并, 从而生成一个包含多个查询的图结构.2000年, Prasan[
plan-DAG实例
An example of plan-DAG
2000年, Chen提出了通过签名(signature)将多个查询表达式进行合并的技术.在其论文[
Q2的签名
Signature of Q2
Q1、Q2、Q3的签名组
Signature groups of Q1, Q2, Q3
常量 | 查询id |
|
Q1 |
|
Q2 |
|
Q3 |
2007年, Zhou提出了一种表签名技术[
2012年, Silva也提出了类似识别公共子表达式的技术[
(1) 如果
(2) 否则:
在该定义中, ⊕是XOR操作;
2018年, Jindal对公共子表达式的选择问题进行了基于整数线性规划(integer linear programming)的定义, 并将该问题抽象为二分图标记(bipartite graph labeling)问题[
2018年, Jonathan[
运算符的共享计算也是多查询共享技术研究的另一大方向, 主要的研究内容即针对各个运算符设计共享算法, 如选择、连接、排序以及分组等.选择运算符的多查询共享算法主要分为两种: (1) 在查询编译阶段, 将多个查询的谓词表达式合并, 在扫描一条元组的同时, 进行多个查询谓词的评估, 最后根据查询识别算法[
2004年, Krishnamurthy等人[
2007年, Zukowski等人[
2013年, Alonso[
多查询索引
An index of multiple query
2016年, Duy-Hung[
而
搜索DAG实例
An example of a search DAG
该算法的基本思想如下.
● 第1步是构建仅由终端节点和根节点组成的初步方案树.文献[
● 第2步以该初步方案树为输入, 从根节点自顶向下地递归寻找子节点的最优化方案, 然后生成全局逻辑查询计划, 最后生成全局物理查询计划并执行.
Duy-Hung的实验结果表明: 与未优化的计划相比, 该算法最多可将查询执行时间减少34%.
2017年, Sun[
2018年, Makreshanski等人[
1988年, Timos[
● 一种是基于计划合并的方法, 主要思路是: 为每个查询生成最佳访问计划, 并将这些计划合并为一个多查询访问路径.但这种方式并不适用于多连接的OLAP负载, 因为当单个查询确定了连接的顺序之后, 查询之间因为连接结果的不一致会导致无法共享;
● 第2种更为复杂的方法是基于全局优化器, 在该方案中, Timos等人将优化问题表述为状态空间搜索问题, 并针对该问题提出了一种算法.但该算法的时间复杂度较高, 导致生成多查询计划的时间远远超过单查询计划.
类似的策略还包括文献[
2000年, Chen[
2000年, Prasan在其文章中首次证明了启发式的多查询优化是切实可行的, 并且具有明显的优势.他提出了3种基于成本的启发式算法: Volcano-SH、Volcano-RU以及贪心启发式算法.这3种算法均基于AND-OR DAG[
2003年, Nilesh[
2007年, Zhou设计了一个实用、统一且具有扩展性的探测和利用相似子表达式的方案[
2012年, Silva[
实现多查询共享技术的SCOPE查询处理流程
SCOPE query processing flow to implement multiple query sharing technology
1) 识别公共子表达式: 系统事先将所有的子表达式分类, 并对其进行hash, 结果映射为一张hash表, 新来的query被拆分为多个子表达式, 而公共子表达式可根据hash表进行快速识别, 并分为若干共享组;
2) 记录物理性质: 常规优化器被扩展, 从而记录步骤1中被标识的物理属性.作为共享子表达式组的根节点, 各个查询物理属性存储在一个链表中;
3) 传播有关共享组的信息并标识最小公共祖先组(LCA): 在步骤4开始重新优化之前, 立即执行这一步骤.有关共享组的信息从上至下从共享组传播到根.该过程还为每个共享的子表达式
4) 重新优化执行物理属性的查询: 这是添加新阶段以利用常见子表达式重新优化脚本.该步骤重新优化了在共享组中强制执行物理属性的查询.当优化器处理不是LCA的组
2014年, Georgios[
2018年, Michiardi[
● 首先, 通过修改哈希树以快速识别常用子图, 并枚举可行的常用表达式的算法, 对查询表达式进行合并;
● 然后, Michiardi等人将多查询优化问题转换为多选背包问题: 每个可行的逻辑共享查询计划都与一个值(查询之间可以共享多少工作量)和一个权重(内存压力)相关联, 确保通过缓存公用数据来确定, 并且目标是最佳填充给定容量(内存限制)的背包.
总体而言, 该多查询执行流程与GQP系统的执行流程是一致的, 该方案能将多查询优化问题转换为多选背包问题是其一大亮点, 但影响多查询效率的因素不仅仅与Michiardi等人所提到的两个自变量相关(查询之间可共享的工作以及内存压力).所以, 该方案的可扩展性值得进一步加以研究和实验.
2018年, Jonathan设计出一种用于分布式数据流分析查询系统的多查询算法[
2019年, Karimov[
基于多查询计划的优化研究种类繁多, 像多查询计划的抽象模型、子表达式合并规则、中间结果的数据模型、适应新型存储结构的多查询调度以及多查询计划搜索算法等都囊括在内.目前的研究主要集中在设计出适应性更强的多查询调度策略(这些策略大多是启发式的), 即: 为不断变化的负载动态地生成全局查询计划, 最大化地利用查询之间的共享机会, 并保证单查询的响应时间.
多查询共享算法的性能往往依赖于多查询优化器对查询的调度, 若不能把握住稍纵即逝的共享机会, 那么再优秀的算法也会因错过共享时机而无法得以发挥.很多的共享算法研究往往不考虑多查询优化过程, 而只是研究运算符之间如何进行共享, 这就导致所研究的内容与实际应用互相脱离, 上述提到的方法中的实验结果固然好看, 但无法兼容到现有的多查询引擎中.因此, 虽然目前关于排序和分组的多查询共享算法的研究论文最多, 但在实际的多查询系统中, 往往只应用了针对选择和连接运算符的共享算法.
1982年, Finkelstein提出了热点多查询标记算法[
2001年, Kian-Lee[
另外, 他们还提出了两种基于COD框架的缓存策略, 即Conform-COD和Scramble-COD.
2007年, Christian[
扫描组实例
An example of scan group
2008年, Qiao等人[
2005年, Stavros[
2009年, Candea等人设计了CJoin查询流水线模型[
2018年, Jonathan为流分析查询系统专门设计了作业调度模式[
在多查询系统中, 数据的利用率与数据的共享性往往成正相关, 这使得多查询缓存的管理相较单查询而言更为复杂.此外, 在大多数多查询系统中, 数据通常以push的方式自底向上推入各个运算符, 一方面增加了数据之间的共享机会, 但另一方面也导致较大的内存开销.因此, 一个良好的多查询缓存策略还需考虑大量中间结果所带来的内存消耗问题.
由于OMP的执行引擎比较特殊, 如第2节所述, 其执行引擎的内部由若干个μ-engine组成, 不同μ-engine分别执行不同的计算, 相互之间通过packet传递数据.因此, 多个μ-engine之间保持良好的通信, 相互之间协调地传递数据, 是OMP执行效率的关键.
在多查询共享技术研究伊始, 就有不少基于该技术的系统问世, 这些系统基本上是用来解决数据仓库并发查询激增而带来的资源争用问题, 能够处理的共享运算符非常有限, 也没有较好的方案生成多查询计划.随着多查询优化技术的不断发展——多查询计划的优化方法日趋成熟, 各种运算符的共享算法愈来愈完备, 包括图数据库、Map-Reduce、半结构化数据库等多个领域开始尝试应用多查询共享技术来解决查询并发的问题.本节将梳理多查询共享技术在这些领域中的应用.
在多查询共享技术的研究历史中, 大部分技术都应用于处理OLAP负载的系统.2000年, Chen等人设计了NiagaraCQ[
实验结果表明: 虽然NiagaraCQ的适用场景存在着局限性, 不过对于高并发的Web查询场景, NiagaraCQ的吞吐量要明显优于同类系统.
2007年, Zukowski等人将协作扫描技术和多查询缓存管理技术应用到了数据仓库中, 他们描述了一个“协作扫描”框架[
2009年, Candea等人设计了CJoin查询流水线模型[
Cjoin查询流水线模型
Cjoin pipeline
该模型专为星型查询所设计, 星型查询模式如
星型查询模式
Star query mode
2010年, Subi利用各种多查询共享技术, 设计了一个以数据为中心的多查询原型数据库系统, 名为Datapath[
Datapath主要围绕两个问题进行研究: 路径网络和调度策略.Subi等人设计的显示调度策略如下: 调度程序为单线程, 主要对work queue进行操作.当I/O子系统或waypoint产生一个块时, 该块和任何相关的元数据将被放入work queue中.调度程序不断监视work queue中块的进出.从work queue中提取块时, 调度程序有两个选项:
(1) 系统可能没有足够的CPU资源来处理该块, 因此必须丢弃该块; (2) 调度程序可以将块提供给相关的waypoint.waypoint本身在调度程序的线程上运行, 并像调度程序一样, 它们实际上不执行任何数据处理.取而代之的是: 一个waypoint将数据块打包到一个工作单元中, 该工作单元既包含数据块, 也需要处理该数据块所需的任何其他状态信息, 包括代码和元数据.工作单元构造完成后, 调度程序将工作单元发送到工作线程, 由该线程执行工作单元.调度程序通常为每个CPU内核维护一个工作线程.Subi等人设计的路径网络优化策略如下: 路径网络优化器类似于传统的基于成本的查询优化器; 系统将现有的路径网络作为输入, 然后以数据移动代价尽可能小的方式将新查询应用到路径网络中; 他们将路径网络优化视为基于成本的搜索问题, 对于一个
到目前为止, Datapath的研究进展并不是很乐观, 最大的原因是: 当查询并发量非常大时, waypoint的管理和维护成本也变得非常高, 新来的查询往往无法与原本的waypoint进行合并, 从而达不到共享的效果.对此, sharedDB在该方面进行了妥协, sharedDB不允许在查询执行时将新来的运算符加入到查询计划中, 在最初的设计中, sharedDB甚至手动生成全局查询计划以处理已知的工作负载; 在之后的研究中, 多查询路径搜索技术[
此外, 该团队还专门为支持列存储的sharedDB版本[
2012年, Silva[
2018年, Jonathan将共享查询技术运用到分布式流分析查询系统中[
2019年, Karimov[
OLTP[
多查询共享技术被广泛地应用于基于关系模式的数据库系统中, 其中不乏sharedDB、Qpipe、Cjoin、DataPath等经典多查询系统.目前, 几乎所有的系统都遵循第3.1节中所描述的两种查询模式: 基于全局查询计划的多查询执行模式, 其性能稳定, 可扩展性强, 应用范围更广, 依赖于良好的全局查询搜索算法; 以运算符为中心的多查询执行模式, 其共享机会更多, 但可扩展性、μEngine之间的调度还有待优化.
2012年, Wang[
2016年, Ren[
2019年, Guo[
2013年, Wang对具有复杂软件优化和硬件配置的数据库查询进行了全面研究, 他们指出: 在当前的GPU数据库中, 系统使用专用的优化器来处理每个单独的查询, 并不支持在并发查询之间共享GPU资源.在开源GPU查询引擎[
2008年, Parag等人把共享查询的场景搬到了Map-Reduce中, 他们在文献[
2010年, Tomasz[
2011年, Wang[
2012年, Wolf等人[
● 在第1阶段, cyclic piggybacking提供了一种自然而有效的技术来摊销共享扫描的成本.作业被分解为多个子作业, 这些子作业与自然优先级约束相关.与文献[
● 在第2阶段, 针对各种度量标准, 解决了由此产生的优先级调度问题.Wolf等人给出了最近调度算法研究的概况, 用于在此cyclic piggybacking范式的背景下优化调度.该调度可根据各种成本指标进行定制, 该类成本指标包括平均响应时间、平均拉伸和任何minimax-type指标等总共11个单独的标准指标.
该方案的性能较MRShare和Coscan略有不及, 然而策略中各个作业立即执行, 无需等待, 因此对单个作业的影响确也是3种策略中最小的.
2013年, Guoping等人[
● 其一是通用的分组技术, 该技术将多个作业合并到单个作业中, 从而使合并的作业能够共享输入文件的扫描以及公共Map阶段的输出;
● 其二是提出了一种基于成本的两阶段优化算法来优化批量MR的执行计划: 在第1阶段, Guoping等人为每个作业选择Map输出键, 以最大化这批作业之间的共享机会; 在第2阶段, 他们将一批工作划分为几组, 并为每组选择处理技术, 以最大程度地降低总评估成本.
值得一提的是, 他们提到的MR工作共享策略与MRShare十分类似, 相比之下, 二者都提出了计算批量共享任务的代价模型, 且在代价模型上设计了启发式的查询计划算法, 并且二者的时间复杂度均为O(
2015年, Lei等人设计了一个为Map-Reduce基础架构中的重复工作量身定制的可扩展多查询共享引擎[
2003年, Bruno等人把共享查询技术的研究场景搬到了XML数据库系统中[
2007年, Hong[
大规模多查询联接处理中两阶段的处理模式
Two-stage processing mode in large-scale multi-query join processing
多查询共享技术应用在此类系统的程度, 完全取决于该应用领域的兴衰.如在21世纪10年代初期, Map- Reduce的研究进行得如火如荼之际, 也正是大量出产Map-Reduce多任务方案研究文章的时期; 再如半结构化数据中的多查询共享技术, 也随着该领域热度的减少而停止了研究.
从上述研究结果可以看出: 共享查询技术的本质是将多个查询或任务的公共部分执行一次, 从而达到共享资源的目的.本文对多查询共享优化进行了详细的阐述, 并梳理了基于多查询计划的各种优化技术以及多查询共享的各种算法, 之后还梳理了多查询共享优化在数据库系统领域的应用, 总结了两个通用的多查询执行模式.总体来说, 多查询共享技术的研究历史较久, 应用范围较广, 虽未广泛地应用到工业中, 但相关技术正在逐渐成熟.我们认为, 该领域还存在如下值得进一步研究的问题.
1) 针对多查询计划的优化而言, 现有研究往往是基于某个特定工作负载或硬件下的优化.例如在文献[
a) 改变现有查询流程, 从而避免全局查询计划的生成.研究团队不妨借鉴文献[
b) 另一个是采用机器学习(machine learning, 简称ML)的方法, 对查询和数据集进行训练, 从而启发对多查询引擎的设计.如2019年, Schleich等人[
2) 目前, 多查询共享在很多领域的应用还比较初步, 我们希望相关团队接下来会有更进一步的研究.例如, 文献[
3) 由于大多数多查询系统(如SharedDB、QPipe、CJoin、DataPath等)不开源, 导致后续研究无法开展, 其他团队无法跟进, 不少共享查询算法仅仅停留在模拟实验阶段.如第3.5节所述, 很多共享算法的研究往往无法考虑多查询优化过程, 而只是研究运算符之间如何进行共享, 如文献[
在之后的研究中, 我们将会开源地实现GQP以及OMP系统, 并在其上进一步实现各种多查询共享算法以及优化策略.我们希望能够在平台环境相当的基础上, 对目前主流的多查询共享技术进行一次全面的实验与分析, 旨在制定出一套该行业统一的性能评价标准; 同时, 也希望更多的研究者参与我们的工作.
Hector GM, Ullman JD, Widom J. Database System Implementation. Vol. 672, Upper Saddle River: Prentice Hall, 2000.
https://olap.com/olap-definition]]>
https://database.guide/what-is-oltp]]>
Georgios G, Alonso G, Kossmann D. SharedDB: Killing one thousand queries with one stone. Proc. of the VLDB Endowment, 2012, 5(6): 526-537.
Hong MS, Demers AJ, Gehrke J, Koch C, Riedewald M, White WM. Massively multi-query join processing in publish/subscribe systems. In: Proc. of the 2007 ACM SIGMOD Int'l Conf. on Management of Data. 2007.761-772.
Chakravarthy US, Minker J. Multiple query processing in deductive databases using query graphs. In: Proc. of the VLDB. 1986.384-391.
Cui YS, Zhang Y, Ceng C, Feng JH, Xing XC. Database physical structure optimization technology. Ruan Jian Xue Bao/Journal of Software, 2013, 24(4): 761-780(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4355.htm[doi:10.3724/SP.J. 1001.2013.04355]
崔跃生, 张勇, 曾春, 冯建华, 邢春晓. 数据库物理结构优化技术. 软件学报, 2013, 24(4): 761-780. http://www.jos.org.cn/1000-9825/4355.htm[doi:10.3724/SP.J.1001.2013.04355]
Rehrmann R, Binnig C, Böhm A, Kim K, Lehner W, Rizk A. OLTPShare: The case for sharing in OLTP workloads. Proc. of the VLDB Endowment, 2018, 11(12): 1769-1780.
Finkelstein S. Common expression analysis in database applications. In: Proc. of the SIGMOD. 1982.235-245.
Rosenthal A, Chakravarthy US. Anatomy of a Modular multiple query optimizer. In: Proc. of the VLDB. 1988.230-239.
Chen JJ, DeWitt DJ, Tian F, Wang Y. NiagaraCQ: A scalable continuous query system for Internet databases. In: Proc. of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. 2000.379-390.
Giannikis G, Makreshanski D, Alonso G, Kossmann D. Shared workload optimization. Proc. of the VLDB Endowment, 2014, 7(6): 429-440.
Krishnamurthy S, Franklin MJ, Hellerstein JM, Jacobson G. The case for precision sharing. In: Proc. of the 30th Int'l Conf. on Very Large Data Bases. 2004.972-986.
Alonso G, Kossmann D, Salomie T, Schmidt A. Shared scans on main memory column stores. Technical Report, Systems Group, Department of Computer Science, ETH Zurich, 2012.769.
Makreshanski D, Giannikis G, Alonso G, Kossmann D. Many-query join: Efficient shared execution of relational joins on modern hardware. Journal of VLDB, 2018, 27(5): 669-692.
Sun JZ, Li JZ, Gao H. Efficient batch grouping in relational datasets. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications. 2017.376-390.
Dalvi NN, Sanghai SK, Roy P, Sudarshan S. Pipelining in multi-query optimization. Journal of Computer and System Sciences, 2003, 66(4): 728-762.
Cao Y, Bramandia R, Chan CY, Tan KL. Sort-sharing-aware query processing. Journal of VLDB, 2012, 21(3): 411-436.
Johnson R, Hardavellas N, Pandis I, Mancheril N, Harizopoulos S, Sabirli K, Ailamaki A, Falsafi B. To share or not to share? In: Proc. of the VLDB Endowment. 2007.351-362.
Harizopoulos S, Shkapenyuk V, Ailamaki A. QPipe: A simultaneously pipelined relational query engine. In: Proc. of the 2005 ACM SIGMOD Int'l Conf. on Management of Data. 2005.383-394.
Arumugam S, Dobra A, Jermaine CM, Pansare N, Perez LL. The DataPath system: A data-centric analytic processing engine for large data warehouses. In: Proc. of the 2010 ACM SIGMOD Int'l Conf. on Management of Data. 2010.519-530.
Candea G, Polyzotis N, Vingralek R. A scalable, predictable join operator for highly concurrent data warehouses. In: Proc. of the 35th Int'l Conf. on Very Large Data Bases. 2009.277-288.
Zukowski M, Héman S, Nes N, Boncz PA. Cooperative scans: Dynamic bandwidth sharing in a DBMS. In: Proc. of the 33rd Int'l Conf. on Very Large Data Bases. 2007.723-734.
Psaroudakis I, Athanassoulis M, Ailamaki A. Sharing data and work across concurrent analytical queries. In: Proc. of the 39th Int'l Conf. on Very Large Data Bases. 2013.637-648.
Silva YN, Larson PÅ, Zhou JR. Exploiting common subexpressions for cloud query processing. In: Proc. of the 28th IEEE Int'l Conf. on Data Engineering. 2012.1337-1348.
Le WC, Kementsietsidis A, Duan SY, Li FF. Scalable multi-query optimization for SPARQL. In: Proc. of the 28th IEEE Int'l Conf. on Data Engineering. 2012.666-677.
Guo XT, Gao H, Zou ZN. Leon: A distributed RDF engine for multi-query processing. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications. 2019.742-759.
Ren XG, Wang JH. Multi-query optimization for subgraph isomorphism search. Proc. of the VLDB Endowment, 2016, 10(3): 121-132.
Chakravarthy US, Minker J. Multiple query processing in deductive databases using query graphs. In: Proc. of the VLDB Endowment. 1986.384-391.
Wang KB, Zhang K, Yuan Y, Ma SY, Lee RB, Ding XN, Zhang XD. Concurrent analytical query processing with GPUs. Proc. of the VLDB Endowment, 2014, 7(11): 1011-1022.
Paul J, He J, He BS. GPL: A GPU-based pipelined query processing engine. In: Proc. of the 2016 Int'l Conf. on Management of Data. 2016.1935-1950.
Wang XD, Olston C, Sarma AD, Burns RC. CoScan: Cooperative Scan sharing in the cloud. In: Proc. of the 2nd ACM Symp. on Cloud Computing. 2011.1-12.
Nykiel T, Potamias M, Mishra C, Kollios G, Koudas N. MRShare: Sharing across multiple queries in MapReduce. Proc. of the VLDB Endowment, 2010, 3(1): 494-505.
Agrawal P, Kifer D, Olston C. Scheduling shared scans of large data files. Proc. of the VLDB Endowment, 2008, 1(1): 958-969.
Wang GP, Chan CY. Multi-query optimization in MapReduce framework. Proc. of the VLDB Endowment, 2013, 7(3): 145-156.
Wolf JL, Balmin A, Rajan D, Hildrum K, Khandekar R, Parekh S, Wu KL, Vernica R. On the optimization of schedules for MapReduce workloads in the presence of shared scans. Journal of VLDB, 2012, 21(5): 589-609.
Lei C, Zhuang ZF, Rundensteiner EA, Eltabakh MY. Shared execution of recurring workloads in MapReduce. Proc. of the VLDB Endowment, 2015, 8(7): 714-725.
Yang J, Zhang Y, Wang J, Xing C. Distributed query engine for multiple-query optimization over data stream. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications. 2019.523-521.
Karimov J, Rabl T, Markl V. AStream: Ad-hoc shared stream processing. In: Proc. of the 2019 Int'l Conf. on Management of Data. 2019.607-622.
Jonathan A, Chandra A, Weissman JB. Multi-query optimization in wide-area streaming analytics. In: Proc. of the ACM Symp. on Cloud Computing. 2018.412-425.
Xin JC, Wang GR, Li GH, Gao YJ, Zhang ZQ. State of the art data model and its research progress. Ruan Jian Xue Bao/Journal of Software, 2019, 30(1): 142-163(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/5649.htm[doi:10.13328/j.cnki.jos.005649]
信俊昌, 王国仁, 李国徽, 高云君, 张志强. 数据模型及其发展历程. 软件学报, 2019, 30(1): 142-163. http://www.jos.org.cn/1000-9825/5649.htm[doi:10.13328/j.cnki.jos.005649]
Roy P, Seshadri S, Sudarshan S, Bhobe S. Efficient and extensible algorithms for multi query optimization. In: Proc. of the 2000 ACM SIGMOD Int'l Conf. on Management of Data. 2000.249-260.
Qin XP, Wang HJ, Du XY, Wang S. Big data analysis-Competition and symbiosis of RDBMS and MapReduce. Ruan Jian Xue Bao/Journal of Software, 2012, 23(1): 32-45(in Chinese with English abstract). http://www.jos.org.cn/1000-9825/4091.htm[doi:10.3724/SP.J.1001.2012.04091]
覃雄派, 王会举, 杜小勇, 王珊. 大数据分析——RDBMS与MapReduce的竞争与共生. 软件学报, 2012, 23(1): 32-45. http://www.jos.org.cn/1000-9825/4091.htm[doi:10.3724/SP.J.1001.2012.04091]
Zhou JR, Larson PÅ, Freytag JC, Lehner W. Efficient exploitation of similar subexpressions for query processing. In: Proc. of the 2007 ACM SIGMOD Int'l Conf. on Management of Data. 2007.533-544.
Reinard D. Graph Theory, Grad. Texts in Math. Springer-Verlag, 2005.
Jindal A, Karanasos K, Rao S, Patel H. Selecting subexpressions to materialize at datacenter scale. Proc. of the VLDB Endowment, 2018, 11(7): 800-812.
Cordella LP, Foggia P, Sansone C, Vento M. A (sub) graph isomorphism algorithm for matching large graphs. IEEE Trans. on Pattern Analysis & Machine Intelligence, 2004, 26(10): 1367-1372.
Sellis TK. Multiple-query optimization. ACM Trans. on Database Systems, 1988, 13(1): 23-52.
Phan DH, Michiardi P. A novel, low-latency algorithm for multiple group-By query optimization. In: Proc. of the 32nd IEEE Int'l Conf. on Data Engineering. 2016.301-312.
Schleich M, Olteanu D, Khamis MA, Ngo HQ, Nguyen XL. A layered aggregate engine for analytics workloads. In: Proc. of the 2019 Int'l Conf. on Management of Data. 2019.1642-1659.
Guravannavar R, Sudarshan S. Reducing order enforcement cost in complex query plans. In: Proc. of the 23rd IEEE Int'l Conf. on Data Engineering. 2007.856-865.
Neumann T, Moerkotte G. A combined framework for grouping and order optimization. In: Proc. of the 30th Int'l Conf. on Very Large Data. 2004.960-971.
Nambiar RO, Wakou N, Carman F, Majdalany M. Transaction processing performance council (TPC): State of the council 2010. In: Proc. of the TPCTC. 2010.1-9.
Zukowski M, van de Wiel M, Boncz P. Vectorwise: A vectorized analytical DBMS. In: Proc. of the 28th IEEE Int'l Conf. on Data Engineering. 2012.1349-1350.
Sellis T. Multiple query optimization. ACM TODS, 1988, 13(1): 23-52.
Selinger PG, Astrahan MM, Chamberlin DD, Lorie RA, Price TG. Access path selection in a relational database management system. In: Proc. of the 1979 ACM SIGMOD Int'l Conf. on Management of Data. 1979.23-34.
https://www.pdl.cmu.edu/DatabaseSystems/CMUDBAC/index.shtml]]>
Roussopolous N. View indexing in relational databases. ACM Trans. on Database Systems, 1982, 7(2): 258-290.
Graefe G, McKenna WJ. Extensibility and search efficiency in the volcano optimizer generator. In: Proc. of the Intl. Conf. on Data Engineering. 1993.
Michiardi P, Carra D, Migliorini S. Cache-based multi-query optimization for data-intensive scalable computing frameworks. In: Proc. of the Information Systems Frontiers. 2018.
Chintapalli S, Dagit D, Evans B, Farivar R, Graves T, Holderbaugh M, Liu Z, Nusbaum K, Patil K, Peng BY, Poulosky P. Benchmarking streaming computation engines: Storm, flink and spark streaming. In: Proc. of the 2016 IEEE Int'l Parallel and Distributed Processing Symp. on Workshops. 2016.1789-1792.
Tan KL, Goh ST, Ooi BC. Cache-on-demand: Recycling with certainty. In: Proc. of the 17th Int'l Conf. on Data Engineering. 2001.633-640.
Lang CA, Bhattacharjee B, Malkemus T, Padmanabhan S, Wong K. Increasing buffer-locality for multiple relational table scans through grouping and throttling. In: Proc. of the 23rd IEEE Int'l Conf. on Data Engineering. 2007.1136-1145.
Qiao L, Raman V, Reiss F, Haas PJ, Lohman GM. Main-memory scan sharing for multi-core CPUs. Proc. of the VLDB Endowment, 2008, 1(1): 610-621.
Chaiken R, Jenkins B, Larson PÅ, Ramsey B, Shakib D, Weaver S, Zhou ZR. SCOPE: Easy and efficient parallel processing of massive data sets. Proc. of the VLDB Endowment, 2008, 1(2): 1265-1276.
Le WC, Li FF. Query access assurance in outsourced databases. IEEE Trans. on Services Computing, 2012, 5(2): 178-191.
Miller E. An introduction to the resource description framework. Bulletin of the American Society for Information Science and Technology, 1998, 4(5).
Bruno N, Gravano L, Koudas N, Srivastava D. Navigation-vs. index-based XML multi-query processing. In: Proc. of the 19th Int'l Conf. on Data Engineering. 2003.139-150.
Jiao EH, Ling TW, Chan CY. PathStack: A holistic path join algorithm for path query with not-predicates on XML data. In: Proc. of the Int'l Conf. on Database Systems for Advanced Applications. 2005.113-124.
Hong MS, Demers AJ, Gehrke J, Koch C, Riedewald M, White WM. Massively multi-query join processing in publish/subscribe systems. In: Proc. of the 2007 ACM SIGMOD Int'l Conf. on Management of Data. 2007.761-772.
Clark J, DeRose S: XML path language (XPath) version 1.0.
Dewitt D, Ghandeharizadeh S, Schneider D, Hsiao H, Bricker A, Rasmussen R. The gamma database machine project. IEEE Trans. on Knowledge and Data Engineering, 1999, 2: 1.
Abadi M, Barham P, Chen JM, Chen ZF, Davis A, Dean J, Devin M, Ghemawat S, Irving G, Isard M, Kudlur M, Levenberg J, Monga R, Moore S, Murray DG, Steiner B, Tucker PA, Vasudevan V, Warden P, Wicke M, Yu Y, Zheng XQ. TensorFlow: A system for large-scale machine learning. In: Proc. of the 12th Symp. on Operating Systems Design and Implementation. 2016.265-283.
Akdere M, Çetintemel U, Riondato M, Upfal E, Zdonik SB. The case for predictive database systems: Opportunities and challenges. In: Proc. of the CIDR. 2011.167-174.
Ashari A, Tatikonda S, Boehm M, Reinwald B, Campbell K, Keenleyside J, Sadayappan P. On optimizing machine learning workloads via kernel fusion. In: Proc. of the ACM SIGPLAN Notices. 2015.173-182.
Kumar A, Boehm M, Yang J. Data management in machine learning: Challenges, techniques, and systems. In: Proc. of the 2017 ACM Int'l Conf. on Management of Data. 2017.1717-1722.