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

第五章分布查询的存取优化基于代价的优化查询优化过程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）/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=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））基数：如果投影涉及单个属性ACard（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具体算法由两部分组成：一是根据评估缩减算法确定一个收益最大的执行策略，但此执行策略的效率