《数据库技术与应用 教学课件 ppt 作者 第10章 查询处理和优化》由会员分享，可在线阅读，更多相关《数据库技术与应用 教学课件 ppt 作者 第10章 查询处理和优化（41页珍藏版）》请在金锄头文库上搜索。
1、第10章 查询处理和优化,本章学习目标,了解并掌握查询处理的过程。 了解查询处理代价的度量方法。 了解查询优化在关系数据库系统中的必要性和可行性。 掌握查询优化的一般策略。 理解并掌握代数优化的思想和算法。 理解物理优化的基本思想和方法。,本章概述,本章主要讨论关系数据库的查询优化技术。查询处理是关系数据库系统最主要的功能。关系数据库的查询一般都使用SQL语句实现。对于同一个用SQL表达的查询要求，通常可以对应于多个不同形式但相互“等价”的关系代数表达式。对于描述同一查询要求但具有不同形式的关系代数表达式来说，由于存取路径可以不同，相同的查询，其效率就会产生差异，有时这种差异会相当巨大。在关系
2、数据库中，查询优化是查询处理中一项重要和必要的工作，查询优化通过寻求好的查询路径或好的等价代数表达式来提高查询效率，通常包括代数优化和物理优化技术。,主要内容,10.1 查询处理,10.3 代数优化,10.4 物理优化,10.2 查询优化,10.5实际应用中的查询优化,主要内容,10.1 查询处理,10.3 代数优化,10.4 物理优化,10.2 查询优化,10.5实际应用中的查询优化,10.1 查询处理,10.1.1 查询处理步骤,1. 查询分析 首先，对查询语句进行扫描、词法分析和语法分析。从查询语句中识别出语言符号，如SQL关键字，关系名和属性名等，并进行语法检查和分析，即判断查询语句是
3、否符合SQL语法规则。 2. 查询检查 查询检查首先根据数据字典对合法的查询语句进行语义检查，检查语句中的数据库对象(如关系名、属性名)是否存在和是否有效。然后，根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查，如果用户没有相应的访问权限或违反了完整性约束原则，就拒绝执行该查询。检查通过后，把查询语句转换成等价的关系代数表达式。RDBMS一般都用查询树(query tree)，也称为语法分析树(syntax tree)，来表示扩展的关系代数表达式。这个过程就是把数据库对象的外部名称换为内部表示。,10.1 查询处理,3. 查询优化 每个查询都会有很多可供选择的执行策略和操作算法
4、，查询优化是指选择一个高效执行的查询处理策略。DBMS会调用系统的优化处理器制定一个执行策略，由此产生一个查询计划。对关系型数据库来说，查询优化过程是由RDBMS系统自动完成的，它与用户提交的查询语句无关。,10.1 查询处理,查询优化有多种方法。按照优化的层次一般可分为代数优化和物理优化。 (1) 代数优化：指关系代数表达式的优化，即按照一定的启发式规则，改变代数表达式中操作的次序和组合，使查询执行得更高效。例如“优先选择、投影而后连接”等就可完成优化。 (2) 物理优化： 指存取路径和底层操作算法的选择。选择的依据可以是基于语义的，也可以是基于代价的，还可以是基于规则的。 实际优化过程都综
5、合运用了这些优化技术，以获得最好的查询优化效果。 4. 查询执行 依据查询优化器得到的查询计划，由代码生成器生成执行这个查询计划的可执行代码。,10.1 查询处理,查询优化有多种方法。按照优化的层次一般可分为代数优化和物理优化。 (1) 代数优化：指关系代数表达式的优化，即按照一定的启发式规则，改变代数表达式中操作的次序和组合，使查询执行得更高效。例如“优先选择、投影而后连接”等就可完成优化。 (2) 物理优化： 指存取路径和底层操作算法的选择。选择的依据可以是基于语义的，也可以是基于代价的，还可以是基于规则的。 实际优化过程都综合运用了这些优化技术，以获得最好的查询优化效果。 4. 查询执行
6、 依据查询优化器得到的查询计划，由代码生成器生成执行这个查询计划的可执行代码。,10.1 查询处理,目前DBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。 查询执行代价可以通过查询对各种资源的使用情况进行度量。在集中式数据库中，查询的执行开销主要包括磁盘存取时间(I/O代价)，处理器时间(CPU代价)，查询的内存时间。在并行/分布式数据库系统中还要加上通信代价，即： 查询执行总代价= I/O代价+ CPU代价+内存代价+通信代价。,10.1.2 查询执行代价度量,主要内容,10.1 查询处理,10.3 代数优化,10.4 物理优化,10.2 查询优化,10.
7、5实际应用中的查询优化,10.2 查询优化,10.2.1 查询优化的必要性,还可以写出其他等价的关系代数表达式，但分析这三种就足以说明问题了。下面我们计算这3种表达式查询所需时间，可以发现由于查询执行策略的不同，使得查询时间有很大的差异。在计算之前做以下统一约定。,10.2 查询优化,设Student有1000个元组，SC有10000个元组，其中选修“C003”号课程的元组数为50个。 设一个物理块能装10个Student元组或100个SC元组。 内存有6个块的缓冲区，其中5块存放Student元组，1块存放SC元组。 读/写磁盘一物理块的时间为1/20s，即1s读写20个磁盘块。 为简化起见
8、，所有内存操作所花时间可以忽略不计。,10.2 查询优化,10.2.2 查询优化的可行性,关系数据库系统查询语句表示查询操作基于集合运算，称之为关系代数。关系代数具有5种基本运算，这些运算间满足一定的运算定律，如结合律、交换律、分配律和串接律等，这就表示不同的关系代数表达式可以得到相同的结果，因此用关系代数语言进行查询时可以进行必要的优化，以获取较优的查询性能。 由于关系查询语言的特点，能够找到有效的算法，使得查询优化过程在DBMS内部自动完成，向用户屏蔽优化的细节实现。因此，用户只需向DBMS提出“做什么”，而不必指出“如何做”，这样用户在编程时只需表示出所想要的结果，无需给出获得结果的具体
9、步骤，这一切由DBMS完成。 查询优化一般可分为代数优化和物理优化。代数优化是指关系代数表达式的优化；物理优化是指存储路径和底层操作算法的优化。,主要内容,10.1 查询处理,10.3 代数优化,10.4 物理优化,10.2 查询优化,10.5实际应用中的查询优化,10.3 代数优化,所谓关系代数表达式的等价是指用相同的关系代入两个关系表达式中所得到的结果是相同的。两个关系表达式E1和E2是等价的，可记作E1E2。 常用的代数表达式的等价变换规则主要有以下几类，证明从略。 (1) 连接、笛卡尔积的交换律 设E1和E2是关系代数表达式，F是连接运算的条件，则下列等价公式成立。,10.3.1 关系
10、代数表达式等价交换规则,10.3 代数优化,(2) 连接、笛卡尔积的结合律 设E1、E2和E3是关系代数表达式，F1和F2是连接运算条件，则下列等价公式成立。,10.3 代数优化,(3) 投影的串接定律 设E是关系代数表达式，Ai(i=1，2，n)，Bj(j=1，2，m)是E中的某些属性名，且 构成 的子集，则下列等价公式成立。,(4) 选择的串接定律 设E是关系代数表达式，、是选择条件，则下列等价公式成立。,10.3 代数优化,10.3 代数优化,(7) 选择与并运算的分配律 设E1和E2是两个关系代数表达式，并且E1和E2具有相同的属性名，F是选择条件，则下列等价公式成立。,(8) 选择与
11、差运算的分配律 设E1和E2是两个关系代数表达式，并且E1和E2具有相同的属性名，F是选择条件，则下列等价公式成立。,10.3 代数优化,10.3 代数优化,关系代数表达式的查询优化是由RBMS的DML编译器自动完成的。因此，查询优化的基本前提是需要将关系代数表达式转换为某种内部表示，常用的内部表示就是所谓的关系代数语法树，简称为语法树。其实现的过程是先对一个关系代数表达式进行语法分析，将分析结果用树的形式表达出来，此时的树就称之为语法树。语法树具有如下特征： (1) 树中的叶节点表示关系。 (2) 树中的非叶子结点表示操作。 例10-2 下面给出例10-1中SQL语句的关系代数语法树示例。,
12、10.3.2 语法树,10.3 代数优化,1. 选择运算优先原则 尽可能早地先做选择运算。在优化策略中这是最重要、最基本的一条，因为选择运算往往会使关系运算中间结果的记录数量大大减少，从而可以成数量级地减少执行时间和存取磁盘次数。例如：同时执行一串选择运算或一串连接运算。这样可避免分开执行时，造成多次扫描关系记录的情况。 2. 投影运算优先原则 把投影运算同其前或其后的双目运算结合起来，以避免对关系的重复扫描。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。,10.3.3 关系代数表达式优化算法,10.3 代数优化,5. 必要的
13、预处理 在执行连接(或乘积后跟选择)运算之前，先对关系文件作一些预处理，比如排序和建立索引，这样会使两个关系的连接效率高一些。 下面根据上述的启发式优化策略以及关系表达式的等价交换规则，可以得到关系代数表达式的优化算法。 算法：关系表达式的优化。 输入：一个关系表达式的查询树。 输出：优化的查询树。 方法： (1) 利用选择运算合取条件分解定律，把形如 的表达式进行分解，转换为 。,10.3 代数优化,(2) 对每一个选择，利用等价交换规则尽可能把它移到树的叶端。 (3) 对每一个投影，利用等价交换规则尽可能把它移向树的叶端。其中，利用投影的串接定律使一些投影消失，而利用选择与投影的交换律可把
14、一个投影分裂为两个，其中一个有可能被移向树的叶端。 (4) 利用等价转换的各个规则把选择和投影的串接合并成单个选择，单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，尽管这种交换似乎违背“投影运算优先原则”，但这样做效率更高。 (5) 把上述得到的语法树的内节点分组。每一双目运算和它所有的直接祖先为一组(这些直接祖先是(运算)；如果其后代直到叶子全是单目运算，则也将它们并进该组。但当双目运算是笛卡尔积，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组，应当把选择条件单独分为一组。,主要内容,10.1 查询处理,10.3 代数优化,10
15、.4 物理优化,10.2 查询优化,10.5实际应用中的查询优化,10.4 物理优化,1. 选择操作的启发式规则 (1) 对于小关系，使用全表顺序扫描方法，即使选择列上有索引。 对于大关系，可以采用的启发式规则如下： (2) 对于选择条件是“主码=值”的查询，查询结果最多是一个元组，可以选择主码索引。一般的RDBMS会自动建立主码索引。 (3) 对于选择条件是“非主属性=值”的查询，并且选择列上有索引，此时需要估算查询结果的元组数目。如果比例较小(10%)，可以使用索引扫描方法，否则使用全表顺序扫描。 (4) 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果
16、的元组数目，如果比例较小(10%)，可以使用索引扫描方法，否则使用全表顺序扫描。,10.4.1 基于启发式规则的存取路径选择优化,10.4 物理优化,（5) 对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，则优先采用组合索引扫描方法。如果某些属性上有一般的索引，则可以用索引扫描方法，否则使用全表顺序扫描。 (6) 对于用OR连接的析取选择条件，一般使用全表顺序扫描方法。 2. 连接操作的启发式规则 连接操作是数据库中开销很大的操作，一直是查询优化研究的重点。本节主要讨论最基本、使用最多的二元连接的优化。多元连接操作是以二元为基础的。实现连接操作一般有嵌套循环连接、基于索引的连接、排序合并连接和散列连接。,10.4 物理优化,1. 统计信息 基于代价的优化需要计算各种操作算法的执行代价，它与数据库中数据的状态密切相关。数据库管理系
