第五章分布查询的存取优化

第五章分布查询的存取优化

基于代价的优化查询优化过程QueryExecutionPlan查询优化：最小化查询代价搜索空间搜索空间搜索策略搜索策略全局存取优化

基本概念存取优化的理论基础半联接优化方法SDD-1系统优化技术枚举法优化技术CENTRALIZEDQUERYOPTIMIZATION§5.1基本概念1、分布执行过程

分布执行过程实际上就是从查询场地发出查询命令、从数据源获取数据、确定最佳的执行场地和返回执行结果的过程。§5.1基本概念1、分布执行过程查询场地：指发出查询命令和存储最终查询结果的场地。查询场地也称最终结果文件。源数据场地：指查询命令需要访问的数据副本所在的场地，可能涉及到一个或一个以上的场地。源数据场地也称源数据文件。执行场地：指查询操作执行所在的场地。执行场地可以和查询场地或源数据场地处于同一场地，也可不处于同一场地。执行场地也称中间结果文件。

§5.1基本概念2、分布执行策略举例-1例5.1.1

有关系EMP和DEPT。EMP{ENO，ENAME，BIRTH，SALARY，DNO}（主键）雇员编号雇员姓名出生日期工资部门号DEPT{DNO，DNAME}（主键）部门号部门名称假设：（1）EMP：元组数：10000，元组大小：100B，关系大小：100*10000=1000KB（2）DEPT：元组数：100，元组大小：35B，关系大小：35*100=3.5KB假设：结果元组大小40字节，S3为查询场地 结果关系大小：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：为每页平均访问代价；

X：数据量大小。CPU代价模型：CCPU（X）=X*CCPU其中：CCPU：单位指令代价；X：为指令数。通常具有下面的统计值：广域网环境：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=50∵Card（S）=50Val（R，B）/2=70/2=35∴Val（R，B）/2<Card（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=10∵Card（S）=10Val（R，B）/2=35∴Card（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））基数：如果投影涉及单个属性A Card（S）=Val（R，A）如果A中包含关键字

Card（S）=Card（R）关系的宽度：Length（S）=∑Length（Ai）（Ai∈A）Size（S）=Card（S）*Length（S）Size（S）<Size（R）不同值的个数：

Val(S,A)=Val(R,A)§5.2存取优化的理论基础中间关系大小③

联接运算S=R∞T，（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=R∝T，（R.a=T.b）

半联接操作是全联接操作的一种缩减。是一种导出操作，且具有不对称性。如：半联接操作（R∝T）是R与T自然连接后在R上的投影，描述为：R∝T=∏Attr（R）（R∞T）存在：Card（R∝T）≤Card（R）R∝T≠T∝R基数：

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存取优化的理论基础TTTaaaa对联接操作的优化有两种趋势，一种为采用半联接技术，减少联接操作的操作数，以降低传输费用；另一种为采用全联接技术，主要考虑局部代价。一个系统需根据其目标综合确定其优化算法。1、半联接的作用---1采用半联接技术的优化目标是减少联接操作的操作数，以降低传输费用。§5.3半联接优化方法1、半联接的作用----2§5.3半联接优化方法查询场地下面通过三种查询策略分析其代价评估（COST）策略1：执行场地设在S2需将EMP的Eno和Ename属性传送到S2场地COST=(Length(Eno)+Length(Ename))*Card(EMP)=39*10000=39KB1、半联接的作用----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.9KB1、半联接的作用----3§5.3半联接优化方法查询场地执行场地

策略3：采用半联接①将DEPT的Mgno属性传送到S1场地，即将D1=∏Mgno（DEPT）传送到S1场地。COST1=Length(Mgno)*Card(DEPT)=4*100=0.4KB②在场地S1。完成EMP与D1的联接，即实现E1=EMP∞D1，则：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=DEPT∞E2。

COST=COST1+COST2=0.4+3.9=4.3KB。策略3相当于：EMP∞

DEPT=（EMP

∝DEPT）∞DEPT。

①②实现③实现1、半联接的作用----4§5.3半联接优化方法

2、

半联接优化算法输入信息：位于不同场地上的两个关系R和S输出信息：实现R∞S（R.A=S.B）算法：（设S的尺寸小于R）（1）在S所在场地上计算S′=∏B（S）;（2）传送S′到R场地（3）在R场地上计算R′=R∞S′=R∝S（4）将R′传到S所在场地（5）在S所在场地上计算

R′∞S=（R∝S）∞S=R∞S§5.3半联接优化方法

