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

计算机科学２００３Ｖ０１．３０Ｎ２－．１０（增刊）自适应的并行关系存储方式选择算法及在线转换技术¨ＡｄａｐｔｉｖｅＣｈｏｓｅｎＡｌｇｏｒｉｔｈｍｏｆＤａｔａＤｅｃｌｕｓｔｅｒｉｎｇａｎｄＯｎ—ｌｉｎｅＣｏｎｖｅｒｓｉｏｎＳｔｒａｔｅｇｙｉｎＰａｒａｌｌｅｌＤａｔａｂａｓ８艾春宇１李建中“。

高宏２王伟平２（黑龙江大学计算机科学技术学院哈尔滨１５００８０）１（哈尔滨工业大学计算机科学与技术学院哈尔滨１５０００１）２ＡｂｓｔｒａｃｔＰｈｙｓｉｃａｌｄａｔａｂａｓｅｄｅｓｉｇｎｉｓｉｍｐｏｒｔａｎｔｆｏｒｑｕｅｒｙｐｅｒｆｏｒｍａｎｃｅｉｎａｓｈａｒｅｄ’ｎｏｔｈｉｎｇｐａｒａｌｌｅｌｄａｔａｂａｓｅｓｙｓ—ｔｅｍ．ｉｎｗｈｉｃｈｄａｔａｉｓｈｏｒｉｚｏｎｔａｌｌｙｐａｒｔｆｆｉｏｎｅｄａｍｏｎｇｍｕｌｔｉｐｌｅｉｎｄｅｐｅｎｄｅｎｔｎｏｄｅｓ．Ａｎａｄａｐｔｉｖｅｄａｔａｄｅｃｌｕｓｔｅｒｉｎｇｓｔｒａｔｅｇｙｃａｎｉｍｐｒｏｖｅｔｈｅｅｆｆｉｃｉｅｎｃｙｏｆｐａｒａｌｌｅｌｄａｔａｂａｓｅｓｙｓｔｅｍ．Ｐｒｅｖｉｏｕｓｒｅｓｅａｒｃｈｈａｓｇｉｖｅｎａｎｏｐｔｉｍａｌｄａｔａｄｅｃｌｕｓ—ｔｅｒｉｎｇｓｔｒａｔｅｇｙａｃｃｏｒｄｉｎｇｔｏｔｈｅｑｕｅｒｙｗｏｒｋｌｏａｄｆｏｒｅｃａｓｔ・Ｉｎｔｈｉｓｐａｐｅｒｔｗｅｐｒｏｐｏｓｅａｎａｄａｐｔｉｖｅｐａｒｔｉｔｉｏｎｉｎｇｋｅｙｄｙｎａｍｉｃｓｅｌｅｃｔｉｏｎａｌｇｏｒｉｔｈｍａｎｄｏｎ—ｌｉｎｅｃｏｎｖｅｒｓｉｏｎｏｆｄａｔａｄｅｃｌｕｓｔｅｒｉｎｇｓｔｒａｔｅｇｙ，ＡｎｄｍａｋｅｄａｔａｄｅｃｌｕｓｔｅｒｉＲｇｓｔｒａｔ—ｅｇｙａｐｐｒｏｐｒｉａｔｅｆｏｒｔｈｅｃｈａｒｇｅｓｏｆｄａｔａｂａｓｅｓｙｓｔｅｍ’３ｑｕｅｒｙｗｏｒｋｌｏａｄ・ｓｏｗｅｃａｎａｃｈｉｅｖｅｏｖｅｒａｌｌｏｐｔｉｍａｌｐｅｒｆｏｒｍａｎ。

ｃｅＫｅｙｗｏｒｄｓＰａｒａｌｌｅｌｄａｔａｂａｓｅ。

Ｄａｔａｄｅｃｌｕｓｔｅｒｉｎｇ．Ｐａｒｔｉｔｉｏｎｉｎｇｋｅｙｓｅｌｅｃｔｉｏｎ，Ｒｅｐａｒｔｉｔｉｏｎ１．引言在基于机群系统并行数据库的研究中，并行数据库物理存储方法是一个重要的研究内容。

