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

第五章分布查询的存取优化第五章分布查询的存取优化分布式查询处理概述分布式查询查询分解查询存取优化局部查询优化优化的本地执行策略片段查询的逻辑查询计划全局模式本地模式带通讯的查询执行策略全局控制局部控制物理查询计划逻辑查询计划查询优化数据局部化分片模式全局逻辑查询计划树分片状态第五章分布查询的存取优化分布查询的存取优化基本概念优化的理论基础半联接优化方法SDD-1系统优化技术第五章分布查询的存取优化5.1基本概念分布执行过程实际上就是从查询场地发出查询命令、从数据源获取数据、确定最佳的执行场地和返回执行结果的过程。查询场地：指发出查询命令和存储最终查询结果的场地。查询场地也称最终结果文件。源数据场地：指查询命令需要访问的数据副本所在的场地，可能涉及到一个或一个以上的场地。源数据场地也称源数据文件。执行场地：指查询操作执行所在的场地。执行场地可以和查询场地或源数据场地处于同一场地，也可不处于同一场地。执行场地也称中间结果文件。查询场地源数据场地执行场地查询命令数据查询结果第五章分布查询的存取优化基本概念分布执行策略举例有关系EMP和DEPT。EMP{ENO，ENAME，BIRTH，SALARY，DNO}（ENO为主键，DNO为外键）ENO，ENAME，BIRTH，SALARY，DNO分别为雇员编号雇员姓名出生日期工资部门号DEPT{DNO，DNAME}（DNO为主键）DNO，DNAME分别为部门号，部门名称假设：（1）EMP：元组数：10000，元组大小：100B，关系大小：100*10000=1000KB（2）DEPT：元组数：100，元组大小：35B，关系大小：35*100=3.5KB第五章分布查询的存取优化假设：结果元组大小40字节，S3为查询场地结果关系大小：40*10000=400KB基本概念S1(EMP)网络S2(DEPT)S3(查询场地)(3)存在三个场地，S1、S2和S3。如图：查询要求：查询每个雇员的姓名及所在单位。则：（1）SQL语句：SELECTENAME，DNAMEFROMEMP，DEPTWHEREEMP.DNO=DEPT.DNO（2）关系表达式：ENAME，DNAME（EMP∞DEPT）分布执行策略举例第五章分布查询的存取优化分布执行策略举例-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查询存取优化的内容第五章分布查询的存取优化例子:5.2存取优化的理论基础site1site2site3xy假设只考虑通信代价总时间=2*消息启动时间+单位传输代价*(x+y)第五章分布查询的存取优化5.2.1查询代价模型代价模型主要指传输代价（Ccom）、I/O代价（CIO）和CPU代价（Ccpu）Totalcost=Ccom+CIO+Ccpu传输代价费用和延迟。其中费用起决定作用。传输费用是指通信中的整个传输开销，即传输的数据量。模型为：CCOM（X）=C0+C1*X其中：C0：场地间传输数据的启动所需的固定费用（启动一次），简称启动代价；C1：网络单位传输数据费用，简称单位传输代价；X：需传输的数据量。第五章分布查询的存取优化5.2.1查询代价模型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。可见，在广域网环境，以传输代价为主；在局域网环境，需综合考虑传输代价和局部代价。第五章分布查询的存取优化•关系的基：指关系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数据库的特征参数第五章分布查询的存取优化1.选择运算（S=σF（R））选择度：满足选择谓词F的元组与R元组总数之比，记为ρ基数：Card（S）=ρ*Card（R）5.2.3关系运算的特性参数第五章分布查询的存取优化5.2.3关系运算的特性参数选择度的具体计算方法:①等值比较S=A=X(R)，其中A是R的属性，X是常数。则=1/Val(R,A)Card(S)=Card(R)/Val(R,A)②非等值比较S=AX(R)时：=(Max(A)-X)/(Max(A)-Min(A))S=AX(R)时：=(X-Min(A))/(Max(A)-Min(A))③不等比较S=AX(R)时:=(Val(R,A)-1)/Val(R,A)④多属性选择条件S=CiANDCj(R)时:=i*jS=CiORCj(R)时:=1-(1-i)(1-j)=(i+j-i*j)第五章分布查询的存取优化1.选择运算（S=σF（R））关系的宽度：Length（S）=Length（R）属性不同值：5.2.3关系运算的特性参数第五章分布查询的存取优化属性不同值：当属性B属于选择谓词时，如果选择条件中有等式条件B=X，则Val（S，B）=1当属性B与选择谓词相关且为关键字时，则Val（S，B）=σVal（R，B）当属性B不属于选择谓词时，Card（S），若Card（S）=Val(R,B)/2(Card(S)+Val(R,B))/3,Val(R,B)若Card（S）=2Val(R,B)5.2.3关系运算的特性参数第五章分布查询的存取优化2.投影运算(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.3关系运算的特性参数(,)()iiAAttrListValRACardR()(,)iiAAttrListCardSValRA第五章分布查询的存取优化联接运算T=R∞S，（R.a=S.a）基数：存在Card（T）≤Card（R）×Card（S）基本计算形式若Val(R.A)≤Val（S.A),则对于R的每个元组都有1/Val（S.A)的概率与S中的元组进行连接，因此能够连接的元组数是Card（S）/Val（S.A)，则连接所产生的元组数是：Card（R）*Card（S）/Val（S.A)因此：Card（T）=Card（R）*Card（S）/max(val(R,A),Val(S,b))若b为关键字，a为外关键字Card（S）=Card（R）关系的宽度Length（T）=Length（R）+Length（S）-Length（A）5.2.3关系运算的特性参数第五章分布查询的存取优化联接运算T=R∞S，（R.a=S.a）不同值的个数：设a为联接属性Val(S,a)≤Min(Val(R,a),Val(S,a))若a不为联接属性Val（T，a）≤Val（R，a）(a为R的属性)Val（T，a）≤Val（S,a）(a为S的属性)5.2.3关系运算的特性参数第五章分布查询的存取优化半联接运算T=R∝S，（R.a=S.a）半联接操作是全联接操作的一种缩减。是一种导出操作，且具有不对称性。R∝S≠S∝R半联接操作（R∝S）是R与S自然连接后在R上的投影，描述为：R∝S=Attr（R）(R∞S)基数：Card（S）=ρ*Card（R）ρ为半联接选择度关系的宽度：Length（S）=Length（R）不同值的个数：a.设a为联接属性Val（T，a）=ρ*Val（R，a）b.若a不为联接属性：选择运算中不同值的估计方法Val（S，a）≤Val（R，a）5.2.3关系运算的特性参数Val(,A)(.)Val([A])SSAdom第五章分布查询的存取优化对联接操作的优化有两种趋势，一种为采用半联接技术，减少联接操作的操作数，以降低传输费用；另一种为采用全联接技术，主要考虑局部代价。一个系统需根据其目标综合确定其优化算法。5.3半联接优化方法第五章分布查询的存取优化经半连接操作，减少操作关系的大小，从而减少站点间数据的传输量。假定站点1上的关系R和站点2上的关系S，在属性R.A=S.A上做连接操作。()(())()(())RASARSRSRSSRSRSR半连接操作第五章分布查询的存取优化()(())()(())AARSRSSRSSRSSRRSRR采用半连接方法表示连接操作第五章分布查询的存取优化半联接的作用5.3.1半连接操作及相关规则假设有雇员关系EMP和部门关系DEPT，EMP：Card（EMP）=10000；DEPT：Card（DEPT）=100其中，关系EMP保存在场地S1，关系DEPT保存在场地S2，如下图所示。现有查询要求：在场地S2上查询部门名称和部门经理姓名，选择最优的执行策略，这里只考虑数据传输代价。查询的SQL语句如下：SELECTDNAME,ENAMEFROMDEPT,EMPWHEREDEPT.MgrNO=EMP.ENO关系代数表达式为：Q=DNAME，ENAME(DEPT∞EMP)属性ENOENAME……长度(B)435属性DNODNAMEMgrNo…长度(B)4354场地S1：EMP网络场地S2：DEPT查询Q第五章分布查询的存取优化下面通过三种查询策略分析其代价评估（COST）策略1：执行场地设在S2需将EMP的Eno和Ename属性传送到S2场地COST=(Length(Eno)+Length(Ename))*Card(EMP)=39*10000=390KB5.3.1半连接操作及相关规则执行场地场地S1：EMP网络场地S2：DEPT查询Q第五章分布查询的存取优化策略2：执行场地设在S1需将DEPT的Dname和Mgno属性传送到S1场地，做自然连接后，再将结果传回场地S2。设R为结果。COST1=(Length(Dname)+Length(M