自适应的并行关系存储方式选择算法及在线转换技术.pdf

《自适应的并行关系存储方式选择算法及在线转换技术.pdf》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、计算机科学2003V01．30N2-．10(增刊)自适应的并行关系存储方式选择算法及在线转换技术¨AdaptiveChosenAlgorithmofDataDeclusteringandOn—lineConversionStrategyinParallelDatabas8艾春宇1李建中“。高宏2王伟平2(黑龙江大学计算机科学技术学院哈尔滨150080)1(哈尔滨工业大学计算机科学与技术学院哈尔滨150001)2AbstractPhysicaldatabasedesignisimportantforqueryperformancein

2、ashared’nothingparalleldatabasesys—tem．inwhichdataishorizontallypartffionedamongmultipleindependentnodes．Anadaptivedatadeclusteringstrategycanimprovetheefficiencyofparalleldatabasesystem．Previousresearchhasgivenanoptimaldatadeclus—teringstrategyaccordingtothequeryworkl

3、oadforecast·Inthispapertweproposeanadaptivepartitioningkeydynamicselectionalgorithmandon—lineconversionofdatadeclusteringstrategy，AndmakedatadeclusteriRgstrat—egyappropriateforthechargesofdatabasesystem’3queryworkload·sowecanachieveoveralloptimalperforman。ceKeywordsPar

4、alleldatabase。Datadeclustering．Partitioningkeyselection，Repartition1．引言在基于机群系统并行数据库的研究中，并行数据库物理存储方法是一个重要的研究内容。在查询处理过程中，如果数据分布不合理，系统的并行性就得不到充分的发挥，从而降低并行数据库的性能“J。目前．在数据分布策略方面已开展了大量的研究工作，提出了很多有效的并行数据分布方法，如Round—Robin、Hash、Range—Partition、CMD等数据分布方法，这几种数据分布方法都有各自的优缺点。不同的分布

5、方式只针对某一类查询有很好的效率，在实际应用中，一个并行数据库中的所有关系不可能只简单地采用一种分布策略。为了提高并行数据库的查询效率，在进行数据库应用设计过程中，需要根据每个关系上的查询操作类型以及操作发生的频率来为每个关系确定相应的分布存储策略。目前已有的算法主要是在给定的查询负载上自动给出优化的存储方式的算法o。]。但是这些方法获得较好的查询性能的前提是能准确地预测出数据库将要接收的查询的类型和频度。而实际上在大部分应用中，这种预测是很难的。一方面预测的结果不够准确，另一方面数据库在不同时期的查询负载变化也很大。如果预测与实际

6、查询的情况差距太大，或是应用发生很大的变化，那么最初优化的数据库物理设计也会导致极低的查询执行效率。既然在最初设计关系的存储方式时，很难预知这组关系之上的查询操作类型以及操作发生的频率及其变化，那么静态的关系存*)本文研究得到了国家863计划(2002AA444110)基金支持·124·储方式就很难适应不断变化的查询需求。通过统计系统的查询负载，动态地调整关系的存储方式以适应查询需求，将使数据库具有更好的整体查询效率。本文的贡献在于提出了根据数据库系统的查询负载动态地选择关系划分属性的算法，并介绍了关系存储方式的在线转换策略，使得关

7、系能够根据数据库查询的特点改变其存储方式，从而提高数据库总体性能。本文第2节首先分析了并行数据库关系的划分方式对各种查询性能的影响，给出了查询代价模型及查询代价的计算方法。在第3节中，讨论了如何统计数据库查询信息，并给出了根据查询统计信息计算合适的关系划分属性的算法。在第4节中，介绍了三种并行关系存储方式转换的实现策略，通过分析可以看出在线的关系存储方式转换策略具有更好的性能。最后对本文的工作进行了总结。2．查询代价模型基于机群的并行数据库执行查询时，经常需要重分布数据，这会带来节点机之间的通讯开销，这种通讯开销极大地影响了查询的执

8、行效率。并行数据库的关系存储方式的设计目标就是尽量减少这种通讯开销[3]。因此对于基于机群的并行数据库，以通讯开销来定义查询的执行代价是一种直观而又准确的方法。连接和聚集操作是两类常用而且费时的查询操作，关系的分布属性的选择对于这两种