第五章分布查询的存取优化PPT推荐.ppt

第五章分布查询的存取优化PPT推荐.ppt

《第五章分布查询的存取优化PPT推荐.ppt》由会员分享，可在线阅读，更多相关《第五章分布查询的存取优化PPT推荐.ppt（86页珍藏版）》请在冰点文库上搜索。

40*10000=400KB,5.1基本概念2、分布执行策略举例-1,

（1）策略（设结果为R，以传输代价为主）策略1：

S3为执行场地，则需传输EMP、DEPT传输量=1000K+3.5K=1003.5K策略2：

S2为执行场地，则需传输EMP到S2，结果R传输到S3。

传输量=1000K+400K=1400K策略3：

S1为执行场地，则需传输DEPT到S1，结果R传输到S3。

传输量=3.5K+400K=403.5K从上面三个策略看，选择不同的执行场地，传输代价差别很大。

应选择最低的传输代价。

但组成系统的环境不同，优化的侧重点也不同。

5.1基本概念2、分布执行策略举例-1,5.1基本概念3、存取优化,存取优化的目标

（1）对于远程网，主要考虑通信开销，使通信代价最小。

（2）对于局域网，需同时考虑通信代价和本地处理代价，使综合代价最小。

存取优化的内容存取优化是在全局优化后的片段查询的基础上进行的实际物理副本查询操作的优化。

具体如下：

输入：

片段查询表达式输出：

分布执行计划,内容：

（1）确定片段查询需访问的物理副本。

通常：

本场地上的物理副本优先；

若二元运算存在尽量选择本场地上的二元运算；

数据最小的物理关系应被优先选中；

网络通信代价小的应优先选中

（2）确定片段查询表达式操作执行的最优顺序。

包括从叶到根的执行和同一层叶子上表达式执行的先后，特别是对查询树上的并操作和联接操作的执行次序的确定，其代价差别很大。

（3）选择执行每个操作的方法。

如：

尽量将同一场地上的、同一物理副本的全部操作组合在一起统一考虑完成。

5.1基本概念3、存取优化,代价函数,5.2存取优化的理论基础,1、代价模型主要指传输代价、I/O代价和CPU代价。

Totalcost=CPU代价+I/O代价+传输代价传输代价在传输过程中，有两种影响：

费用和延迟。

其中费用起决定作用。

按传输费用衡量是指使通信中的整个传输开销最小，即传输的数据量最小。

模型为：

CCOM（X）=C0+C1*X其中：

C0：

场地间传输数据的启动所需的固定费用（启动一次），简称启动代价；

C1：

网络单位传输数据费用，简称单位传输代价；

X：

需传输的数据量。

5.2存取优化的理论基础,I/O代价模型为：

CIO（X）=X/P*CIO其中：

P：

页面的大小；

CIO：

为每页平均访问代价；

数据量大小。

CPU代价模型：

CCPU（X）=X*CCPU其中：

CCPU：

单位指令代价；

为指令数。

通常具有下面的统计值：

广域网环境：

CCOM/CIO=20：

1；

局域网环境：

CCOM/CIO=1.6：

1。

可见，在广域网环境，以传输代价为主；

在局域网环境，需综合考虑传输代价和局部代价。

例子,1、查询模型

（1）数据库特征参数假设R为一关系。

关系的基：

指关系R包含的元组个数，记为Card（R）属性的长度：

指属性A定义的取值字节数，记为Length（A）元组的长度：

关系R中每个元组的字节数，记为Length（R）,Length（R）=Length（Ai）关系的大小：

关系R所包含的字节数，记为Size（R）Size（R）=Card（R）*Length（R）属性的特征值：

指关系R中属性A取值不同的属性值个数，记为Val（A）属性A的值域：

记为Dom（A）属性A的最大值和最小值：

记为Max（A）和Min（A）,5.2存取优化的理论基础,

（2）、关系运算的特征参数假设：

R、S为关系。

选择运算（S=f（R）-1选择度：

满足选择谓词F的元组与R元组总数之比，记为基数：

Card（S）=*Card（R）关系的宽度：

Length（S）=Length（R）Length（S.A）=Length（R.A）,5.2存取优化的理论基础,中间关系大小,选择运算（S=f（R）-2不同值的个数：

a.设B不属于选择谓词F，其值均匀分布。

