关系DBS的查询优化ppt课件

1、6.2 关系关系DBS的查询优化的查询优化6.1 DBMS简介简介 6.3 关系关系DBMS的开展的开展1. DBMS位置位置 DBMS是是DBS的中心软的中心软件，介于用户和件，介于用户和OS之之间的系统软件，它实现间的系统软件，它实现对共享数据的有效组织、对共享数据的有效组织、管理和各种操作。管理和各种操作。用户运用程序用户运用程序DBMSDBMSOSOSDBDB DBMS DBMS建立在建立在OSOS之上，之上， 需求需求OSOS的支持。的支持。 DBMS DBMS是用户支配、管理是用户支配、管理 DB DB的工具。的工具。 阐明阐明: :独立独立DBMSDBMS、OSOS扩展扩展nDB

2、MS的特点的特点n1. 完备高效完备高效n2. 界面友好界面友好n3. 事务处置事务处置n4. 构造明晰构造明晰n5. 规范开放规范开放nDBMS的功能的功能 n (1) 数据定义数据定义 (用用DDL)n (2) 数据支配数据支配 (用用DML)n (3) 数据组织、存储和管数据组织、存储和管理理 n (4) 数据库运转管理数据库运转管理n (5) 数据库的建立和维护数据库的建立和维护 n (6) 数据通讯接口数据通讯接口 2.DBMS2.DBMS的组成的组成 (1) (1) 数据定义言语及其翻译处置程序数据定义言语及其翻译处置程序 (2) (2) 数据支配言语及其编译或解释程序数据支配言语

3、及其编译或解释程序 (3) (3) 数据库运转控制程序数据库运转控制程序 (4) (4) 适用程序适用程序 3.DBMS3.DBMS运转环境运转环境 (1) (1)分布分布: : 数据分布、功能分布、处置分布。数据分布、功能分布、处置分布。 (2) (2)开放：开放的硬件平台、支撑软件、网络支持、开放：开放的硬件平台、支撑软件、网络支持、 异质数据库互连、用户界面。异质数据库互连、用户界面。 系统缓冲区系统缓冲区概念方式概念方式内方式内方式DBMS OS 外部记录外部记录存储记录存储记录数据库数据库 运用程序运用程序A A 外方式外方式日志日志运用程序运用程序A A形状形状任务区任务区 OS

4、OS执行读命令并把数据从外存读到内存的系统缓冲区。执行读命令并把数据从外存读到内存的系统缓冲区。 DBMS DBMS按方式、子方式定义，导出用户程序需求的记录按方式、子方式定义，导出用户程序需求的记录方式，并送到运用程序方式，并送到运用程序A A的任务区。的任务区。 DBMS DBMS向运用程序向运用程序A A送命令执行情况的形状信息。送命令执行情况的形状信息。 记载日志记载日志 DBMS DBMS把对数据库更新操作的全部情况都记载下来，以把对数据库更新操作的全部情况都记载下来，以便数据库的恢复。便数据库的恢复。 运用程序检查形状信息，假设胜利，对任务区中的数运用程序检查形状信息，假设胜利，对

5、任务区中的数据正常处置；假设失败，决议下一步如何执行。据正常处置；假设失败，决议下一步如何执行。n数据查询是DBS中最根本、最常用和最复杂的数据操作，查询优化是影响关系DBMS性能的关键要素。n关系数据实际基于关系代数，同一个查询要求可以对应多个不同方式却相互等价的表达式。n关系数据查询言语是非过程化的，由DBMS自动生成假设干候选的查询方案并择优运用。查询语句查询语句查询输出查询输出关系代数表达式关系代数表达式执行方案执行方案语法分析与语法分析与翻译翻译执行引擎执行引擎优化器优化器数据数据有关数据的统计有关数据的统计信息信息n查询处置包括三个根本步骤：n 解析和翻译n 优化n 实现求值n解析

6、和翻译解析和翻译n解析：检查语法、验证关系解析：检查语法、验证关系n翻译：将查询转化为内部方式，并进一步翻译翻译：将查询转化为内部方式，并进一步翻译为关系代数为关系代数.n实现实现n执行引擎选取一个查询方案并执行，而后将结执行引擎选取一个查询方案并执行，而后将结果前往给查询果前往给查询.n查询优化查询优化: 在一切等价的执行方案中选取代价最低的那在一切等价的执行方案中选取代价最低的那个。个。 n代价是利用从系统目录中获取的统计信息估算得到的。代价是利用从系统目录中获取的统计信息估算得到的。ne.g. 关系中的元组数目关系中的元组数目, 元组的大小等元组的大小等.n需求研讨：需求研讨：n如何估量

7、查询的代价如何估量查询的代价n实现关系代数操作的算法实现关系代数操作的算法n将单个操作算法结合起来构成一个对表达式的完好求值将单个操作算法结合起来构成一个对表达式的完好求值n如何实现查询优化，即如何寻求一个具有最低代价的执如何实现查询优化，即如何寻求一个具有最低代价的执行方案。行方案。n代价通常是利用回答查询所需的时间来度量的。代价通常是利用回答查询所需的时间来度量的。n很多要素会影响查询时间：磁盘存取很多要素会影响查询时间：磁盘存取, CPU, 网络衔接网络衔接等等n通常磁盘存取是最耗时的部分通常磁盘存取是最耗时的部分, 并且容易估算并且容易估算, 主要思主要思索索. nNumber of