在查询处理过程中，如果数据分布不合理，系统的并行性就得不到充分的发挥，从而降低并行数据库的性能“Ｊ。

目前．在数据分布策略方面已开展了大量的研究工作，提出了很多有效的并行数据分布方法，如Ｒｏｕｎｄ—Ｒｏｂｉｎ、Ｈａｓｈ、Ｒａｎｇｅ—Ｐａｒｔｉｔｉｏｎ、ＣＭＤ等数据分布方法，这几种数据分布方法都有各自的优缺点。

不同的分布方式只针对某一类查询有很好的效率，在实际应用中，一个并行数据库中的所有关系不可能只简单地采用一种分布策略。

为了提高并行数据库的查询效率，在进行数据库应用设计过程中，需要根据每个关系上的查询操作类型以及操作发生的频率来为每个关系确定相应的分布存储策略。

目前已有的算法主要是在给定的查询负载上自动给出优化的存储方式的算法ｏ。

］。

但是这些方法获得较好的查询性能的前提是能准确地预测出数据库将要接收的查询的类型和频度。

而实际上在大部分应用中，这种预测是很难的。

一方面预测的结果不够准确，另一方面数据库在不同时期的查询负载变化也很大。

如果预测与实际查询的情况差距太大，或是应用发生很大的变化，那么最初优化的数据库物理设计也会导致极低的查询执行效率。

既然在最初设计关系的存储方式时，很难预知这组关系之上的查询操作类型以及操作发生的频率及其变化，那么静态的关系存＊）本文研究得到了国家８６３计划（２００２ＡＡ４４４１１０）基金支持・１２４・储方式就很难适应不断变化的查询需求。

通过统计系统的查询负载，动态地调整关系的存储方式以适应查询需求，将使数据库具有更好的整体查询效率。

本文的贡献在于提出了根据数据库系统的查询负载动态地选择关系划分属性的算法，并介绍了关系存储方式的在线转换策略，使得关系能够根据数据库查询的特点改变其存储方式，从而提高数据库总体性能。

本文第２节首先分析了并行数据库关系的划分方式对各种查询性能的影响，给出了查询代价模型及查询代价的计算方法。

在第３节中，讨论了如何统计数据库查询信息，并给出了根据查询统计信息计算合适的关系划分属性的算法。

在第４节中，介绍了三种并行关系存储方式转换的实现策略，通过分析可以看出在线的关系存储方式转换策略具有更好的性能。

最后对本文的工作进行了总结。

２．查询代价模型基于机群的并行数据库执行查询时，经常需要重分布数据，这会带来节点机之间的通讯开销，这种通讯开销极大地影响了查询的执行效率。

并行数据库的关系存储方式的设计目标就是尽量减少这种通讯开销［３］。

因此对于基于机群的并行数据库，以通讯开销来定义查询的执行代价是一种直观而又准确的方法。

连接和聚集操作是两类常用而且费时的查询操作，关系的分布属性的选择对于这两种操作执行效率的影响最大。

例如当连接算法采用ｈａｓｈＪｏｉｎ算法时，如果连接的两个关系都在连接属性上ｈａｓｈ分布，那么连接操作在各个节点上本地执行，没有额外的通讯开销，这是最理想的情况ｉ如果有一个关系不是在连接属性上划分的，那么算法就需要在各个节点机上重新分布数据，查询执行的性能就会下降。

查询中其它操作的执行一般不会带来额外的通讯开销，因此，本文只对连接和聚集操作的执行代价进行分析和定义。

定义１设数据库模式Ｄ为一组关系模式的集合，表示为Ｄ｛Ｒ．ｆＲ，为关系模式｝。

在数据库Ｄ上有操作集合Ｑ（Ｏ。

｜０，∈｛连接，聚集｝｝，则Ｑ在Ｄ上的查询代价为：Ｃｏｓｔ（Ｑ。

Ｄ）一２５Ｃｏｓｔ（０，，Ｄ）Ｏｉ∈口其中Ｃｏｓｔ（０．，Ｄ）表示每个操作的代价，同文［３］一样，该代价即为执行该操作需要的通讯开销。

