Grammar-aware Parallelization for Scalable XPath Querying
Grammar-aware Parallelization for Scalable XPath Querying
复制标题
可扩展 XPath 查询的语法感知并行化
DOI：
--
复制
发表时间：
2017
期刊：
影响因子：
--
通讯作者：
Zhijia Zhao
中科院分区：
文献类型：
--
作者：
Lin Jiang;Zhijia Zhao
半结构化数据出现在许多领域，特别是在Web分析和商业智能领域。然而，由于输入数据的嵌套结构，查询这样的数据本质上是顺序的。现有的解决方案悲观地枚举所有执行路径以规避依赖关系，从而产生次优性能和有限的可伸缩性。本文提出了GAP，一个并行化方案，第一次，利用输入数据的语法，以提高并行化效率。GAP利用静态分析来基于半结构化数据的语法推断特定上下文的可行执行路径。它可以在不影响正确性的情况下消除不必要的路径。在没有预定义语法的情况下，GAP切换到推测执行模式，并采用从先前输入中提取的可能不完整的语法。总之，双模式GAP将所有路径中的执行路径减少到最少，从而最大限度地提高并行化效率和可扩展性。路径消除的好处不仅仅是减少额外的计算-它还可以使用更有效的数据结构，从而进一步提高效率。在一个大的标准基准测试集上的不同查询的评估表明，GAP产生显着的效率提高，并提高了速度从2.9倍到17.6倍的最先进的20核机器上的一组200个查询。
Semi-structured data emerge in many domains, especially in web analytics and business intelligence. However, querying such data is inherently sequential due to the nested structure of input data. Existing solutions pessimistically enumerate all execution paths to circumvent dependencies, yielding sub-optimal performance and limited scalability. This paper presents GAP, a parallelization scheme that, for the first time, leverages the grammar of the input data to boost the parallelization efficiency. GAP leverages static analysis to infer feasible execution paths for specific con- texts based on the grammar of the semi-structured data. It can eliminate unnecessary paths without compromising the correctness. In the absence of a pre-defined grammar, GAP switches into a speculative execution mode and takes potentially incomplete grammar extracted either from prior inputs. Together, the dual-mode GAP reduces the execution paths from all paths to a minimum, therefore maximizing the parallelization efficiency and scalability. The benefits of path elimination go beyond reducing extra computation -- it also enables the use of more efficient data structures, which further improves the efficiency. An evaluation on a large set of standard benchmarks with diverse queries shows that GAP yields significant efficiency increase and boosts the speedup of the state-of-the-art from 2.9X to 17.6X on a 20-core ma- chine for a set of 200 queries.