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

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

 一种是基于计划合并的方法,主要思路是:为每个查询生成最佳访问计划,并将这些计划合并为一个多
查询访问路径.但这种方式并不适用于多连接的 OLAP 负载,因为当单个查询确定了连接的顺序之后,
查询之间因为连接结果的不一致会导致无法共享;
 第 2 种更为复杂的方法是基于全局优化器,在该方案中,Timos 等人将优化问题表述为状态空间搜索问
题,并针对该问题提出了一种算法.但该算法的时间复杂度较高,导致生成多查询计划的时间远远超过
单查询计划.
类似的策略还包括文献[54,57],这些优化策略专注于为少量查询找到最佳的全局计划,通常适用于查询事
先给出或少量类似的查询会在很短的时间间隔内进入系统的场景.但每当添加新查询时,系统往往需要重新优
化所有的查询,这种方法对于大型动态环境显然是不可接受的.
2000 年,Chen [11] 提出了一种启发式的多查询优化策略,该策略的核心思想如下:首先,根据现有查询的签名
为它们创建组,这些签名代表查询之间的相似结构;每组允许共享两个或多个查询的公共部分;查询组中的每个
单独查询共享执行组计划的结果;提交新查询时,组优化器会将现有组视为潜在的优化选择.新查询将合并到与
其签名匹配的现有组中,因此现有查询并不会重新分组.该策略可能无法产生最优多查询计划,但它显著降低了
优化的成本;更重要的是,它在动态环境中具有很高的可伸缩性.由于查询组中经常添加和删除连续查询,可能
使当前组执行的效率变得非常低下.在之后的研究中,该团队又提出了“动态重新分组”技术,该技术定期或在系
统性能下降到某个阈值以下时,重新组织部分或全部查询.
2000 年,Prasan 在其文章中首次证明了启发式的多查询优化是切实可行的,并且具有明显的优势.他提出了
3 种基于成本的启发式算法:Volcano-SH、Volcano-RU 以及贪心启发式算法.这 3 种算法均基于 AND-OR
DAG [58,59] ,并且算法的思路大致也相同,只是启发式规则略有差异.算法的大致思路如下:通过启发式规则将公
共子表达式合并,生成多个 AND-OR DAG;然后对每一个 DAG 进行深度优先遍历,找出等价操作节点 e;然后设
cost(e)为节点 e 的计算开销,numuses(e)为 e 操作重叠的次数,matcost(e)为节点 e 物化的开销,reusecost(e)为重用
物化后 e 的结果开销.如果满足 cost(e)+matcost(e)+reusecost(e)(numuses(e)1)<numuses(e)cost(e),则对该节点
的结果进行物化,从而与其他相同操作的节点共享.当对 DAG 遍历完成后,计算出所有 DAG 的开销,找出开销最
小的 DAG.Prasan 等人将传统 Vocalno 与 Volcano-SH、Volcano-RU 以及贪心启发式算法进行了对比实验:随着
数据量的增加,3 种算法的成本与收益比明显增加;但当处理非共享的工作负载时,3 种算法的性能就不及传统
Vocalno 算法,贪心启发式算法的性能下降得最多,高达 25%.
2003 年,Nilesh [17] 证明了找到最低成本的多查询计划是 NP-hard 问题,并提出了一种启发式的贪心算法,用
以搜索最优查询计划(多查询计划已由 plan-DAG 构建).Nilesh 等人首先对谓词相同的节点合并,以生成全局的
多查询计划图,该图的节点之间以有向边连接,有向边代表数据从一个节点(运算符)传递到另一个节点(运算
符),传递方式包括流水线和固化两种.算法的思想就是将读取成本最高的边进行固化,以共享公共元组,剩下的
边进行流水线化,直到无法将边进行流水线化为止,从而达到局部成本最优的解.
2007 年,Zhou 设计了一个实用、统一且具有扩展性的探测和利用相似子表达式的方案 [44] ,子表达式分为选
择(select)、投影(projection)、连接(join)、分组(group)这 4 种类型(SPJG).该方案首先通过关系表签名(table
signature)机制快速找到可能共享的 SPJG 子表达式组,所谓表签名,即通过将子查询中的 SPJG 信息结构化并存
入二元组中.在探测到相似子表达式集合后,系统按照启发式规则同时生成多个名为 Covering SubExpression
(CSE)的数据结构,每个 CSE 对应同类子表达式所要求的元组集合,这样的 CSE 集合称为候选 CSE.然后,优化器
根据所定义的代价模型,排除开销较大以及冗余的 CSEs,并将剩下的 CSEs 加入查询计划,被选中的 CSEs 对所
有的元组进行评估并产生相应的查询结果.实验结果表明,CSE 有效缩短了生成查询计划所需的时间.
2012 年,Silva [25] 提出了一个基于识别公共子表达式的查询优化框架,该查询优化策略如图 11 所示.
1) 识别公共子表达式:系统事先将所有的子表达式分类,并对其进行 hash,结果映射为一张 hash 表,新来
的 query 被拆分为多个子表达式,而公共子表达式可根据 hash 表进行快速识别,并分为若干共享组;
2) 记录物理性质:常规优化器被扩展,从而记录步骤 1 中被标识的物理属性.作为共享子表达式组的根节