在基于机群的并行数据库中，存储方式的选择决定了各个操作的代价。

我们下面讨论存储方式与操作代价之间的关系。

首先看连接操作，我们使用的算法为ＨａｓｈＪｏｉｎ算法“Ｊ。

定义２在并行数据库模式中，关系Ｒ；、Ｒ．分布在ｐ个处理机上，ｓＲ，ｔＴ，）、ＳＲｊ‘Ｔ，）分剐表示关系Ｒ，、Ｒ，的分布方式，Ｔ，、Ｔ，表示Ｒ。

、Ｒ，的划分属性。

则将Ｒ．在属性Ａ和Ｒ．在属性Ｂ上的连接代价定义为：Ｊｏｉｎ—Ｃｏｓｔ（Ｒ．（Ａ），Ｒｊ（Ｂ））一ｒ０（。

）ｌＩＲ，ｌ×１ｔ。

ｌ×Ｐ，＋ｌＲ，Ｉ×｝ｔ。

ｌ×ｎ（６），．、ｌ｝Ｒ，ｌ×Ｉｔ。

Ｉ×Ｂ（ｃ）…【ＩＲ，１×Ｉｔ，，ｌ×ｎ（ｄ）其中，｛Ｒ，ｌ、ｌＲ．Ｉ表示关系Ｒ．、Ｒ，的元组数…ｔｔｏ表示Ｒ．和Ｒ，中的一个元组包含的字节数，Ｂ、Ｐ，表示Ｒ。

和Ｒ．中参加连接运算的元组数占总元组数的百分比（Ｂ、ｎ是查询优化时的估计值）。

当ＳＲ。

（Ｔ，）、ＳＲ．（Ｔ，）均为Ｈａｓｈ分布，Ｔ，一Ａ，Ｔ，一Ｂ，并且Ｈａｓｈ函数相同；或者ＳＲ．（Ｔ．）、ＳＲ，（Ｔ，）均为Ｒａｎｇｅ—Ｐａｒｔｉｔｉｏｎ分布，Ｔｉ＝Ａ，Ｔ，一Ｂ，并且值域的划分区问相同时，则Ｊｏｉｎ—Ｃｏｓｔ按照情况（ａ）计算；当Ｔ．≠Ａ且Ｔ．≠Ｂ按照情况（ｂ）计算；当Ｔ．≠Ａ且Ｔ，＝Ｂ按照情况（ｃ）计算；当Ｔ．一Ａ且Ｔ，≠Ｂ按照情况（ｄ）计算；当ＳＲ，（Ｔ，）、ＳＲ．（Ｔ，）均为Ｈａｓｈ分布，Ｔ．一Ａ．Ｔ．一Ｂ，但是Ｈａｓｈ函数不同；或者ＳＲ，（Ｔ．）、ＳＲ．（Ｔ．）均为Ｒａｎｇｅ—Ｐａｒｔｉｔｉｏｎ分布，Ｔ．一Ａ，Ｔ．一Ｂ，但是值域的划分区间不同时，则Ｊｏｉｎ—Ｃｏｓｔ按照情况（ｃ）或（ｄ）计算。

我们为关系的每个属性定义一个特征量。

定义５关系Ｒ中属性Ａ的特征量为ｎｃＡ，一｛：：爻：柔耋羹主管笛募票譬毽，ｔｚ，则上面式（１）可以简化表示为：Ｊｏｉｎ—Ｃｏｓｔ（Ｒ，（Ａ），Ｒ，（Ｂ））一｜Ｒ，ｌ×ｌｔ。

ｌ×Ｒ×ｈ（Ａ）＋ＩＲ，ｌ×ｌｔ，，Ｉ×ｎ×ｈ（Ｂ）‘３）其中ｈ（Ａ）、ｈ【Ｂ）分别为属性Ａ、Ｂ的特征量。

由式（３）可以看出，连接代价Ｊｏｉｎ—Ｃｏｓｔ（Ｒ，（Ａ），Ｒ，【Ｂ））由两部分组成。

其中第一个数据项为关系足的连接代价，另一个数据项为关系Ｒ，的连接代价。

