基于连接代价图的并行数据库关系存储方式选择算法

计算机科学2002Voi．29N_O．8 基于连接代价图的并行数据库关系存储方式选择算法¨ AChosenAlgorithmofDataDeclusteringStrategyinParallelDatabaseBasedor／Join—CostGraph 王伟平李建中高宏 (哈尔滨工业大学计算机科学与 工程 路基工程安全技术交底工程项目施工成本控制工程量增项单年度零星工程技术标正投影法基本原理 系 哈尔滨150001) AbstractJoinisafrequentlyusedandtimeconsumingqueryoperation．Intheparalleldatabase system，agooddatadeclusteringstrategycanimprovetheefficiencyofjoingreatly·Inthispaper， weproposeachosenalgorithmofdatadeclusteringstrategybasedonjoin—costgraph·Givenaset ofrelationsandasetofjoinqueries，ouralgorithmassignseveryrelationanappropriatedata declusteringstrategy，whichcanmakethejoinsexecutiontimenearlyshortest· KeywordsParalleldatabase，Datadeclusteringstrategy，Join，Join—costgraph 1．引言 在基于群机系统并行数据库的研究中，并行数 据库物理存储方法是一个重要的研究内容。在查询 处理过程中，如果数据分布不合理，系统的并行性就 得不到充分的发挥，降低了并行数据库的性能[1]。 目前，在数据分布策略方面已开展了大量的研 究工作，提出了很多有效的并行数据分布方法，如 Round—Robin、Hash、Range—Partition、CMD等数据 分布方法。Round—Robin方法以轮转的方式将关系 的元组分布到各个处理机上，当关系上的操作需要 存取大量元组时，一般采用这种分布方法，但是 Round—Robin不能有效地支持具有低选择性谓词的 查询[1]。Hash分布方法选择关系的一个属性进行 Hash，然后根据Hash值将关系分布到各个处理机 上。这种分布方法可以有效地支持划分属性上低选 择性谓词的数据操作，但Hash方法不能保证数据 均匀地分布在多个处理机上[1]。Range—Partition的 分布方法是将关系的一个属性的值域分成若干个区 间，然后根据这些区间将关系分布到各个处理机上。 这种分布方法不但可以有效地支持要求大数据量存 取的查询和在分布属性上具有低选择性谓词的数据 操作，也支持数据的聚集存储。Range—Partition分 布方法可能引起两个问题。第一个问题是数据在处 理机之间分布不均匀；另一个问题是工作负载的不 均匀，在最坏的情况下，一个大数据量查询的执行可 能集中在一个处理机上[1’2]。CMD的存储方法是一 种多维的数据分布方法，可以有效地支持多个属性 上的查询操作，对于多维数据分布感兴趣的读者可 以阅读文[3，4]。 上述的数据分布方法都有各自的优缺点。在实 际应用中，一个并行数据库中的所有关系不可能只 简单地采用一种分布策略。为了提高并行数据库的 查询效率，在数据库应用设计过程中，需要根据每个 关系上的查询操作类型以及操作发生的频率来为每 个关系确定相应的分布存储策略。当给定了一组关 系以及基于这组关系之上的查询操作，如何为每一 个关系选择存储策略，以使并行数据库系统获得整 体优化的查询执行效率，是一个重要且具有实际意 义的问题。目前人们虽然已经对每个独立的数据分 *)本文研究得到了国家自然科学基金、国家973 计划 项目进度计划表范例计划下载计划下载计划下载课程教学计划下载 (01999032704)、国家863计划(2001一AA一415—410)、国家教委博士基金、黑龙江省科委项 目和黑龙江省自然科学基金项目资助． 参考文献 1 ZivianiN。eta1．Compression：Akeyfornext-generationtextfe- trievalsystem 2 MouraE，eta1．FastandFie妇hieWbrdSearchingonCom- pressedText．ACMTranslniormationsystems。2000．18(2)：113 ～139 3 BooksteinA。KleinST．Compressionofcorrelatedbit—vectors． InformationSystems，1991，16<4)：387～400 4 MoffatA．ZobelJ．Parameterisedcompressionforsparse bitmaps．InSIGIR，1992．274～285 5 LinoffG，StaufillG．Compressionofindexeswithfullpositional informationinverylargetextdatabase．In：PrOC。ofIml。AcM ·252· S珏tIRConf．onResearchanddevelopmentinInformationre- trieval(sIRGIR’99)，1993．88～95 6 Iheza-YatesR。Gonnet0．AnewapproachtOtextSearching． Comm．ACM。Oct．1992．74～82 7 B&eza—YatesR。NavarroG．FasterA．pproximateStringmatching． Algorithmica，1999．23(2)：127～158 8 NavarroG。eta1．AddingcompressiontOblockaddressinginvert— edindexes．Informationretrieval，2000，3(1)：49～77 9 EliasP．Universalcodewordsetsandfepresentationsoftheinte— gers．IEEETfansactionsonInformationTheory，I’I乙Zl：194— 203，March1975 10GolombSW．Run．1engthencodings．1EEETransactionsonIn． formationTheory，ITl2(3)：399—401．July1966 布策略进行了充分的研究，然而，如何根据具体应用 需求，综合应用这些已有的分布策略，为每一个关系 确定相对优化的存储 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 却是数据库应用设计者们 所关心，而又被研究者们忽略的一个问题。 连接操作是查询处理中经常使用的操作，并且 其时间也是开销最大的[1]。对于有连接操作的两个 关系来说，他们各自的分布方式对于其连接操作的 执行效率有很大的影响。例如图1(1)中的两个关系 Ri、R，，设他们分布在P个处理机上。如果令R；以 Round—Robin方式分布，Ri同样以Round—Robin方 式分布，这样对于Ri、R-单表上的查询效率可能很 高，但是在执行R；和Ri的连接操作时，就需要对Ri 和R，的数据进行重新分布。在群机系统中，网络通 信的带宽一直是系统的瓶颈，处理机间的数据交换 会大大地增加连接操作执行的时间开销。如果Ri在 属性A上Hash分布，Rj在属性B上Hash分布，并 且Hash函数相同，那么在执行连接操作时，就不需 要对关系Ri、Rj的数据重新分布，有效地提高连接 执行的效率。 图1连接操作示意图 在数据库应用中。关系之间的连接操作可能是 非常复杂的。例如在图1(2)中，关系Ri在属性A上 与关系Rj有连接操作，同时在属性C上与关系Rk 有连接操作。可以证明，没有一种多维的分布方式， 可以使Ri无论是在属性A还是在属性C上作连接 时，处理机之间都没有通信开销。在一维分希方式 中，如果令Ri在属性A上选择适当的分布方式分 布，来保证与Ri之间的连接操作没有处理机之间数 据通信开销，那么在执行Ri与Rt的连接操作时，这 种通信开销就不可避免，反之亦然。由于Ri只能选 取其中一个属性分布，我们希望选择在执行这两个 连接操作时使总的通信开销最小的那个连接属性进 行分布。 本文主要通过分析连接操作的执行效率来考虑 如何选择关系的存储方式。在一个数据库应用中，连 接操作在设计数据库模式时是可预见的。本文提出 一个基于连接代价图的关系存储方式选择算法，当 给定一组关系以及基于这组关系之上的一组连接查 询时，该算法为每个关系分配一种合适的存储方式， 使得这组连接查询的执行时间近似最短。 2连接代价图的定义及构造方法 在基于群机系统的并行数据库中，每个查询都 由前端机分懈成子查询，下发到存储数据的后端处 理机上执行。网络通信的速度一直是群机系统的瓶 颈，如果查询执行过程中需要大量的交换数据，那么 查询执行的效率就会大大降低。为了提高系统的查 询效率，在为数据库模式设计存储方案时，应该尽量 避免额外的通信开销。通过分析可以看出，只是在执 行含聚集操作的查询以及等值连接时，关系的存储 方式才对处理机间的数据交换有影响。而对于关系 上的运算来说，连接操作是经常使用的操作，并且其 时间开销也是最大的。在一个数据库系统中，连接操 作是很复杂的，我们为这些连接操作生成一个连接 代价图，图的顶点表示关系，边表示关系的连接操 作，每一个边有一个权值，表示执行这个连接操作时 处理机之间的通信开销。 在本文中，默认的连接算法是Hash—Join算法。 当两个关系执行连接操作时，如果需要在处理机间 交换数据，为了分析简单，我们认为两个关系的所有 元组都需要移动。为了描述方便，首先给数据库模式 的定义。 定义1 数据库模式D为一组关系模式的集 合，表示为D{RilRi为关系模式，1≤i≤n)。 定义2在并行数据库模式中，关系R。、R，分布 在P个处理机上，SRi(Ti)、SR，(Tj)分别表示关系 Ri、Rj的分布方式，Ti，T，表示Ri、R，的划分属性。则 Ri在属性A和Rj在属性B上的连接通讯开销定义 为： Join—Cost(R，(A)，R，(B))一 f0 (1) I lRFI×It。I+IR，l×It，，I (2) 当SRi(Ti)、SR，(TJ)均为Hash分布，Ti—A，Tj—B， 并且Hash函数相同；或者SRi(Ti)、SRj(Ti)均为 Range—Partition分布，Ti—A，Tj—B，并且值域的划 分区间相同时，则Join—Cost按照情况(1)计算；其 他时候均按照情况(2)计算。这里，lRiI、IRjI表示关 系Rl、Rj的元组数，tn,t，j表示Rl和R，中的一个元组 包含的字节数。 在一个数据库应用中，每个查询语句执行的频 度是不一样的，因此每个连接操作出现的概率也不 一样。我们用p(Ri(A)，Rj(B))表示关系Ri、R，在属 性A、B上的连接出现的概率，这个概率是一个经验 值。当根据连接操作的执行效率来选择关系的存储 方式时，连接操作出现的概率也是一个重要的决定 因素。下面给出连接代价图的定义。 定义5 给定一个并行数据库模式D{R。，R。， ⋯，R。}以及D上的一组连接查询Q(q。，q。，⋯，q。)， 如下定义连接代价图Gjoi。(V，E)： 1．V={viIvi表示Ri，Ri∈D，14i≤m}。 2．E一((u，vi)J(vi，vj)表示Ri，Rj之间有连接 ·253· 操作，这个连接操作出现在Q中一个查询中，R。，R， ∈D，1≤i，j≤m}。 3．f((v。，v，))一A，A为关系Ri和R．的连接属 性标识，A∈r。 4．w((v。，v，))一Join—Cost(R：(A)，R，(A))×P (Ri(A)，R，(A))，R，，R，∈D，A为关系R，和R，的连 接属标识。 在定义3中，f((v。，v，))表示关系Ri和关系R，的 连接属性，设Ri的连接属性为c1，Rj的连接属性为 c2，这里统一用一个标识符A来标识。如果关系Ri 在属性c1上和Rt在属性c3上又有连接操作，同样 定义f((v。，Vk))一A，这时A就同时表示R。的属性 c1、R，的属性c2和Rk的属性c3。下面我们举例说明 如何构造连接代价图G。。 例1 已知数据库模式D(R1，R2，R3，R4，R5， R6)和一组查询连接查询QjoiTI，设QjoitI为： ‰一{R1冈AR3。R2冈AR3，R3冈BR4，R4 冈cR5，R4冈cR6，RsVplDR7} 这里用关系代数表示连接。设每个连接操作对应的 概率为：{0．2，0．2，0．1，0．1，0．1，0．3)，则生成的 G。图为： 图z连接代价图 f((v1，V3))一A，f((v2，v3))一A，f((v3，v4))=B，f ((v4，v5))一C，f((v4，v6))一C，f((v5，v7))一D 关系R的大小可以由R的元组数和它的每个元组 所占的字节数计算出来。这里我们假设R1的大小为 10000Byte，R2为9000Byte，R3为8000Byte，R4为 11000Byte，R5为1000Byte，R6为2000Byte，R7为 1000Byte。假定每个关系的分布方式均为Round— Robin，则通过w的计算 公式 小学单位换算公式大全免费下载公式下载行测公式大全下载excel公式下载逻辑回归公式下载 可以得到w((vl，v3)) =3600，W((v2，v3))一3400，w((v3，v4))=1900，w ((v4，v5))一1200，W((v4，v6))=1300，w((v5，v7)) 一600。 5基于连接代价图的关系存储方式选择算 法 在生成G蜘图后，问题转化为V中每一个点选 、] 择一种分布方式，使得厶w(vi，vj)最小。如果用 穷举的方法来求最小EW的，就需要对V中各个点 每种分布方式的组合都计算一次w。设关系可以选 择的分布方式为Round—Robin、Hash、Range—Parti— tion三种，每个关系平均具有t个属性，那么一个关 ·254· 系可以在t个属性上进行Hash或者Range—Patti— tion分布，也就是说，它有2t+1个存储方式可以选 择。如果V中有m个点，则V中各个点分布方式的 组合就有(2t+1)“种。对于一个有10个关系模式的 数据库，如果每个关系有10个属性，那么在求最小的 Ew时，需要计算2110次，这个计算量是十分惊人的。 显然，穷举的方法不可行。 我们设计了一个贪心算法来求这个问题的优化 解，下面以图2为例来说明这个算法。在图2中。f ((vl，v3))一A，f((v2，v3))一A，如果v1，v2，v3所 表示的关系不在属性A上分布，则带来的通讯开销 为w((vl，v3))+w((v2，v3))一7000，定义这个开 销为属性A的save值，表示为save(A)一7000。如 果v1，v2，v3所表示的关系均在属性A上Hash分 布并且默认Hash函数相同，则w((v1，v3))一W ((v2，v3))一0，这时由于v3选择A属性Hash分 布，而f((v3，v4))≠A，因此w((v3，v4))一1900。 也就是说v1，vz，v3选择A属性Hash分布，则带来 的通讯开销为1900。我们将这个开销定义为属性A 的cost，表示成cost(A)一1900。定义属性A的效益 函数为： profit(A)一save(A)--cOSt(A) 其含义是当选择属性A为关系的分布属性时，可以 节省的通讯开销。 根据这个原则，可以计算出每个连接属性的 profit。表1列出了图2中每个连接属性的profit值。 表1连接属性的profit值表 属性名 Save COSt Profit A 7000 1900 5100 B 1900 9500 ——7600 C 2500 2500 0 D 600 1200 ——600 显然，我们应该选取profit值最大的属性先分 配存储方式。对于图2，我们先选取属性A进行分 配，即令关系v1、v2、v3所表示的关系在属性A上 Hash分布。然后在图2中将v1、v2、v3三个点删除。 重新计算新图中每个连接属性的profit值，再选取 pro{it最大的属性进行分配，循环上述操作直到图 中没有边为止。按照这个原则我们为图2中的关系选 取的分布方式为： 1．Rl、R2、R3在属性A上Hash分布。 2．R4、R6在属性C上Hash分布。 3．R7根据其他查询的特点来选取分布方式。 这种分布方式的∑w=2500。需要说明的是， R4、R6以及R1、R2、R3也可以选择Rallge—Partition 分布。至于是选取Hash分布还是选取Range—Parti— tion分布，可以根据关系本身的一些属性以及其他 查询的特点来决定。 本文用邻接链表表示Gh。图，链表的每个节点 需要 记录 混凝土 养护记录下载土方回填监理旁站记录免费下载集备记录下载集备记录下载集备记录下载 边的w和f权值。用链表存储每个连接属 性的profit值，同时也用链表存储最后为每个关系 分配的存储方式。关系存储方式选择算法描述如下： 输入：数据库模式D{R，，R2，⋯，Rm}，连接查询Q(q。，q。，⋯ q。)，每个连接操作出现的概率(px，P：，⋯，P。) 输出：关系的存储方式DS{SR。(A)，⋯，SR。(K)) 1构造存储G。的邻接表 2while(E中的边不为空){ 3 将profit链表置空 4 for(E中每条边(vi，vi)) 5 iff(vi，vi)不在profit链表中 6 计算profit(f(vi，vi))的值．并将其插入到profit 链表中 7 找到profit值最大的属性Ak 8 在邻接表中查找所有满足f(vi，vi)=Ak的vi点，将vi 点从邻接表中删除．将其加入到存储分布方式的链 表中．令分布方式为Hash或Range—Partition，分布 属性为Ak } 算法时问复杂性分析 设lVl一---m，IEl=i1。算 法的第1步需要时间复杂度为O(m+n)，算法的第3 步需要遍历profit链表，B寸I'B-J复杂度为0(n)，第4步 需要循环i1次，第6步需要遍历邻接表，复杂度为O (m+n)；第4～6步的复杂度为O(n(m+n))；第7步 的复杂度为0(n)，第8步的复杂度为O(m+n)；最 外层的while循环最坏要循环n次，因此算法的时 间复杂度为0(n2(m+n))。 结论在基于群机系统的并行数据库中，关系 的存储方式对于数据库系统的查询效率有着很大的 影响。连接操作是数据库系统中经常使用并且时问 开销很大的一种数据操作，在并行数据库中，如果关 系分布方式选择得合理，在执行连接操作时就可以 避免在处理机间交换数据，大大提高连接的执行效 率。本文提出了一个基于连接代价图的关系分布方 式选择算法，当给定一个数据库模式和一组连接查 询时，该算法可以为数据库中每个关系分配一种存 储方式，有效地提高这组连接查询的执行效率。 参考文献 1 李建中，孙文隽．并行关系数据库管理系统引论．科学出版社． 1998．57～71 2 GhandeharizadhS．DewittDJ．PerformanceAnalysisofAherna— riveDeclusteringStrategies．In：Proc．oftheSixthIntl．Conf．on DataEngineering，1990 3 LiJianzhong，Srivastava】．RotemD．CMD：AMulti—dimensional DeclusteringMethodforParallelDatabaseSystems．In：Proc．of Intl．Conl．onVeryLargeDataBases，1992 4 Li曩anzhong，SrivastavaJ．RotemD．CMD：AMulti—dimensional DeclusteringMethodforParallelDatabaseSystems：[Technical Report，TR一91-sg]．DepartmentofComputerScience．University ofMinnesota．1991 (上接第258页) 6 PengZ．KambayashiY．DeputyMechanismsforObject—Orient— edDatabases．In：Proc．ofIEEEllthIntl．Conf．onDataEngi— neering，1995．333～340 7 BayardoRJ，eta1．Infosleuth：Agent-BasedSemanticIntegration ofInformationinOpenandDynamicEnvironments．In：Proc．of ACMSIGMODIntl．Conf．1997．195～206 8 GeneserethMR．KellerAM．DuschkaOM．Informaster：An InformationIntegrationSystem．In：Proc．OfACMSIGMOD Intl．Conf．1997．539～542 9 LiC．eta1．CapabilityBasedMediationinTSIMMIS．In：Proc．of theACMSIGMODConf．1998．564～566 10JosifovskiV．Risch。F．IntegratingHeterogeneousOverlapping DatabasesThroughObject—OrientedTransIormations．In：Proc． ofthe25’hVLDBConf．Edinburgh．Scotland。1999．435～446 ·255· 基于连接代价图的并行数据库关系存储方式选择算法 作者： 王伟平， 李建中， 高宏 作者单位： 哈尔滨工业大学计算机科学与工程系,哈尔滨,150001 本文链接：http://d.g.wanfangdata.com.cn/Conference_6061370.aspx