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

.,1,第五章分布查询的存取优化,.,2,分布式查询处理概述,.,3,查询存取优化输入：片段查询找到好的（不必最优的）全局调度最小代价函数分布Join处理稠密树与线性树需要传输的关系全部传输与按需传输确定使用半连接使用半连接可减少通信代价Join方法嵌套循环与顺序join（合并join与hashjoin）,分布式查询处理概述,.,4,基于代价的优化搜索空间（Solutionspace）等价的代数表达式(querytrees).代价函数（Costfunction）I/O代价+CPU代价+communication代价不同的分布环境中各因素权重不同(LANvsWAN).最大吞吐量搜索算法（Searchalgorithm）如何在解决空间中移动穷举搜索，启发式算法(递归改进、模拟退火、遗传法等）,分布式查询处理概述,.,5,查询优化最小化查询代价,查询优化过程,分布式查询处理概述,.,6,分布式查询处理概述,搜索空间(SearchSpace)搜索空间由可选择的执行计划描述侧重Join树若存在n个关系，有O(N!)等价的Join树例如，selectENAME,RESPFromEMP,ASG,PROJWhereEMP.ENO=ASG.ENOAndASG.PNO=PROJ.PNO,.,7,分布式查询处理概述,搜索空间(SearchSpace)由启发式规则约束如一元操作先于二元操作执行约束join树的形状只考虑线性树而忽略了稠密树,线性join树：,稠密join树：,.,8,搜索策略(SearchStrategy)如何在搜索空间中构建查询计划确定的（Deterministic）开始于基关系，每步加一个关系构建执行计划动态规划法：宽度优先（breadth-first）贪婪法:深度优先（depth-first）（只构造一个计划）随机的（Randomized）从一个特定的点起始搜索最优执行计划(首先应用贪婪法构建一个或多个执行计划，接着通过邻居关系替换来改进执行计划)综合考虑优化时间和执行时间适合大于5-6个关系模拟退化（Simulatedannealing）递归改进（Iterativeimprovement）,构造所有可能的执行计划；尽早剪裁不是优化的计划；Isalsoexhaustive;关系数少时，优化代价可接受;,分布式查询处理概述,.,9,随机的（Randomized）随机交换操作关系,搜索策略(SearchStrategy)确定的（Deterministic）从基关系开始，每步联接一个或多个关系，直到获得全部的计划,分布式查询处理概述,.,10,分布查询的存取优化,基本概念优化的理论基础半联接优化方法SDD-1系统优化技术枚举法优化技术集中的查询优化(CENTRALIZEDQUERYOPTIMIZATION),.,11,基本概念,分布执行过程实际上就是从查询场地发出查询命令、从数据源获取数据、确定最佳的执行场地和返回执行结果的过程。,查询场地：指发出查询命令和存储最终查询结果的场地。查询场地也称最终结果文件。源数据场地：指查询命令需要访问的数据副本所在的场地，可能涉及到一个或一个以上的场地。源数据场地也称源数据文件。执行场地：指查询操作执行所在的场地。执行场地可以和查询场地或源数据场地处于同一场地，也可不处于同一场地。执行场地也称中间结果文件。,.,12,基本概念,分布执行策略举例有关系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,.,13,假设：结果元组大小40字节，S3为查询场地结果关系大小：40*10000=400KB,基本概念,(3)存在三个场地，S1、S2和S3。如图：查询要求：查询每个雇员的姓名及所在单位。则：（1）SQL语句：SELECTENAME，DNAMEFROMEMP，DEPTWHEREEMP.DNO=DEPT.DNO（2）关系表达式：ENAME，DNAME（EMPDEPT）,分布执行策略举例,.,14,分布执行策略举例-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从上面三个策略看，选择不同的执行场地，传输代价差别很大。应选择最低的传输代价。但组成系统的环境不同，优化的侧重点也不同。,基本概念,.,15,基本概念,分布查询的存取优化的目标对于远程网，主要考虑通信开销，使通信代价最小。对于局域网，需同时考虑通信代价和本地处理代价，使综合代价最小。优化的内容优化是在片段查询的基础上进行的实际物理副本查询操作的优化。具体如下：输入：片段查询表达式输出：分布执行计划,.,16,查询存取优化内容：确定片段查询需访问的物理副本。通常：本场地上的物理副本优先；若二元运算存在尽量选择本场地上的二元运算；数据最小的物理关系应被优先选中；网络通信代价小的应优先选中确定片段查询表达式操作执行的最优顺序。包括从叶到根的执行和同一层叶子上表达式执行的先后，特别是对查询树上的并操作和联接操作的执行次序的确定，其代价差别很大。选择执行每个操作的方法。如：尽量将同一场地上的、同一物理副本的全部操作组合在一起统一考虑完成。,基本概念,.,17,存取优化的理论基础,代价函数(thetotaltimeortheresponsetime)总的时间（TotalTime）-所有时间组件的和减少每一个组件的时间代价尽可能减少每个代价组件的代价优化资源利用率，增加系统吞吐率响应时间（ResponseTime）-从查询开始到执行结束所用的时间尽可能并行执行（Doasmanythingsaspossibleinparallel）增加总的活动（activity）可能会增加总时间,.,18,例子:,存取优化的理论基础,假设只考虑通信代价总时间=2*消息启动时间+单位传输代价*(x+y)响应时间=max(从1传输x到3的时间，从2传输x到3的时间),.,19,存取优化的理论基础,代价模型主要指传输代价（Ccom）、I/O代价（CIO）和CPU代价（Ccpu）Totalcost=Ccom+CIO+Ccpu传输代价费用和延迟。其中费用起决定作用。传输费用是指使通信中的整个传输开销，即传输的数据量。模型为：CCOM（X）=C0+C1*X其中：C0：场地间传输数据的启动所需的固定费用（启动一次），简称启动代价；C1：网络单位传输数据费用，简称单位传输代价；X：需传输的数据量。,.,20,存取优化的理论基础,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。可见，在广域网环境，以传输代价为主；在局域网环境，需综合考虑传输代价和局部代价。,.,21,查询模型主要代价因素:中间关系大小数据库特征参数假设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),存取优化的理论基础,.,22,关系运算的特征参数假设：R、S为关系。选择运算（S=F（R）选择度：满足选择谓词F的元组与R元组总数之比，记为基数：Card（S）=*Card（R）关系的宽度：Length（S）=Length（R）Length（S.A）=Length（R.A）,存取优化的理论基础,.,23,存取优化的理论基础,选择运算(中间关系大小)选择度的具体计算方法:等值比较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=CiANDCj(R)时:=i*jS=CiORCj(R)时:=1-(1-i)(1-j)=(i+j-i*j),.,24,选择运算（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)/2Card(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）,.,25,令=0.1则：Card(S)=*Card(R)=0.1*100=10Card(S)=10,Val(R,B)/2=35Card(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=50Card(S)=50,Val(R,B)/2=70/2=35Val(R,B)/2Card(S)2*Val(R,B),Val(S,B)=(Card(S)+Val(R,B)/3=40,.,26,投影运算(S=A(R)基数：如果投影涉及单个属性A：Card（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),存取优化的理论基础,.,27,并、交与差(如果结果关系执行消除重复操作，则都只能计算出结果关系基数的上限和下限，因此通常采用平均值作为基数的估计值。)基数：并运算如果不消除重复，则结果关系基数等于两个关系基数之和：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,存取优化的理论基础,.,28,并、交与差基数：交运算交运算的结果关系最小可以是空，最大可以等于两个关系的较小者，因此按取区间中间值的方法估计结果关系的基数为较小关系基数的一半：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三个关系的概要图更新为如下：,.,54,举例重新计算利益代价表P2=SupplyDEPTVal(SUPPLY,DNO)与Val(DEPT,DNO)同比例缩减，因此2=0.2Benefit2=(1-2)*Card(SUPPLY)*Length(SUPPLY)=0.8*500*6=2.4KCost2=Val(DEPT,DNO)*Length(DEPT,DNO)=20*2=0.04KP3=SupplierSupply由于DOM(SUPPLY.SNO)DOM(SUPPLIER.SNO)，因此3=Val(SUPPLY,SNO)/Val(SUPPLIER,SNO)=100/200=0.5Benefit3=(1-3)*Card(SUPPLIER)*Length(SUPPLIER)=0.5*200*24=2.4KCost3=Val(SUPPLY,SNO)*Length(SUPPLY,SNO)=100*4=0.4KP4=DeptSupply近似为1，Benefit4近似为0,SDD-1系统优化技术,P1=SupplySupplier=SupplySupplierP2=SupplyDeptP3=SupplierSupplyP4=DeptSupply,.,55,SDD-1系统优化技术,举例循环2从受益半联接集P中选择利益代价最小者P2，将P2加到策略集P中，得：P=，P2，P1。重新计算概要图对于外连接SUPPLYDEPT，需要更新SUPPLY的概要图内容，假设外连接后结果为SUPPLY(SNO,DNO)，则对于SUPPLY有：Card(SUPPLY)=*Card(SUPPLY)=0.2*500=100DNO属于连接谓词：Val(SUPPLY,DNO)=*Val(SUPPLY,DNO)=0.2*100=20SNO不属于连接谓词：Val(SUPPLY,SNO)=100，由于1/2(SUPPLY,SNO)Card(SUPPLY)GE，GJJG选择(JG)E):选择具有索引JNAME的J；再基于索引JNO与G实现Join操作；再基于索引ENO与E实现Join操作,集中式系统中的查询优化算法,.,93,考虑代价的动态规划方法首先构建一个只包含单个关系的基本代价表，之后，通过不断将关系填充到代价表进行评估，并仅保留必要信息，最后，获得最终的连接顺序。例如，现有待执行连接的四个关系，其特征参数表如下：,集中式系统中的查询优化算法,.,94,代价评估步骤：在基础表中，每个单一关系R构成一个集合，其内容包括R的大小、代价取值为0和连接表达式就是关系R本身。,集中式系统中的查询优化算法,在基本表的基础上，生成两个关系构成集合的表。连接的结果大小采用结果公式进行计算，由于没有中间结果，最小代价为0，而表达式则使用较小关系作为外关系的连接。,结果公式：Card(RS)=Card(R)*Card(S)/Max(Val(R,A),Val(S,A),.,95,代价评估步骤：,集中式系统中的查询优化算法,接下来考虑三个关系集合的连接表。三个关系进行连接，顺序必然是先由两个关系连接，然后结果再和第三个关系连接，因此，必然存在一个中间结果关系。三个关系连接的结果大小可以由结果计算公式算出，且无论连接的顺序如何，其结果大小是固定的。对于最小代价的估计，这里使用中间结果大小作为简单的代价估计方法。由于要选择最小代价，因此选择连接结果最小的关系对，并基于这两个关系的连接生成三个关系的连接表达式。,.,96,代价评估步骤：,集中式系统中的查询优化算法,以R,S,T三个关系连接为例，需要比较其中任意两个关系连接的结果大小，选择其中最小的作为最小代价和连接计划。可以看出，SR的大小为20000，TR的中间关系大小为2000000，而ST的中间关系大小为10000。因此选择它来生成R,S,T集合的连接计划。,.,97,代价评估步骤：,集中式系统中的查询优化算法,最后考虑全部四个关系连接的情况，无论连接的顺序如何，结果关系的大小估计值都是1500000个元组，而连接的代价可以看作是中间关系的代价之和。在本例中我们不仅考虑由三个关系的集合生成四个关系的集合情况，也考虑由两个包含两个关系的集合连接生成最终连接的情况，如右图。可以看出代价最小的连接顺序为(UR)T)S，其代价为9000。,.,98,集中式系统中的查询优化算法,PostgreSQL中的遗传查询优化图示为四个关系连接RSTU的连接树，每个关系使用整数进行对应的连接编码为“4-1-2-3”，表示oid为4的关系R先与oid为1的关系S连接，再与T和U连接。,在使用遗传查询优化(GEQO，GeneticQueryOptimization)模块生成执行计划时，GEQO模块首先使用标准的查询优化器生成在独立关系上查询谓词的扫描策略，对于连接则使用遗传算法处理。,.,99,集中式系统中的查询优化算法,PostgreSQL中的遗传查询优化初始阶段：GEQO模块简单地随机生成一些可行的连接序列，使用标准查询优化器来估计执行代价，选择代价最小的作为估计代价。GEQO模块应用遗传算法，将执行代价作为连接序列的适应性（适应性与执行代价成反比)，保留执行代价较低的连接序列。下一阶段：GEQO模块对在上一阶段保留的执行代价较低的连接序列，随机地选择这些连接序列中部分片段并改变其连接顺序以生成新的连接序列。对于新生成的连接序列，GEQO模块评估其执行代价，并保留其中执行代价小的作为下一个循环阶段的候选连接序列。最后，从所有被评估过的连接序列中，选择执行代价最小的作为最终的执行策略。,.,100,分布式查询优化问题,代价模型多查询优化启发式规则裁剪大的查询集合优化select-project-join查询也需要处理复杂查询(如unions,disjunctions,aggregations和sorting)平衡优化代价与执行代价启发式规则裁剪heuristicstocutdownonalternatives控制搜索策略优化与重优化间隔数据库概要信息变化需要重优化,.,101,分布式系统中的查询优化算法DistributedINGRES方法SystemR*方法DistributedINGRES方法当一个查询Q被分解为一组不可规约的子查询q1,q2,qn后，集中式环境中可以简单地顺序执行每个子查询。在分布式环境中，由于关系以分片的形式存储在多个站点上，因此子查询可能还需要继续细分以便能够在多个场地上执行，而这将产生在站点之间复制关系所需的通信代价。一种简单的优化方式是优先处理无前继查询且所涉及的关系较小的子查询。一方面可以获得较小的中间结果，另一方面可以减少复制关系所需的传输代价。,分布式查询优化算法,.,102,DistributedINGRES方法执行过程大致如下：1：首先所有在单关系上的选择和投影查询操作会被下推到每个数据所在站点的本地执行；2：使用INGRES中的归约算法，将包含n个关系变量的查询q分解为一个连续的查询序列q1q2qn，由于单关系变量的查询已经处理结束（1：步），这里仅考虑不可归约的查询序列。3：对于查询归约后获得的n个不可归约子查询，算法每次选择其中一个子查询进行处理。每次执行哪个子查询是根据查询结构、关系分片大小和关系分片的位置分布选择的，主要根据查询序列的代价估计来确定子查询的执行顺序（用一种贪婪算法）。4：如果这个不可规约子查询能够在某个独立的站点执行而不需要复制关系分片，则直接跳转到第8步。否则需要复制关系分片。,分布式查询优化算法,.,103,DistributedINGRES方法执行过程大致如下（续）：5：选择查询的执行站点。根据分片涉及的站点，以及网络的拓扑结构（点到点或广播），对所有可能的执行场地进行考虑。6：生成查询执行策略。假设有n个关系的子查询，一个执行查询的站点包含其中一个关系的一个分片，则必须将其他n-1个关系全部复制到这个站点上才能够满足执行查询的条件。7：根据第5步中的执行策略复制各关系的分片到指定的站点。为了对查询进行优化，仅传输与查询相关的分片内容，并且可以使用广播的形式提高传输效率。8：由主INGRES站点向所有被选择的站点广播查询，查询被传输到各站点后，在各站点进行本地查询处理。如果所有站点上的本地查询都没有发生错误，则移除已执行的查询，在必要的情况下还要修改剩余关系变量的查询范围。9：返回第3步继续执行，直到处理完全部查询序列。,分布式查询优化算法,.,104,DistributedINGRES方法-举例核心：选择哪个子查询执行；查询执行策略的选择例如：存在三个关系：SUPPLIER（SNO,SNAME,CITY）PROJECT(JNO,JNAME,CITY)SUPPLY(SNO,JNO,AMOUNT)存在场地：S1：PROJECT（200元组），SUPPLIER1（50元组）S2：SUPPLY（400元组），SUPPLIER2（50元组）要查询“供货商及其所供应的工程属于同一城市的供货商名称和工程名称”，查询的SQL语句如下：SELECTS.SNAME,J.JNAMEFROMSUPPLIERS,PROJECTJ,SUPPLYSJWHERES.SNO=SJ.SNOandSJ.JNO=J.JNOandS.CITY=J.CITY,分布式查询优化算法,.,105,分布式查询优化算法,DistributedINGRES方法-举例查询划分可有以下几种候选策略：Q1：SELECTS.SNAME,J.JNAMEINTOtempFROMSUPPLIERS,PROJECTJ,SUPPLYSJWHERES.SNO=SJ.SNOandSJ.JNO=J.JNOandS.CITY=J.CITYQ2：SELECTS.SNAME,S.CITY,SJ.JNOINTOtempFROMSUPPLIERS,SUPPLYSJWHERES.SNO=SJ.SNOQ3：SELECTS.SNAME,S.SNO,J.JNAME,J.JNOINTOtempFROMSUPPLIERS,PROJECTJWHERES.CITY=J.CITYQ4：SELECTJ.JNAME,J.CITY,SJ.SNOINTOtempFROMPROJECTJ,SUPPLYSJWHEREJ.JNO=SJ.JNO,SELECTS.SNAME,J.JNAMEFROMSUPPLIERS,PROJECTJ,SUPPLYSJWHERES.SNO=SJ.SNOandSJ.JNO=J.JNOandS.CITY=J.CITY,Q1:S1上关系PROJECT的200个元组和SUPPLIER1的50个元组复制到S2上执行连接。,S1：PROJECT（200元组），SUPPLIER1（50元组）S2：SUPPLY（400元组），SUPPLIER2（50元组）,.,106,分布式查询优化算法,DistributedINGRES方法-举例Q2：SELECTS.SNAME,S.CITY,SJ.JNOINTOtempFROMSUPPLIERS,SUPPLYSJWHERES.SNO=SJ.SNOQ2:S1上的SUPPLIER1复制到S2，代价是50个元组。Q2的执行结果将被传输到S1执行剩余的查询：JtempSELECTT.SNAME,J.JNAMEFROMPROJECTJ,tempTWHERET.CITY=J.CITYandT.JNO=SJ.JNO需要根据在关系和关系属性值上的相关特征参数进行评估执行代价。从中选择一个代价小的策略,SELECTS.SNAME,J.JNAMEFROMSUPPLIERS,PROJECTJ,SUPPLYSJWHERES.SNO=SJ.SNOandSJ.JNO=J.JNOandS.CITY=J.CITY,S1：PROJECT（200元组），SUPPLIER1（50元组）S2：SUPPLY（400元组），SUPPLIER2（50元组）,.,107,分布式查询优化算法,DistributedINGRES方法-举例Q2：SELECTS.SNAME,S.CITY,SJ.JNOINTOtempFROMSUPPLIERS,SUPPLYSJWHERES.SNO=SJ.SNOQ2:S1上的SUPPLIER1复制到S2，代价是50个元组。Q2的执行结果将被传输到S1执行剩余的查询：JtempSELECTT.SNAME,J.JNAMEFROMPROJECTJ,tempTWHERET.CITY=J.CITYandT.JNO=SJ.JNO需要根据在关系和关系属性值上的相关特征参数进行评估执行代价。从中选择一个代价小的策略具体参见书,SELECTS.SNAME,J.JNAMEFROMSUPPLIERS,PROJECTJ,SUPPLYSJWHERES.SNO=SJ.SNOandSJ.JNO=J.JNOandS.CITY=J.CITY,S1：PROJECT（