两个数据项之间是相互独立的，可以分别进行计算。

下面给出聚集操作的通讯代价，我们使用的聚集算法是Ｒｅｐａｒｔｉｔｉｏｎ算法ｏ］。

本文讨论聚集是分组聚集，并且聚集操作只涉及一个关系。

聚集的分组属性可能是一个属性也可能是一组属性。

当分组属性集包括关系的分布属性时，聚集操作不需要重新分布数据或合并结果，没有通讯开销，否则聚集操作需要重新分布数据，而产生通讯开销。

我们用ＧｒｏｕｐＳｅｔ（ｐ）表示聚集操作Ｐ中的分组属性集合。

在给出聚集操作代价之前，先对ＧｒｏｕｐＳｅｔ（ｐ）的特征量进行定义。

定义４分组属性集合ＧｒｏｕｐＳｅｔ（ｐ）的特征量为：ｇ（ＧｒｏｕｐＳｅｔ（Ｐ））＝ｆ０ｉｆ（ＧｒｏｕｐＳｅｔ（ｐ）包括划分属性）…１１ｉｆ（ＧｒｏｕｐＳｅｔ（ｐ）不包括划分属性）…定义５关系Ｒ．上的聚集操作的通讯代价：Ａｇｇｒ＿Ｃｏｓｔ（Ｐ，Ｒ，）一ＩＲ，ｌ×ｌｔ。

ｌ×ｎ×ｇ（ＧｒｏｕｐＳｅｔ（ｐ））（５）我们将式（ｚ）和式（４）用统一的形式表示。

定义６关系Ｒ，上的操作相关的属性或属性集用Ｏ—Ｓｅｔ（Ａ）表示．则其特征量为：Ｓ（０一Ｓｅｔ（Ａ））一』０ｉｆ（０一Ｓｅｔ（Ａ）包括划分属性）ｌ１ｉｆ（０一Ｓｅｔ（Ａ）不包括划分属性）…由于一个操作的通讯代价等于它涉及的关系的通讯代价的和，而且各关系通讯代价之间是相互独立的，那么Ｑ在Ｄ上的查询的通讯代价就可以定义为Ｃｏｓｔ（Ｑ．Ｄ）一厶Ｃｏｓｔ（Ｏ。

，Ｄ）一２５２５Ｃｏｓｔｏｉ∈ＱＯｉ∈ｑＲ∈Ｄ（０，，Ｒ．）一２５厶Ｃｏｓｔ（Ｏ．，Ｒ．）Ｒｊ∈ＩＸ）ｉ∈Ｑ其中Ｃｏｓｔ（Ｏ，，Ｒ，）为操作Ｏ．在关系Ｒ，上的通讯代价。

我们要使Ｃｏｓｔ（Ｑ，Ｄ）最小，只需对每个关系Ｒ，求五Ｃｏｓｔ（ｏ。

，Ｒ，）的最小值（操作在其不涉及的关系上的代价为０）。

求这个最小值的过程也就是为该关系选择划分属性的过程。

０一Ｓｅｔ（Ａ．）是操作Ｏ．的操作属性集，ｍ咔２＿ｑ；ｃＯＳｔ（ｏｔ，Ｒ，）一毫ＩＲ，Ｊ×ＪｔｆＪｊ×・１２５・ｐ，ＸＳ（０一Ｓｅｔ（Ａ，））一１Ｒｊｌ×１ｔＴｊｌｘ龟ＲＸＳ（０～ｓｅｔ（Ａ，））对于每个关系Ｒ，来说，ｆＲ，』×ｆｔ。

ｆ均是固定值。

所以只需求２ｊＲ×Ｓ（Ｏ—ｓｅｔ（Ａ．））的最小值。

设关系Ｒ．有ｋ个属性，可以分别求每个属性作为划分属性时的姜０×双。

一Ｓｅ“Ａ∽值，其中使得Ｏ∑ｉＥＱ既ＸＳ（Ｏ—Ｓｅｔ（Ａ．））最小的那个属性即为划分属性。

显然，划分属性的选择与该关系的大小无关，只与各个属性上的操作和操作发生的频率有关。