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

1、一种交互感知的并行查询优化策略研究ISSN 1673-9418 CODEN JKYTA8 E-mail: fcstJournal of Frontiers of Computer Science and Technology http:/www.ceaj.org1673-9418/2012/06(00)-0000-00 Tel: +86-10-51616056DOI: 10.3778/j.issn.1673-9418.2012.00.000 一种交互感知的并行查询优化策略*An Interaction-Aware Optimizing Strategy of Parallel QueryAbs

2、tract: While optimizing database performance, parallel query technology can significantly improve the throughput and resource utilization of the database server. Interactions among different queries that run concurrently can have a great impact on system performance. However, current optimizing stra

3、tegies of parallel query often only focus on individual queries rather than their interactions. In order to capture the impact of parallel query interactions and reduce the negative interactions, we propose an interaction-aware optimizing strategy of parallel query. Compared with other methods, the

4、experimental results demonstrate that our optimizing strategy can effectively improve the database performance. Finally, some future trends in this area are prospected and discussed.Key words: Parallel query; Query interactions; Performance optimization; Performance modeling 摘 要: 在数据库性能优化时，通过并行查询技术可

5、以显著提高数据库服务器的吞吐率和资源利用率。不同的查询任务并行执行时会产生复杂的交互作用，这些交互作用会对系统性能产生非常巨大的影响。然而，目前的并行查询性能优化策略往往只关注单个查询任务的优化而忽略了彼此交互作用的影响。为了捕获并行查询之间的交互作用，减小交互作用带来的消极影响，提出了一种交互感知的并行查询优化策略。通过实验与其它进行了比较，证明交互感知的优化策略可以较好地提升数据库性能，最后对未来的研究工作进行了展望和讨论。 关键词: 并行查询；查询交互；性能优化；性能建模文献标识码：A 中图分类号：*1 引言在数据库系统应用中，查询任务往往占绝大多数，因此查询优化是数据库性能优化的一项最

6、为重要的技术手段。随着数据库变得越来越大，大量业务数据被收集和存储以便用于更加智能的分析和决策，为了提高数据库服务器的资源利用率和吞吐率，并行计算技术被引入到了数据库系统中，通过并行查询技术，使用更少的时间来完成相同数量的查询任务。因为查询任务并行时共享内存、CPU和磁盘等底层硬件资源，因此并行查询的优化策略比传统数据库的查询优化要复杂的多，在优化时必须考虑底层资源冲突等问题。在本文中我们主要研究并行查询的优化策略，具体来说我们要解决的问题可以描述如下：“给定一组查询任务Q1,Q2,Q3Qn,随机并发执行访问同一个数据库服务器，假定数据库允许并行执行的查询数即并发级别（Multi Progra

7、mming Level,MPL）是固定不变的，选择合适的并行查询优化策略，使完成所有查询任务的总时间最小。”针对以上问题，本文提出了一种交互感知的并行查询优化策略。在我们的方法中，和传统查询优化方法的主要区别是我们考虑了并行查询之间的交互作用。实验发现当大量查询任务并发执行共享计算资源和数据的时候会出现非常复杂的交互作用，这些复杂的交互作用将对系统性能产生非常大的影响，并且这些影响可能是积极的，也可能是消极的。因此我们认为在进行并行查询优化时，考虑并行查询之间的交互作用是非常重要的。本文的主要工作有以下几个方面：1、 提出了一个影响并行查询任务性能的度量指标：交互成本率（Interaction

8、 Cost Rate, ICR）。2、 提出了一种新的交互感知的并行查询优化策略交互成本最小优先（ICRMF：ICR Minimum First）策略。3、 通过对MySQL/TPC-H研究的实验结果证明了ICRMF优化策略的有效性。通过利用ICRMF优化策略，查询任务整体执行时间比SJF算法和FIFO算法减少了很多。本文的主要内容组织如下：第二节介绍了并发查询优化的相关研究工作；第三节通过实验说明了交互作用对查询性能的影响；第四节介绍了交互感知的并行查询优化策略；第五节对并行查询优化策略进行试验评估；最后是对本论文的研究工作进行总结和展望。2 相关研究工作2.1 查询优化 所谓查询优化，就是

