分布查询的存取优化PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,2,*,第五章 分布查询的存取优化,第五章 分布查询的存取优化,1,2,分布式查询处理概述,分布式查询,查询分解,查询存取优化,局部查询优化,优化的本地执行策略,片段查询的逻辑查询计划,全局模式,本地模式,带通讯的查询执行策略,全局控制,局部控制,物理查询计划,逻辑查询计划,查询优化,数据局部化,分片模式,全局逻辑查询计划树,分片状态,2,2025/4/30 周三,查询存取优化,输入：片段查询,找到好的（不必最优的）全局调度,最小代价函数,分布,Join,处理,稠密树与线性树,需要传输的关系,全部传输与按需传输,确定使用半连接,使用半连接可减少通信代价,Join,方法,嵌套循环与顺序,join,（合并,join,与,hash join,）,分布式查询处理概述,3,2025/4/30 周三,基于代价的优化,搜索空间（,Solution space,）,等价的代数表达式,(query trees).,代价函数（,Cost function,）,I/O,代价,+CPU,代价,+communication,代价,不同的分布环境中各因素权重不同,(LAN vs WAN).,最大吞吐量,搜索算法（,Search algorithm,）,如何在解决空间中移动,穷举搜索，启发式算法,(,递归改进、模拟退火、遗传法等）,分布式查询处理概述,4,2025/4/30 周三,查询优化,最小化查询代价,查询优化过程,分布式查询处理概述,Input Query,Search Space,generation,等价的,QEP,（,query execution plan,）,Search strategy,Best QEP,Transformation,Rules,Cost model,5,2025/4/30 周三,分布式查询处理概述,搜索空间,(,Search Space,),搜索空间由可选择的执行计划描述,侧重,Join,树,若存在,n,个关系，有,O(N!),等价的,Join,树,例如，,select ENAME,RESP,From EMP,ASG,PROJ,Where EMP.ENO=ASG.ENO,And ASG.PNO=PROJ.PNO,EMP,ASG,PROJ,ENO,PNO,PROJ,ASG,PNO,ENO,EMP,EMP,PROJ,ENO,PNO,ASG,6,2025/4/30 周三,分布式查询处理概述,搜索空间,(,Search Space,),由启发式规则约束,如一元操作先于二元操作执行,约束,join,树的形状,只考虑线性树而忽略了稠密树,线性,join,树：,R,1,R,2,R,3,R,4,稠密,join,树：,R,1,R,2,R,3,R,4,7,2025/4/30 周三,搜索策略,(,Search Strategy,),如何在搜索空间中构建查询计划,确定的（,Deterministic,）,开始于基关系，每步加一个关系构建执行计划,动态规划法：宽度优先（,breadth-first,）,贪婪法,:,深度优先（,depth-first,）（,只构造一个计划,）,随机的（,Randomized,）,从一个特定的点起始搜索最优执行计划,(,首先应用贪婪法构建一个或多个执行计划，接着通过邻居关系替换来改进执行计划,),综合考虑优化时间和执行时间,适合大于,5-6,个关系,模拟退化（,Simulated annealing,）,递归改进（,Iterative improvement,）,构造所有可能的执行计划；,尽早剪裁不是优化的计划；,Is also exhaustive;,关系数少时，优化代价可接受,;,分布式查询处理概述,8,2025/4/30 周三,随机的（,Randomized,）,随机交换操作关系,搜索策略,(,Search Strategy,),确定的（,Deterministic,）,从基关系开始，每步联接一个或多个关系，直到获得全部的计划,分布式查询处理概述,R,1,R,2,R,3,R,4,R,1,R,2,R,3,R,1,R,2,R,1,R,2,R,3,R,1,R,3,R,2,9,2025/4/30 周三,分布查询的存取优化,基本概念,优化的理论基础,半联接优化方法,SDD-1,系统优化技术,枚举法优化技术,集中的查询优化,(CENTRALIZED QUERY OPTIMIZATION),10,2025/4/30 周三,基本概念,分布执行过程,实际上就是从查询场地发出查询命令、从数据源获取数据、确定最佳的执行场地和返回执行结果的过程,。,查询场地,：,指发出查询命令和存储最终查询结果的场地。查询场地也称最终结果文件。,源数据场地,：指查询命令需要访问的数据副本所在的场地，可能涉及到一个或一个以上的场地。源数据场地也称源数据文件。,执行场地,：指查询操作执行所在的场地。执行场地可以和查询场地或源数据场地处于同一场地，也可不处于同一场地。执行场地也称中间结果文件。,查询场地,源数据场地,执行场地,查询命令,数据,查询结果,11,2025/4/30 周三,基本概念,分布执行策略举例,有关系,EMP,和,DEPT,。,EMPENO,，,ENAME,，,BIRTH,，,SALARY,，,DNO,（,ENO,为主键）,ENO,，,ENAME,，,BIRTH,，,SALARY,，,DNO,分别为雇员编号 雇员姓名 出生日期 工资 部门号,DEPTDNO,，,DNAME,（,ENO,为主键）,DNO,，,DNAME,分别为部门号，部门名称,假设：,（,1,）,EMP,：元组数：,10000,，元组大小：,100B,，关系大小：,100*10000=1000KB,（,2,）,DEPT,：元组数：,100,，元组大小：,35B,，关系大小：,35*100=3.5KB,12,2025/4/30 周三,假设：,结果元组大小,40,字节，,S3,为查询场地,结果关系大小：,40*10000=400KB,基本概念,S1(EMP),网络,S2(DEPT),S3(,查询场地,),(3),存在三个场地，,S1,、,S2,和,S3,。如图：,查询要求：,查询每个雇员的姓名及所在单位。,则：（,1,）,SQL,语句：,SELECT ENAME,，,DNAME,FROM EMP,，,DEPT,WHERE EMP.DNO=DEPT.DNO,（,2,）关系表达式：,ENAME,，,DNAME,（,EMPDEPT,）,分布执行策略举例,13,2025/4/30 周三,分布执行策略举例,-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,从上面三个策略看，选择不同的执行场地，传输代价差别很大。应选择最低的传输代价。但组成系统的环境不同，优化的侧重点也不同。,基本概念,14,2025/4/30 周三,基本概念,分布查询的存取优化,的目标,对于远程网，主要考虑通信开销，使通信代价最小。,对于局域网，需同时考虑通信代价和本地处理代价，使综合代价最小。,优化的内容,优化,是在片段查询的基础上进行的实际物理副本查询操作的优化。具体如下：,输入：片段查询表达式,输出：分布执行计划,15,2025/4/30 周三,查询存取优化,内容：,确定片段查询需访问的物理副本,。,通常：,本场地上的物理副本优先；,若二元运算存在尽量选择本场地上的二元运算；,数据最小的物理关系应被优先选中；网络通信代价小的应优先选中,确定片段查询表达式操作执行的最优顺序。,包括从叶到根的执行和同一层叶子上表达式执行的先后，特别是对查询树上的并操作和联接操作的执行次序的确定，其代价差别很大。,选择执行每个操作的方法。,如：尽量将同一场地上的、同一物理副本的全部操作组合在一起统一考虑完成。,基本概念,16,2025/4/30 周三,存取优化的理论基础,代价函数,(the total time or the response time),总的时间（,Total Time,）,-,所有时间组件的和,减少每一个组件的时间代价,尽可能减少每个代价组件的代价,优化资源利用率，增加系统吞吐率,响应时间（,Response Time,）,-,从查询开始到执行结束所用的时间,尽可能并行执行（,Do as many things as possible in parallel,）,增加总的活动（,activity,）可能会增加总时间,17,2025/4/30 周三,例子,:,存取优化的理论基础,site1,site2,site3,x,y,假设只考虑通信代价,总时间,=2*,消息启动时间,+,单位传输代价*,(x+y),响应时间,=max(,从,1,传输,x,到,3,的时间，从,2,传输,x,到,3,的时间,),18,2025/4/30 周三,存取优化的理论基础,代价模型,主要指传输代价（,C,com,）,、,I/O,代价（,C,IO,）和,CPU,代价（,C,cpu,）,Total cost=C,com,+C,IO,+C,cpu,传输代价,费用,和,延迟,。其中费用起决定作用。,传输费用,是指使通信中的整个传输开销，即传输的数据量。,模型为：,C,COM,（,X,）,=C,0,+C,1,*X,其中：,C,0,：场地间传输数据的启动所需的固定费用（启动一次），简称启动代价；,C,1,：网络单位传输数据费用，简称单位传输代价；,X,：需传输的数据量。,19,2025/4/30 周三,存取优化的理论基础,I/O,代价,模型为：,C,IO,（,X,）,=X/P*C,IO,其中,：,P,：页面的大小；,C,IO,：为每页平均访问代价；,X,：数据量大小。,CPU,代价,模型：,C,CPU,（,X,）,=X*C,CPU,其中：,C,CPU,：单位指令代价；,X,：为指令数。,通常具有下面的统计值：,广域网环境：,C,COM,/C,IO,=20,：,1,；,局域网环境：,C,COM,/C,IO,=1.6,：,1,。,可见,，在广域网环境，以传输代价为主；在局域网环境，需综合考虑传输代价和局部代价。,20,2025/4/30 周三,查询模型,主要代价因素,:,中间关系大小,数据库特征参数,假设,R,为一关系,关系的基：,指关系,R,包含的元组个数，记为,Card(R),属性的长度,：指属性,A,定义的取值字节数，记为,Length(A),元组的长度,：关系,R,中每个元组的字节数，记为,Length(R),Length(R)=,Length(A,i,),关系的大小,：关系,R,所包含的字节数，记为,Size(R),Size(R),=,Card(R),*,Length(R),属性的特征值,：指关系,R,中属性,A,取值不同的属性值个数，记为,Val(A),属性,A,的值域,：记为,Dom(A),属性,A,的最大值和最小值,：记为,Max(A),和,Min(A),存取优化的理论基础,21,2025/4/30 周三,关系运算的特征参数,假设：,R,、,S,为关系。,选择运算,（,S=,F,（,R,）,选择度：,满足选择谓词,F,的元组与,R,元组总数之比，记为,基数：,Card,（,S,）,=*Card,（,R,）,关系的宽度：,Length,（,S,）,=,Length,（,R,）,Length,（,S.A,）,=,Length,（,R.A,）,存取优化的理论基础,22,2025/4/30 周三,存取优化的理论基础,选择运算,(,中间关系大小,),选择度,的具体计算方法,:,等值比较,S=,A=X,(R),，其中,A,是,R,的属性，,X,是常数。,则,=,1/Val(R,A),非等值比较,S=,AX,(R),时：,=(Max(A)-X)/(Max(A)-Min(A),S=,AX,(R),时：,=(X-Min(A)/(Max(A)-Min(A),不等比较,S=,AX,(R),时,:=(Val(R,A)-1)/Val(R,A),多属性选择条件,S=,Ci AND Cj,(R),时,:=,i,*,j,S=,Ci OR Cj,(R),时,:=1-(1-,i,)(1-,j,)=(,i,+,j,-,i,*,j,),23,2025/4/30 周三,选择运算,（,S=,F,（,R,）,不同值的个数：,a.,设,B,不属于选择谓词,F,，其值均匀分布。,存取优化的理论基础,Card(S),当,Card(S)Val(R,B)/2,时,Val(S,B)=(Card(S)+Val(R,B)/3,当,Val(R,B)/2,Card(S)2Val(R,B),时,Val(R,B),当,Card(S),2Val(R,B),时,b.,设,B,属于选择谓词,F,若,B=X,（值），则：,Val,（,S,，,B,）,=1,若,B,与选择谓词,F,相关且为关键字，,则：,Val,（,S,，,B,）,=*Val,（,R,，,B,）,24,2025/4/30 周三,令,=0.1,则：,Card(S)=*Card(R)=0.1*100=10,Card(S)=10,Val(R,B)/2=35,Card(S)Val(R,B)/2,Val(S,B)=Card(S)=10,存取优化的理论基础,选择运算,（,S=,F,（,R,）,举例：,设,Card,（,R,）,=100,，,Val,（,R,，,B,）,=70,令,=0.5,则：,Card(S)=*Card(R)=0.5*100=50,Card(S)=50,Val(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,25,2025/4/30 周三,投影运算,(S=,A,(R),基数：,如果投影涉及单个属性,A,：,Card,（,S,）,=Val,（,R,，,A,）,如果,A,中包含关键字：,Card,（,S,）,=Card,（,R,）,投影涉及多个属性：,关系的宽度：,Length,（,S,）,=Length,（,A,i,）（,A,i,A,）,Size,（,S,）,=Card,（,S,）*,Length,（,S,）,Size,（,S,）,Size,（,R,）,不同值的个数：,Val(S,A)=Val(R,A),存取优化的理论基础,26,2025/4/30 周三,并、交与差,(,如果结果关系执行消除重复操作，则都只能计算出结果关系基数的上限和下限，因此通常采用平均值作为基数的估计值。,),基数：,并运算,如果不消除重复，则结果关系基数等于两个关系基数之和：,Card(T)=Card(R)+Card(S),如果消除重复，则结果关系基数最大可大至两个关系基数之和，最小可小至两个关系基数的大者，因此有：,MaxCard(R),Card(S)Card(T)Card(R)+Card(S),在估计中使用中间值作为结果关系基数,:,(MaxCard(R),Card(S)+Card(R)+Card(S)/2,存取优化的理论基础,27,2025/4/30 周三,并、交与差,基数：,交运算,交运算的结果关系最小可以是空，最大可以等于两个关系的较小者，因此按取区间中间值的方法估计结果关系的基数为较小关系基数的一半：,Card(T)=MinCard(R),Card(S)/2,差运算,对于两个关系的差运算,R-S,，其结果关系基数的区间为：,Card(R)-Card(S)Card(T)2Val(SUPPLY,DNO),，因此：,Val(SUPPLY,DNO)=Val(SUPPLY,DNO)=100,三个关系的概要图更新为如下：,Card(SUPPLY)=500,Length,Val,4,100,2,100,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,DNAME,53,2025/4/30 周三,举例,重新计算利益代价表,P,2,=Supply,DEPT,Val(SUPPLY,DNO),与,Val(DEPT,DNO),同比例缩减，因此,2=0.2,Benefit2=(1-2)*Card(SUPPLY)*Length(SUPPLY)=0.8*500*6=2.4K,Cost2=Val(DEPT,DNO)*Length(DEPT,DNO)=20*2=0.04K,P,3,=SupplierSupply,由于,DOM(SUPPLY.SNO),DOM(SUPPLIER.SNO),，因此,3=Val(SUPPLY,SNO)/Val(SUPPLIER,SNO)=100/200=0.5,Benefit3=(1-3)*Card(SUPPLIER)*Length(SUPPLIER)=0.5*200*24=2.4K,Cost3=Val(SUPPLY,SNO)*Length(SUPPLY,SNO)=100*4=0.4K,P,4,=DeptSupply,近似为,1,，,Benefit4,近似为,0,SDD-1,系统优化技术,Card(SUPPLY)=500,Length,Val,4,100,2,100,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,TYPE,半联接,代价,(Cost),选择度,利益,(Benefit),P,1,0.8K,None,None,P,2,0.04K,0.2,2.4K,P,3,0.4K,0.5,2.4K,P,4,0.2K,1,0,P1=SupplySupplier=SupplySupplier,P2=SupplyDept,P3=SupplierSupply,P4=DeptSupply,54,2025/4/30 周三,SDD-1,系统优化技术,举例,循环,2,从受益半联接集,P,中选择利益代价最小者,P,2,，,将,P,2,加到策略集,P,中，得：,P=,，,P,2,，,P,1,。,重新计算概要图,对于外连接,SUPPLY,DEPT,，需要更新,SUPPLY,的概要图内容，假设外连接后结果为,SUPPLY,(SNO,DNO),，则对于,SUPPLY,有：,Card(SUPPLY,)=*Card(SUPPLY)=0.2*500=100,DNO,属于连接,谓词：,Val(SUPPLY,DNO)=*Val(SUPPLY,DNO)=0.2*100=20,SNO,不属于,连接谓词：,Val(SUPPLY,SNO)=100,，,由于,1/2(SUPPLY,SNO),Card(SUPPLY,)2Val(SUPPLY,SNO),，因此：,Val(SUPPLY,SNO)=1/3*(Val(SUPPLY,SNO)+Card(SUPPLY,)=1/3*(100+100)=200/3,P1=SupplySupplier,P2=Supply,Dept,P3=SupplierSupply,P4=DeptSupply,Card(SUPPLY)=500,Length,Val,4,100,2,100,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,TYPE,55,2025/4/30 周三,SDD-1,系统优化技术,举例,循环,2,三个关系的概要图更新为如下,Card(SUPPLY,)=100,Length,Val,4,200/3,2,20,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,STYPE,Card(SUPPLY)=500,Length,Val,4,100,2,100,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,TYPE,P1=SupplySupplier,P2=Supply,Dept,P3=SupplierSupply,P4=DeptSupply,56,2025/4/30 周三,举例,重新计算利益代价表,P3=SUPPLIER,SUPPLY,由于,DOM(SUPPLY,.SNO),DOM(SUPPLIER.SNO),，选择度为：,3=Val(SUPPLY,SNO)/Val(SUPPLIER,SNO)=200/3/200=1/3,Benefit3,=(1-3)*Card(SUPPLIER)*Length(SUPPLIER)=0.67*200*24=3.2K,Cost3,=Val(SUPPLY,SNO)*Length(SUPPLY,SNO)=200/3*4=0.27K,P4=DEPT,SUPPLY,，,4,近似为,1,，,Benefit4,近似为,0,。,SDD-1,系统优化技术,半联接,代价,(Cost),选择度,利益,(Benefit),P,1,0.8K,None,None,P,2,0.04K,None,None,P,3,0.27K,0.33,3.2K,P,4,0.04K,1,0,Card(SUPPLY,)=100,Length,Val,4,200/3,2,20,SNO,DNO,Card(SUPPLIER)=200,Length,Val,4,200,20,200,SNO,SNAME,Card(DEPT)=20,Length,Val,2,20,2,1,DNO,STYPE,P1=SupplySupplier,P2=Supply,Dept,P3=SupplierSupply,P4=DeptSupply,57,2025/4/30 周三,SDD-1,系统优化技术,P1=SupplySupplier,P2=SupplyDept,P3=SupplierSupply,P4=DeptSupply,举例,循环,3,从受益半联接集,P,中选择,P,3,添加到策略集,P,中，得：,P=,，,P,3,，,P,2,，,P,1,。,重新计算概要图,对于外连接,SUPPLIER,SUPPLY,，需要更新,SUPPLIER,的概要图内容，假设外连接后结果为,SUPPLIER,(SNO,SNAME),，则对于,SUPPLIER,有：,Card(SUPPLIER)=*Card(SUPPLIER)=1/3*200=200/3,SNO,属于连接谓词，因此：,Val(SUPPLIER,SNO)=*Val(SUPPLIER,SNO)=1/3*200=200/3,SNAME,不属于连接谓词，因此：,Card(SUPPLIER)=200/3,PS,P),，则除去,SP,P,。同理，除去,SP,S,；,由于在关系,P.PNAME,上有索引，因此选择,(P,SP),，除去,SP,S,。,当加入第三个关系后，得到连接序列,(P,SP),S,。,90,2025/4/30 周三,System R-,举例,q1:SELECT,E.ENAME,RFOM E,G,J,WHERE E.ENO=G.ENO AND J.JNO=G.JNO,AND J.JNAME=,”,CAD/CAM,”,假设存在下列索引,:,E has an index on ENO,G has an index on JNO,J has an index on JNO and an index on JNAME,首先选择单关系的访问方法：,E:sequential scan,(,because there is no selection on E,),G:sequential scan,(because there is no selection on G),J:index on JNAME,集中式系统中的查询优化算法,91,2025/4/30 周三,假设,E,G,G,E,，,G,J,J,G,选择,(J,G)E):,选择具有索引,JNAME,的,J,；再基于索引,JNO,与,G,实现,Join,操作；再基于索引,ENO,与,E,实现,Join,操作,集中式系统中的查询优化算法,E,G,J,E,G,E,J,G,E,G,J,J,G,J,E,(G,E)J,(J,G)E,92,2025/4/30 周三,考虑代价的动态规划方法,首先构建一个只包含单个关系的基本代价表，之后，通过不断将关系填充到代价表进行评估，并仅保留必要信息，最后，获得最终的连接顺序。,例如，现有待执行连接的四个关系，其特征参数表如下：,集中式系统中的查询优化算法,R(a,b),S(b,c),T(c,d),U(d,a),Card(R)=2000,Card(S)=1000,Card(T)=1000,Card(U)=1500,Val(R,a)=2000,Val(S,b)=50,Val(T,c)=100,Val(U,d)=50,Val(R,b)=100,Val(S,c)=20,Val(T,d)=200,Val(U,a)=100,93,2025/4/30 周三,代价评估步骤：,在基础表中，每个单一关系,R,构成一个集合，其内容包括,R,的大小、代价取值为,0,和连接表达式就是关系,R,本身。,集中式系统中的查询优化算法,R,S,T,U,结果大小,2000,1000,1000,1500,最小代价,0,0,0,0,表达式,R,S,T,U,在基本表的基础上，生成两个关系构成集合的表。连接的结果大小采用结果公式进行计算，由于没有中间结果，最小代价为,0,，而表达式则使用较小关系作为外关系的连接。,结果公式：,Card(R,S)=Card(R)*Card(S)/Max(Val(R,A),Val(S,A),94,2025/4/30 周三,代价评估步骤：,集中式系统中的查询优化算法,R,S,R,T,R,U,S,T,S,U,T,U,结果大小,20,000,2,000,000,1,500,10,000,1,500,000,7,500,最小代价,0,0,0,0,0,0,表达式,S,R,T,R,U,R,S,T,S,U,T,U,接下来考虑三个关系集合的连接表。三个关系进行连接，顺序必然是先由两个关系连接，然后结果再和第三个关系连接，因此，必然存在一个中间结果关系。三个关系连接的结果大小可以由结果计算公式算出，且无论连接的顺序如何，其结果大小是固定的。对于最小代价的估计，这里使用中间结果大小作为简单的代价估计方法。由于要选择最小代价，因此选择连接结果最小的关系对，并基于这两个关系的连接生成三个关系的连接表达式。,95,2025/4/30 周三,代价评估步骤：,集中式系统中的查询优化算法,以,R,S,T,三个关系连接为例，需要比较其中任意两个关系连接的结果大小，选择其中最小的作为最小代价和连接计划。可以看出，,S,R,的大小为,20000,，,T,R,的中间关系大小为,2000000,，而,S,T,的中间关系大小为,10000,。因此选择它来生成,R,S,T,集合的连接计划。,R,S,T,R,S,U,R,T,U,S,T,U,结果大小,200000,15000,7500,75000,最小代价,10000,1500,1500,7500,表达式,(S,T),R,(U,R),S,(U,R),T,(T,U),S,96,2025/4/30 周三,代价评估步骤：,集中式系统中的查询优化算法,最后考虑全部四个关系连接的情况，无论连接的顺序如何，结果关系的大小估计值都是,1500000,个元组，而连接的代价可以看作是中间关系的代价之和。在本例中我们不仅考虑由三个关系的集合生成四个关系的集合情况，也考虑由两个包含两个关系的集合连接生成最终连接的情况，如右图。可以看出代价最小的连接顺序为,(UR)T)S,，其代价为,9000,。,连接的顺序,代价,(S,T),R),U,210000,(U,R),S),T,16500,(U,R),T),S,9000,(T,U),S),R,82500,(S,R),(T,U),27500,(T,R),(S,U),3500000,(U,R),(S,T),11500,97,2025/4/30 周三,集中式系统中的查询优化算法,PostgreSQL,中的遗传查询优化,图示为四个关系连接,R,S,T,U,的连接树，每个关系使用整数进行对应的连接编码为“,4-1-2-3”,，表示,oid,为,4,的关系,R,先与,oid,为,1,的关系,S,连接，再与,T,和,U,连接。,R,4,S,1,T,2,U,3,在使用遗传查询优化,(GEQO,，,Genetic Query Optimization,),模块生成执行计划时，,GEQO,模块首先使用标准的查询优化器生成在独立关系上查询谓词的扫描策略，对于连接则使用遗传算法处理。,98,2025/4/30 周三,集中式系统中的查询优化算法,PostgreSQL,中的遗传查询优化,初始阶段：,GEQO,模块简单地随机生成一些可行的连接序列，使用标准查询优化器来估计执行代价，选择代价最小的作为估计代价。,GEQO,模块应用遗传算法，将执行代价作为连接序列的适应性（适应性与执行代价成反比,),，保留执行代价较低的连接序列。,下一阶段：,GEQO,模块对在上一阶段保留的执行代价较低的连接序列，随机地选择这些连接序列中部分片段并改变其连接顺序以生成新的连接序列。,对于新生成的连接序列，,GEQO,模块评估其执行代价，并保留其中执行代价小的作为下一个循环阶段的候选连接序列。,最后，,从所有被评估过的连接序列中，选择执行代价最小的作为最终的执行策略。,99,2025/4/30 周三,分布式查询优化问题,代价模型,多查询优化,启发式规则裁剪,大的查询集合,优化,select-project-join,查询,也需要处理复杂查询,(,如,unions,disjunctions,aggregations,和,sorting),平衡优化代价与执行代价,启发式规则裁剪,heuristics to cut down on alternatives,控制搜索策略,优化与重优化间隔,数据库概要信息变化需要重优化,100,2025/4/30 周三,分布式系统中的查询优化算法,Distributed INGRES,方法,System R*,方法,Distributed INGRES,方法,当一个查询,Q,被分解为一组不可规约的子查询,q1,q2,qn,后，,集中式环境中可以简单地顺序执行每个子查询。,在分布式环境中，由于关系以分片的形式存储在多个站点上，因此子查询可能还需要继续细分以便能够在多个场地上执行，而这将产生在站点之间复制关系所需的通信代价。,一种简单的优化方式是优先处理,无前继查询,且所涉及的,关系较小,的子查询。一方面可以获得较小的中间结果，另一方面可以减少复制关系所需的传输代价。,分布式查询优化算法,101,2025/4/30 周三,Distributed INGRES,方法,执行过程大致如下：,1,：首先所有在单关系上的选择和投影查询操作会被下推到每个数据所在站点的本地执行；,2,：使用,INGRES,中的归约算法，将包含,n,个关系变量的查询,q,分解为一个连续的查询序列,q1,q2,qn,，由于单关系变量的查询已经处理结束（,1,：步），这里仅考虑不可归约的查询序列。,3,：对于查询归约后获得的,n,个不可归约子查询，算法每次选择其中一个子查询进行处理。每次执行哪个子查询是根据查询结构、关系分片大小和关系分片的位置分布选择的，主要根据查询序列的代价估计来确定子查询的执行顺序（用一种贪婪算法）。,4,：如果这个不可规约子查询能够在某个独立的站点执行而不需要复制关系分片，则直接跳转到第,8,步。否则需要复制关系分片。,分布式查询优化算法,102,2025/4/30 周三,Distributed INGRES,方法,执行过程大致如下（续）：,5,：选择查询的执行站点。根据分片涉及的站点，以及网络的拓扑结构（点到点或广播），对所有可能的执行场地进行考虑。,6,：生成查询执行策略。假设有,n,个关系的子查询，一个执行查询的站点包含其中一个关系的一个分片，则必须将其他,n-1,个关系全部复制到这个站点上才能够满足执行查询的条件。,7,：根据第,5,步中的执行策略复制各关系的分片到指定的站点。为了对查询进行优化，仅传输与查询相关的分片内容，并且可以使用广播的形式提高传输效率。,8,：由主,INGRES,站点向所有被选择的站点广播查询，查询被传输到各站点后，在各站点进行本地查询处理。如果所有站点上的本地查询都没有发生错误，则移除已执行的查询，在必要的情况下还要修改剩余关系变量的查询范围。,9,：返回第,3,步继续执行，直到处理完全部查询序列。,分布式查询优化算法,103,2025/4/30 周三,Distributed INGRES,方法,-,举例,核心：,选择哪个子查询执行；查询执行策略的选择,例如：存在三个关系：,SUPPLIER,（,SNO,SNAME,CITY,）,PROJECT(JNO,JNAME,CITY),SUPPLY(SNO,JNO,AMOUNT),存在场地：,S1,：,PROJECT,（,200,元组），,SUPPLIER1,（,50,元组）,S2,：,SUPPLY,（,400,元组），,SUPPLIER2,（,50,元组）,要查询“供货商及其所供应的工程属于同一城市的供货商名称和工程名称”，查询的,SQL,语句如下：,SELECT S.SNAME,J.JNAME,FROM SUPPLIER S,PROJECT J,SUPPLY SJ,WHERE S.SNO=SJ.SNO and SJ.JNO=J.JNO and S.CITY=J.CITY,分布式查询优化算法,104,2025/4/30 周三,分布式查询优化算法,Distributed INGRES,方法,-,举例,查询划分可有以下几种候选策略：,Q1,：,SELECT S.SNAME,J.JNAME INTO temp,FROM SUPPLIER S,PROJECT J,SUPPLY SJ,WHERE S.SNO=SJ.SNO and SJ.JNO=J.JNO and S.CITY=J.CITY,Q2,：,SELECT S.SNAME,S.CITY,SJ.JNO INTO temp,FROM SUPPLIER S,SUPPLY SJ WHERE S.SNO=SJ.SNO,Q3,：,SELECT S.SNAME,S.SNO,J.JNAME,J.JNO INTO temp,FROM SUPPLIER S,PROJECT J,WHERE S.CITY=J.CITY,Q4,：,SELECT J.JNAME,J.CITY,SJ.SNO INTO temp,FROM PROJECT J,SUPPLY SJ,WHERE J.JNO=SJ.JNO,SELECT S.SNAME,J.JNAME,FROM SUPPLIER S,PROJECT J,SUPPLY SJ,WHERE S.SNO=SJ.SNO and SJ.JNO=J.JNO and S.CITY=J.CITY,Q1:S1,上关系,PROJECT,的,200,个元组和,SUPPLIER1,的,50,个元组复制到,S2,上执行连接。,S1,：,PROJECT,（,200,元组