全局查询处理和优化.pptx

主要内容主要内容4.1 4.1 查询优化基础查询优化基础4.2 4.2 查询处理概述查询处理概述4.3 4.3 查询分解查询分解4.4 4.4 数据本地化数据本地化4.5 4.5 片段查询的优化片段查询的优化优化目标优化目标 优化优化就是寻找执行代价（费用和时间）最小的查询执行策略，使系统执行效率降到最低。优化的优化的目标目标就是指局部执行代价和网络传输代价的和最小。局部执行代价局部执行代价：主要指输入/输出次数（I/O代价）及CPU处理代价。网络传输代价网络传输代价：主要指传输启动代价和数据传输代价。4.1查询优化的基础查询优化的基础4.1 查询优化的基础查询优化的基础执行策略执行策略我们以一个例子来说明选择何种执行策略。我们以一个例子来说明选择何种执行策略。例例4.1.1 求选修求选修2号课程的学生姓名号课程的学生姓名SQL表示表示:select Snamefrom Students,SCwhere Students.Sno=SC.Sno and Cno=2;关系代数表示关系代数表示:Q1=sname(Students.Sno=SC.Sno and Cno=2(Students SC)Q2=sname(Cno=2(Students SC)Q3=sname(Students Cno=2(SC)代价计算代价计算 Q1代价计算代价计算(仅考虑仅考虑I/O代价代价)-计算广义笛卡尔积代价计算广义笛卡尔积代价假定:在内存中,存放5块Students元组和一块SC元组,一块可以装10个Students元组或100个SC元组.假定:Students有1000个元组,SC有10000个元组,其中选2号课程的有50个元组数据只有读到内存才能进行连接Q1=sname(Students.Sno=SC.SnoandCno=2(Students SC)10100SCStudents5块块4.1 查询优化的基础查询优化的基础通过读取块数计算I/O代价 读取块数计算方法:Students 1000个元组 SC 10000个元组读取总块数:若每秒读写20块,则花费:10100SCStudents5块块Student块数块数Student读入内存读入内存的次数的次数SC块数块数Q1=sname(Students.Sno=SC.SnoandCno=2(Students SC)4.1 查询优化的基础查询优化的基础条件条件:Students 1000个元组，SC 10000个元组-笛卡尔集计算后的元组个数为:103 104=107-连接后的中间结果内存放不下,需暂时写到外存-若每块可装10个完成笛卡尔集后的元组,则写这些元组需:(107/10)/20=5 104s选择操作选择操作:读回需读回需5 104s,假设假设选择后剩选择后剩50个元组个元组,均可均可放在内存放在内存投影操作投影操作:查询共花费查询共花费:105+2 5 104 105 s 28小时小时10100SCStudents5块块每秒读每秒读20块块Q1=sname(Students.Sno=SC.SnoandCno=2(Students SC)4.1 查询优化的基础查询优化的基础Q2Q2=snamesname(Cno=Cno=2 2(Students SC)(Students SC)Q2代价计算代价计算(仅考虑仅考虑I/O代价代价)计算自然连接代价-也要把数据读到内存进行连接,但连接结果比笛卡尔积要小得多-读取块数依然为:-花费为2100/20 105s-假设连接结果大小为104个元组,写到外存需:(104/10)/20=50s每秒读每秒读20块块4.1 查询优化的基础查询优化的基础 Q2 Q2=snamesname(Cno=Cno=2 2(Students SC)(Students SC)-读取自然连接结果,执行选择运算,需50s,选择结果均可放在内存-投影运算:-总花费为:105+50+50=205s 3.4分钟分钟Q3代价计算代价计算(仅考虑仅考虑I/O代价代价)计算对SC做选择运算的代价-需读SC到内存进行选择运算-读SC块数为:10000/100=100-花费为:100/20=5s-选择结果为50个SC元组,均可放在内存 Q3 Q3=snamesname(Students (Students Cno=Cno=2 2(SC)(SC)4.1 查询优化的基础查询优化的基础Q3Q3=snamesname(Students (Students Cno=Cno=2 2(SC)(SC)计算和Students自然连接的代价-需读Students到内存进行连 接运算-读Students块数为:1000/10=100-花费为:100/20=5s-连接结果为50个元组,均可放在内存-投影运算:总花费:5+5=10s1050SCStudents5块块4.1 查询优化的基础查询优化的基础4.1 查询优化的基础查询优化的基础从上述三种策略看，虽然都能实现所要从上述三种策略看，虽然都能实现所要完成的功能，但三种实现方法所须的代完成的功能，但三种实现方法所须的代价却相差很大。若是分布式系统的多用价却相差很大。若是分布式系统的多用户、多应用需求的复杂任务，采用不同户、多应用需求的复杂任务，采用不同的实现策略会相差更大，将直接影响整的实现策略会相差更大，将直接影响整个系统整体性能。因此，确定出一种执个系统整体性能。因此，确定出一种执行代价最小的查询执行策略是分布式数行代价最小的查询执行策略是分布式数据库系统必须重视的一因素。据库系统必须重视的一因素。4.1查询优化的基础查询优化的基础优化内容优化内容优化内容体现如下几点：优化内容体现如下几点：（1）执行运算的次序。）执行运算的次序。（2）执行每种运算的方法。如上例，不同方法代）执行每种运算的方法。如上例，不同方法代价不同。价不同。（3）所访问的副本场地。如：选择就近的场地，）所访问的副本场地。如：选择就近的场地，节约传输代价。节约传输代价。（4）执行运算的场地的选择。使总的传输代价或）执行运算的场地的选择。使总的传输代价或总代价最低。总代价最低。综合考虑，确定出一种执行代价最小的查询执行策综合考虑，确定出一种执行代价最小的查询执行策略。略。4.1 查询优化的基础查询优化的基础 用用户户或或应应用用看看到到的的是是全全局局关关系系组组成成的的全全局局数数据据库库，用用户户通通过过查查询询语语言言（通通常常用用SQL语语言言操操纵纵语语言言）来来表表达达全全局局查查询询。之之后后，由由系系统统将将其其转转换换成成等等价价的的关关系系表表达达式式内内部部表表示示，为为描描述述关关系系的的操操作作序序列列，提提出出一种称一种称查询树查询树的内部表示方法。的内部表示方法。关系代数关系代数 一元运算一元运算 U：=（选择）（选择）/（投影）（投影）二元运算二元运算 b：=（联接）（联接）/X（笛卡儿积）（笛卡儿积）/（并）（并）/（交）（交）/-（差）（差）/（半联接）（半联接）4.4 查询优化的基础查询优化的基础 等价变换等价变换重复律：重复律：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 查询优化的基础查询优化的基础查询树查询树在查询树中，在查询树中，叶子叶子表表示关系，示关系，中间节点中间节点表表示运算，前序遍历关示运算，前序遍历关系表示运算次序。系表示运算次序。定义：定义：ROOT：=TT：=R/（T）/TbT/UTU：=F/Ab：=/X/-/4.4 查询优化的基础查询优化的基础 举例举例 例例4.2.1 设有一供应关系数据库，有供应者和供应两关系，设有一供应关系数据库，有供应者和供应两关系，如下：如下：供应者：供应者：SUPPLIERSNO，SNAME，AREA 供应者编号供应者编号 供应者姓名供应者姓名 供应者所属地域供应者所属地域供应：供应：SUPPLYSNO，PNO，QTY供应者编号供应者编号 零件号零件号 质量质量查询要求：找出地域在查询要求：找出地域在北方北方供应供应100号零件的供应商的信息。号零件的供应商的信息。SQL查询语句：查询语句：SELECT SNO，SNAME FROM SUPPLIER，SUPPLY WHERE AREA=北方北方AND PNO=100 AND SUPPLIER.SNO=SUPPLY.SNO4.4 查询优化的基础查询优化的基础举例举例等价的关系表达式：等价的关系表达式：Q1：SNO，SNAMEAREA=北方北方PNO=100（SUPPLIERSUPPLY）查询树：查询树：影响查询处理效率的因素有影响查询处理效率的因素有：网络传输代价（数据量和延迟等）、局部I/O代价及CPU使用情况代价等，但主要由网络通信代价和局部I/O代价来衡量。不同的分布式数据库系统可能对评估查询处理的传输代价和I/O代价的侧重不同。为提高查询的效率，在查询处理过程中还要进行优化处理。查询优化查询优化就是确定出一种执行代价最小的查询执行策略或寻找相对较优的操作执行步骤。一般可采用多级优化多级优化。本章介绍全局查询的处理与优化。4.2 查询处理概述 查询语言查询语言SQL非过程化的关系数据库语言，是非过程化的关系数据库语言，是元组验算语言元组验算语言元组演算：元组演算：其中t:元组变量，F(t):well-formed formula(wff),例如例如:查询所有 managers 的 no.和 name。4.2 查询处理概述 域演算：域演算：其中其中xs:域变量域变量,F(x1,xn):wff例如例如:查查询询处处理理将将查查询询转转换换为为过过程程操操作作来来访访问问数据。数据。分分布布查查询询处处理理器器还还需需要要处处理理查查询询分分解解（querydecomposition）和数据局部化（和数据局部化（datalocalization）4.2 查询处理概述 QueryprocessorCalculusformulaRelationalalgebraoperations 查询处理问题集中查询处理器必须：-将演算查询转换为代数操作 -选择最好的执行计划例如:SELECT ENAMEFROM E,GWHERE RESP=“Manager”and E.ENO=G.ENO4.2 查询处理概述 关系代数关系代数1:关系代数关系代数2:可见：可见：执行计划执行计划2好好。4.2 查询处理概述 对于对于分布式数据库分布式数据库,查询处理器必须考虑通信代价和查询处理器必须考虑通信代价和选择最佳场地选择最佳场地!如上例如上例：若若G和和E是分布的是分布的.简单计划简单计划是将所有片段传到查询场地并执行，但通信是将所有片段传到查询场地并执行，但通信代价太大。代价太大。.分布式查询举例：分布式查询举例：4.2 查询处理概述 Site1Site2Site3Site4QuerySite5查询查询：优化的查询优化的查询4.2 查询处理概述 查询处理的目标：查询处理的目标：查询处理的目标：查询处理的目标：两方面：两方面：转换（转换（transformation）和优化（）和优化（optimization）。）。考虑的优化代价：考虑的优化代价：CPUtimeI/OtimeCommunicationtime在在WAN内，侧重通信代价内，侧重通信代价.在在LAN内，三者同等重要内，三者同等重要4.2 查询处理概述 4.2.1 查询处理器概述查询处理器概述优化类型优化类型穷举法（穷举法（Exhaustivesearch）workableforsmallsolutionspace.启发式（启发式（Heuristics），performfirst,semijoin,etc.forlargesolutionspace.优化时机优化时机静静态态的的(Static)doitatcompilingtimeby using statistics,appropriate forexhaustive search,optimized once,butexecutedmanytimes.动动态态的的(Dynamic)do it at executiontime,accurate,repeated for everyexecution,expensive.4.2.1 查询处理器概述查询处理器概述4.2.1 查询优化器概述查询优化器概述统计数据（统计数据（Statistics）元组基数,属性值分布，关系大小等。信息提供给查询优化器并定期修改。决策场地（决策场地（DecisionSite）查询优化场地可以查询优化场地可以：单场地单场地集中的方法集中的方法,简单，需要整个分布库的知识。简单，需要整个分布库的知识。分分布布的的涉涉及及所所有有的的场场地地协协调调确确定定调调度度，只只需需本本地地知知识识，需需要协调代价。要协调代价。混混合合型型的的一一个个场场地地确确定定全全局局调调度度，其其他他场场地地优优化化局局部部子子查询。查询。复制的片段复制的片段最小化通信代价。最小化通信代价。使用半连接使用半连接缩减操作关系大小，减少通信代价。缩减操作关系大小，减少通信代价。4.2.2 查询处理层次查询处理层次 rewrittentonormalizeIncorrectdetectingSimplifiedrestructuredLocalizethequerydataMappingtofragmentquerySimplificationandrestructuringFindingthe“best”orderingofoperationsDefinecostfunctionAlgorithmsofCentralizedsystem查询分解（查询分解（QueryDecomposition）基于全局概念模式将演算查询分解为代数查询。基于全局概念模式将演算查询分解为代数查询。Step1演算规范化演算规范化Step2语义分析，去掉不正确的查询。语义分析，去掉不正确的查询。Step3简化，去除冗余的部分简化，去除冗余的部分Step4将演算查询转化为优化的代数查询。将演算查询转化为优化的代数查询。数据本地化（数据本地化（DataLocalization）分布查询映射为片段查询，简化、重组为优化分布查询映射为片段查询，简化、重组为优化（good）的查询。）的查询。4.2.2 查询处理层次查询处理层次 全全 局局 查查 询询 优优 化化（GlobalQueryOptimization）找接近于最优的执行策略；找接近于最优的执行策略；找片段查询中最佳的操作顺序，包括通信操作。找片段查询中最佳的操作顺序，包括通信操作。需要实时定义代价函数。需要实时定义代价函数。局部查询优化局部查询优化（LocalQueryOptimization）集中的系统算法集中的系统算法(tobediscussedinchapter5).INGRESdynamicoptimizationSystemRstaticoptimizationbasedonexhaustivesearch4.2.2 查询处理层次查询处理层次 4.3 Decomposition QUERYDECOMPOSITIONInput:CalculusqueryonglobalrelationsNormalizationmanipulatequeryquantifiersandqualificationAnalysisdetectandreject“incorrect”queriespossibleforonlyasubsetofrelationalcalculusSimplificationeliminateredundantpredicatesRestructuringcalculusqueryalgebraicquerymorethanonetranslationispossibleusetransformationrules4.3 Decomposition NormalizationForSQLstatement,thisisthenormalization on predicates in WHEREclause,which may be arbitrarily complex,quantifier-freepredicate,precededbynecessaryquantifier.4.3 Decomposition NormalizationLexicalandsyntacticanalysischeckvalidity(similartocompilers)checkforattributesandrelationstypecheckingonthequalificationPutintonormalformConjunctivenormalform（合取范式）(p11p12p1n)(pm1pm2pmn)Disjunctivenormalform（析取范式）(p11p12p1n)(pm1pm2pmn)ORsmappedintounionANDsmappedintojoinorselection4.3 DecompositionNormalization-Transformationrules.4.3 DecompositionNormalizationExample:SELECTENAMEFROME,GWHEREE.ENO=G.ENOAND G.JNO=”J1”AND(DUR=12ORDUR=24)TheconjunctivenormalformE.ENO=G.ENOG.JNO=“J1”(DUR=12DUR=24)Thedisjunctivenormalform(E.ENO=G.ENOG.JNO=“J1”DUR=12)(E.ENO=G.ENOG.JNO=“J1”DUR=24)Redundantwork4.3 DecompositionAnalysisObjective:reject type incorrect or semanticallyincorrectqueries.*Type incorrectundefined relation,attribute,wrong typemappingetc.Analysis-Example:SELECTE#!undefined attributeFROMEWHEREENAME200!type mismatching4.3 Decomposition*Semantically incorrectAqueryhassomecomponentsnotcontributingtothequeryresult.Fact its impossible to determine the semanticalcorrectnessofageneralquery.Butitispossibletodosoforqueriesnotcontainingand.Todetectconnectiongraph(querygraph)joingraph4.3 DecompositionAnalysis-Toolofanalysisquery graphdefinedbylonenoderepresentingtheresultrelationlothernodestorepresentoperandrelations,andledgesoftwoclasses-an edge to represent a join if neither of its twonodesistheresult-anedgetorepresentaprojectionifoneofitsnodeistheresultnodeNodes and edges may be labeled by predicates forselection,projectionorjoin.4.3 DecompositionAnalysis-ToolofanalysisJoin graph=Asubgraphofquerygraphforjoinoperation4.3 DecompositionQUERYDECOMPOSITIONAnalysis-Toolofanalysis A conjunctive query without negation is semantically incorrect if its query graph is NOT connected!4.3 DecompositionSimplification Whysimplify?RemembertheexampleHow?Usetransformationruleseliminationofredundancyidempotencyrulesp1(p1)falsep1(p1p2)p1p1falsep1applicationoftransitivityuseofintegrityrules4.3 DecompositionSimplificationThetechniqueusingidempotencyrulestoeliminateredundantpredicatesfromWHEREclause.4.3 DecompositionSimplification SELECTTITLEFROMEMPWHEREEMP.ENAME=“J.Doe”OR(NOT(EMP.TITLE=“Programmer”)AND(EMP.TITLE=“Programmer”OREMP.TITLE=“Elect.Eng.”)ANDNOT(EMP.TITLE=“Elect.Eng.”)isequivalenttoSELECTTITLEFROMEMPWHEREEMP.ENAME=“J.Doe”Byusingtherules.4.3 DecompositionReconstructionRewriteacalculusqueryinrelationalalgebra:translationreconstructionofalgebraquerytoimproveperformanceRelational algebra treeatreedefinedbyarootnoderepresentingthequeryresultleavesrepresentingdatabaserelationsnon-leafnodesrepresentingrelationsproducedbyoperations,andedgesfromleavestorootrepresentingthesequencesofoperations.4.3 DecompositionReconstructionHowtotranslateanSQLqueryintoanalgebratree1)createaleafforeveryrelationintheFROMclause2)create the root as a project operationinvolvingattributesintheSELECTclause3)create the operation sequence by thepredicatesandoperatorsintheWHEREclause 4.3 DecompositionReconstruction Reconstruction初步优化优化实际是将用户请求构成的查询树进行等价变换。实际是将用户请求构成的查询树进行等价变换。等价变换的基本思想是把中间结果变小的运算先做。等价变换的基本思想是把中间结果变小的运算先做。假设：假设：n为关系元组个数，进行顺序查询。为关系元组个数，进行顺序查询。则关系运算的执行代价表为：则关系运算的执行代价表为：运算类型执行代价、（不消重复项）O（n）（消重复项）、GROUPO（nLOGn）XO（n2）、-、O（nLOGn）变换的通用准则为：准则准则1尽可能将一元运算移到查询树的底部（树叶部分），使之优先执行一元运算。准则准则2利用一元运算的重复律，缩减每一关系，以减少关系尺寸，降低网络传输量和I/O大小。4.3 Decomposition4.3 Decomposition 举例举例等价的关系表达式：等价的关系表达式：Q1：SNO，SNAMEAREA=北方北方PNO=100（SUPPLIERSUPPLY）查询树：查询树：SUPPLIERSNO，SNAME，AREASUPPLYSNO，PNO，QTY4.3 Decomposition面向全局优化的面向全局优化的reconstruction准则准则在查询树在查询树Q1的基础上进行全局优化。的基础上进行全局优化。根据分配律，将一元运算向下移。得到全局优化后的查询树根据分配律，将一元运算向下移。得到全局优化后的查询树查询的处理过程查询的处理过程是从全局关系到片段关系，最后是从全局关系到片段关系，最后再到实际操作的副本关系。本节将介绍再到实际操作的副本关系。本节将介绍全局查询全局查询到到片段查询片段查询的变换。即利用全局关系与其片段关的变换。即利用全局关系与其片段关系的等价关系，将全局查询中的全局关系替换为系的等价关系，将全局查询中的全局关系替换为对片段关系的查询，变换后的查询称为对片段关系的查询，变换后的查询称为片段查询片段查询。对应于片段查询的查询树，称为对应于片段查询的查询树，称为片段查询树片段查询树。下。下面介绍全局查询与片段查询的等价关系及片段查面介绍全局查询与片段查询的等价关系及片段查询树的生成。询树的生成。4.4 Data Localization 全局查询与片段查询的等价关系全局查询与片段查询的等价关系（1）对于全局关系R的水平分片R1，R2，Rn，表示为：R=R1R2Rn（2）对于全局关系R的垂直分片R1，R2，Rn，表示为：R=R1R2Rn 片段查询树的生成步骤片段查询树的生成步骤（1）将分片树的h（水平）节点转换为查询树的（并集）节点。（2）将分片树的v（垂直）节点转换为查询树的（联接）节点。（3）用替换后的分片树代替全局查询树中的全局关系，得到片段查询树。4.4 Data Localization 片段查询树的生成步骤片段查询树的生成步骤具体如下：4.4 Data Localization4.4 Data Localization例例4.4：例例4.5：假设：SUPPLIER和SUPPLY的分片如下：SUPPLIER水平分片为S1和S2，具体如下：S1=AREA=北方（SUPPLIER）S2=AREA=南方（SUPPLIER）SUPPLY水平分片为SUPPLY1和SUPPLY2，具体如下：SUPPLY1=AREA=北方（SUPPLY）SUPPLY2=AREA=南方（SUPPLY）4.4 Data Localization 转换为片段查询树转换为片段查询树4.4 Data Localization4.4 Data Localization 在Q2基础上，用SUPPLIER分片树替换后的节点替换查询树Q2的全局关系SUPPLIER，用SUPPLY分片树替换后的节点替换查询树Q2的全局关系SUPPLY，即得到转换后的片段查询树为Q3。4.5片段查询的优化片段查询的优化片段查询优化规则片段查询优化规则准则准则1：对于一元运算，根据一元运算的重复律，将叶子节点之前的选择运算作用于片段，如果不满足片段的限定条件，则置为空关系。准则准则2：对于联接运算的树，若联接条件不满足，则将其置为空关系。准则准则3：在查询树中，将联接运算（）下移到并运算（）之前执行。准则准则4：消去不影响查询运算的垂直片段。4.5片段查询的优化片段查询的优化接例接例4.5:以片段查询树以片段查询树Q3为基础，为基础，（1）根据片段查询优化准则）根据片段查询优化准则1，按限定条件化简，得到，按限定条件化简，得到Q4。4.5片段查询的优化片段查询的优化（2）根据）根据S1=AREA=北方北方（SUPPLIER）S2=AREA=南方南方（SUPPLIER）SUPPLY1=AREA=北方北方（SUPPLY）SUPPLY2=AREA=南方南方（SUPPLY）所以，所以，Q4中的虚线部分为空关系，可将其去掉，得到中的虚线部分为空关系，可将其去掉，得到Q5查询查询树。树。4.5片段查询的优化片段查询的优化（3）根据准则）根据准则3，将联接运算（，将联接运算（）下移到并运算（）下移到并运算（）之前，）之前，得到得到Q6。S1=AREA=北方北方（SUPPLIER）S2=AREA=南方南方（SUPPLIER）SUPPLY1=AREA=北方北方（SUPPLY）SUPPLY2=AREA=南方南方（SUPPLY）则应将其置为空关系4.5片段查询的优化片段查询的优化得到得到Q7。Q7为化简后的最终的优化查询。4.5片段查询的优化片段查询的优化例例4.6假设：一雇员关系 EMP ENO，ENAME，BIRTH，SALARY，DNO其分片为：E1=ENO，ENAME，BIRTH（EMP）E2=ENO，SALARY，DNO（EMP）E21=Dno=201（E2）E22=Dno=202（E2）E23=Dno201 AND Dno202（E2）要求：查询SQL：SELECTENO，ENAME，BIRTHFROMEMP4.5片段查询的优化片段查询的优化例例4.6消去不影响查询运算的垂直片段E21、E22和 E23，得到优化后的查询树Q3。4.5片段查询的优化片段查询的优化例例4.6优化后的结果：