华科数据库系统原理第九章.

第9章关系查询处理和查询优化9.1问题的提出非过程化，无需显示指明存取路经。查询操作的多解性：同一个查询操作可能存在多种实现途径（算法不同、存取方法不同）。代数优化——优化关系代数表达式物理优化——优化存取路径和底层操作算法，可进一步分为基于规则的（rulebased）、基于代价的（costbased）和基于语义的（semanticbased）。12查询语句词法分析语法分析语义分析符号名转换安全性检查完整性检查查询树（querytree）语法分析树（syntaxtree）代数优化物理优化等执行策略描述代码生成查询计划的执行代码查询分析查询检查查询优化查询执行数据库数据字典基于规则的基于代价的基于语义的关系代数等价变换规则查询处理步骤基本概念1查询分析（词法、语法、语义、符号名）查询树（querytree）语法分析树（syntaxtree）执行树执行计划3实例设有如下关系：学生（学号，姓名，性别，出生日期，所在系）课程（课号，名称，学分）成绩（学号，课号，成绩）要求查询选修了2号课程的学生姓名。可用如下等价的代数表达式来完成这一查询：Q1＝π姓名（σ学生.学号=成绩.学号∧课号=’2’（学生×成绩））Q2＝π姓名（σ课号=’2’(学生成绩））Q3＝π姓名（学生σ课号=’2’（成绩））由于查询执行的策略不同,查询时间相差很大。4统计量：学生记录——1000条；成绩记录——10000条；选修了2号课程的记录——50条。一个物理块（页面）能容纳：10条学生记录或100条成绩记录。内存仅提供7个存储页面，其中5页存放学生记录，1页存放成绩记录，1页存放中间结果。磁盘每秒钟读/写20块数据记录。采用嵌套循环实现方式。5外表:学生表内表:成绩表第一种情况：Q1＝π姓名（σ学生.学号=成绩.学号∧课号=’2’（学生×成绩））1．计算：学生×成绩读取的总块数为：1000/10+1000/(10×5)×10000/100=2100(块)所需时T1=2100/20=105(秒)笛卡儿集的元组个数为103×104＝107，设每块能装10个元组，则写出这些块所需的时间T2=106/20=5×104(秒)6学生表块数学生表批量读次数成绩表块数注意:写出!2．作选择σ依次读入连接后的结果，选择满足条件的记录，假定内存处理时间忽略不计，则读取中间结果的时间T3与T2相等，即T3=5×104(秒)，满足条件的记录仅有50条，结果直接驻留内存。3．作投影π将内存中的结果在“姓名”上作投影，得最终结果，因此第一种情况下执行查询的总时间为：T=T1+T2+T3≈105(秒)（总时间约28小时）7第二种情况Q2＝π姓名（σ课号=’2’(学生成绩））1．计算自然连接读取学生表和成绩表的策略不变，总的读取时间仍105秒，但自然连接的结果比第一种情况大大减少，为104条，因此，写出这些元组所需时间为104/10/20＝50（秒）。2．作选择读取中间结果所需的时间仍为50（秒），符合条件的记录为50条。3．作投影将中间结果投影输出。第二种情况总的执行时间为：105＋50＋50＝205（秒）810000条成绩记录第三种情况Q3＝π姓名（学生σ课号=’2’（成绩））1．先对成绩表作选择运算，只读取一遍成绩表，存取花费时间为5秒，因满足条件的记录为50条，不必使用中间文件。2．读取学生表并与内存中的成绩记录作连接，花费时间5秒。3．输出投影结果。第三种情况总的执行时间为10秒。上例充分说明查询优化的必要性，同时给出一些查询优化方法的基本思想（避免笛卡儿积,尽量让选择运算在连接运算之前执行）。91000/10/20基本概念2选择运算的实现方法：全表扫描索引扫描连接运算的实现方法：嵌套循环连接（nestedloop）排序—合并连接（sort-mergejoin）Hash连接（hashjoin）索引连接（indexjoin）10两个关系是否只扫描一次？如果两个关系的连接属性均存在重复值又会如何？HASH连接9.2查询优化的任务：提高速度（DBMS）9.3查询优化的目标1、减少中间关系规模2、减少I/O关系代数表达式的等价变换规则（课本269～271页）SQL查询的代数处理过程（课本272页，图9.3~9.5）9.4一般策略（查询树的启发式优化）1、“选择”尽可能提前执行；最基本一条，因为“选择”使中间结果变小。2、索引和排序特别是对连接运算，连接前“先排序”或“建立”索引，提高速度。11例如：对Borrower与Loans进行自然联接计算时：①对loans按card-no建立索引；②对Borrower每一元组的card-no值：·通过loans索引查元组·Borrower元组与相应元组连接起来③无需反复扫描loans3、“投影”和“选择”同时进行，（避免多次扫描关系，否则投影选择各扫描一次）。前提是两种运算对同一关系运算才成立。124、（某些）选择与选择前的笛卡尔积结合扫描得到的元组立即与参与计算的另一元组做匹配条件过滤，将这种笛卡尔积转变为连接运算。连接运算（特别是等值连接运算）比笛卡尔积快。5、投影与其前后的其它双目运算同时进行，避免重复扫描关系。6、提取公共子表达式。①计算公共子表达式结果②结果存入外存③需要时从外存调入内存使用（无需重计算）④前提：外存调入内存的时间大大少于计算公共表达式时间13关系表达式代数优化算法1）运用选择的串接定律，得到选择运算“串”；2）对每个选择运算符，利用等价变换尽量将其移至树的叶端；3）对每个投影运算符，利用等价变换尽量将其移至树的叶端；4）尝试将“选择”和“投影”串接合并成单个“选择”或“投影”，或“选择”后跟一个“投影”；5）上述得到的语法树内结点分组：双目运算和它的父节点为一组。若其后代直至叶节点全是单目运算，也合并为一组。笛卡尔积的子节点若是不能组合成等值连接的“选择”，则二者不合并。14查询树selectsnamefromstu,scwherestu.sno=sc.snoandsc.cno=2结果Project(sname)Select(sc.cno=2)Join(stu.sno=sc.sno)stusc15关系代数语法树投影（sname）选择（sc.cno=2）选择（stu.sno=sc.sno）笛卡尔积stusc16代数优化后的查询树1投影（sname）选择（sc.cno=2）等值连接（stu.sno=sc.sno）stusc17代数优化后的查询树218投影（sname）选择（sc.cno=2）等值连接（stu.sno=sc.sno）stusc9.5物理优化常常先使用启发式规则选取若干较优的候选查询方案，然后分别估算这些候选方案的执行代价，从而选取代价最小的作为执行计划。总代价＝I/O代价＋CPU代价＋内存代价＋通信代价•启发式规则选择操作的启发式规则1）对于小关系，使用全表顺序扫描，即使选择列上有索引。2）对于选择条件是“主码=值”的查询，可以选择主码索引。（一般的DBMS会自动的建立主码索引）193）对于选择条件是“非主属性=值”的查询，并且选择列上有索引，则估算查询结果元组数目，如果比例较小，可以使用索引扫描算法，否则还是使用全表顺序扫描。（DBA监控）4）对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，则估算查询结果的元组数目，如果比例较小，可以使用索引扫描，否则使用全表顺序扫描。5）对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，则优先采用组合索引；如果有多个一般索引，可以用索引扫描并求交集的方法；否则采用全表顺序扫描。6）对于用OR连接的析取选择条件，一般使用全表顺序扫描。20selectivity连接操作的启发式规则1）如果2个表都已按照连接属性排序，则选用merge-sort方法。2）如果1个表在连接属性上有索引，则可选用索引连接方法。3）如果上述2个规则均不适用，且其中1个表较小，可选用hashjoin方法。4）对于nestedloopjoin方法，选择占用块数较小的表作外表。问题：内存块的分配？外表的选择？21为什么采用启发式规则？可能的执行策略很多，要穷尽所有的策略进行代价估算需要的计算开销往往与被连接的关系数成指数复杂度关系。可能造成查询优化过程的开销大于获得的查询开销的减小，得不偿失。22所有可能的执行策略随机选择一种执行估算所有策略，寻找估算代价最小的一种执行随机选择所用时间+被选择策略的执行时间估算过程所用时间+被选择策略的执行时间更小？最小？启发式规则在一般情况下适用，但不一定保证获得最优执行计划。（试运行、DBA性能调整）和启发式方法类似的其他解决方法：贪婪算法、遗传算法。。。其思想都是类似——求近似最优解。启发式方法适用于解释执行方式（优化开销包含在查询总开销中），对于编译执行方式，可采用基于代价的优化方法。23代价估算与数据库的状态密切相关，需要在数据字典中存储优化器所要的统计信息。统计信息1.基本表元组总数、元组长度、占用块数、溢出块数2.列不同值的个数、选择率selectivity、最大值、最小值、是否有索引、索引类型3.索引索引层数、不同索引值个数、索引选择基数（同索引值的情况）、叶结点个数24代价估算公式B：表的块数；L：索引深度；S：索引选择基数；Y：索引叶结点数；Frs:连接选择性；Mrs:连接结果单块记录数；Nr关系R元组数；Ns关系S元组数。1.全表扫描cost=B,对于单值搜索，cost=B/22.索引扫描cost=L+1码=值cost=L+S非码属性=值cost=L+Y/2+B/2、=、、=3.nestedloopjoincost=Br+Br*Bs/(K-1)+(Frs*Nr*Ns)/Mrs4.mergejoincost=Br+Bs+(Frs*Nr*Ns)/Mrs259.6查询优化小结•优化是为了减小查询的代价，包括I/O、CPU、内存和通信代价，是关系数据库的重要问题。•导致查询代价较高的一个主要原因是关系代数的笛卡儿积运算。•理解优化的问题需要先了解关系操作的执行过程。26优化的手段包括代数和逻辑两种类型，涉及众多方面：关系代数运算符执行的先后顺序和组合情况、运算符执行所采用的算法、数据的聚集存储、表的分区、文件中的碎片、跨页链接的数量、元组的排序、索引的建立、缓冲区的大小、DBMS对语句的缓存机制、语句的解释或者编译执行、优化算法的开销和准确性、统计信息的时效性与详细程度、代价估算模型的精确与否等等。27查询优化的过程：•查询树经过变形后得到语法树，•然后根据代数优化的启发式规则对语法树进行逻辑优化，•再考虑存取路径、底层操作算法的不同，根据物理操作的启发式规则提出多种查询计划，•然后可根据某种代价模型评估这些查询计划的执行代价，从中选取评估结果最小的作为执行计划。28DBMS查询优化1）优化器可以获取数据字典中的统计信息；2）关系数据库中统计信息改变系统可自动重新优化而无需重写应用程序；3）优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑优先的几种可能；4）优化器将很多复杂的优化技术封装在系统中，降低应用程序的编写难度。29目前比较成熟的是对传统数据类型、关系代数运算表达式的优化策略，而面对新的数据类型、更为复杂的查询需求、更为复杂的数据分布方式和查询运行机制、以及用户的个性化需求，查询优化依然是关系数据库要解决的主要问题。30