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

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

area network)带宽的可用性作为首要考虑因素,从而确定需要利用哪些共享机会,最后生成全局查询计划.具体
而言:对于“输入-运算符共享”来说,查询优化器需要确保顶点共享算子 v i 所在的节点具有足够的出口带宽以传
输其他输出流;在“输入共享”的情况下,查询优化器需要进一步确保入口和出口链路中都有足够的带宽来分别
传输附加的输入和输出流;在此基础上,优化器对所有流过该共享算子的数据进行运算,输出结果则发往下一个
算子.该算法的缺陷在于:当工作负载中的查询执行时间存在较大差异时,执行较慢的查询会严重拖慢执行较快
的查询.比如查询 A 含有 5 层 join、6 层聚合,其数据可能需要在 6 个以上的广域网络节点中互相传输;若查询 B
只含有 1 层 join、1 层聚合,一旦二者进行共享,则查询 B 的执行需要付出比原来多出 6 倍以上的广域网络传输
代价,这显然是非常昂贵的.
2019 年,Karimov [39] 提出了一种支持共享查询的分布式数据流处理框架(AStream),主要面向的场景是流处
理系统中的临时查询(ad-hoc query).具体策略如下:AStream 内维护着一个名为“共享流运算中心(shared stream
in goperator)”的模块,随着查询的提交,系统会先将可共享的查询合并,并且为合并后的查询创建若干个“共享选
择、连接、聚合等实例”,数据流则会依次通过这些操作实例从而得到查询结果,最后,系统将查询结果反馈.该框
[4]
架主要借鉴了 sharedDB 全局查询计划的设计思路,并为选择、连接、聚合等算子设计了增量查询处理的共享
算法,使得系统能够计算临时流聚合,并以增量的方式进行连接.对于差异性较大的临时查询来说,Astream 生成
的全局查询计划往往不是最优的.Karimov 等人也在文献[39]中最后提出:在未来的工作中,他们计划使用基于
成本的优化器和自适应查询处理技术来扩展 AStream,并通过对相似的查询进行分组来生成更优化的查询
计划.

3.5 小 结
基于多查询计划的优化研究种类繁多,像多查询计划的抽象模型、子表达式合并规则、中间结果的数据模
型、适应新型存储结构的多查询调度以及多查询计划搜索算法等都囊括在内.目前的研究主要集中在设计出适
应性更强的多查询调度策略(这些策略大多是启发式的),即:为不断变化的负载动态地生成全局查询计划,最大
化地利用查询之间的共享机会,并保证单查询的响应时间.
多查询共享算法的性能往往依赖于多查询优化器对查询的调度,若不能把握住稍纵即逝的共享机会,那么
再优秀的算法也会因错过共享时机而无法得以发挥.很多的共享算法研究往往不考虑多查询优化过程,而只是
研究运算符之间如何进行共享,这就导致所研究的内容与实际应用互相脱离,上述提到的方法中的实验结果固
然好看,但无法兼容到现有的多查询引擎中.因此,虽然目前关于排序和分组的多查询共享算法的研究论文最
多,但在实际的多查询系统中,往往只应用了针对选择和连接运算符的共享算法.

4 查询执行阶段中的多查询共享技术

4.1 多查询缓存管理
[9]
1982 年,Finkelstein 提出了热点多查询标记算法 ,首先筛选出热点查询,然后分析多个热点查询的表达式,
将公共子表达式合并,并将这些查询的结果固化,达到共享中间结果的目的.由于当时 io 的性能严重制约了关系
数据系统的性能,不少学者希望通过反复利用内存中的数据及代码以达到减少 I/O 开销的负担,而将频繁使用
的查询计划或者中间结果存储在内存中,这也是之后许多研究并发查询解决方案的中心思想.
2001 年,Kian-Lee [62] 提出了按需缓存(COD)的概念,即缓存肯定会被重用的结果.为了确定缓存的可重用性,
而不是像传统的缓存策略那样预测未来,Kian-Lee 等人将重点放在当前系统内的查询上.该方案的思路大致如
下:(1) 系统检查系统中当前正在运行的查询,确定传入查询和正在运行的查询之间的公共子表达式,并标识可
被重新使用的查询的中间或最终结果,这些中间或最终结果被放在虚拟缓存中;(2) 让刚提交的查询利用这些
结果.Kian-Lee 等人将研究重点放在如何查找候选虚拟缓存以及重用虚缓存上.为此,他们定义了两个数据结构
来保存相应的信息:(1) VirtualCache(VC),用来跟踪所有正在运行查询的虚拟缓存上的信息;(2) Operation
ExecutionStatus(DES)表,用来保留正在运行的虚拟缓存(或算子)的执行状态.