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

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

sharedDB 在该方面进行了妥协,sharedDB 不允许在查询执行时将新来的运算符加入到查询计划中,在最初的设
计中,sharedDB 甚至手动生成全局查询计划以处理已知的工作负载;在之后的研究中,多查询路径搜索技术 [12]
以及多连接优化算法 [15] 等技术被陆续应用到了 sharedDB 中.
此外,该团队还专门为支持列存储的 sharedDB 版本 [14] 优化了共享算子.
2012 年,Silva [25] 指出:在早期利用共享表达式的共享查询系统中,只是将结果视为一个集合,通常对于不同
用户的不同物理需求(如排序和结果集分区)需要分别处理.对于某些查询来说,加入这样一个共享查询显然是
不划算的.为了满足用户的各种需求且保证查询的响应时间,Silva 等人提出了一个基于识别公共子表达式的查
询框架,该框架在 SCOPE [65] 中实现.其实验结果表明,扩展的优化器生成计划的成本降低了 21%~57%.
2018 年,Jonathan 将共享查询技术运用到分布式流分析查询系统中 [40] ,文献[40]探讨了在广域流分析中应
用多查询优化的机会,从而有效地利用了广域网络带宽,同时实现了高吞吐量和低延迟执行.在这项工作中,
Jonathan 团队研究了不同类型的共享机会,并将其分为“输入-运算符共享”“输入共享”两种,随后提出一种实用
的在线算法,该算法允许流分析查询逐步共享其执行的公共部分.该策略以有向无环图(DAG)来表示逻辑查询
计划,查询优化器以顶点为中心的方式分析查询之间的共性,将广域网络(wide-area network)带宽的可用性作为
首要考虑因素,从而确定需要利用哪些共享机会,最后生成全局查询计划.之后,文献[40]还介绍了基于该算法实
现的原型系统 Sana,该系统的底层为 Apache Flink [61] (一款开源的数据流处理系统),Jonathan 团队已经将其部署
并对其进行实验.实验结果表明:在相同条件下,Sana 的吞吐量要比没有任何共享的系统高出 21%,带宽利用率
则提高了 33%.
[4]
2019 年,Karimov [39] 提出了一种支持共享查询的分布式流处理框架(AStream).该框架借鉴了 SharedDB ,
并对临时查询(ad-hocquery)负载作了优化.AStream 旨在通过共享资源和计算来提高数据流处理系统中临时查
询的吞吐量和整体响应时间.值得一提的是:上文所提到的 Sana 也是支持共享查询的分布式数据流处理框架,
二者最大的区别在于查询处理流程的不同.AStream 属于 GQP 系统,因其需要生成全局查询计划,并为每个共享
查询创建一个查询实例;而 Sana 则属于 OMP 系统,其查询处理是以运算符为中心的,集群中的每个节点拥有自
己的计算实例(这类似于上文所述的 CJoin [22] ),数据通过“推(push)”的方式进入各计算实例,系统不需要提前制
定全局查询计划,每个-engine 只需将当前提交过来的算子与正在进行的算子共享即可.由于二者均不开源,测
试所用的查询负载以及数据集也均不相同,虽然都是在 Apache Flink 上实现,但我们也很难通过实验比较其性
能上的差异.
5.1.2 OTLP 数据库中的多查询共享
[3]
OLTP 负载存在着大量更新操作,对响应时间的要求较高,存在大量点查询等共享机会不高的查询.这些都
[8]
是共享查询技术鲜有支持 OLTP 负载的原因.近来,逐渐有团队试图解决这些不利因素,2018 年,Robin 等人 系
统地研究了大量 OLTP 工作负载,旨在得出实际 OLTP 工作负载中的共享潜力.他们围绕:(1) 典型的 OLTP 应用
程序使用了多少个不同的查询语句?(2) 哪种查询句式最常用?这两个问题,对来自卡内基梅隆数据库应用程序
目录(CMDBAC) [57] 中的大量 OLTP 工作负载进行分析,结果 89%的应用程序只有 10 个不同的语句字符串或更
少,50%的应用程序只使用单个不同的语句字符串,100%的程序仅使用单语句事务,并且超过 80%的语句是简单
的基于键的查找查询.从 Robin 等人研究的结果可以看出,OTLP 工作负载也具有相当的共享潜力.在之后的工
作中,他们又提出了一种名为 OLTPShare 的执行策略,该策略实现了 OLTP 工作负载的查询共享方案.该方案大
致如下:OLTPShare 使用基于队列的方法批量处理所有输入的事务,根据公共子表达式合并规则对查询进行合
并,在最初的设计中,OLTPShare 并未对合并后的全局查询进行优化.Robin 等人在文献[8]的最后也指出,未来的
工作会为 OLTPShare 实现多查询计划的优化策略.就系统本身而言,OLTPShare 适用的场景较为苛刻.根据
Robin 等人的实验,OLTPShare 处理读写混合负载的性能仅是读负载的 50%.
5.1.3 小 结
多查询共享技术被广泛地应用于基于关系模式的数据库系统中,其中不乏 sharedDB、Qpipe、Cjoin、
DataPath 等经典多查询系统.目前,几乎所有的系统都遵循第 3.1 节中所描述的两种查询模式:基于全局查询计