设Card（R）=100，Val（R，B）=70令=0.5则：

Card（S）=*Card（R）=0.5*100=50Card（S）=50Val（R，B）/2=70/2=35Val（R，B）/2Card（S）2*Val（R，B）Val（S，B）=（Card（S）+Val（R，B）/3=40,5.2存取优化的理论基础,令=0.1则：

Card（S）=*Card（R）=0.1*100=10Card（S）=10Val（R，B）/2=35Card（S）Val（R，B）/2Val（S，B）=Card（S）=10b.设B属于选择谓词F若B=X（值），则：

Val（S，B）=1若B与选择谓词F相关且为关键字，则：

Val（S，B）=*Val（R，B）,5.2存取优化的理论基础,选择运算（S=f（R）-3,投影运算（S=A（R）基数：

如果投影涉及单个属性ACard（S）=Val（R，A）如果A中包含关键字Card（S）=Card（R）关系的宽度：

Length（S）=Length（Ai）（AiA）Size（S）=Card（S）*Length（S）Size（S）Size（R）不同值的个数：

Val（S,A）=Val（R,A）,5.2存取优化的理论基础,中间关系大小,联接运算S=RT，（R.a=T.b）基数：

存在Card（S）Card（R）Card（T）具体分下面几种情况：

基本计算形式（为联接选择度）Card（S）=*Card（R）*Card（T）若b为关键字，a为外来关键字Card（S）=Card（R）关系的宽度：

Length（S）=Length（R）+Length（T）Length（S.a）=Length（R.a）不同值的个数：

设a为联接属性Val（S，a）Min（Val（R，a），Val（T，b）若c不为联接属性Val（S，c）Val（R，c）（c为R的属性）Val（S，c）Val（T，c）（c为T的属性）,5.2存取优化的理论基础,半联接运算S=RT，（R.a=T.b）半联接操作是全联接操作的一种缩减。

是一种导出操作，且具有不对称性。

半联接操作（RT）是R与T自然连接后在R上的投影，描述为：

RT=Attr（R）（RT）存在：

Card（RT）Card（R）RTTR基数：

Card（S）=*Card（R）为半联接选择度关系的宽度：

Length（S）=Length（R）不同值的个数：

a.设a为联接属性Val（S，a）=*Val（R，a）b.若c不为联接属性Val（S，c）Val（R，c）,5.2存取优化的理论基础,对联接操作的优化有两种趋势，一种为采用半联接技术，减少联接操作的操作数，以降低传输费用；

另一种为采用全联接技术，主要考虑局部代价。

一个系统需根据其目标综合确定其优化算法。

1、半联接的作用-1采用半联接技术的优化目标是减少联接操作的操作数，以降低传输费用。

5.3半联接优化方法,1、半联接的作用-2,5.3半联接优化方法,查询场地,下面通过三种查询策略分析其代价评估（COST）策略1：

执行场地设在S2需将EMP的Eno和Ename属性传送到S2场地COST=（Length（Eno）+Length（Ename）*Card（EMP）=39*10000=39KB,1、半联接的作用-3,5.3半联接优化方法,查询场地,执行场地,下面通过三种查询策略分析其代价评估（COST）。

策略2：

执行场地设在S1需将DEPT的Dname和Mgno属性传送到S1场地，操作后，再将结果传回场地S2。

设R为结果。

COST1=（Length（Dname）+Length（Mgno）*Card（DEPT）=39*100=3.9KBCOST2=（Length（Dname）+Length（Ename）*Card（R）=70*100=7KBCOST=COST1+COST2=10.9KB,1、半联接的作用-3,5.3半联接优化方法,查询场地,执行场地,策略3：

采用半联接将DEPT的Mgno属性传送到S1场地，即将D1=Mgno（DEPT）传送到S1场地。

COST1=Length（Mgno）*Card（DEPT）=4*100=0.4KB在场地S1。

完成EMP与D1的联接，即实现E1=EMPD1，则：

Card（E1）=100。

将E1的属性Eno和Ename传到S2，即将E2=Eno，Ename（E1）传到S2。

COST2=（Length（Eno）+Length（Ename）*Card（E1）=39*100=3.9KB在场地S2上计算：

R=DEPTE2。

COST=COST1+COST2=0.4+3.9=4.3KB。

策略3相当于：

EMPDEPT=（EMPDEPT）DEPT。

