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

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

达到输出状态时,NFA 输出在该状态下所接受查询的所有匹配项.与用于标识常规语言的 NFA 不同,对 XML 文
档的过滤要求继续进行处理,直至达到所有可能的接受状态为止.传入的 XML 文档一次被解析一个标签,解析
时,开始标记令牌会触发 NFA 中的转换;解析结束标记令牌后,执行将回溯到紧接在相应开始标记之前的状态.
Bruno 等人对两种策略分别进行了实验,结果显示:当并发查询在 500 个以下时,索引过滤的性能要高于 Y 过滤
的性能;而并发查询在多余 500 个时,则 Y 过滤的性能会更好.
2007 年,Hong [70] 提出了一种多查询联接处理技术,名为“大规模多查询联接处理”技术,用于有效评估 XML
文档流上的并发连接查询.该策略的核心是将连接条件分解为树模式和值比较组件,通过两阶段的处理方式,在
查询之间有效地共享存储和计算,两阶段的处理模式如图 15 所示.Hong 等人为第 1 个处理阶段的结果开发了一
个紧凑的表示形式,核心思想是存储 XPath [71] 查询块中涉及的所有变量绑定的有效组合;他们在第 2 阶段提出
了一个可扩展的连接处理器,主要思想是将问题映射到一个关系框架中,该框架有助于在不同查询之间共享连
接运算.实验结果表明,采用该连接共享方案的系统吞吐量较原始系统提升了 100%.
XML流文本 XML流文本
Streams of x路径监控 Streams of
XML Document x路径评估模块 Xpath witness 连接处理器 XML Document
Xpath evaluator Join processor
Fig.15 Two-stage processing mode in large-scale multi-query join processing
图 15 大规模多查询联接处理中两阶段的处理模式
5.2.5 小 结
多查询共享技术应用在此类系统的程度,完全取决于该应用领域的兴衰.如在 21 世纪 10 年代初期,Map-
Reduce 的研究进行得如火如荼之际,也正是大量出产 Map-Reduce 多任务方案研究文章的时期;再如半结构化
数据中的多查询共享技术,也随着该领域热度的减少而停止了研究.
6 总结与展望

从上述研究结果可以看出:共享查询技术的本质是将多个查询或任务的公共部分执行一次,从而达到共享
资源的目的.本文对多查询共享优化进行了详细的阐述,并梳理了基于多查询计划的各种优化技术以及多查询
共享的各种算法,之后还梳理了多查询共享优化在数据库系统领域的应用,总结了两个通用的多查询执行模式.
总体来说,多查询共享技术的研究历史较久,应用范围较广,虽未广泛地应用到工业中,但相关技术正在逐渐成
熟.我们认为,该领域还存在如下值得进一步研究的问题.
1) 针对多查询计划的优化而言,现有研究往往是基于某个特定工作负载或硬件下的优化.例如在文献
[21]中,多查询计划搜索算法根本无法适应变化的负载;而文献[4]等通用的优化方案存在着单查询延
迟高、非并发条件下性能较差等问题.再如,变化的负载导致基于成本的全局查询计划的生成开销过
大,从而无法适应某些数据流处理系统的并发场景.Karimov [39] 提到:在未来的工作中,他们计划使用
基于成本的优化器和自适应查询处理技术 [72] 来扩展 AStream.我们为此类问题的解决总结出两种
思路.
a) 改变现有查询流程,从而避免全局查询计划的生成.研究团队不妨借鉴文献[20]所做的工作,改进
或重新设计现有的查询模式,从而为多个查询创造更多的共享机会,这在第 3 节和第 4 节已有详
细说明;
b) 另一个是采用机器学习(machine learning,简称 ML)的方法,对查询和数据集进行训练,从而启发
对多查询引擎的设计.如 2019 年,Schleich 等人 [50] 提出了 LMFAO(layered multiple functional
aggregate optimization),这是基于 ML 的执行引擎,用于在输入数据库上批量处理聚合运算.
Schleich 等人将大量查询数据集、表达式及查询计划作为训练集,并且考虑了并发、负载类型以
及时间等因素,训练的结果则作为查询优化器制定查询计划的主要依据.同样,类似的方式也可
以用于多查询中.目前,使用 ML 的大规模数据分析为许多数据驱动的应用程序奠定了基础.数