9、在查询执行引擎生成一个执行策略的过程中，尽量使查询的总开销和总时间达到最小。一般来说，查询优化可以归纳为四个步骤：(1)将查询转换成某种内部表示，通常是语法树。(2)根据一定的等价变换规则把语法树换成优化(标准)形式。(3)选择底层的操作算法。对于语法树中的每一个操作需要根据存取路径、数据的存储分布、存储数据的聚簇等信息来选择具体的执行算法。（4）生成查询计划。查询计划是由一系列内部操作组成的，这些内部操作按照一定的次序构成查询的一个执行方案，通常这样的执行方案有很多个，需要对每个执行计划计算代价，从中选择代价最小的一个。目前关于查询优化的研究主要集中在两个方面：SQL查询重写和查询优化算法。

10、查询重写是查询优化器的重要组成部分，它将一个查询表示根据一定的规则，转换为另一个效率更高或更易于优化的查询表达式。如何发现更多而有效的重写规则，也是当前查询优化研究的主要研究内容。对于查询优化算法的研究仍然是查询优化研究的一个难点和热点。在数据库中，最难处理和优化的多连接查询，由于多个关系连接时可以有很多不同的次序，因此对应的查讯执行计划的数目会随着该查询包含的关系个数呈指数级增长，当关系个数很多时，将导致搜索空间极度膨胀，这将使得传统的搜索算法无能为力。现在越来越多成熟的优化算法被引入到多连接查询优化中来，如爬山算法、模拟退火算法、遗传算法，都在一定程度上提高了查询优化的性能。2.2 并行查

11、询优化 目前并行查询优化的研究主要是基于两阶段的并行查询优化策略。两阶段优化方法是最有影响的缩减并行查询优化空间的方法。其基本思想是把查询优化划分为两个阶段，第一阶段采用传统的查询优化方法产生一个高效的顺序查询执行计划；第二阶段称为并行化阶段，对第一阶段产生的顺序查询执行计划进行并行化，产生一个优化的并行查询执行计划。两阶段优化能够明显地缩减搜索空间，并且可以直接利用传统的、成熟的顺序优化技术，系统设计人员只需将精力集中于并行化阶段。但两阶段优化技术有一个重要的假设：对最优顺序计划的并行化可以得到最优的并行计划。但我们认为并行查询操作具有不同的处理特性，对资源的竞争使用模式也不同，并行查询之间

12、的交互作用将使得最优顺序计划并行后不再最优。由于并行查询系统的性能因素繁多，因此目前关于并行查询的性能分析和评估大多是通过实验的方法进行。并行查询的性能模型大致可分为：白盒模型和黑盒模型。白盒模型通常需要找出应用程序负载特征( 输入) 和性能( 输出) 之间的定量函数关系。数据库系统常见的负载特征包括缓冲池请求、I/O数、查询队列长度、查询到达顺序等等。常见性能指标包括吞吐率、延迟、资源利用率等。然而，由于负载特征和性能输出之间的关系非常复杂， 是很难给出明确的函数表达的。黑盒模型把整个系统看成一个黑盒子，不考虑系统的内在逻辑，避开去寻找负载特征和性能输出之间的定量关系，而是通过概率统计、机器

13、学习等方法去预测性能输出。目前，由于黑盒模型自身的特点，越来越受到人们的关注，已广泛应用于一些复杂的数据库系统性能分析和建模中。 黑盒模型主要有以下几类：分析模型、基于机器学习的模型、线性回归、回归树、局部加权线性回归、高斯处理等。本文中基于黑盒模型方法对并行查询之间的交互影响进行量化分析，从而避开了对复杂的底层物理系统进行建模。这个模型是从单独运行和两两并发执行查询的样本中推导出来的。2.3 查询交互 目前，在数据库研究领域对查询优化的研究非常多，但令人意外的是，关于普通意义上的查询交互的研究目前还非常少。在国外一些研究机构，已经有一些学者开始针对查询交互进行一些探索，主要基于查询交互进行延