实现实现,1、半联接的作用-4,5.3半联接优化方法,2、半联接优化算法输入信息：

位于不同场地上的两个关系R和S输出信息：

实现RS（R.A=S.B）算法：

（设S的尺寸小于R）

（1）在S所在场地上计算S=B（S）;

（2）传送S到R场地（3）在R场地上计算R=RS=RS（4）将R传到S所在场地（5）在S所在场地上计算RS=（RS）S=RS,5.3半联接优化方法,3、传输代价的比较假设：

关系R和S分别在不同的场地上，C0为启动代价，C1为单位传输代价。

设：

在S所在的场地上执行，则传输关系R实现RS的代价C=C0+C1*（Length（R）*Card（R）=C0+C1*Size（R）,5.3半联接优化方法,3、传输代价的比较

（2）采用半联接的传输代价（见半联接优化算法：

需传输S和R）C=CS+CR=C0+C1*（Length（S）*Card（S）+C0+C1*（Length（R）*Card（R）=2C0+C1*（Length（B）*Val（B）+Length（R）*Card（R）=2C0+C1*（Size（S）+Size（R）分析：

如果有：

CC则：

C0+C1*Size（R）2C0+C1*（Size（S）+Size（R）C0/C1+Size（S）+Size（R）Size（R）,5.3半联接优化方法,5.4SDD-1系统优化技术SDD-1是美国采用ARPANET远程网建立的世界上第一个分布式数据库管理系统。

该系统为人们进一步理解和解决分布式数据库中的一些问题做出了很大贡献。

SDD-1的查询优化就是对片段数据使用选择、投影、半联接操作来最大限度地缩减。

SDD-1具体算法由两部分组成：

一是根据评估缩减算法确定一个收益最大的执行策略，但此执行策略的效率可能不一定高；

二是进行后优化，将基本算法得到的解进行修正，以得到更合理的执行策略。

5.4SDD-1系统优化技术,5.4SDD-1系统优化技术,3代价利益模型根据代价利益模型，找出所有受益的半联接，组成受益半联接集。

设有关系R和S（半连接条件R.A=S.B）,5.4SDD-1系统优化技术,获益：

RS,代价：

SR,比传输R减少了

（1）倍的数据,4基本优化算法输入信息：

查询联接图及关系概要图输出信息：

半联接执行序列集合P及最后的执行场地算法：

Begin/*初始化*/包含所有可执行的一元操作和局部操作，构成执行策略集P；

计算所有的半联接的代价和利益，构成受益半联接集P。

/*选择半联接*/While（存在满足（Benefit（）Cost（）P=P|为最大受益半联接修改概要图（最大受益半联接执行结果的概要图）；

重新估计执行后的各个半联接的代价和利益；

/*选择执行场地*/FORI=1，n计算在场地Si上执行联接运算的网络传输代价Cost（Si）SR=MinCost（S1），Cost（S2），Cost（Sn）End,5.4SDD-1系统优化技术,5.4SDD-1系统优化技术,5000,5、举例-例5.4.2假设：

C0=0，C1=1DOM（Supplier.Sno）DOM（Supply.Sno）DOM（Dept.Dno）DOM（Supply.Dno）优化过程：

（1）求可能的半联接集合P1=SupplySupplierP2=SupplyDeptP3=SupplierSupplyP4=DeptSupply

（2）初始的利益代价表以P1=SupplySupplier为例，求初始的利益代价表，需要的计算公式如下：

1=Val（Supplier,Sno）/Val（Supply,Sno）=200/1000=0.2Benefit1=（1-）*Card（Supply）*length（Supply）=0.8*5000*（2+4）=24KCost1=Val（Supplier,Sno）*length（Supplier,Sno）=200*4=0.8K,5.4SDD-1系统优化技术,5、举例-例5.4.2同理：

2=20/200=0.2Benefit2=0.8*5000*6=0.8*5000*6=24KCost2=Val（Dept,Dno）*length（Dept,Dno）=20*2=0.04K3=1，Benefit3=04=1，Benefit4=0因此，初始的利益代价表如下：