3、传输代价的比较假设：关系R和S分别在不同的场地上，C0为启动代价，C1为单位传输代价。设：在S所在的场地上执行，则传输关系R实现R∞S的代价

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′))分析：如果有：C∞≥C∝

则：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系统优化技术本地（S.B的选择度）设查询在S所在的场地获益：R’S代价：S’R比传输R减少了（1－）倍的数据4

基本优化算法输入信息：查询联接图及关系概要图输出信息：半联接执行序列集合P′及最后的执行场地算法：Begin/*初始化*/包含所有可执行的一元操作和局部操作，构成执行策略集P′；计算所有的半联接的代价和利益，构成受益半联接集P。/*选择半联接*/While（存在∝满足（Benefit（∝）≥Cost（∝）））{

P′=P′∪{∝′|∝′为最大受益半联接}

修改概要图（最大受益半联接∝′执行结果的概要图）；重新估计执行∝′后的各个半联接的代价和利益}；/*选择执行场地*/

FORI=1，…，n{计算在场地Si上执行联接运算的网络传输代价Cost（Si）} SR=Min{Cost（S1），Cost（S2），……，Cost（Sn）}

End§5.4SDD-1系统优化技术§5.4SDD-1系统优化技术50005、举例--例5.4.2假设：C0=0，C1=1 DOM（Supplier.Sno）∈DOM（Supply.Sno）DOM（Dept.Dno）∈DOM（Supply.Dno）优化过程：(1)求可能的半联接集合

P1=Supply∝Supplier P2=Supply∝DeptP3=Supplier∝Supply P4=Dept∝Supply（2）初始的利益代价表以P1=Supply∝Supplier为例，求初始的利益代价表，需要的计算公式如下：ρ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.04Kρ3=1，Benefit3=0ρ4=1，Benefit4=0因此，初始的利益代价表如下：根据初始的利益代价表，得到受益半联接集P={P1，P2}§5.4SDD-1系统优化技术§5.4SDD-1系统优化技术5、举例--例5.4.2§5.4SDD-1系统优化技术5、举例--例5.4.25000

c.重新计算利益代价表·P1=Supply′∝Supplier∵Supply′∝Supplier的选择度ρ同Supply∝Supplier的选择度ρ∴ρ1=0.2Benefit1=(1-ρ)*Card(Supply′)*Size(Supply′)=0.8*1000*(4+2)=4.8KCost1=Val（Supplier,Sno）*Size(Supplier,Sno)=200*4=0.8K·P3=Supplier∝Supply′∵Val（Supply，Sno）=1000缩减到Val（Supply′，Sno）=666而：DOM（Supplier.Sno）∈DOM（Supply.Sno）因此，200:x=1000:666,x=200*666/1000=133=400/3∴ρ3=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.6K·P4=Dept∝Supply′ρ4=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=200•Val（Supply″,Sno）∵ Sno属于选择谓词Val（Supply′，Sno）=666∴Val（Supply″,Sno）=ρ*Val（Supply′,Sno）=0.2*666=133•Val（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=Supply′∝Supplier已处理，无Supply″∝Dept半联接） P3=Supplier∝Supply″ P4=Dept∝Supply″

c.重新计算利益代价表·P3=Supplier∝Supply″∵DOM（Supplier.Sno）∈DOM（Supply.Sno）

Val（Supply″,Sno）=133,则Val（（Supplier∝Supply″），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.5K·P4=Dept∝Supply″ρ4=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=133•Val（Supplier′,Sno）∵ Sno属于选择谓词Val（Supplier，Sno）=200∴Val（Supplier′,Sno）=ρ*Val（Supplier,Sno）=0.666*200=133•Val（Supplier′,Sname）∵ Sname不属于选择谓词，Card（Supplier′）=133，Val（Supplier，Sname）=200有：Val（Supplier，Sname）/2≤Card（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′=Supply∝Dept=P2（在场地上S2执行）Supply″=Supply′∝Supplier=P1（在场地上S2执行）Supplier′=Supplier∝Supply″=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后优化处理---准则27、半联接技术的不足半联接技术是通过局部缩减操作缩减关系的数据量，发送缩减的关系到执行场地，在执行场地对缩减后的关系进行查询处理。采用该技术大大地降低了场地间传递的信息量，从而减少了整个系统的传输代价。但同时，增加了系统的局部处理代价。这是半联接技术存在的缺点。归纳半联接技术，有如下不足：（1）没有考虑局部代价；如：R∞S=（R∝S）∞S=R∞∏B（S）①∏B（S）的代价②R∞∏B（S）的代价（2）

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

