Page 213 - 《软件学报》2021年第10期
P. 213
危剑豪 等:多查询共享技术研究综述 3185
符)传递到另一个节点(运算符),虚线边则表示数据以固化的方式从一个节点(运算符)传递到另一个节点(运算
符).用 DAG 表示多查询计划的优势在于,执行引擎可以并行地从多个根节点开始执行该查询计划.在最近的研
究中,shareDB 与 Datapath、AStream 等系统也使用 DAG 来表示全局查询计划.与 plan-DAG 不同,sharedDB 等
系统处理数据的方式为 push,即自底向上将元组推入查询计划中.而由于 plan-DAG中数据的传递方式包含固化
和流水线两种,因此能够采用 pull 的数据处理方式.
sort
user order item
Fig.7 An example of plan-DAG
图 7 plan-DAG 实例
3.2 多查询表达式合并
2000 年,Chen 提出了通过签名(signature)将多个查询表达式进行合并的技术.在其论文 [11] 中提出了多种签
名策略:首先,用占位符替换谓词中出现的常量,为选择谓词创建表达式签名,该签名是一种树形结构(如图 8 所
示),父节点存储运算符,左叶子节点存储公共表表达式,右叶子节点存储变化的常量;在此基础上提出了签名组
概念(所谓签名组就是所有查询的通用表达式签名(见表 3)),从而使得在合并表达式时能够记录常量所属的查
询.该签名组为二维表结构:第 1 列表示常量值,第 2 列表示查询 id.
=
COUNTRY=‘CHINA’
SELECT*FROM USERS OR COUNTRY=‘USA’
Fig.8 Signature of Q2
图 8 Q2 的签名
Table 3 Signature groups of Q1, Q2, Q3
表 3 Q1、Q2、Q3 的签名组
常量 查询 id
AGE>? Q1
COUNTRY=‘CHINA’ OR COUNTRY=‘USA Q2
COUNTRY=‘CHINA’ AND AGE>? AND AGE<? Q3
2007 年,Zhou 提出了一种表签名技术 [44] ,用来快速标记多个查询的公共部分.该表签名可以表示为 S e =[G e ;
T e ](其中,e 为选择、投影、连接、分组等表达式;S e 为表签名;G e 是一个布尔值,表明 e 是否包含 groupby 运算;T e
是表达式 e 中表的集合).例如,Q1、Q2、Q3 的表签名分别表示为 S Q1 =[T;{User}]、S Q2 =[F;{User}]、S Q3 =[F; {User}].
表签名充当表达式的高级摘要,用作检测潜在可共享表达式的快速筛选器.