根据初始的利益代价表，得到受益半联接集P=P1，P2,5.4SDD-1系统优化技术,5.4SDD-1系统优化技术,5、举例-例5.4.2,5.4SDD-1系统优化技术,5、举例-例5.4.2,5000,c.重新计算利益代价表P1=SupplySupplierSupplySupplier的选择度同SupplySupplier的选择度1=0.2Benefit1=（1-）*Card（Supply）*Size（Supply）=0.8*1000*（4+2）=4.8KCost1=Val（Supplier,Sno）*Size（Supplier,Sno）=200*4=0.8KP3=SupplierSupplyVal（Supply，Sno）=1000缩减到Val（Supply，Sno）=666而：

DOM（Supplier.Sno）DOM（Supply.Sno）因此，200:

x=1000:

666,x=200*666/1000=133=400/33=400/3/200=0.666Benefit3=（1-3）*Card（Supplier）*Size（Supplier）=0.333*200*24=1.6KCost3=Val（Supply,Sno）*Size（Supply,Sno）=666*4=2.6KP4=DeptSupply4=1，Benefit4=0,5.4SDD-1系统优化技术,5、举例-例5.4.2,5.4SDD-1系统优化技术,5、举例-例5.4.2,a重新计算Supply的概要图：

Card（Supply）=*Card（Supply）=0.2*1000=200Val（Supply,Sno）Sno属于选择谓词Val（Supply，Sno）=666Val（Supply,Sno）=*Val（Supply,Sno）=0.2*666=133Val（Supply,Dno）Dno不属于选择谓词，Card（Supply）=200，Val（Supply，Dno）=20有：

Card（Supply）2*Val（Supply，Dno）Val（Supply,Sno）=Val（Supply，Dno）=20,5.4SDD-1系统优化技术,5、举例-例5.4.2,b.重新求可能的半联接集合P有：

（P1=SupplySupplier已处理，无SupplyDept半联接）P3=SupplierSupplyP4=DeptSupplyc.重新计算利益代价表P3=SupplierSupplyDOM（Supplier.Sno）DOM（Supply.Sno）Val（Supply,Sno）=133,则Val（SupplierSupply），Sno）=133,3=133/200=0.666Benefit3=（1-3）*Card（Supplier）*Size（Supplier）=0.333*200*24=1.6KCost3=Val（Supply,Sno）*Size（Supply,Sno）=133*4=0.5KP4=DeptSupply4=1，Benefit4=0,5.4SDD-1系统优化技术,5、举例-例5.4.2,5.4SDD-1系统优化技术,5、举例-例5.4.2,a重新计算Supplier的概要图：

Card（Supplier）=*Card（Supplier）=0.666*200=133Val（Supplier,Sno）Sno属于选择谓词Val（Supplier，Sno）=200Val（Supplier,Sno）=*Val（Supplier,Sno）=0.666*200=133Val（Supplier,Sname）Sname不属于选择谓词，Card（Supplier）=133，Val（Supplier，Sname）=200有：

Val（Supplier，Sname）/2Card（Supplier）2*Val（Supplier，Sname）Val（Supplier，Sname）=（Card（Supplier+Val（Supplier，Sname）/3=（133+200）/3=111因此、概要图如下：

5.4SDD-1系统优化技术,5、举例-例5.4.2,5.4SDD-1系统优化技术,5、举例-例5.4.2,根据联接图及其概要图，代价计算：

Cost（S1）=Cost（Supply）+Cost（Dept）=200*（4+2）+20*（20+2）=1.640KCost（S2）=Cost（Supplier）+Cost（Dept）=133*24+20*22=3.6KCost（S3）=Cost（Supplier）+Cost（Supply）=133*24+200*6=4.4K对比以上各个执行场地的代价，可知：

场地1的代价Cost（S1）最小。

所以、最后执行场地选为场地1（S1）。

将上面得到的结果进行修正，以得到更合理的执行策略。

按下面两个准则处理。

准则1在执行策略集中，消去用于缩减处于执行场地上的关系的半联接操作。

准则2延迟执行代价高的半联接，以尽可能利用已缩减的关系。

5.4SDD-1系统优化技术,6、SDD-1后优化处理,例5.4.3：

上例得到执行策略集P=P2，P1，P3，P2、P1、P3分别为：

Supply=SupplyDept=P2（在场地上S2执行）Supply=SupplySupplier=P1（在场地上S2执行）Supplier=SupplierSupply=P3（在场地上S1执行）因为：

执行场地选在S1，而P3缩减程序是在场地S1上执行，因此，基于准则1，从策略集P中消去P3，所以：

