数据库上课第十三讲查询处理优化

机械自动化学院2015主讲：顾曦电话：[phone]Email：[e-mail]数据库系统原理与设计主要内容09:5921.查询处理2.查询优化09:593Profile简介Profile是在Mysql5.1以后版本引入，来源于开源社区JeremyCole的贡献。当一条查询提交给服务器时，此工具会记录剖析信息到一张临时表，并且给查询赋予一个整数标识符。剖析信息包含数据库对某个查询的详细执行情况，对于分析和优化查询，提高数据库的性能很有帮助。Profile工具的使用启动数据库，登录客户端；使用数据库scoreDBmysqlusescoredb；启动查询刨析工具：mysqlsetprofiling=1;执行查询mysqlselect*fromstudent;查看执行时间信息（单位：秒）mysqlshowprofiles；09:595查看详细信息09:596推荐书目高性能MySQL（第3版）BaronSchwartz，PeterZaitsev，VadimTkachenko著宁海元，周振兴，彭立勋，等译电子工业出版社2013-509:59709:5981.1概述查询处理(queryprocessing)是指从数据库中提取数据时所涉及的一系列活动。用高层数据库语言(如SQL)表示的查询语句翻译成能在文件系统的物理层上使用的表达式。为优化查询而进行的各种转换以及查询的实际执行。查询处理的主要过程包括：语法分析与翻译查询优化查询执行1）语法分析与翻译器查询处理开始之前，系统将查询语句翻译成可使用的形式。语法分析与翻译阶段的主要工作有：检查用户查询的语法，利用数据字典验证查询中出现的关系名、属性名等是否正确；构造该查询语句的语法分析树表示，并将其翻译成关系代数表达式。2）查询执行计划与查询优化器一个给定的查询任务，一般都会有多种计算结果的方法例如，考虑如下查询selectstudentNamefromStudentwhereclassNo='CS0701'andsex='女'该查询语句可翻译成如下关系表达式中的任意一个σclassNo='CS0701'(σsex='女'(∏studentName(Student)))σsex='女'(σclassNo='CS0701'(∏studentName(Student)))σclassNo='CS0701'(∏studentName(σsex='女'(Student)))∏studentName(σsex='女'(σclassNo='CS0701'(Student)))执行一个查询，不仅需要提供关系代数表达式，还要对该表达式加上注释来说明如何执行每个操作。加了“如何执行”注释的关系代数运算称为执行原语。用于执行一个查询的原语操作序列称为查询执行计划。不同的查询执行计划会有不同的代价。DBMS通过查询优化器构造具有最小查询执行代价的查询执行计划，称为查询优化。查询优化是影响RDBMS性能的关键因素。关系数据库系统和非过程化的SQL语言能够取得巨大成功关键是得益于查询优化技术的发展。3）查询执行引擎查询执行引擎根据输入的查询执行计划，调用相关算法实现查询计算，并将计算结果返回给用户。有效地对内存缓冲区进行管理是影响查询执行性能的非常重要的方面。09:59142.1概述查询处理的代价可以通过该查询对各种资源的使用情况进行度量。主要包括磁盘存取时间执行一个查询所用的CPU时间、在并行/分布式数据库系统中的通信开销等对于大型数据库系统而言，在磁盘上存取数据的代价通常是最重要的代价，可以通过传输磁盘块数以及搜索磁盘次数来度量。在代价估算时，通常假定是最坏的情形。大型数据库系统最重要的代价通常是在磁盘上存取数据的代价，通过传输磁盘块数以及搜索磁盘次数来度量。例如：一个传输b块并作s次磁盘搜索的操作将耗时b×tT+s×tS（毫秒(ms)）其中：tT：传输一块数据的平均耗时tS：搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)09:5916查询优化器利用存储在DBMS的数据字典中的统计信息来估算查询执行计划的代价，相关的统计信息主要包括：nr：关系r中的元组数目。br：用于存储关系r所有元组的块数目。lr：关系r中一个元组的大小。fr：关系r的块因子，即一个物理块中能存放的关系r的元组数目。V(A,r)：关系r中属性A所具有的不同值的数目，该数目与∏A(r)的大小相同。若A为关系r的码，则V(A,r)=nr。SC(A,r)：关系r关于属性A的选择度，表示在属性A上满足某个等值条件（假设至少有一条记录满足该等值条件）的平均记录数。若A为关系r的码，则SC(A,r)=1；若A为非码属性，并假定V(A,r)上不同的值在所有元组中平均分配，则SC(A,r)=nr/V(A,r)。HTi：索引i的层数，即高度。2.2选择运算用于选择运算的搜索算法：1)文件扫描：不用索引的搜索算法线性搜索算法A1二分搜索算法A22)索引扫描：使用索引的搜索算法在主索引的码属性上的等值比较算法A3在主索引的非码属性上的等值比较算法A4在辅助索引上的等值比较算法A5在主索引上的范围比较算法A6在辅助索引上的范围比较算法A71)选择运算—文件扫描文件扫描：用于定位、检索满足选择条件的记录①线性搜索算法A1线性搜索中，系统扫描每一个文件块，对所有记录进行测试，看它们是否满足选择条件。开始时需作一次磁盘搜索来定位文件的第一个块。线性搜索的代价为EA1=br*tT+tS，其中br代表文件中的磁盘块数。09:5919线性搜索算法A1的优缺点09:5920优点可用于任何文件，不管该文件是否有序，是否有索引，也不管何种类型的选择操作；缺点线性搜索比其他实现选择操作的算法速度慢。②二分搜索算法A2关于搜索码物理有序存储，搜索过程是针对文件的磁盘块进行，而不是针对记录进行最坏情况下，找到包含所需记录的磁盘块所需访问和检查的磁盘块数目为log2(br)，而且每一个这样的磁盘块都需要一次磁盘搜索定位，因此算法A2的时间代价为EA2=⌈log2(br)⌉*(tT+tS)如果是在非码属性上的选择操作，那么可能会有多个块包含所需记录，这样还需顺序读取包含选择结果的额外块，估计有⌈SC(A,r)/fr⌉-1个额外块。09:59212）选择运算—索引扫描①主索引码属性上的等值比较算法A3具有主索引的码属性上的等值比较算法，可以通过主索引检索到指向满足相应等值条件的唯一记录的指针，再根据该指针到数据文件中访问磁盘块。若使用B+树索引，则访问索引块的数量等于树高度HTi，访问文件块的数量为1；而且每一次I/O操作都需要一次磁盘搜索定位和一次磁盘块传输。因此，算法A3的时间代价为：EA3=⌈HTi+1⌉*(tT+tS)09:5922②主索引非码属性上的等值比较算法A4通过主索引检索到指向满足相应等值条件的第一条记录（可能有多条记录，但它们在物理上顺序存放）的指针，再根据该指针到数据文件中访问磁盘块。需要访问的文件块的数目可估计为：b=⌈SC(A,r)/fr⌉算法A4的时间代价为EA4=⌈HTi+1⌉*(tT+tS)+(⌈SC(A,r)/fr⌉-1)*tT09:5923③辅助索引的等值比较算法A5如果是码属性上的等值条件，算法A5的时间代价与算法A3相同。如果是非码属性上的等值条件，则通过辅助索引可以检索到存放满足相应等值条件的多条记录的指针桶的指针，再根据该指针桶中的每一个指针分别到数据文件中访问包含相应记录的文件块。最坏情况下，算法A5的时间代价为：EA5=⌈HTi+1+SC(A,r)⌉*(tT+tS)其中的加1是表示访问指针桶的代价。09:5924④主索引上的范围比较算法A6对于形如Av或A≥v的比较条件，首先通过主索引（如B+树索引）搜索，定位在满足Av或A≥v条件的第一个索引项，该索引项中的指针指向满足查询条件的所有记录中的第一条。然后通过该指针到文件中搜索磁盘块，并从该磁盘块开始顺序访问所有的磁盘块，直到文件结束。其时间代价可估算为（SC(P(A),r)表示满足谓词P(A)的选择度）EA6=⌈HTi+1⌉*(tT+tS)+(⌈SC(P(A),r)/fr⌉-1)*tT对于形如Av或A≤v的比较条件，没有必要查找索引，时间代价为EA6=tS+⌈SC(P(A),r)/fr⌉*tT09:5925⑤辅助索引上的范围比较算法A7Av或A≥v的比较条件Av或A≤v的比较条件如果满足查询条件的记录数很多，使用辅助索引的代价甚至比线性搜索还要大。辅助索引只适合于满足查询条件的记录很少时使用。09:59263）复杂选择的实现多码索引——建立在多个属性搜索码上的索引例：Score（studentNo，courseNo，score）在搜索码（studentNo，courseNo）上建立和使用索引，studentNo，courseNo）称为复合搜索码。每一个索引项（或索引记录）由一个复合搜索码(A1,A2,…,An)上的属性值列表(v1,v2,…,vn)和一个指向相应的文件记录或指针桶的指针组成，而且要求关于搜索码值列表(v1,v2,…,vn)升序存放。09:5927①复杂选择-合取(∧)选择操作选择满足选择谓词θi的记录的交集合取(conjunction)选择操作的一般形式为：处理算法包括：利用一个索引的合取选择算法A8利用组合索引的合取选择算法A9通过记录标识的交实现合取选择的算法A1009:5928rm...21a.利用一个索引的合取选择算法A8首先确定一个其选择属性Ai上存在索引的选择谓词θi。如果存在，则首先用选择算法A2～A7中的一个来检索满足谓词θi的记录；然后在内存缓冲区中，通过测试每条检索到的记录是否满足其余的选择谓词，所有满足其余选择谓词的记录都是该合取选择操作的最后结果。为了减少代价，选择某个θi及A2～A7的算法之一，它们的组合可使的代价达到最小，并且所选算法的代价就是算法A8的代价。09:5929b.利用组合索引的合取选择算法A9首先确定k个简单选择谓词，不访记为它们都是等值选择，并且在这些谓词的属性组合上存在组合索引。如果存在首先基于该组合索引用选择算法A2～A7中的一个来检索满足合取选择谓词的记录；然后在内存缓冲区中，通过测试每条检索到的记录是否满足其余的选择谓词，所有满足其余选择谓词的记录都是该合取选择操作的最后结果。为了减少代价，选择某个可以使用复合索引的谓词组合及A2～A7的算法之一，它们的组合可使的代价达到最小，并且所选算法的代价就是算法A9的代价。09:5930kiii，，，21)(21kiii，A，，AAc.通过记录标识的交实现合取选择的算法A10对每一个选择属性Ai上存在索引的选择谓词θi，通过索引来检索指向满足谓词θi的记录的指针(或标识)，并将这些记录的指针的列表记为Li计算所有Li的交集列表L，要求交集列表L中的所有指针按升序排列；根据有序的交集列表L中的每一个指针到文件中去访问磁盘块并检索相关记录，这些记录就是满足所有这些带索引谓词的合取条件的记录对检索来的每一条记录再测试它是否满足其余的选择谓词(即选择属性上不存在索引的选择谓词)。算法A10的代价是扫描各个单独索引的代价的总和，加上获取指针列表Li的交集列表L中的指针所指向记录的代价。09:5931②复杂选择-析取(∨)选择操作所有满足单个选择谓词θi的记录的并集就是该析取选择操作的结果。析取(conjunction)选择操作的一般形式为：处理算法包括：通过记录标识的并实现析取选择的算法A1109:5932rm...21a.通过记录标识的并实现析取选择的算法A11如果析取选择中的每个简单选择谓词θi的属性上都存在相应的索引，则首先通过索引来检索指向满足谓词θi的记录的指针，并将这些记录的指针