SDD-1优化技术是采用半联接技术对所有受益半联接进行缩减操作，确定一个执行代价最小的场地。再经过后优化处理得到最佳的执行策略。系统的总代价需根据系统的组成环境综合考虑传输和局部代价，或侧重考虑某一方面的代价。因此，在应用半联接技术时，要考虑其适应的环境。

§5.4SDD-1系统优化技术§5.5枚举法优化技术查询操作的代价评估，需要综合考虑局部代价和传输代价。侧重于哪一方面，需根据系统组成环境确定。若侧重传输代价，局部代价可以忽略不计时，采用半联接技术较好；相反，侧重局部代价时，采用直接联接比采用半联接技术优越。因为直接联接技术实现简单。枚举法是基于直接联接的实现方法，下面介绍其优化技术。1、实现联接运算的方法如：关系O、I，实现O∞I（O.A∞I.B）。下面将介绍其实现的两种方法及其代价评估。两种实现方法为：嵌套循环法（nest_loop）和合并扫描法（merge_scan）。§5.5枚举法优化技术1、实现联接运算的方法§5.5枚举法优化技术1、实现联接运算的方法（3）

执行联接的代价实现联接：Result=Out∞In①

嵌套循环法嵌套循环法是将关系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代价为2*Nin*Cio。§5.5枚举法优化技术（２）按需存取（FetchedasNeeded）按需存取是根据请求命令，按需读取所需要的信息。其传送费用可描述如下： １＊Cmes＋[（Card（O′）*Size（O′））/m]*Cmes其中：•１为请求报文；

•O′为需要传送的关系；（３）执行场地执行场地有三种情况：设在关系Ｏ所在的场地（Site(O)）或关系I所在的场地（Site(I)）或其它场地（Site(Other)）。确定不同的执行场地，需传送的不同的数据信息。如下所示：•Ｓite(O)：需传送Ｉ关系。•Ｓite(Ｉ)：需传送Ｏ关系。•Ｓite(Other)：需传送O和Ｉ关系。§5.5枚举法优化技术2、联接关系的传输方法３、Ｒ＊系统优化技术Ｒ＊系统是美国IBM公司研制的分布式数据库系统。其特点是各场地间既互相协调又自治；不支持数据分片和重复数据，但支持位置透明；支持场地间用局域网连接。Ｒ＊系统的优化目标是同时考虑传输费用和局部费用。其优化技术采用的是基于全部传送和按需存取的枚举法优化技术。下面就介绍Ｒ＊系统所采用的几种代价评估方法。（１）

内关系所在的场地Site(I)为执行场地①嵌套循环，外关系全体传送费用Ｃ1为嵌套循环的局部费用和外关系Ｏ的传输费用之和，其费用描述为：Ｃ1=C(nest_loop)+[（Card（O）*Size（O））/m]*Cmes②合并扫描，外关系全体传送费用Ｃ2为合并扫描的局部费用和外关系Ｏ的传输费用之和，其费用描述为：Ｃ2=C(merge_scan)+[（Card（O）*Size（O））/m]*Cmes§5.5枚举法优化技术

(2)