14、迟预测和性能评估。而在国内，据我们所知，还没有发现有学者进行这方面的研究，我们的工作是国内第一次在并行查询优化研究中引入了查询交互的分析。目前一些具体的研究工作例如多查询的优化、事务组合优化等，都没有考虑这些并行查询以及并发执行中的一些交互影响。这些不考虑交互作用的性能模型通常被用来进行性能预测、容量规划和异常检测等。在本文中，我们将证明被这些研究工作忽略的交互作用会对性能产生非常巨大的影响。3 查询交互对系统性能的影响分析为了描述并发查询的交互作用会对数据库系统性能产生巨大的影响,我们用TPC-H测试基准中的查询语句在大小为10G的数据库上进行了一系列实验研究。我们的数据库系统用的是MySQ

15、L5.1，我们的实验运行在双核3.4GHz的Intel Xeon CPUs和12G内存，WindowsServer2003的机器。数据库的缓冲池大小设置为2.4G。我们假设相关的数据库配置参数都已经进行了很好的优化。我们用Q1,Q2,Q22来表示TPC-H的22个查询类型。查询组合就是包含了不同数量的不同的TPC-H查询类型实例，这些实例中TPC-H规范定义了需要的不同的参数值（这些查询实例可以用TPC-H的QGEN程序生成）。因为TPC-H使用均匀分布的数据和查询参数，因此对一个特定的查询类型来说，不同参数的查询实例的执行时间会有一些微小的差异。因为我们选择了10G的数据库规模，因此为了实验

16、方便我们从TPC-H查询类型中选择10个较小量级的查询类别为研究对象，这10个查询类的执行时间在所有22个查询类中也都是相对较短的。首先，我们用QGEN程序为这个10个查询类分别生成10个实例，然后在10G数据库上单独运行这100个查询语句，记录每个查询的执行时间，从而可以得到每个查询类单独运行时的平均运行时间。表1显示了这些查询类在10G数据库上运行时的平均花费时间。Tj代表了特定的查询类型的10个实例的平均运行时间。Tj将作为我们以后研究交互作用的基准时间。表1：TPC-H查询单独运行时的平均完成时间查询类型平均运行时间Tj（秒）Q3210.76Q4163.43Q6174.92Q7349.

17、77Q8167.90Q10290.45Q1227.25Q1650.49Q1714.88Q19158.73在下一节中，我们将分别通过实验来描述不同类型的查询交互，以及不同并发级别产生的交互作用对查询性能的影响。3.1 两两查询之间的交互分析 为了更好地描绘查询之间是如何交互的，我们首先来研究两个查询之间的交互作用。我们选择TPC-H中运行时间较短的10个查询类，执行所有查询类之间的唯一的两两组合，共有n*(n+1)/2 = 55个查询组合。分别执行55个查询组合，并记录相应的查询执行时间的变化。用Ti表示Qi单独运行时的执行时间，Ti/j表示Qi与Qj并发时的执行时间，则可以Ti/j来表示Qi与

18、Qj并发时的变化。Ti/j = Ti/j Ti 如果Ti/j是正的，说明速度变慢了，如果是负值，说明速度变快了。需要注意的是两两查询之间的交互不是对称的 (Ti/j Tj/i)。为了定量的分析并行交互成本，我们定义了一个新的度量指标：并行交互成本率ICR(Interaction Cost Rate)：通过实验，我们可以得到10个查询类两两查询之间的并行交互成本率。表2列出了几对两两查询交互的并行交互成本率：表2：两两交互的并行交互成本率序号QiQjTi/jTj/iICR(i/j)ICR(j/i)1Q3Q72Q4Q83Q6Q144Q7Q195Q10Q16实验分析：当Q3和Q7一起并行时，Q3获得

19、了10秒的加速，而Q7的执行时间却增加了30秒。当Q6和Q14一起运行时，他们都会获得平均10秒的加速。这是因为它们的查询执行计划都主要是进行事实表的顺序扫描。当Q19和Q7并发运行时，他们的运行时间分别增加了大约50秒和30秒。由此可见，并行查询之间的交互作用会对查询性能产生非常显著的影响，有时这些影响会是积极的，但有时也会是消极的。而交互作用的产生又是非常复杂的，其原因也是多种多种多样的。例如，一个查询Q1会把数据加载到缓冲池中，然后一个并行查询Q2会用到这个数据，那就会产生积极的交互作用。而相对应的，在硬件资源使用上的冲突会使Q1和Q2会互相竞争，例如对CPU、内存或者数据库系统内部资源