8、seeks * average-seek-costnNumber of blocks read * average-block-read-costnNumber of blocks written * average-block-write-costn写的代价大于读的代价：写以后需求回读以确保正确的写的代价大于读的代价：写以后需求回读以确保正确的写写n简化起见，仅运用简化起见，仅运用 number of block 从磁盘传送块的从磁盘传送块的数目作为代价的度量。数目作为代价的度量。n代价依赖于内存缓冲区的大小代价依赖于内存缓冲区的大小n更多内存降低磁盘存取次数更多内存降低磁盘存取次数n可用内

9、存数与可用内存数与 OS 其它进程相关其它进程相关, 难以事先确定难以事先确定 n普通运用最坏估计普通运用最坏估计, 假设可用内存最小时的情况。假设可用内存最小时的情况。n是实践模型的简化是实践模型的简化n忽略了顺序和随机读写的区别忽略了顺序和随机读写的区别n忽略了忽略了CPU的代价的代价 n忽略了写到磁盘的代价。忽略了写到磁盘的代价。n为什么要查询优化？为什么要查询优化？n 例例: Student: Student表有表有l000l000个学生记录，每人平个学生记录，每人平均选均选1010门课程，门课程，n SC SC表共有表共有10001000* *10=l000010=l0000个选课记

10、录。个选课记录。统计信息。要求统计信息。要求: :n 查学生查学生“王林所选课程的成果在王林所选课程的成果在8585分以分以上的课程号。上的课程号。n SELECT Cno SELECT Cnon FROM S FROM S，SCSCn WHERE S.Sno=SC.Sno AND Sname= WHERE S.Sno=SC.Sno AND Sname=王林王林 AND Grade 85 AND Grade 85 ； 等价的关系代数表示：等价的关系代数表示： Cno( F1 F2 F3 ( S Cno( F1 F2 F3 ( SSC ) ) SC ) ) Cno( F2 F3 ( S Cno(

11、 F2 F3 ( S SC ) ) SC ) ) Cno( F2 (S) Cno( F2 (S) F3 (SC) ) F3 (SC) ) 条件条件 F1 条件条件 F2 条件条件 F3分析：分析：哪种效率高？哪种效率高？ Cno( F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ) 先在两表上做先在两表上做 ，产生，产生1000*10000=107个衔接记录，个衔接记录，再在其上进展先再在其上进展先后后操作。其根本运算的次数为：操作。其根本运算的次数为：3*107。 先在两个表上做先在两个表上做 ，产生，产生1000*1

12、0=104个衔接记录，个衔接记录，再在其上进展先再在其上进展先后后操作。其根本运算的次数为：操作。其根本运算的次数为：107+2*104。 先分别在两个表上做先分别在两个表上做,再做再做 ，产生，产生1*10=10个衔接个衔接记录，再在其上进展记录，再在其上进展 。其根本运算的次数为：。其根本运算的次数为：104+103+*101。n衔接时间复杂度为：衔接时间复杂度为：n O(107) O(107)n O(104) O(104)n O(101) O(101)2.查询优化的普通战略查询优化的普通战略n启发式优化利用一套规那么来转换查询树启发式优化利用一套规那么来转换查询树, 这些规那么通常这些规

13、那么通常(但不是一切情况但不是一切情况)都能改善执行性能都能改善执行性能:n尽早执行选择尽早执行选择 (减少元组数目减少元组数目)n尽早执行投影尽早执行投影 (减少属性数目减少属性数目)n在其他类似操作之前执行最具限制性的选择和衔接操作在其他类似操作之前执行最具限制性的选择和衔接操作.n某些系统只运用启发式某些系统只运用启发式, 其他的结合了启发式与部分基于代其他的结合了启发式与部分基于代价的优化价的优化.3. 关系代数表达式的转换关系代数表达式的转换假设在每个合法的数据库实例上假设在每个合法的数据库实例上, 两个关系代数表两个关系代数表达式都生成同样的元组集合达式都生成同样的元组集合, 那么

14、这两个关系代那么这两个关系代数表达式称为等价的数表达式称为等价的留意留意: 元组次序是无关的元组次序是无关的在在SQL中中, 输入和输出都是元组的多重集合输入和输出都是元组的多重集合假设在每个合法的数据库实例上假设在每个合法的数据库实例上, 两个关系代数表两个关系代数表达式都生成同样的元组多重集合达式都生成同样的元组多重集合, 那么这两个表那么这两个表达式在关系代数的多重集合版本下称为等价的达式在关系代数的多重集合版本下称为等价的等价规那么阐明了两种方式的表达式是等价的等价规那么阐明了两种方式的表达式是等价的可以用一个表达式交换另一个可以用一个表达式交换另一个12条等价规那么条等价规那么n合取

