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

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

连接的索引,当它收到一个新的元组时,即会有效地探查索引以识别失败的所有已注册子句,然后将所有这些失
败记录在元组的沿袭矢量(lineage vector)中.如果在处理元组结束时有任何对元组的实时查询(即仍然可以满足
的查询),则仍然将元组输出.实验结果显示:使用 TULIP 方案的系统在查询重叠较大的负载之下,平均响应时间
要比没有使用的系统少 20%~30%.
2007 年,Zukowski 等人 [12] 提出了运算符 CScan,是扫描运算符的一种协作变体.Cscan 通过活动缓冲区管理
器(ABM)追踪每个 Cscan 算子,找到算子之间的公共部分,并尝试安排磁盘进行读取,以便使多个并发扫描重用
同一数据块.此外,为了在高并发查询场景下获得良好的带宽,扫描处理通常使用称为块的大型的 io 单元.相比
于传统扫描,协作扫描框架实现了一种叫作相关性扫描的策略,该策略通过使用一组相关性函数来进行调度决
策.当每次需要处理大量数据时,系统会调用 choiceAvailableChunk 函数,该函数访问搜索仍然需要由查询处理
的所有缓存块;同时,useRelevance 会“推荐”出尽可能被较少查询访问的块.这样一来,不太活跃的块将会尽快被
消耗掉,从而加入新的活跃的块.协作扫描框架还维护了一个查询优先级队列,较短的查询会有较高的优先级,
这样就能保证短查询的响应时间,但是系统也会优先执行将等待时间较长的长查询.实验结果表明:协作扫描框
架在上亿数据集的 OLAP 工作负载之下,吞吐量和整体响应时间都要优于使用传统扫描框架的查询引擎.不足
之处在于:协作扫描不能很好地保证单查询的响应时间,由于块长度过大,使得该框架必须运行在高内存设
备上.
2013 年,Alonso [14] 提出了一套在列存数据库上共享扫描的算法,该算法如下:首先遍历列的集合,对于每一
个列,为该列的每一个值标记它的位置以及它所对应的查询 id,从而为每列生成一个位置数组;最后,各查询扫描
后的结果集根据位置数组生成.该算法采用两种方法来避免冗余计算:(a) 对选择性高的谓词尽量优先进行评
估,从而减少中间结果的数量;(b) 为查询谓词添加索引,索引的 key 为高选择性谓词的值,value 则是该谓词所对
应的查询 id 集合.整个索引的生成过程如图 9 所示,该想法早在文献[48]中即已提出,但适用性较差(查询开销必
须普遍高于构建查询索引的开销),因此之后的研究鲜有提及.作者将该方案应用到列存数据库引擎中,能够提
高探测索引的效率,但构建索引的代价较大,尤其是在高并发场景下,而作者并未对此做出优化.

Fig.9 An index of multiple query
图 9 多查询索引

2016 年,Duy-Hung [49] 提出了一种针对聚合查询的共享查询算法,名为“自顶向下拆分(top-down splitting)”
算法.该算法可扩展到数百甚至数千个查询,并且可以快速、有效地生成优化的查询执行计划.首先,Duy-Hung
假定表 T 有 m 列属性.设 S={s 1 ,s 2 ,…,s n }为 n 个查询的分组(grouping)集合,s i 表示表 T 的一个或多个属性.Q i 代表
一个分组查询:
Q i :Select s i , Count(*) From T Group By s i .