20、例如存取锁的使用上产生的冲突，都会产生消极的交互作用。3.2 高并行级别的查询交互分析 在分析了两两并行查询之间的交互影响之后，我们将对更高级别（并行级别大于2）的查询交互进行研究和分析。我们用MPL（multiprogramming level）来表示数据库系统的并行级别，MPL是指在任何时候在系统中并发执行的查询语句的数量。那么我们将系统中并行执行的一组查询定义为一个查询组合Mi，我们假设有t个查询类型，那么查询组合Mi可以被表示为一个矢量，这儿Nij是查询组合Mi中查询类型Qj的实例数量，我们把组合Mi中的查询类型Qj的平均运行时间表示为Aij。从以上定义我们可以知道：Ni1+Ni2 +

21、 Ni3 + +Nit = M 我们通过不同的实验来分析高并行级别情况下查询交互对查询组合中每个查询任务的的完成时间的影响。首先，我们对M=5的两个查询类型的不同组合的交互作用进行分析，如表3所示。在表3中我们依次减少Q19的实例数量，同时增加Q6的实例数量，从而观察Q6和Q19的执行时间的变化情况。表3：两个查询类型的不同组合的交互作用分析MixQ6（Nij）Q19（Nij）Q6（Aij）Q19（Aij）M1050M214M323M432M541M6500从以上数据可以看出，即使只有两个查询类型时，仅仅用一个查询类型的实例来替换另一个查询类型的实例也会显著地改变查询执行时间，这也进一步证明了

22、查询交互的重要性。接下来，我们将分析多种查询类型的组合中交互作用。在表4中我们对不同查询组合中其它实例的变化对同一查询执行时间的影响。表4：不同查询组合对同一查询的不同影响MixQ4（Nij）Q7（Nij）Q16（Nij）Q16（Aij）M7041172.49M8131140.24M9221129.62M10311M11401在表4中，首先Q16的完成时间因为一个Q4的实例的加入而减少，然后当我们继续增加Q4的实例数量和减少Q7的实例数量时，Q16完成时间出现不规则的变化，有降低也有增加。这也说明，并行查询的交互作用是相当复杂的，在查询组合中的一个小的改变有时会对性能有巨大的影响，但这些可能是

23、非常难预测的。下面，我们将对多种查询类型的组合进行试验，如表5所示。我们选择4个查询类型的实例进行变化组合，保持组合的实例数量M=5不变，即保持并行级别不变。表5：不同查询组合的实例数量和平均运行时间MixQ3Q7Q10Q16NijAijNijAijNijAijNijAijM121386.851560.903425.180386.85M131352.111501.962380.411352.11M141332.051469.64003332.05M15在表5中我们可以得到以下几个方面的结论：一个包含了多种查询类的组合并行运行时可能既包含积极的交互，也包含消极的交互。一些查询类，在并行环境下他们

24、的查询执行时间表现出更多的不确定性，他们对一起并行的其他查询的影响更加的敏感。相反，其它一些查询类就更加的稳定，这个查询可能就是一个简单的查询任务，例如仅仅包含一个数据表的扫描和一个轻量级的合计。以上这些实验也说明了除非我们能够对查询组合中的并行交互影响进行建模，否则我们不可能得到最优化的查询性能，如果只关注单独的查询类型而忽略并行交互作用，我们将不能够得出关于性能的准确的结论。因此，我们认为开发基于查询组合的交互作用的性能模型对我们更好地进行性能优化是非常重要的。4 交互感知的并行查询优化策略通过第三节的分析，我们知道了并行查询的交互对性能有着非常大的影响。因此，为了实现最优化的并行查询性能

25、，我们下一步将基于查询交互进行性能分析，并提出一个交互感知的性能优化策略，使并行任务能够按照一定的顺序执行，从而达到任务完成总时间最小的目标。查询任务完成的总时间可以定义为从第一个查询开始启动到所有查询都完成时总共消耗的时间。4.1 交互成本最低优先算法 我们已知并行负载W由N个查询任务Q1,Q2,Q3Qn构成，每个查询所属的TPC-H查询类型是已知的，数据库的并发级别为M。通过分析我们可以知道在并行过程中，同时只有M个查询在执行，这M个查询就构成了一个查询组合mi，由所有的mi构成了一个查询组合集X=m1,m2,mi。此外，我们做了以下两个假设：1、所有特定类型的查询都有着相同的性能；2、数

