第四章全局查询处理和优化

第四章分布查询处理和优化Outline§4.1查询优化基础§4.2查询处理概述§4.3查询分解§4.4数据本地化§4.5片段查询的优化1、优化目标优化就是寻找执行代价（费用和时间）最小的查询执行策略，使系统执行效率降到最低。因此，优化的目标就是指局部执行代价和网络传输代价的和最小。（1）局部执行代价：主要指输入/输出次数（I/O代价）及CPU处理代价。（2）网络传输代价：主要指传输启动代价和数据传输代价。§4.1查询优化的基础§4.1查询优化的基础2、执行策略我们以一个例子来说明选择何种执行策略。例4.1.1设有关系AB{A，B}和BC{B，C}，分别有100和1000个元组。AB中有10个元组为A=X，B是外来关键字。要求：实现如下查询SQL功能。SELECT*FROMAB，BCWHEREAB.B=BC.BANDA=″x″§4.1查询优化的基础2、执行策略-例4.1.1等价变换与SQL等价的关系代数表达式：σA=″x″（AB∞BC）实现的方法及其代价分析假设：只考虑局部I/O次数代价。•策略1：T1：T1=AB∞BCT2：σA=″x″（T1）分析：T1：需100（AB元组数）*1000（BC元组数）=105（次I/O），T1的元组数为105T2：需105（T1元组数）次I/O总代价：T1的代价+T2的代价=2*105（次I/O）§4.1查询优化的基础2、执行策略-例4.1.1策略2：T1：T1=σA=″x″（AB）T2：T1∞BC分析：T1：需100（AB元组数）次I/O，得：T1的元组数为10T2：需10（AB元组数）*1000（BC元组数）=104（次I/O）总代价：100+104≈104（次I/O）从上述两种策略看，虽然都能实现所要完成的功能，但两种实现方法所须的代价却相差很大。若是分布式系统的多用户、多应用需求的复杂任务，采用不同的实现策略会相差更大，将直接影响整个系统整体性能。因此，确定出一种执行代价最小的查询执行策略是分布式数据库系统必须重视的一因素。§4.1查询优化的基础3、优化内容优化内容体现如下几点：（1）执行运算的次序。（2）执行每种运算的方法。如上例，不同方法代价不同。（3）所访问的副本场地。如：选择就近的场地，节约传输代价。（4）执行运算的场地的选择。使总的传输代价或总代价最低。综合考虑，确定出一种执行代价最小的查询执行策略。§4.1查询优化的基础用户或应用看到的是全局关系组成的全局数据库，用户通过查询语言（通常用SQL语言操纵语言）来表达全局查询。之后，由系统将其转换成等价的关系表达式内部表示，为描述关系的操作序列，提出一种称查询树的内部表示方法。1、关系代数（1）一元运算U：=σ（选择）/П（投影）（2）二元运算b：=∞（联接）/X（笛卡儿积）/∪（并）/∩（交）/-（差）/∝（半联接）§4.4查询优化的基础（2）等价变换重复律：UR≡UUR交换律：U1U2R≡U2U1R分配律：U（RbS）≡（UR）b（US）结合律：Rb1（Sb2T）≡（Rb1S）b2T提取律：（UR）b（US）≡U（RbS）其中：R、S、T为关系，U1、U2、U为一元运算符，b1、b2、b为二元运算符。§4.4查询优化的基础2、查询树在查询树中，叶子表示关系，中间节点表示运算，前序遍历关系表示运算次序。定义：ROOT：=TT：=R/（T）/TbT/UTU：=σF/ПAb：=∞/X/∪/∩/-/∝§4.4查询优化的基础3、举例例4.2.1设有一供应关系数据库，有供应者和供应两关系，如下：供应者：SUPPLIER{SNO，SNAME，AREA}供应者编号供应者姓名供应者所属地域供应：SUPPLY{SNO，PNO，QTY}供应者编号零件号质量查询要求：找出地域在″北方″供应100号零件的供应商的信息。SQL查询语句：SELECTSNO，SNAMEFROMSUPPLIER，SUPPLYWHEREAREA=″北方″ANDPNO=100ANDSUPPLIER.SNO=SUPPLY.SNO§4.4查询优化的基础3、举例等价的关系表达式：Q1：ПSNO，SNAMEσAREA=″北方″σPNO=100（SUPPLIER∞SUPPLY）查询树：通常用SQL语言操纵语言来表达全局查询。之后，由系统将其转换成内部表示。实际上，在查询执行过程时，最终涉及的是具体场地上的物理关系的查询。影响查询处理效率的因素有：网络传输代价（数据量和延迟等）、局部I/O代价及CPU使用情况代价等，但主要由网络通信代价和局部I/O代价来衡量。不同的分布式数据库系统可能对评估查询处理的传输代价和I/O代价的侧重不同，同时，为提高查询的效率，在查询处理过程中还要进行优化处理，查询优化就是确定出一种执行代价最小的查询执行策略或寻找相对较优的操作执行步骤。一般可采用多级优化。本章介绍全局查询的处理与优化。§4.2OverviewofQueryProcessing§4.2OverviewofQueryProcessingSQL-nonprocedurallanguageofRDBTuplecalculuswheret:tuplevariable,F(t):well-formedformula(wff),Example:gettheno.andnameofallmanagers§4.2OverviewofQueryProcessing§4.2OverviewofQueryProcessingQueryprocessortransformsqueriesintoproceduraloperationstoaccessdata.Distributedqueryprocessorhastodealwithquerydecomposition,anddatalocalization§4.2OverviewofQueryProcessing•QUERYPROCESSINGPROBLEMSCentralizedqueryprocessormust-transformcalculusqueryintoalgebraoperation-choosethebestexecutionplanExample:SELECTENAMEFROME,GWHERERESP=“Manager”andE.ENO=G.ENO§4.2OverviewofQueryProcessingN§4.2OverviewofQueryProcessingInDDB,thequeryprocessormustconsiderthecommunicationcostandselectthebestsite!Samequeryastheexampleabove,butGandEaredistributed.Simpleplan:totransportallsegmentstoquerysiteandexecutethere.Thiscausestoomuchnetworktraffic,verycostly.§4.2OverviewofQueryProcessingDistributedqueryexample§4.2OverviewofQueryProcessingDistributedqueryexample§4.2.1CHARACTERIZATIONOFQUERYPROCESSORLanguagesForusers:calculusoralgebrabasedlanguages.Forqueryprocessor:maptheinputintointernalformofalgebraaugmentedwithcommunicationprimitives.§4.2.1CHARACTERIZATIONOFQUERYPROCESSORTypesofOptimizationExhaustivesearch–workableforsmallsolutionspace.§4.2.1CHARACTERIZATIONOFQUERYPROCESSOROptimizationTimingStatic–doitatcompilingtimebyusingstatistics,appropriateforexhaustivesearch,optimizedonce,butexecutedmanytimes.Dynamic–doitatexecutiontime,accurate,repeatedforeveryexecution,expensive.§4.2.1CHARACTERIZATIONOFQUERYPROCESSORStatisticsFactsofcardinalities,attributevaluedistribution,sizeofrelation,etc.providedtoqueryoptimizerandperiodicallyupdated.DecisionSiteForqueryoptimization,itmaybedonebysinglesite–centralizedapproach,orallthesitesinvolved–distributed,orHybrid–onesitemakesmajordecisionincooperationwithothersitesmakinglocaldecisions§4.2.1CHARACTERIZATIONOFQUERYPROCESSORExplorationoftheNetworkTopologyWAN–communicationcostisdominantLAN–communicationcostiscomparabletoI/Ocost.Broadcastingcapability,starnetwork,satellitenetworkshouldbeconsidered.ExplorationofReplicatedFragmentsUsereplicationstominimizecommunicationcosts.UseofSemijoinsReducethesizeofoperandrelationstocutdowncommunicationcosts§4.2.2LAYERSOFQUERYPROCESSINGCALCULUSQUERYONDISTRIBUTEDRELATIONSQUERYDECOMPOSITIONALGEBRAQUERYONDISTRIBUTEDRELATIONSDATALOCALIZATIONFRAGMENTQUERYGLOBALOPTIMIZATIONOPTIMIZEDFRAGMENTQUERYWITHCOMMUNICATIONOPERATIONSLOCALOPTIMIZATIONOPTIMIZEDLOCALQUERYGLOBALSCHEMAFRAGMENTSCHEMASTATISTICSONSCHEMALOCALSCHEMACONTROLSITELOCALSITEGenericLayeringSchemeforDistributedQueryProcessing•rewrittentonormalize•Incorrectdetecting•Simplified•restructured•Localizethequery’data•Mappingtofragmentquery•Simplificationandrestructuring•Findingthe“best”orderingofoperations•Definecostfunction•AlgorithmsofCentralizedsystem§4.2.2LAYERSOFQUERYPROCESSINGQueryDecompositionDecomposecalculusqueryintoalgebraqueryusingglobalconceptualschemainformation.Step1–calculusnormalizationSt