高级数据库原理第2部分：查询处理及优化

第二部分第二部分查询处理及优化查询处理及优化第二部分第二部分查询处理及优化查询处理及优化存储介质访问策略存储介质访问策略„„存储介质及访问策略存储介质及访问策略„查询处理过程概述„查询处理过程概述„查询代价的测量方式„关系操作的基础算法„查询优化机制„查询优化机制„实际开发中SQL语句优化原则及数据库性能调优的主要因素能调优的主要因素.一、存储介质及访问策略存储器层次三级存储器备份归档三级存储器备份归档二级存储器（磁盘）存储速度主存储器计算高速缓冲存储器DBMS主要与磁盘进行交互所以我们主要讨论磁盘的存DBMS主要与磁盘进行交互。所以我们主要讨论磁盘的存储及访问策略。磁盘的存储特性与磁盘相关的参数:*磁盘的容量：片数，磁道数，扇区数实际应用中，使用逻辑单元----磁盘块。一个磁盘块包含一个或几个扇区一个磁盘块包含一个或几个扇区磁盘的访问特性访问过程：访问程定位：将磁头移到目标块所在的柱面旋转：磁盘旋转，将第一个扇区移至磁头下面旋转旋转将第个扇移头面读或写数据访问速度：存取时间（延迟），指从发出数据请求到内容出现在主存中请求到内容出现在主存中。A.处理器与控制器处理请求所花的时间B.寻道时间：将磁头定位到合适的柱面所花的时间，时间，一般用平均寻道时间.C旋转时间：磁头转到组成块的第一个扇区所存取时间BCDC.旋转时间：磁头转到组成块的第个扇区所需时间D数据传输时间在块内读或写数据所需时间存取时间=B+C+DD.数据传输时间：在块内读或写数据所需时间。注这个时间与磁盘的物理特性密切相关不注：这个时间与磁盘的物理特性密切相关，不同类型的磁盘，时间不同。磁盘存取优化策略①按柱面组织数据①按柱面组织数据将所需要的数据存储在同一个磁道或同一个柱面上。②使用磁盘臂调度算法电梯算法②使用磁盘臂调度算法—电梯算法处理大量块请求的非常有效的算法③使用多磁盘并行处理方法③使用多磁盘—并行处理方法将数据分配到多个磁盘上④磁盘镜像技术④磁盘镜像技术通过选择寻道时间昀短的磁盘来提高读速度。⑤预取与大规模缓冲技术⑤预取与大规模缓冲技术通过预测将所需数据块先装入缓存，从而减少等待时间或者使用较好的缓冲策略尽量减少磁盘的访问时间。或者使用较好的缓冲策略尽量减少磁盘的访问次数等。二查询二查询处理简介处理简介二、查询二、查询处理简介处理简介„„即使是一个简单的单操作符赋值，也有许即使是一个简单的单操作符赋值，也有许多不同赋值方式。每种方法都可能在某些多不同赋值方式。每种方法都可能在某些多不同赋值方式每种方法都可能在某些多不同赋值方式每种方法都可能在某些场合下优于其它方法。场合下优于其它方法。个实际查询通常不止涉及个操作符个实际查询通常不止涉及个操作符„„一个实际查询通常不止涉及一个操作符。一个实际查询通常不止涉及一个操作符。包含几个操作符的查询有更多的赋值方式包含几个操作符的查询有更多的赋值方式选项发或找到个好查询计划是项选项发或找到个好查询计划是项选项，发现或找到一个好查询计划是一项选项，发现或找到一个好查询计划是一项重要的挑战。重要的挑战。„„DBMSDBMS必须考虑可替换的各种可选方式，并必须考虑可替换的各种可选方式，并选择其中具有昀少估算代价的一个选择其中具有昀少估算代价的一个选择其中具有昀少估算代价的个选择其中具有昀少估算代价的个。。关系查询处理概述查询的处理过程SQL语句语句语法分析（语法树）查询编语法分析（语法树）初始逻辑查询计划元数据编译优化逻辑查询计划元数据统计数据创建并优化物理查询计划查询执行引擎数据查询结果查询处理步骤查询处理步骤查询处理步骤查询处理步骤„„查询处理器：查询处理器：是是查询处理器查询处理器是是DBMSDBMS系统的核心系统的核心部件，能接受在很部件，能接受在很部件能接受在很部件能接受在很高层次上表达的高层次上表达的SQLSQL命令，并将命令，并将QQSQLSQL命令转化为数命令转化为数据库上的具体操作据库上的具体操作据库的具体操作据库的具体操作序列；序列；„„包括：包括：查询编译查询编译„„包括：包括：查询编译查询编译器器和和查询执行器查询执行器两个部分两个部分两个部分两个部分查询处理的主要过程与阶段„查询语法分析查询语法分析„„生成初步的语法分析树生成初步的语法分析树„查询预处理(查询编译的类型检查)查询预处理(查询编译的类型检查)„通过类型检查的语法分析树„生成查询代数表达式树生成查询代数表达式树„„将语法分析树转化为代数表达式树将语法分析树转化为代数表达式树„„生成初步逻辑查询计划生成初步逻辑查询计划查询编译器„查询重写（查询优化）„„生成优化的逻辑查询计划生成优化的逻辑查询计划查询编译器成优化的逻辑查询计划成优化的逻辑查询计划„物理计划生成„„生成物理查询计划生成物理查询计划生成物理查询计划生成物理查询计划„„为逻辑查询计划的每个操作符选择实现为逻辑查询计划的每个操作符选择实现算法算法并选择这些操作符的执行顺序和方式并选择这些操作符的执行顺序和方式„查询执行„„物理计划－－提交－－“查询执行器”执行物理计划－－提交－－“查询执行器”执行查询执行器11查询分析查询分析1.1.查询分析查询分析对查询语句进行扫描法分析和语法分析对查询语句进行扫描法分析和语法分析„„对查询语句进行扫描、词法分析和语法分析对查询语句进行扫描、词法分析和语法分析„„从查询语句中识别出语言符号从查询语句中识别出语言符号„„从查询语句中识别出语言符号从查询语句中识别出语言符号„„进行语法检查和语法分析进行语法检查和语法分析22查询检查查询检查2.2.查询检查查询检查„根据数据字典对合法的查询语句进行语义检查„根据数据字典中的用户权限和完整性约束定义对„根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查检查通过后把SQL查询语句转换成等价的关系代„检查通过后把SQL查询语句转换成等价的关系代数表达式般都用查询树语法分析树来表示扩展„RDBMS一般都用查询树(语法分析树)来表示扩展的关系代数表达式„把数据库对象的外部名称转换为内部表示33查询优化查询优化3.3.查询优化查询优化„„查询优化：选择一个高效执行的查询处理策略查询优化：选择一个高效执行的查询处理策略„„查询优化：选择个高效执行的查询处理策略查询优化：选择个高效执行的查询处理策略„„查询优化分类查询优化分类„„代数优化：指关系代数表达式的优化代数优化：指关系代数表达式的优化物理优化指存取路径和底层操作算法的选择物理优化指存取路径和底层操作算法的选择„„物理优化：指存取路径和底层操作算法的选择物理优化：指存取路径和底层操作算法的选择„„查询优化方法选择的依据查询优化方法选择的依据„„查询优化方法选择的依据查询优化方法选择的依据„„基于规则基于规则(rulebased)(rulebased)„„基于代价基于代价(costbased)(costbased)„„基于语义基于语义(semanticbased)(semanticbased)„„基于语义基于语义(semanticbased)(semanticbased)44查询执行查询执行4.4.查询执行查询执行依据优化得到的执行策略生成查询计划依据优化得到的执行策略生成查询计划„„依据优化器得到的执行策略生成查询计划依据优化器得到的执行策略生成查询计划„„代码生成器代码生成器(codegenerator)(codegenerator)生成执行查询生成执行查询计划的代码计划的代码计划的代码计划的代码SQLSQL的一个简单子集的语法的一个简单子集的语法SQLSQL的个简单子集的语法的个简单子集的语法查询查询QSFWQSFWQuery::=SFWQuery::=SFWQuery::=(Query)Query::=(Query)式式SelectSelect--FromFrom--WhereWhere形式形式SFW::=SELECTSFW::=SELECTSelListSelListFROMFROMFromListFromListWHEREConditionWHEREConditionSelectSelect列表列表SelectSelect列表列表„„SelListSelList::=Attribute,::=Attribute,SelListSelList„„SelListSelList::=Attribute::=Attribute14„„SelListSelList::=Attribute::=AttributeFromFrom列表列表„„FromListFromList::=Relation,::=Relation,FromListFromList,,„„FromListFromList::=Relation::=Relation条件条件条件条件Condition::=ConditionANDConditionCondition::=ConditionANDConditionCondition::=Condition::=TupleTupleINQueryINQueryCondition::=Condition::=TupleTupleINQueryINQueryCondition::=Attribute=AttributeCondition::=Attribute=AttributeCondition::=AttributeLIKEPatternCondition::=AttributeLIKEPatternCondition::=AttributeLIKEPatternCondition::=AttributeLIKEPatternTupleTuple::=Attribute::=Attribute15一一个简单的个简单的SQLSQL语法语法子集子集（文法产生式）（文法—产生式）1.1.查询查询QueryQueryÆÆSFWSFWyyQueryQueryÆÆ((QueryQuery))2.Select2.Select--FromFrom--WhereWhere形式形式SFWSFWÆÆSELECTSELECTSelListSelListFROMFROMFromListFromListSFWSFWÆÆSELECTSELECTSelListSelListFROMFROMFromListFromListWHEREConditionWHERECondition3.Select3.Select列表列表SelListSelListÆÆAttribute,Attribute,SelListSelListFFSelListSelListÆÆAttributeAttribute4F4F列表列表4.From4.From列表列表romListromListÆÆRelNameRelName,,FromListFromListFromListFromListÆÆRelNameRelNameFromListFromListÆÆRelNameRelName5.5.条件条件ConditionConditionÆÆConditionANDConditionConditionANDConditionConditionConditionÆÆTupleTupleinQueryinQueryConditionConditionÆÆAttribute=AttributeAttribute=