26、据库可以以任意的顺序执行队列中的查询任务。查询之间的优先级限制可以在系统外进行强行控制。基于以上分析和假设，我们的性能优化算法的主要目标就是优先执行交互成本低的查询组合，避免执行交互成本高的查询组合，从而使整个并行任务的交互成本最低，也就是任务总执行时间最少。优化策略的执行步骤可以描述如下： 1) 从N个查询任务中选择M个查询组成一个并行交互成本最小的查询组合Mmin启动并行任务；2) 在任意一个查询Qmin最先结束时，得到Mmin中的其他（M-1）个查询任务；3) 对每一个等待队列中的查询，计算其与正在执行的（M-1）个查询组成的查询组合的并行交互成本；4) 获得新的并行交互成本最小的查询Q

27、next；5) 重新从2）开始循环执行；6) 以此类推，直到完成所有的查询任务。以上算法用形式化语言可以表示如下：输入：并行负载W，由N个查询组成；输出：并行交互成本最小优先的查询执行顺序。Algorithm ICRMF（W）Begin selectMminFromW(W); runMmin(); while(Qmin is end) do runQM = getRunQueryMix(M-1)； for each Qi in arrival queue do ICR(i) = EstimateICR(Qi,runQM); end for sortArrivalQuery(ICR with r

28、unQM ); getTheMinICRQueryToAdd(); end WhileEnd要实现以上的性能优化算法，我们要选择交互成本最小的查询组合就必须选择一个适合的性能模型，对查询组合的交互成本进行建模分析。对不同的并发级别需要进行分别建模，当并发级别为2时，我们可以直接用实验数据进行分析；当并发级别大于2时，我们需要建立更复杂的性能模型，从而能够更好地估计并行查询组合的交互成本。而对于高级别的并发查询交互的性能模型，可以从单独（非并发）运行和两两并发执行的样本中推导出来。4.2 并行查询交互的性能模型 在本节中，我们将探讨如何对高并行级别的查询交互建立性能模型。因为查询交互作用的产生因

29、素是非常复杂的，为了避免建立如此复杂的模型而需要的监控需求，我们采用了实验驱动的黑盒模型。实验驱动的模型使我们能够粗略地估计并行状态下查询之间是如何进行交互的。当一个新的查询Qj加入到一个查询组合Mi中时，由于Qj的加入而产生的并行交互成本率可以计算如下：ICR = Ni1 Ni2 Ni3+ + Nit = 其中，Tj是Qj在单独执行时的运行时间，而Aij是Qj在Mi中执行时的平均运行时间，Nij是组合Mi中Qj的实例数量。有很多著名的模型结构，例如线性回归、回归树、局部加权线性回归、高斯处理等等，都可以用来描述并行查询之间的交互作用。此外，利用机器学习技术可以对查询交互进行性能建模。在我们的

30、研究中，我们发现多元线性回归模型和机器学习是一个非常适合对查询组合的性能进行描述的模型结构，因此下一步我们将利用多元线性回归模型和机器学习技术进行相关方面的深入研究。5 实验评估与分析本章将交互感知的优化(Interaction Cost Minimum First, ICMF)算法和传统数据库的最短时间优先(Shortest Job First, SJF)算法和先到先服务(First Come First Served, SCSF)算法进行对比实验。首先介绍了实验环境, 然后给出实验结果, 并进行了结果的评估和分析。5.1 实验环境实验使用的硬件配置是：Intel Core 2 Pentiu

31、m 4 Duo CPU 2.83 GHz，12 GB 内存。操作系统为Windows 2008，数据库采用的是开源的MySQL5.0，使用的存储引擎是MyISAM，有10G大小的数据。我们用C+语言实现了我们的优化算法，作为一个独立的组件来进行查询任务的优化调度，调度组件在查询任务启动之前工作，和数据库服务器在逻辑上是独立的。5.2 实验分析我们从TPC-H中选择了6个运行时间较短的查询类型，每个查询类型生成了30个查询语句实例，总共180个查询语句。假设180个查询语句按照每个类型依次加载n个实例的顺序到达，优化器提前可以知道即将到来的30个查询任务。实验一：将数据库的并发级别MPL分别设置为10