高级数据库技术 (6)

1UNITfive查询处理武汉大学计算机学院武汉大学计算机学院2思考几个问题1.数据库语言是非过程的语言，而最终这些非过程的语句都将转换为过程性的程序。DBMS是如何进行这种转换的？2.在转换的过程中，有必要进行查询优化吗？3.DBMS一定会找到一个最优的执行计划吗？DBMS依靠什么信息找到最优执行计划？所谓的最优是指哪些方面最优？查询优化占用很多系统资源吗？我能要求系统不做查询优化处理吗？武汉大学计算机学院3思考几个问题4.对于下面这些等价的查询，DBMS使用同样的执行计划吗？语句一：SELECTDISTINCTSDFROMS，SCWHERES.S#=SC.S#ANDC#=‘C1’;语句二：SELECTDISTINCTSDFROMSWHERES.S#IN（SELECTS#FROMSCWHEREC#=‘C1’）;语句三：SELECTDISTINCTSDFROMSWHERES.S#=SOME（SELECTS#FROMSCWHEREC#=‘C1’）;语句四：SELECTDISTINCTSDFROMSWHEREEXISTS（SELECT*FROMSCWHERES.S#=SC.S#ANDC#=‘C1’）;武汉大学计算机学院4学完本讲后，你应该能够了解：1.查询优化的可能性、必要性；2.查询处理的过程最终将一个非过程的查询请求转换成一个完全过程性的查询执行计划；3.数据库系统中查询执行引擎为每一个关系操作的实现提供多种物理实现方法；4.查询优化的目标是找到一个相当好的查询执行计划，使得查询请求的响应时间最小；5.三类查询优化器的基本原理：穷尽（精确）优化方法、两段优化方法和启发式方法本讲主要目标武汉大学计算机学院5一．查询优化的可能性二．查询优化的必要性三．查询处理的过程四．查询优化的目标五．查询优化的基本原理武汉大学计算机学院6查询优化的可能性武汉大学计算机学院7查询优化的可能性1．查询优化的可能性●关系数据库语言的非过程性与查询执行计划的过程性之间的差别；查询执行计划----用户的查询请求在数据库系统中的具体执行步骤。关系数据库的查询操作一般用非过程性的语言描述，查询语句本身重在表达查找条件和结果关系的组成，而把查找的实施过程以及查找策略的选择交给关系数据库管理系统负责。●优化器可从DD中获取很多有用的统计信息。武汉大学计算机学院8查询优化的可能性2．实例例1求选修了‘C2’号课程的学生姓名。用SQL表达：SELECTS.SNFROMS,SCWHERES.S#=SC.S#ANDSC.C#=‘C2’；可以用多种等价的关系代数表达式表达：Q1=πSN(σs.s#=sc.s#∧sc.c#=‘c2’(S×SC))Q2=πSN(σsc.c#=‘c2’(S⋈SC))Q3=πSN(S⋈σsc.c#=‘c2’(SC))武汉大学计算机学院9查询优化的必要性武汉大学计算机学院10查询优化的必要性1．查询优化的优点●用户表达查询时不必考虑效率问题●在寻找有效查询执行计划方面，系统比用户程序做得更好2.查询优化的必要性同一查询请求的不同查询执行计划之间的代价差异巨大。武汉大学计算机学院11查询优化的必要性3．不同查询执行计划的执行时间分析例1的三种情况：Q1=πSN(σs.s#=sc.s#∧sc.c#=‘c2’(S×SC))Q2=πSN(σsc.c#=‘c2’(S⋈SC))Q3=πSN(S⋈σsc.c#=‘c2’(SC))（1）第一种情况计算广义笛卡尔积作选择操作作投影操作执行总时间为105s（2）第二种情况计算自然连接作选择操作作投影操作执行总时间为205s（3）第三种情况先对SC作选择运算作连接运算作投影操作执行总时间为10s武汉大学计算机学院12查询处理的过程武汉大学计算机学院13查询处理的过程1．查询处理的过程RDBMS处理用户查询请求的过程是：接到用高级查询语言书写的查询请求后，首先进行词法分析和语法分析，并确认语义正确后，产生查询的内部表示（通常为查询树或查询图），然后由RDBMS选定一个执行策略（包括操作的执行顺序，如何访问外部文件，存储中间结果），接着由查询执行引擎(queryexecutionengine)负责产生执行查询的代码，交给运行时数据库处理器执行，最终产生查询结果或报告出错信息。武汉大学计算机学院14查询处理的过程词法分析、语法分析、语义确认查询优化器运行时数据库处理器查询执行引擎执行查询的代码查询结果查询的内部表示执行策略高级语言查询语句图1处理高级查询语句的过程查询的表示形式功能模块武汉大学计算机学院15查询处理的过程2．处理过程中的功能模块●词法分析、语法分析、语义确认●查询优化器●查询执行引擎●运行时数据库处理器武汉大学计算机学院16查询处理的过程（1）查询优化器（queryoptimizer）功能：负责产生最有效的查询执行计划（QEP）●逻辑转换部分：对于一个语法树，根据关系代数等价变换规则，得到所有的等价的关系代数表达式；●物理转换部分：对于每一个关系代数表达式，根据查询引擎提供的物理操作，找出所有可能的查询执行计划●比较和查找：根据代价估计函数，估计每一个查询执行计划的代价，并从中找出代价最小的查询执行计划。武汉大学计算机学院17查询处理的过程（1）查询优化器（queryoptimizer）代价最小QEP逻辑转换查询请求等价变换规则集等价的语法树集合物理转换等价的QEPjoinjoinR3R2R1join树Sort-mergeNested-loopR3R2R1操作树物理操作集代价估计函数查找武汉大学计算机学院18查询处理的过程（2）查询执行引擎(queryexecutionengine)功能：●查询执行引擎为每一个关系操作的实现提供多种物理实现方法，如选择操作有二种可能的物理操作：顺序扫描和索引扫描；如连接操作有三种可能的物理操作：嵌套循环连接、合并连接和散列连接。当然查询执行引擎还可以提供更多的物理实现方法。每一种物理实现方法利用不同的存取路径（如索引、数据的存储分布、元组的排序等）●负责产生执行查询的代码武汉大学计算机学院19查询处理的过程嵌套循环连接（Nested-loopJoin）将一个表用作外部输入表，另一个表用作内部输入表。外部循环逐行消耗外部输入表。内部循环对于每个外部行，在内部输入表中搜索匹配行。最简单的情况是，搜索时扫描整个表，则称为单纯嵌套循环连接。如果搜索时使用索引，则称为索引嵌套循环连接。如果将索引生成为查询计划的一部分（并在查询完成后立即将索引破坏），则称为临时索引嵌套循环连接。武汉大学计算机学院20查询处理的过程嵌套循环连接查询优化器考虑所有这些不同形式。如果外部输入表很小而内部输入表很大且预先创建了索引，则嵌套循环连接尤其有效。在许多小事务中（如那些只影响较小的一组行的事务），索引嵌套循环连接远比合并连接和散列连接优越。但在大查询中，嵌套循环连接通常不是最佳选择。武汉大学计算机学院21查询处理的过程合并连接(Sort-mergeJoin)合并连接要求两个输入都在合并列上排序。查询优化器一般扫描索引（如果在适当的一组列上存在一个索引），或在合并连接的下面放一个排序运算符。由于每个输入都已排序，MergeJoin运算符将获取每个输入中的行并将其进行比较。例如，对于内连接操作，如果行相等则返回。如果行不相等，则废弃值较小的行并从该输入中获得另一行。这一过程将重复进行，直到处理完所有的行为止。武汉大学计算机学院22查询处理的过程合并连接合并连接本身的速度很快，但如果需要排序操作，选择合并连接就会非常费时。然而，如果数据量很大且能够从现有B树索引中获得预排序的所需数据，则合并连接通常是最快的可用连接算法。武汉大学计算机学院23查询处理的过程散列连接(HashJoin)散列连接有两种输入：生成输入和探测输入。查询优化器指派这些角色，使两个输入中较小的那个作为生成输入。武汉大学计算机学院24查询处理的过程内存中的散列连接散列连接先扫描或计算整个生成输入，然后在内存中生成散列表。根据为散列键计算出的散列值，将每行插入散列存储桶。如果整个生成输入比可用内存少，则可以将所有行都插入散列表中。生成阶段后接着是探测阶段。一次一行地对整个探测输入进行扫描或计算，并为每个探测行计算散列键的值，扫描相应的散列存储桶并生成匹配项。武汉大学计算机学院25查询处理的过程Grace散列连接如果生成输入不适合内存，散列连接将分步进行。每一步都包括生成阶段和探测阶段。首先，消耗整个生成和探测输入表（使用散列键上的散列函数）将其分区为多个文件。这类文件的数目称为分区输出端。通过使用散列键上的散列函数，可以保证任意两个连接记录必在相同的文件对中。因此，连接两个大输入的任务简化为相同任务的多个较小的任务。然后将散列连接应用于每对分区文件。武汉大学计算机学院26查询处理的过程（3）运行时数据库处理器功能：执行查询代码，产生查询结果或报告出错信息武汉大学计算机学院27查询处理的过程3．处理过程中查询的表示形式高级查询在处理过程中表示形式在不断变化，一般经历四种表现形式：●高级查询语句●查询的内部表示●执行策略的表示形式●执行查询的代码武汉大学计算机学院28查询处理的过程（1）高级查询语句通常高级查询语句只描述查找条件和结果关系的组成，而不关心查找过程和细节。例如，SQL例2查找选修了课程名为J的课程，并且成绩高于85分的学生的姓名和成绩SELSCTSN，GFROMS，SC，CWHERE（G85）AND（CN=‘J’）AND（S.S#=SC.S#）AND（C.C#=SC.C#）；武汉大学计算机学院29查询处理的过程（2）查询的内部表示查询的内部表示一般采用关系代数表达式，上面的SQL语句可以用下面的关系代数表达式来表示：πSN，G（σ（G85）∧（CN=‘J’）（S⋈SC⋈C））σ（G85）∧（CN=‘J’）πSN，G⋈⋈SCCS图2语法树关系代数表达式可表示为一棵二叉树，即语法树：武汉大学计算机学院30查询处理的过程（3）执行策略的表示形式执行策略的表现形式是一棵物理操作树。树的叶子结点代表参加查询的关系表，中间结点代表物理操作，同时也表示中间结果关系。σ（G85）∧（CN=‘J’）πSN，G⋈⋈SCCS图2语法树S1（G85）∧（CN=‘J’）P1SN，GSort-mergeNested-loopSCCS图3物理操作树武汉大学计算机学院31查询优化的目标武汉大学计算机学院32查询优化的目标查询优化器的目标是：选择最有效的查询执行计划以存取相关数据和回答查询查询优化的最终目的是：提高查询效率，缩短查询请求的响应时间查询请求的响应时间=优化时间+最佳的查询执行计划的执行时间查询优化器的目标是：找到一个相当好的查询执行计划，使得查询请求的响应时间最小武汉大学计算机学院33查询优化的基本原理武汉大学计算机学院34查询优化的基本原理1．查询优化是一个困难的搜索问题一个查询往往有很多个QEP，这是因为一个查询请求对应着大量的等价关系代数表达式，并且一个关系代数表达式可由大量的查询执行计划来实现，随着Q中包含的关系数的增加和查询执行引擎提供的物理操作的增加，这两个集合成指数级增长。查询优化器从中找出一个好的QEP的问题可以看作是一个非常困难的搜索问题。武汉大学计算机学院35查询优化的基本原理2.三类查询优化器的基本原理（1）穷尽(精确)优化方法（2）两段优化方法（3）启发式方法武汉大学计算机学院36查询优化的基本原理（1）穷尽(精确)优化方法Q对应的代数表达式集合Q对应的QEP集合查询请求Q转换转换图4穷尽优化方法武汉大学计算机学院37查询优化的基本原理（1）穷尽(精确)优化方法穷尽方法的优化代价是非常大的，因为两个转换部分包含着大量转换，并且对所有QEP估计代价都需要大量的时间，而且，这种时间复杂性随着查询中包含的关系个数的增加而成指数级增长。武汉大学计算机学院38查询优化的基本原理（2）两段优化方法将查询优化问题分为两个阶段：一个是逻辑优化阶段，任务是从等价的关系代数表达式中找出几个具有最小代价的关系代