15、选择操作可以分解成个体选择的序列合取选择操作可以分解成个体选择的序列.n选择操作是可交换的选择操作是可交换的.n一个投影操作序列中只需最后一个是必要的一个投影操作序列中只需最后一个是必要的, 其他其他皆可省略皆可省略.n选择可与笛卡儿积及选择可与笛卡儿积及 衔接结合衔接结合.n(E1 X E2) = E1 E2 n1(E1 2 E2) = E1 1 2 E2 )()(1221EE)()(2121EE)()(121EEttntt5. 衔接操作 (及自然衔接) 可交换.E1 E2 = E2 E16.(a) 自然衔接操作是可结合的: (E1 E2) E3 = E1 (E2 E3)(b) 衔接按如下方

16、式是可结合的: (E1 1 E2) 2 3 E3 = E1 2 3 (E2 2 E3) 其中2 仅涉及来自E2 和E3的属性.7.在下面两个条件下, 选择操作对 衔接操作有分配律:(a) 当0中的一切属性仅涉及被衔接表达式之一(E1)的属性时. 0E1 E2) = (0(E1) E2 (b) 当1 仅涉及E1的属性且2仅涉及E2的属性时. 1 E1 E2) = (1(E1) ( (E2)8.投影操作对 衔接操作的分配律如下:(a) 假设 仅涉及来自L1 L2的属性:(b) 思索衔接 E1 E2. 假设 L1 和 L2 分别是来自E1和E2的属性集合. 令 L3 是衔接条件中涉及的E1的属性,

17、但不在L1 L2中, 并且令 L4是衔接条件中涉及的E2的属性,但不在L1 L2中.)()()(2.12.12121EEEELLLL)()().(2.12142312121EEEELLLLLLLLn 集合运算并和交都是可交换的 E1 E2 = E2 E1 E1 E2 = E2 E1 n (集合差不是可交换的).n 集合并和交都是可结合的.n (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3)n 选择操作对, 和可分配. (E1 E2) = (E1) (E2) 类似地可用和 交换同样: (E1 E2) = (E1) E2 类似地可用 交换 , 但不能用

18、 n 12. 投影操作对并可分配n L(E1 E2) = (L(E1) (L(E2) n衔接次序例衔接次序例n 对一切关系对一切关系 r1, r2, 及及r3,n(r1 r2) r3 = r1 (r2 r3 )n 假设假设r2 r3 很大且很大且r1 r2 较小较小, 我们选择我们选择n (r1 r2) r3 n从而我们计算并存储一个较小的暂时关系从而我们计算并存储一个较小的暂时关系.n算法：关系表达式的优化。算法：关系表达式的优化。n 输入：一个关系表达式的语法树。输入：一个关系表达式的语法树。n 输出：计算该表达式的程序。输出：计算该表达式的程序。 1用规那么用规那么4把形如把形如: F1

19、F2. (E) 变为变为: F1(F2.(E) 再利用规那么再利用规那么58 把每一个选择运算尽能够移到树的叶端。把每一个选择运算尽能够移到树的叶端。 2对每一个投影利用规那么对每一个投影利用规那么3、5、9、l0，尽能够把它移向，尽能够把它移向树的叶端。树的叶端。 3利用规那么利用规那么35把选择和投影的串接合并成单个选择、单把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，行，或在一次扫描中全部完成， 4运用规那么运用规那么12 使选择运算与笛卡尔积结合成衔接运算。使选

20、择运算与笛卡尔积结合成衔接运算。 5对语法树中的内节点进展分组。对语法树中的内节点进展分组。 6找出查询树中的公共子树。找出查询树中的公共子树。 7输出由分组结果得到的优化语法树。输出由分组结果得到的优化语法树。例例P278SRA F五种根本五种根本运算表示运算表示n生成、选择查询方案。生成、选择查询方案。用到查询优化用到查询优化的普通战略的普通战略一、关系一、关系DBMSDBMS的开展阶段的开展阶段第一阶段是关系数据库实际研讨和原型开发的时代第一阶段是关系数据库实际研讨和原型开发的时代: :奠定了关系模型的实际根底。奠定了关系模型的实际根底。研讨了关系数据言语。研讨了关系数据言语。研制了大量

21、关系研制了大量关系DBMSDBMS的原型。的原型。第二阶段是关系第二阶段是关系DBMSDBMS的适用阶段的适用阶段: : 攻克了查询优化，并发控制，完好性机制等一系列艰苦攻克了查询优化，并发控制，完好性机制等一系列艰苦技术问题。从而使得数据库走向商业化。技术问题。从而使得数据库走向商业化。 第三阶段是关系第三阶段是关系DBMSDBMS的成熟与开展阶段的成熟与开展阶段: : 运用领域由集中到分布，由单机到网络，由信息管理，运用领域由集中到分布，由单机到网络，由信息管理，辅助决策到企业级的联机事务处置。辅助决策到企业级的联机事务处置。第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段对关系对关系模型的模型的支持支持表构造表构造支持支持支持支持支持支持关系操作关系操作不完善不完善支持支持支持支持完好性完好性无无不完善不完善支持支持运转运转环境环境单单机机单用户单用户有有 有有 有