外关系所在的场地Site(O)为执行场地③嵌套循环，内关系按需传送由于每个外关系Ｏ的元组对Ｉ发一次请求，则平均有NI个元组满足请求被传送回来，因此其费用C3描述为：费用Ｃ3=C(nest_loop)+Cmes*Card（O）*(1+(NI*Size(I)/m)其中：•NI为与关系Ｏ的一个元组相匹配的平均元组个数；•１为请求报文。④合并扫描，内关系全体传送费用Ｃ4为合并扫描的局部费用、内关系Ｉ的传输费用和本场地的IO代价之和，其费用描述为：费用Ｃ4=C(merge_scan)+Cmes*[（Card（I）*Size（I））/m]+2*Nin*Cio⑤合并扫描，内关系按需传送此方法中，需将外关系Ｏ的联接属性Ａ的不同的值在请求报文中传送到Ｉ所在场地，之后将匹配的Ｉ元组传送回来，因此其费用Ｃ5描述为：费用Ｃ５=C(merge_scan)+Cmes*Val（O，A）*[1+（NI*Size（I））/m]§5.5枚举法优化技术

（3）

其它场地Site(Other)为执行场地⑥嵌套循环，内、外关系全体传送费用Ｃ6为嵌套循环的局部费用、内、外关系的传输费用和本场地的IO代价之和，其费用描述为：费用Ｃ6=C(nest_loop)+Cmes*[（Card（I）*Size（I）+Card（O）*Size（O））/m]+2*Nin*Cio⑦合并扫描，内、外关系全体传送费用Ｃ7为合并扫描的局部费用、内、外关系的传输费用和本场地的IO代价之和，其费用描述为：费用Ｃ7=C(merge_scan)+Cmes*[（Card（I）*Size（I）+Card（O）*Size（O））/m]+2*Nin*CioR*系统的优化技术就是对所有存在的联接方法的评估费用进行对比，之后选择一个最优的联接操作策略。其算法可描述如下：（１）

计算７种评估方法的执行代价；（２）

选择最小执行代价的执行方法；（３）

确定执行场地、联接方法和传递方法。§5.5枚举法优化技术Twoexamplesshowingthetechniques–INGRES–dynamicoptimizationSystemR–staticoptimizationbasedonexhaustivesearchCommercialDBMS’s–variants.§5.6.1INGRES Language:QUEL–atuplecalculuslanguageExample:rangeofeisErangeofgisGrangeofjisJretrieveE.ENAMEwheree.ENO=g.ENOandj.JNO=g.JNO

andj.JNAME=”CAD/CAM”Note:e,g,andjarecalledvariable.§5.6

CENTRALIZEDQUERYOPTIMIZATION§5.6.1INGRESOne-variablequery:queriescontainingasinglevariable.Multivariablequery:queriescontainingmorethanonevariable.QUELcanbeequallytranslatedintoSQL.WejustuseSQLforconvenience.GeneralstrategyofINGRES–Decomposeamultivariablequeryintoasequenceofquerieshavinguniquevariableincommonandthenprocesseachone-variablequerybyOVQP(OneVariableQueryProcessor).OVQPoptimizesaquerybyselectingthebestaccessmethod,e.g.index,sequentialscan,etc.Detachmentandsubstitutiontechniques§5.6

CENTRALIZEDQUERYOPTIMIZATION§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATION§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONGeneralcase:q: SELECTV2.A2,V3.A3,…,Vn.An FROM R1V1,R2V2,…,Rn

Vn

WHEREP1(V1.A1)AND P2(V1.A1,V2.A2,…,Vn.An)§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONExampleq1: SELECT

E.ENAME RFOM E,G,J

WHEREE.ENO=G.ENOANDJ.JNO=G.JNO ANDJ.JNAME=”CAD/CAM”q1isdecomposedintoq11q12q13:q11: SELECTJ.JNOINTOJVAR FROMJ WHEREJNAME=”CAD/CAM”q’: SELECTE.ENAME FROME,G,JVAR WHEREE.ENO=G.GNO ANDG.JNO=JVAR.JNOq’canbefurtherprocessedbydetachingG§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONExampleq12: SELECTG.ENOINTOGVARFROMG,JVARWHEREG.JNO=JVAR.JNOq13: SELECTE.ENAME FROME,GVAR WHEREE.ENO=GVAR.ENO§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONSubstitution–forann-variablequeryq,chooseonevariableV1(sayforrelationR1)toreplaceqwitheverytupleofRtogenerate(n-1)-variablerelations.Itcanbesummarizedas§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONSubstitution–Example:LetGandquerybe SELECTE.ENAME FROM E,G WHEREE.ENO=G.ENO G={(E1,J1,_),(E2,J1,_),(E3,J2,_)}ThesubstitutionofGforthequerygeneratesthreesubqueriesq1: SELECTE.ENAMEFROMEWHEREE.ENO=”E1”q2: SELECTE.ENAMEFROMEWHEREE.ENO=”E2” q3: SELECTE.ENAME FROM E WHEREE.ENO=”E3” §5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONRecursivequeryoptimizationalgorithmofINGRES:(1)Usedetachmenttoapplyandasearlyaspossible.TheresultsofmonovariablequerieswillbeusedbyOVQPandlaterqueries.(2)Processingirreduciblequeriesthatremainafterdetachmentbytuplesubstitution.Thevariablerepresentingtherelationwiththesmallestcardinalitywillbechosenforthissubstitution.§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATION§5.6.1INGRES§5.6

CENTRALIZEDQUERYOPTIMIZATIONR§5.6.2SystemRalgorithm

§5.6

CENTRALIZEDQUERYOPTIMIZATIONStaticqueryoptimizationbasedonexhaustivesearchofthesolutionspace. Twomajorsteps:first,thebestacces