P=P2，P1总代价=Cost（S1）+Cost（P2）+Cost（P1）=1640+200*4+20*2=2.48K,5.4SDD-1系统优化技术,6、SDD-1后优化处理-准则1,从优化实现（方法2）可知：

步的实现同方法1的步实现顺序恰好颠倒，其目的是使方法2中步可以利用步的已缩减的S。

即尽可能利用已缩减的关系，使整体传输代价降低。

5.4SDD-1系统优化技术,6、SDD-1后优化处理-准则2,7、半联接技术的不足半联接技术是通过局部缩减操作缩减关系的数据量，发送缩减的关系到执行场地，在执行场地对缩减后的关系进行查询处理。

采用该技术大大地降低了场地间传递的信息量，从而减少了整个系统的传输代价。

但同时，增加了系统的局部处理代价。

这是半联接技术存在的缺点。

归纳半联接技术，有如下不足：

（1）没有考虑局部代价；

RS=（RS）S=RB（S）B（S）的代价RB（S）的代价

（2）当选择度较低时，半联接技术才可行。

SDD-1优化技术是采用半联接技术对所有受益半联接进行缩减操作，确定一个执行代价最小的场地。

再经过后优化处理得到最佳的执行策略。

系统的总代价需根据系统的组成环境综合考虑传输和局部代价，或侧重考虑某一方面的代价。

因此，在应用半联接技术时，要考虑其适应的环境。

5.4SDD-1系统优化技术,5.5枚举法优化技术查询操作的代价评估，需要综合考虑局部代价和传输代价。

侧重于哪一方面，需根据系统组成环境确定。

若侧重传输代价，局部代价可以忽略不计时，采用半联接技术较好；

相反，侧重局部代价时，采用直接联接比采用半联接技术优越。

因为直接联接技术实现简单。

枚举法是基于直接联接的实现方法，下面介绍其优化技术。

1、实现联接运算的方法如：

关系O、I，实现OI（O.AI.B）。

下面将介绍其实现的两种方法及其代价评估。

两种实现方法为：

嵌套循环法（nest_loop）和合并扫描法（merge_scan）。

5.5枚举法优化技术,1、实现联接运算的方法,5.5枚举法优化技术,1、实现联接运算的方法,（3）执行联接的代价实现联接：

Result=OutIn嵌套循环法嵌套循环法是将关系O的每个元组对关系I的元组顺序扫描，查询符合联接属性条件的元组，形成联接结果的一部分。

因此，该方法需要对关系O有一次完整扫描，对关系I有Card（O）次扫描。

其代价可描述如下：

C（nest_loop）=（NOUT+Card（O）*Nin）*CIo+Card（Result）*Ccup其中：

Nout为扫描关系O时读取的平均页面数；

Nin为对关系I读取的平均页面数；

CIo为单位读取页面费用；

Ccpu为单位CPU处理费用。

5.5枚举法优化技术,1、实现联接运算的方法,合并扫描法合并扫描法是按联接属性顺序对两个关系扫描，取其匹配的元组构成结果的一部分。

在实现中为减少I/O次数，在读取内关系时，将内关系中和外关系具有相同联接值的元组放到缓冲区中，则在处理外关系后续元组时，将具有相同联接值的内关系元组直接从缓冲区取出，而不必再去读页面。

但要求将内、外关系排序，排序费用取决于存取方法。

因此，其代价可描述如下：

C（merge_scan）=（Nout+Nin）*CIo+Csort（O）+Csort（I）+Card（Result）*Ccup其中：

Csort（O）、Csort（I）对关系O和I排序费用；

其它同上。

5.5枚举法优化技术,1、实现联接运算的方法,2、联接关系的传输方法存储在不同场地上的关系O和I执行联接操作时，其执行场地可选在O或I所在的某一场地。

执行前，需将不在执行场地的关系传输到执行场地上。

通常采用全部传送或按需传送方法实现关系传输。

（1）全体传送（ShippedWhole）传送费用为要传送的关系的字节数。

若要传输的外关系为O，则其传送费用可描述如下：

（Card（O）*length（O）/m*Cmes其中：

m为传输的报文的字节数；

Cmes为传送报文的单位费用；

若传送内关系，需将其存储在本场地，等传送外关系时将内关系取出与外关系比较。

需增加的I/O代