一种交互感知的并行查询优化策略研究

*The****FoundationofChinaunderGrantNo.****,****(基金中文完整名称);the****FoundationofChinaunderGrantNo.****,****(基金中文完整名称).[需中英文齐全].Received2000-00,Accepted2000-00.ISSN1673-9418CODENJKYTA8E-mail:[e-mail]omputerScienceandTechnology(00)-0000-00Tel:[phone]DOI:10.3778/j.issn.1673-9418.2012.00.000一种交互感知的并行查询优化策略*AnInteraction-AwareOptimizingStrategyofParallelQueryAbstract:Whileoptimizingdatabaseperformance,parallelquerytechnologycansignificantlyimprovethethroughputandresourceutilizationofthedatabaseserver.Interactionsamongdifferentqueriesthatrunconcur-rentlycanhaveagreatimpactonsystemperformance.However,currentoptimizingstrategiesofparallelqueryoftenonlyfocusonindividualqueriesratherthantheirinteractions.Inordertocapturetheimpactofparallelqueryinteractionsandreducethenegativeinteractions,weproposeaninteraction-awareoptimizingstrategyofparallelquery.Comparedwithothermethods,theexperimentalresultsdemonstratethatouroptimizingstrategycaneffectivelyimprovethedatabaseperformance.Finally,somefuturetrendsinthisareaareprospect-edanddiscussed.Keywords:Parallelquery;Queryinteractions;Performanceoptimization;Performancemodeling摘要:在数据库性能优化时，通过并行查询技术可以显著提高数据库服务器的吞吐率和资源利用率。不同的查询任务并行执行时会产生复杂的交互作用，这些交互作用会对系统性能产生非常巨大的影响。然而，目前的并行查询性能优化策略往往只关注单个查询任务的优化而忽略了彼此交互作用的影响。为了捕获并行查询之间的交互作用，减小交互作用带来的消极影响，提出了一种交互感知的并行查询优化策略。通过实验与其它进行了比较，证明交互感知的优化策略可以较好地提升数据库性能，最后对未来的研究工作进行了展望和讨论。关键词:并行查询；查询交互；性能优化；性能建模文献标识码：A中图分类号：****1引言在数据库系统应用中，查询任务往往占绝大多数，因此查询优化是数据库性能优化的一项最为重要的技术手段。随着数据库变得越来越大，大量业务数据被收集和存储以便用于更加智能的分析和决策，为了提高数据库服务器的资源利用率和吞吐率，并行计算技术被引入到了数据库系统中，通过2JournalofFrontiersofComputerScienceandTechnology计算机科学与探索2012,6(0)并行查询技术，使用更少的时间来完成相同数量的查询任务。因为查询任务并行时共享内存、CPU和磁盘等底层硬件资源，因此并行查询的优化策略比传统数据库的查询优化要复杂的多，在优化时必须考虑底层资源冲突等问题。在本文中我们主要研究并行查询的优化策略，具体来说我们要解决的问题可以描述如下：“给定一组查询任务Q1,Q2,Q3…Qn,随机并发执行访问同一个数据库服务器，假定数据库允许并行执行的查询数即并发级别（MultiProgrammingLevel,MPL）是固定不变的，选择合适的并行查询优化策略，使完成所有查询任务的总时间最小。”针对以上问题，本文提出了一种交互感知的并行查询优化策略。在我们的方法中，和传统查询优化方法的主要区别是我们考虑了并行查询之间的交互作用。实验发现当大量查询任务并发执行共享计算资源和数据的时候会出现非常复杂的交互作用，这些复杂的交互作用将对系统性能产生非常大的影响，并且这些影响可能是积极的，也可能是消极的。因此我们认为在进行并行查询优化时，考虑并行查询之间的交互作用是非常重要的。本文的主要工作有以下几个方面：1、提出了一个影响并行查询任务性能的度量指标：交互成本率（InteractionCostRate,ICR）。2、提出了一种新的交互感知的并行查询优化策略——交互成本最小优先（ICRMF：ICRMini-mumFirst）策略。3、通过对MySQL/TPC-H研究的实验结果证明了ICRMF优化策略的有效性。通过利用ICRMF优化策略，查询任务整体执行时间比SJF算法和FIFO算法减少了很多。本文的主要内容组织如下：第二节介绍了并发查询优化的相关研究工作；第三节通过实验说明了交互作用对查询性能的影响；第四节介绍了交互感知的并行查询优化策略；第五节对并行查询优化策略进行试验评估；最后是对本论文的研究工作进行总结和展望。2相关研究工作2.1查询优化所谓查询优化，就是在查询执行引擎生成一个执行策略的过程中，尽量使查询的总开销和总时间达到最小。一般来说，查询优化可以归纳为四个步骤：(1)将查询转换成某种内部表示，通常是语法树。(2)根据一定的等价变换规则把语法树换成优化(标准)形式。(3)选择底层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。（4）生成查询计划。查询计划是由一系列内部操作组成的，这些内部操作按照一定的次序构成查询的一个执行方案，通常这样的执行方案有很多个，需要对每个执行计划计算代价，从中选择代价最小的一个。目前关于查询优化的研究主要集中在两个方面：SQL查询重写和查询优化算法。查询重写是查询优化器的重要组成部分，它将一个查询表示根据一定的规则，转换为另一个效率更高或更易于优化的查询表达式。如何发现更多而有效的重写规则，也是当前查询优化研究的主要研究内容。对于查询优化算法的研究仍然是查询优化研究的一个难点和热点。在数据库中，最难处理和优化的多连接查询，由于多个关系连接时可以有很多不同的次序，因此对应的查讯执行计划的数目会随着该查询包含的关系个数呈指数级增长，当关系个数很多时，张青峰等：一种交互感知的并行查询优化策略3将导致搜索空间极度膨胀，这将使得传统的搜索算法无能为力。现在越来越多成熟的优化算法被引入到多连接查询优化中来，如爬山算法、模拟退火算法、遗传算法，都在一定程度上提高了查询优化的性能。2.2并行查询优化目前并行查询优化的研究主要是基于两阶段的并行查询优化策略。两阶段优化方法是最有影响的缩减并行查询优化空间的方法。其基本思想是把查询优化划分为两个阶段，第一阶段采用传统的查询优化方法产生一个高效的顺序查询执行计划；第二阶段称为并行化阶段，对第一阶段产生的顺序查询执行计划进行并行化，产生一个优化的并行查询执行计划。两阶段优化能够明显地缩减搜索空间，并且可以直接利用传统的、成熟的顺序优化技术，系统设计人员只需将精力集中于并行化阶段。但两阶段优化技术有一个重要的假设：对最优顺序计划的并行化可以得到最优的并行计划。但我们认为并行查询操作具有不同的处理特性，对资源的竞争使用模式也不同，并行查询之间的交互作用将使得最优顺序计划并行后不再最优。由于并行查询系统的性能因素繁多，因此目前关于并行查询的性能分析和评估大多是通过实验的方法进行。并行查询的性能模型大致可分为：白盒模型和黑盒模型。白盒模型通常需要找出应用程序负载特征(输入)和性能(输出)之间的定量函数关系。数据库系统常见的负载特征包括缓冲池请求、I/O数、查询队列长度、查询到达顺序等等。常见性能指标包括吞吐率、延迟、资源利用率等。然而，由于负载特征和性能输出之间的关系非常复杂，是很难给出明确的函数表达的。黑盒模型把整个系统看成一个黑盒子，不考虑系统的内在逻辑，避开去寻找负载特征和性能输出之间的定量关系，而是通过概率统计、机器学习等方法去预测性能输出。目前，由于黑盒模型自身的特点，越来越受到人们的关注，已广泛应用于一些复杂的数据库系统性能分析和建模中。黑盒模型主要有以下几类：分析模型、基于机器学习的模型、线性回归、回归树、局部加权线性回归、高斯处理等。本文中基于黑盒模型方法对并行查询之间的交互影响进行量化分析，从而避开了对复杂的底层物理系统进行建模。这个模型是从单独运行和两两并发执行查询的样本中推导出来的。2.3查询交互目前，在数据库研究领域对查询优化的研究非常多，但令人意外的是，关于普通意义上的查询交互的研究目前还非常少。在国外一些研究机构，已经有一些学者开始针对查询交互进行一些探索，主要基于查询交互进行延迟预测和性能评估。而在国内，据我们所知，还没有发现有学者进行这方面的研究，我们的工作是国内第一次在并行查询优化研究中引入了查询交互的分析。目前一些具体的研究工作例如多查询的优化、事务组合优化等，都没有考虑这些并行查询以及并发执行中的一些交互影响。这些不考虑交互作用的性能模型通常被用来进行性能预测、容量规划和异常检测等。在本文中，我们将证明被这些研究工作忽略的交互作用会对性能产生非常巨大的影响。3查询交互对系统性能的影响分析为了描述并发查询的交互作用会对数据库系统性能产生巨大的影响,我们用TPC-H测试基准中的查询语句在大小为10G的数据库上进行了一系列实验研究。我们的数据库系统用的是MySQL5.1，4JournalofFrontiersofComputerScienceandTechnology计算机科学与探索2012,6(0)我们的实验运行在双核3.4GHz的IntelXeonCPUs和12G内存，WindowsServer2003的机器。数据库的缓冲池大小设置为2.4G。我们假设相关的数据库配置参数都已经进行了很好的优化。我们用Q1,Q2,…,Q22来表示TPC-H的22个查询类型。查询组合就是包含了不同数量的不同的TPC-H查询类型实例，这些实例中TPC-H规范定义了需要的不同的参数值（这些查询实例可以用TPC-H的QGEN程序生成）。因为TPC-H使用均匀分布的数据和查询参数，因此对一个特定的查询类型来说，不同参数的查询实例的执行时间会有一些微小的差异。因为我们选择了10G的数据库规模，因此为了实验方便我们从TPC-H查询类型中选择10个较小量级的查询类别为研究对象，这10个查询类的执行时间在所有22个查询类中也都是相对较短的。首先，我们用QGEN程序为这个10个查询类分别生成10个实例，然后在10G数据库上单独运行这100个查询语句，记录每个查询的执行时间，从而可以得到每个查询类单独运行时的平均运行时间。表1显示了这些查询类在10G数据库上运行时的平均花费时间。Tj代表了特定的查询类型的10个实例的平均运行时间。Tj将作为我们以后研究交互作用的基准时间。表1：TPC-H查询单独运行时的平均完成时间查询类型平均运行时间Tj（秒）Q3210.76Q4163.43Q6174.92Q7349.77Q8167.90Q10290.45Q1227.25Q1650.49Q1714.88Q19158.73在