论文部分内容阅读
随着网络的普及和网络服务的飞速发展,XML作为一种信息交换和存储的标准被广泛使用。XML查询处理是XML数据利用的主要方式。由于XML数据量和XML查询需求的快速增长,人们对XML的查询性能也日益重视,各种查询优化技术成为研究热点。近年来,多核环境的普及为并行计算提供了良好的机遇,面向多核计算的并行化设计成为提高程序性能的重要途径。如何充分利用多核计算来提高XML查询性能成为重要的研究课题。XML查询技术体系以XQuery查询语言为核心,包含XPath求值和XML解析等关键技术。XML解析在XML应用中必不可少,由于对大数据量的解析是高耗时的工作,解析几乎成为大多数XML应用的性能瓶颈,有并行处理的必要。XPath专门用于访问XML数据,是XQuery的重要组成部分。导航式XPath求值方式由于具有容易满足查询语义,适用范围广等优势,在查询引擎设计中广泛使用。然而与多数Twig求值方法相比,导航式方法性能较为低下,通过并行化将提高其性能。XQuery作为主流的XML查询语言,是XML查询技术的核心,其执行效率决定了XML应用的性能,因此需要对XQuery进行并行化处理以提高其执行性能。XQuery是一种函数式语言,具备一些并行化优势,然而并行机会隐藏在各种嵌套中,难以直接并行化,目前尚未出现完整的自动并行化解决方法。鉴于XML查询涉及多项关键技术,一个兼顾各项并行化技术的整体解决方案将有效提升XML查询的整体性能。 本文针对XML查询相关的若干关键技术的并行化所面临的问题提出相应的解决方案,目的是为了充分利用多核计算资源,通过并行计算以提高XML查询性能。本文的创新性研究工作如下: (1)提出了一种基于并行子树构建的XML解析方法。该方法采用一种轻量级的数据划分预处理方法,避免了高代价的划分预处理和复杂的预处理优化;支持对XML数据任意分片的解析,便于负载平衡处理。解析过程中首先进行数据划分,然后并行构建各个分片中的子树,最后通过子树合并获得全局的文档树。实验验证了该法能有效利用多核计算环境,实现XML的并行解析。 (2)提出了一种基于节点关系矩阵的XPath并行求值方法。该法包含节点关系矩阵的并行构建和并行查询求值这两个阶段。根据XML数据的区间编码进行关系矩阵构建,通过并行查询原语序列的执行实现XPath表达式并行求值。其导航式特点使得XPath的各种查询语义容易实现,支持包括反向轴操作和以谓词形式表达的分支查询等操作。由于对应相同XML数据的关系矩阵可以被不同查询复用,提高了数据的利用率。各阶段计算的并行化能利用多核资源提升XPath求值性能。实验测试显示了该法具有较高查询效率;在多核条件下,能进一步通过并行计算提高求值效率。 (3)提出了一种基于函数式中间语言的XQuery自动并行化方法。该方法发展了一种具备并行语义,且与XQuery相适应的函数式中间语言pFXQL,以此作为并行查询计划的描述工具。自动并行化的过程是一个中间语言自动重写的过程:通过划分获取可并行块,据此发掘可并行化机会;结合依赖判别条件和计算代价模型进行可并行块的标识和组合,进而完成并行计划的生成;结合并行代价模型,完成并行计划的优选;通过调用并行原语完成并行执行,而无需依靠复杂的集中式调度机制。该法能综合应用数据并行、流水线并行和任务并行等方式来完成并行执行。各种多核条件下的实验结果显示,通用测试案例经由自动并行处理后获得了性能提升,并行化效果良好。 (4)提出了XML查询并行化整体解决方案。该方案包含XQuery并行化、XPath并行求值和XML并行解析等技术要点,能自动完成XML查询中各功能部分的并行化处理,充分利用多核资源以提高XML查询的整体性能,支持高效的面向多核计算的XML应用系统的开发。 本文通过在XML查询引擎上完成各项并行化技术的整合,实现了一个XML查询并行化测试平台。在该平台上完成各关键技术的并行化测试评估以及整体并行化测试评估等工作。