分布式数据查询处理与优化PPT讲稿.ppt

《分布式数据查询处理与优化PPT讲稿.ppt》由会员分享，可在线阅读，更多相关《分布式数据查询处理与优化PPT讲稿.ppt（36页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、分布式数据查询处理与优化第1页，共36页，编辑于2022年，星期五4.1问题的提出v假设葡萄酒WINE(YEAR,NAME,PRODUCT,AREA,COUNTRY)和天气WEATHER(YEAR，AREA，COUNTRY,SUN,RAIN)的有关数据存放为：WINE-F存放在巴黎，WINE-I存放在罗马，WINE-U存放在旧金山，WEATHER-R存放在奥斯陆，WEATHER-S存放在罗马。另外，还在纽约存放WEATHER整个数据，现在的查询为：在阿姆斯特丹检索RAIN 800mm的葡萄酒的NAME，YEAR 和SUN，可选的查询方案：第2页，共36页，编辑于2022年，星期五 调度1 在纽

2、约对WEATHER 处理 WEATHER1=YEAR，AREA，SUN（RAIN 800(WEATHER)）把WEATHER发送到巴黎，罗马，旧金山，分别在这些节点对WINE-F，WINE-I,WINE-U进行连接 RESULT1=NAME，YEAR，SUN(WINE-FWEATHER1）RESULT2=NAME，YEAR，SUN(WINE-IWEATHER1）RESULT3=NAME，YEAR，SUN(WINE-UWEATHER1）把RESULT1，RESULT2，RESULT3 传回阿姆斯特丹。第3页，共36页，编辑于2022年，星期五调度2：把WINE-F，WINT-I，WINE-U发到

3、纽约，合并成整个关系WINE。在纽约：RESULT=NAME，YEAR，SUN(RAIN 800(WEATHER)WINE)把结果RESULT 传到阿姆斯特丹。如何评价这两个方案？第4页，共36页，编辑于2022年，星期五 衡量分布式查询处理的效率是一个综合指标，涉及下面的主要目标。系统的处理代价：CPU、I/O、通信。一个优化的分布式查询处理算法需要控制数据传输费用。他与数据分片策略及其单位的大小有直接关系。系统直接响应时间：由于数据的分布和重复，使得查询处理的路径增多和并行性增大，不同的调度方案对系统的响应时间有很大影响。第5页，共36页，编辑于2022年，星期五4.2 关系代数的等价变换

4、一、算符树 用算符树来表示对应地查询：例如，对关系供应商S（S#，SNAME），产品P（P#，PNAME），采购B（B#，P#，S#，NUM）作如下查询：Q1：PNAME，SNAME，NUM(NUM 20(B)(SP);Q2：PNAME，SNAME，NUM(NUM 20(BSP);第6页，共36页，编辑于2022年，星期五PNAME，SNAME，NUMNUM 20BSPPNAME，SNAME，NUMNUM 20 PBS第7页，共36页，编辑于2022年，星期五二、关系代数的等价变换 v 设关系代数的两个表达式为E1，E2，如果两个表达式的相同关系具有相同的值时，总是得到相等的结果，那么就说这两

5、个表达式是等价的，并用E1 E2来表示。v令 U和B分别代表一元和二元关系代数运算，则有：一元运算的交换律：U1U2R二元运算的交换律：RBS二元运算的结合律：RB(SBT)一元运算的幂 ：URU2U1RSBR(RBS)BTUUR第8页，共36页，编辑于2022年，星期五U(RBS)U(R)B U(S)U(R)B U(S)U(RBS)一元运算相对于二元运算的分配律：一元运算的因子分解：设Attr(F)表示在一公式F中出现的属性，Attr(R)表示关系R的属性集合 则:F1F2R F2F1RF1A2R A2F1RAF R FA RF(RS)(F R)(F S)A(RS)(A(R)(A(S)第9页

6、，共36页，编辑于2022年，星期五三、在分布式数据库中为简化查询而应用于等价变换的一般准则v 准则1:使用选择和投影的幂等来为每个关系产生相应的选择和投影。v 准则2:把树中的选择和投影运算尽可能地向下推移（在算符树中）。例 Q：PNAME,SNAME,NUM(NUM 20(BSP);可优化为Q*:(NUM 20(PNAME,SNAME,NUM B)(PNAME,SNAME,NUM S)(PNAME,SNAME,NUM P)公共子表达式的问题：在查询中多次出现的子表达式,应该一次求值,多次使用。第10页，共36页，编辑于2022年，星期五4.3把全局查询变换成段查询1.限定关系的代数学 限定

7、关系(Qualified Relation)是一种带有限定语的关系。用R：qR来表示一个限定关系，这里R是一个关系，而qR是一个限定语。通常qR相应于一个分片谓语。限定关系转换规则：规则一：FR:qR规则二：AR:qR规则三：R:qRS:qs规则四：R:qRS:qs规则五：R1:qR1R2:qR2F R:F AND qR AR:qRRS:qR AND qsRS:qR AND qsR1R2:qR1OR qR2第11页，共36页，编辑于2022年，星期五 2.限定关系等价 如果两个限定关系的实体是等价的关系，并且它们的限定语代表了同一真值函数(即 如果我们把两个限定语用到同一元组上，那么就得到相同

8、的真值)，则这两个限定关系是等价的。对于空数据分片：F()A()RRRR R 第12页，共36页，编辑于2022年，星期五准则三：把选择向下推到树叶处，然后对它们使用限定关系代数进行转换；如果结果的限定语是永假式，则用空关系来代替此选择的结果。准则四：利用限定关系代数来求连接的操作数的限定语之值；如果这个连接的结果的限定语是永假式，则用空关系来代替此子树，包括此连接及它的操作树在内。第13页，共36页，编辑于2022年，星期五3.水平分段关系的化简例4-1 对EMP(ENUM,ENAME,SAL,TAX,DNUM)建立水平分段如下：vEMP1=ENUM=10（EMP）vEMP2=10 ENUM

9、20（EMP）v给出查询Q1：ENUM=1（EMP）第14页，共36页，编辑于2022年，星期五ENUM=1 EMP1EMP2EMP3 ENUM=1(EMP1)ENUM=1(EMP2)ENUM=1EMP1 ENUM=1(EMP3)ENUM=1(EMP2)=ENUM=1(EMP2:10ENUM20 AND ENUM=1)=第15页，共36页，编辑于2022年，星期五4.分段连接问题 v设有已分段关系R，S，实现R，S连接有两种策略，第一是先合并，后连接，第2 是先连接后合并（称之为分布连接）v如果有关段的条件是高度选择的话，则采用第一种方法好；如果段与段之间的连接能达到消除大量无关段的目的，则采

10、用第二种方法好。第16页，共36页，编辑于2022年，星期五准则五：为了分布实施出现在全局查询中的连接运算，必须把段的合并向上推，超出分布的连接范围。例4.2 对关系EMP(ENUM,ENAME,SAL,TAX,DNUM)DEPT(DNUM,DNAME,AREA,MGRNUM)建立如下水平分段：EMP1=DNUM=10(EMP)EMP2=10DNUM 20(EMP)DEPT1=DNUM 10(DEPT)给定查询Q：(假定销售部门编号小于10)第17页，共36页，编辑于2022年，星期五Q：DNAM=“sales”(EMP DEPT)DNAM=“sales”EMP1EMP2EMP3DEPT1DE

11、PT2DNAM=“sales”DNAM=“sales”DNAM=“sales”EMP1DEPT1EMP2DEPT1EMP3DEPT1第18页，共36页，编辑于2022年，星期五EMP1雇员（DNUM=10）EMP2雇员（10DNUM20）DEPT1DNUM10EMP1DEPT1DNAM=“sales”第19页，共36页，编辑于2022年，星期五4.4垂直分段的化简垂直分段的化简 化简的原理是在全部段中决定出足以回答给定查询的一个适当子集，然后从查询表达式中删除所有其他的片。以及删除在分段模式的逆反中用来重构全局关系的若干连接操作。例4-3 对关系：EMP(ENUM,ENAME,SAL,TAX,

12、DNUM)DEPT(DNUM,DNAME,AREA,MGRNUM)建立如下分片：EMP1=ENUM，ENAME，SAL(EMP)EMP2=ENUM，ENAME，TAX(EMP)定义查询 Q：ENAME，SAL(EMP)第20页，共36页，编辑于2022年，星期五ENAME，SAL EMP1EMP2ENAME，SALEMP1第21页，共36页，编辑于2022年，星期五4.5 分布式分组和聚集函数求值的查询分布式分组和聚集函数求值的查询一、关系代数的扩充 v 利用GBG,AFR操作来扩充关系代数，其中各符号的含义为:vG 是一些属性，它们决定了R的分组方法；vAF 是要对每个求值分组的聚集函数；v

13、G和AF可以不指定。v GBG,AFR是一个关系，它是由G的属性和AF的聚集函数组成的一个关系模式。元组数与R中的组数一样多，G的属性取分组的值，而AF的属性取对此组求出的聚集函数的值。第22页，共36页，编辑于2022年，星期五例4-4 关系SUPPLY（SNO,PNO,QUAN）Q1：GBAVG(QUAN),PNO=“P01”(SUPPLY)Q2：GBSNO,PNO,SUM(QUAN)(SUPPLY)Q3：SUM(QUAN)300 GBSNO,PNO,SUM(QUAN)(SUPPLY)如果每一分组都完整地包含在一个段里的话，GB相对于合并运算的分配律是成立的，即 GBG,AF(R1R2)(

14、GBG,AFR1)(GBG,AFR2)第23页，共36页，编辑于2022年，星期五例如供应商供应某种产品的情况表（SUPPLY)SNOPNOQUTNS01P01160S01P01200S01P02300S01P02100SNOPNOQUTNS02P0180S02P01100S02P02300S02P02100第24页，共36页，编辑于2022年，星期五准则六准则六 为了在一全局查询中进行分布分组和聚集函数求值，可以把合并运算（表示段的收集）向上推至相应的group-by操作范围之外。Q3对应的算符树为：假设supply的元组按属性Sno和Pno的值进行分组，而且把Sno 相同的值分在了supp

15、ly1和supply2 的分片中，则：SUM(QUAN)300SUM(QUAN)300GBSNUM,PNUM,SUM(QUAN)GBSNUM,PNUM,SUM(QUAN)Supply1Supply2第25页，共36页，编辑于2022年，星期五二、参数性查询 1.参数性查询的化简 Q4：SNo=$X OR SNo=$Y(SUPPLY)对于含有参数性的化简则在编译时只能进行一部分，而另一部分要等到运行时才能完成，由于效率方面的考虑，在运行时不采用过于复杂的优化技术。运行时的优化常采用简单的测试来完成。即在编译的时候通过对一些限定语和选择条件进行的代数操作来获得测试的表达式，然后在执行时通过对可能的

16、数据段进行永假式测试，如成立则简化查询的执行。第26页，共36页，编辑于2022年，星期五2、在参数性查询多次激活中使用的临时关系 为了降低在每次激活时重复执行查询时所需的代价，一个有用的方法是在该查询的元发站点上建立若干临时关系，其中存储每次迭代所需的数据的超集（supperset）第27页，共36页，编辑于2022年，星期五4.6、基于等价变换的查询优化 v基于等价变换的查询优化就是利用查询对应的关系代数并转换成算符树形式，再利用前面介绍的优化准则，达到数据查询的优化目的。v基于等价变换的查询优化的一般步骤如下：把查询语言对应的命令转换成关系代数对应的算符树。如果是分布式透明系统，则需要把

17、全局查询转换成段查询对应的算符树。第28页，共36页，编辑于2022年，星期五u 利用优化准则化简所有的算符树。利用化简的算符树检索数据库并生成查询结果。例 4-5 有全局关系 EMP(ENO,ENAME,EAGE,ESEX)SALE(ENO,PNO,QUANTITY)EMP的水平分片EMP_M和EMP_F为男职员和女职员，SALE的水平分片SALE_G和SALE_L分别为销售数量大于20和不大于20的分片。现在考虑全局查询：SELECT ENAMEFROM EMP,SALEWHERE EMP.ENO=SALE.ENO AND ESEX=FAND QUANTITY20 第29页，共36页，编辑

18、于2022年，星期五EMP.ENO=SALE.ENO1 把SQL语句转换成关系代数对应的算符树ENAME（ESEX=FAND QUANTITY 20(EMP SALE)）对应的算符树如下：ENAME ESEX=FQUANTITY 20EMP.ENO=SALE.ENOEMP-MEMP-FSALE-GSALE-LEMPENAME ESEX=FQUANTITY 20EMP.ENO=SALE.ENOSALE第30页，共36页，编辑于2022年，星期五把全局查询转换成段查询对应的算符树用优化准则化简所有的算符树。ENAMEEMP.ENO=SALE.ENOEMP-MEMP-FESEX=FESEX=FQUA

19、NTITY20QUANTITY20SALE-LSALE-G第31页，共36页，编辑于2022年，星期五ENAMEEMP.ENO=SALE.ENOEMP-FSALE-G第32页，共36页，编辑于2022年，星期五3.7 基于半连接程序的查询优化基于半连接程序的查询优化 v所谓半连接程序是指通过半连接运算来生成等价的处理序列。设A，B分别是R和S的属性组，它的半连接程序可以有如下两种刻画形式。vS A=B(RA=B（B S）)vRA=B(SA=B（A R）)v对于R A=B S，其处理过程为 在本地把S投影到B;把此投影的结果发送到R所在的站点并执行半连接运算;把这个半连接结果送到S所在的站点执行

20、连接运算。第33页，共36页，编辑于2022年，星期五优化步骤和费用估计优化步骤和费用估计基于半连接的查询优化的一般步骤为：基于半连接的查询优化的一般步骤为：v查询语言对应的命令转换成关系代数表达式；v计算所有可能的等价半连接程序的代价；v从中选择一个最小的方案，执行并获得查询结果。费用估计费用估计:v假设网络中站点之间传递相同信息的数据所花费的代价是相同的，并且忽略站点之间的差异以及路游选择费用，则一个站点发送X个字节的信息到另一个站点所花费的费用为：CX=C0+C1*X 其中C0,C1是与网络性能有关的参数。第34页，共36页，编辑于2022年，星期五1.对于连接SA=B(R(B S)费用

21、有：在本地把S投影到B：假如BS结果为个字节，投影费用为：把个字节发送给所在的站点,费用为:CB=C0+C1*XB;和R执行半连接运算：假设结果为XRB个字节，半连接费用为SB;把XRB 个字节送到S所在的站点,费用为:CRB=C0+C1*XRB；和执行连接运算：假设连接费用为JSRB 则费用为：C0ST1=PB+CB+SB+CRB+JSRB =（PB+SB+JSRB）+（2C0+C1*（XB+XRB）=C0ST11+C0ST12（本地费用+站点传输费用）第35页，共36页，编辑于2022年，星期五2.采用A=B（S（AR）C0ST2=PA+CA+SA+CSA+JRSA =(PA+SA+JRSA)+2C0+C1*(XA+XSA)=C0ST21+C0ST223.直接采用连接RA=BS C0ST3=CR+JRS =JRS+（C0+C1*XR）=C0ST31+C0ST324.直接采用全连接A=BRC0ST4=JRS+（C0+C1*XS）=C0ST41+C0ST42从以上计算结果中选取代价最小的加以执行。第36页，共36页，编辑于2022年，星期五