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

3186 Journal of Software 软件学报 Vol.32, No.10, October 2021

2012 年,Silva 也提出了类似识别公共子表达式的技术 [25] ,称为 FINGERPRINTS(FP).简单来说,FP 是一种查
询表达式的摘要,首先,作者将每个查询转化成查询树;然后将树中的操作节点与相应的操作 id 对应,再将树中
的表节点与文件 id 对应;通过数学计算得到相应的 FP.具有相同 FP 的两个表达式很可能相等,具有不同 FP 的
两个表达式不相等.源自根节点 R 的表达式 E 的 FP 表示为 F E ,其计算方式如下.
(1) 如果 R 代表直接从数据文件读取的操作,则:
F E =R.FileID mod N.
(2) 否则:
FE=(R.OpIDFR.child[i]) mod N (0≤i≤k).
在该定义中,是 XOR 操作;N 是足够大的质数,可以防止 FileID 和 OpID 的值之间发生冲突;FileID 是数据
文件的唯一标识符;OpID 是操作的唯一标识符,例如,所有分组操作都具有相同的 OpID.
2018 年,Jindal 对公共子表达式的选择问题进行了基于整数线性规划(integer linear programming)的定义,
并将该问题抽象为二分图标记(bipartite graph labeling)问题 [45] .文献[46]将逻辑查询计划抽象为 G=(V Q ,V S ,E)的
二分图,Q 表示查询,S 表示子表达式,每个顶点 v  V 代表一个查询 q i Q;并且每个顶点 v  V 代表一个子表
1 s
Q
S
1 q
达式 s i S;查询顶点与表达式顶点相互连接,代表查询与表达式之间的关系.基于以上定义,文献[46]阐述了一种
并行的公共子表达式选择算法 BIGSUBS.该算法本质上是一种迭代方法,每个迭代包括两个步骤:首先为每个
查询的子表达式分配标签,以最大化每个查询的效用,同时注意子表达式的交互作用;在第 2 次迭代中,确定在顶
点标注步骤中选择的子表达式,然后遵循等式中的优化目标,通过标记与该查询相邻的边来确定各查询中的公
共子表达式.
2018 年,Jonathan [40] 采用有向无环图(DAG)来表示单个查询的逻辑查询计划,以查询顶点(运算符)为中心,
以拓扑顺序遍历顶点,从源顶点拓扑上将一个新查询与每个现有查询进行比较:如果顶点相等,则继续遍历,直
到找出所有可共享的节点,并将其合并;如果两个顶点不相等,则通过定义,它们的下游顶点均不相等,因此不需
要对其进行比较.该算法可以高效地将非共享的查询区分出来,从而更快地定位相似性高的查询(但相似性高并
不意味着查询能够共享,需要进一步分析).该算法在子图匹配算法 [47] 的基础上进行了改进,并将其运用到共享
查询的匹配上,使得原本只能匹配单个查询的算法可以同时匹配多个查询.
3.3 多查询共享算法
运算符的共享计算也是多查询共享技术研究的另一大方向,主要的研究内容即针对各个运算符设计共享
算法,如选择、连接、排序以及分组等.选择运算符的多查询共享算法主要分为两种:(1) 在查询编译阶段,将多
[4]
个查询的谓词表达式合并,在扫描一条元组的同时,进行多个查询谓词的评估,最后根据查询识别算法 将中间
结果或最终结果返回;(2) 直接在查询执行阶段将多个可共享的选择运算符放入一个队列中,对每一个元组进
行流水线评估,结果直接返回给查询下一阶段.两种策略的性能相仿:第 1 种策略可以对查询表达式进行更多的
优化,从而减少冗余计算,但需要依赖查询识别算法分派结果;第 2 种策略存在更多的冗余计划,但可以直接处理
查询结果.更多共享算法的研究集中于排序、分组和连接运算符,这些运算符使用频繁,而且开销较大,有很高的
共享价值.同时,由于单查询模式下这些运算符大多具有几种以上的处理算法,从而衍生出了相应的多查询处理
算法.本节将列出一些有代表性的多查询共享算法的研究.
2004 年,Krishnamurthy 等人 [13] 指出:简单地将查询谓词合并会导致查询执行时产生大量冗余元组及不必要
的计算.对此,他们提出了一种叫作 TULIP(tuple lineage in plans)的精确共享查询方案,该方案能够最大程度地减
少查询执行带来的冗余元组.精确共享需要满足以下两个条件:(a) 对于每个处理的元组或者元组的副本,任何
给定的算子最多可以应用 1 次;(b) 任何算子都不得产生“僵尸”元组,也就是说,一个元组在数据流中是否存在,
对任何查询的结果都没有影响.不满足条件(a)的计划会遭受冗余开销;不满足条件(b)的算子会导致浪费的生
产,并伴随消除僵尸元组的工作.TULIP 方案首先为每一个中间结果元组添加一个叫作元组谱系的向量结构,该
向量由两部分组成:(1) 引导向量,用于描述数据流中已访问和将要访问的运算符;(2) 完成向量,用于描述系统
中对该元组“无效”的查询,即该元组无法满足的查询.其次,该方案还在内存中维护着当前系统所注册的谓词和