6.2 关系关系DBS的查询优化的查询优化 第六章第六章 数据库管理系统数据库管理系统6.1 DBMS简介简介 6.3 关系关系DBMS的发展的发展6.1 DBMS简介简介1. DBMS位置位置 DBMSDBMS是是DBSDBS的核心软件，的核心软件，介于用户和介于用户和OSOS之间的系之间的系统软件，它实现对共享统软件，它实现对共享数据的有效组织、管理数据的有效组织、管理和各种操作和各种操作。用户应用程序用户应用程序DBMSDBMSOSOSDBDB DBMSDBMS建立在建立在OSOS之上，之上， 需要需要OSOS的支持。的支持。 DBMSDBMS是用户操纵、管理是用户操纵、管理 DBDB的工具。的工具。n 说明说明: :独立独立DBMSDBMS、OSOS扩充扩充6.1 DBMS简介简介nDBMS的特点的特点1. 1. 完备完备高效高效2. 2. 界面友好界面友好3. 3. 事务处理事务处理4. 4. 结构清晰结构清晰5. 5. 规范规范开放开放nDBMS的功能的功能 (1) 数据定义数据定义 (用用DDL) (2) 数据操纵数据操纵 (用用DML) (3) 数据组织、存储和管理数据组织、存储和管理 (4) 数据库运行管理数据库运行管理 (5) 数据库的建立和维护数据库的建立和维护 (6) 数据通信接口数据通信接口 6.1 DBMS简介简介2.DBMS2.DBMS的的组成组成 (1) (1) 数据定义语言及其翻译处理程序数据定义语言及其翻译处理程序 (2) (2) 数据操纵语言及其编译（或解释）程序数据操纵语言及其编译（或解释）程序 (3) (3) 数据库运行控制程序数据库运行控制程序 (4) (4) 实用程序实用程序 3.DBMS3.DBMS运行环境运行环境 (1)(1)分布分布: : 数据分布、功能分布、处理分布。数据分布、功能分布、处理分布。 (2)(2)开放：开放：开放的硬件平台、支撑软件、网络支持、开放的硬件平台、支撑软件、网络支持、 异质数据库互连、用户界面。异质数据库互连、用户界面。 系统缓冲区系统缓冲区概念模式概念模式内模式内模式DBMS OS 外外部部记记录录存存储储记记录录数据库数据库 应用程序应用程序A 外模式外模式日志日志应用程序应用程序A状态状态工作区工作区 6.1 DBMS6.1 DBMS简介简介简介简介4.4.用户访问数据库的工作过程用户访问数据库的工作过程 应用程序应用程序A A向向DBMSDBMS发出读一个记录的命令。程序给出记发出读一个记录的命令。程序给出记录类型名及欲读记录的码值。录类型名及欲读记录的码值。 DBMSDBMS分析命令，并调用分析命令，并调用A A对应的子模式，检查对应的子模式，检查A A的存取的存取权限，决定是否执行权限，决定是否执行A A的命令。的命令。 决定执行决定执行A A的命令后，的命令后，DBMSDBMS调用模式，根据子模式与模调用模式，根据子模式与模式变换的定义，确定所涉及的模式记录类型；通过模式式变换的定义，确定所涉及的模式记录类型；通过模式与内模式的变换找到这些记录类型的内模式名。与内模式的变换找到这些记录类型的内模式名。 DBMSDBMS调用内模式，确定所读入的物理记录。调用内模式，确定所读入的物理记录。 DBMSDBMS向向OSOS发读该物理记录的命令发读该物理记录的命令6.1 DBMS简介简介 OSOS执行读命令并把数据从外存读到内存的系统缓冲区。执行读命令并把数据从外存读到内存的系统缓冲区。 DBMSDBMS按模式、子模式定义，导出用户程序需要的记录按模式、子模式定义，导出用户程序需要的记录形式，并送到应用程序形式，并送到应用程序A A的工作区。的工作区。 DBMSDBMS向应用程序向应用程序A A送命令执行情况的状态信息。送命令执行情况的状态信息。 记载日志记载日志 DBMSDBMS把对数据库更新操作的全部情况都记载下来，以把对数据库更新操作的全部情况都记载下来，以便数据库的恢复。便数据库的恢复。 应用程序检查状态信息，若成功，对工作区中的数据应用程序检查状态信息，若成功，对工作区中的数据正常处理；若失败，决定下一步如何执行。正常处理；若失败，决定下一步如何执行。6.1 DBMS6.1 DBMS简介简介简介简介6.2 关系关系DBS的查询优化的查询优化n数据查询是DBS中最基本、最常用和最复杂的数据操作，查询优化是影响关系DBMS性能的关键因素。n关系数据理论基于关系代数，同一个查询要求可以对应多个不同形式却相互等价的表达式。n关系数据查询语言是非过程化的，由DBMS自动生成若干候选的查询计划并择优使用。查询语句查询语句查询输出查询输出关系代数表达式关系代数表达式执行计划执行计划语法分析与语法分析与翻译翻译执行引擎执行引擎优化器优化器数据数据有关数据的统计有关数据的统计信息信息1.查询处理的过程查询处理的过程6 6.2 .2 关系关系关系关系DBSDBS的查询优化的查询优化的查询优化的查询优化6.2 关系关系DBS的查询优化的查询优化n查询处理包括三个基本步骤： 解析和翻译 优化 实现（求值）n解析和翻译解析和翻译n解析：检查语法、验证关系n翻译：将查询转化为内部形式，并进一步翻译为关系代数.n实现实现n执行引擎选取一个查询计划并执行，而后将结果返回给查询.6.3 关系关系DBS的查询处理的查询处理n查询优化查询优化: 在所有等价的执行计划中选取代价最低的那在所有等价的执行计划中选取代价最低的那个。个。 n代价代价是利用从系统目录中获取的统计信息估算得到的。是利用从系统目录中获取的统计信息估算得到的。ne.g. 关系关系中的元组数目中的元组数目, 元组的大小等元组的大小等.n需要研究：需要研究：n如何估量查询的代价如何估量查询的代价n实现关系代数操作的算法实现关系代数操作的算法n将单个操作算法结合起来形成一个对表达式的完整求值将单个操作算法结合起来形成一个对表达式的完整求值n如何实现查询优化如何实现查询优化，即如何寻求一个具有最低代价的执行计即如何寻求一个具有最低代价的执行计划。划。6.3 关系关系DBS的查询处理代价度量的查询处理代价度量n代价通常是利用回答查询所需的时间来度量的。代价通常是利用回答查询所需的时间来度量的。n很多因素会影响查询时间：很多因素会影响查询时间：磁盘存取磁盘存取, CPU, 网络连接等网络连接等n通常磁盘存取是最耗时的部分通常磁盘存取是最耗时的部分, 并且容易估算并且容易估算, 主要考主要考虑虑. nNumber of seeks * average-seek-costnNumber of blocks read * average-block-read-costnNumber of blocks written * average-block-write-costn写的代价大于读的代价：写以后需要回读以确保正确的写写的代价大于读的代价：写以后需要回读以确保正确的写6.3 关系关系DBS的查询处理代价度量的查询处理代价度量n简化起见，仅使用简化起见，仅使用 number of block 从磁盘传送块的从磁盘传送块的数目作为代价的度量。数目作为代价的度量。n代价依赖于内存缓冲区的大小代价依赖于内存缓冲区的大小n更多内存降低磁盘存取次数更多内存降低磁盘存取次数n可用内存数与可用内存数与 OS 其它进程相关其它进程相关, 难以事先确定难以事先确定 n一般使用最坏估计一般使用最坏估计, 假设可用内存最小时的情况。假设可用内存最小时的情况。n是实际模型的简化是实际模型的简化n忽略了顺序和随机读写的区别忽略了顺序和随机读写的区别n忽略了忽略了CPU的代价的代价 n忽略了写到磁盘的代价。忽略了写到磁盘的代价。 n为什么要查询优化？为什么要查询优化？ 例例: StudentStudent表有表有l000l000个学生记录，每人平均选个学生记录，每人平均选1010门课程，门课程， SCSC表共有表共有1000*10=l00001000*10=l0000个选课记录。个选课记录。（统计信息）。（统计信息）。要求要求: : 查学生查学生“王林王林”所选课程的成绩在所选课程的成绩在85分以上的课程号分以上的课程号。 SELECT Cno FROM S，SC WHERE S.Sno=SC.Sno AND Sname=王林王林 AND Grade 85 ；等价的关系代数表示：等价的关系代数表示： Cno(Cno( F1 F2 F3 F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ) 条件条件 F1 条件条件 F2 条件条件 F3分析：分析：哪种效率高？哪种效率高？6 6.2 .2 关系关系关系关系DBSDBS的查询优化的查询优化的查询优化的查询优化6.2 关系关系DBS的查询优化的查询优化 Cno( F1 F2 F3 ( SSC ) ) Cno( F2 F3 ( S SC ) ) Cno( F2 (S) F3 (SC) ) v先在两表上做先在两表上做 ，产生，产生1000*10000=101000*10000=107 7个连接记录，再在其上个连接记录，再在其上进行先进行先后后操作。其基本运算的次数为：操作。其基本运算的次数为：3*103*107 7。v先在两个表上做先在两个表上做 ，产生产生1000*10=101000*10=104 4个连接记录，再在其上进个连接记录，再在其上进行先行先后后操作。其基本运算的次数为：操作。其基本运算的次数为：10107 7+2*10+2*104 4。v先分别在两个表上做先分别在两个表上做,再再做做 ，产生产生1*10=1*10=1010个连接记录，个连接记录，再在其上进行再在其上进行 。其基本运算的次数为：。其基本运算的次数为：10104 4+10+103 3+*10+*101 1。n连接时间复杂度为：连接时间复杂度为： O(10(107 7) ) O(10(104 4) ) O(10(101 1) ) 2.查询优化的一般策略查询优化的一般策略6 6.2 .2 关系关系关系关系DBSDBS的查询优化的查询优化的查询优化的查询优化n启发式优化利用一套规则来转换查询树启发式优化利用一套规则来转换查询树, 这些规则通常这些规则通常(但但不是所有情况不是所有情况)都能改善执行性能都能改善执行性能:尽早执行选择尽早执行选择 (减少元组数目减少元组数目)尽早执行投影尽早执行投影 (减少属性数目减少属性数目)在其他类似操作之前执行最具限制性的选择和连接操作在其他类似操作之前执行最具限制性的选择和连接操作.某些系统只使用启发式某些系统只使用启发式, 其他的结合了启发式与部分基其他的结合了启发式与部分基于代价的优化于代价的优化.6.2 关系关系DBS的查询优化的查询优化3. 关系代数表达式的转换关系代数表达式的转换n如果在每个合法的数据库实例上如果在每个合法的数据库实例上, 两个关系代数表达式都生成同两个关系代数表达式都生成同样的元组集合样的元组集合, 则这两个关系代数表达式称为则这两个关系代数表达式称为等价的等价的n注意注意: 元组次序是无关的元组次序是无关的n在在SQL中中, 输入和输出都是元组的多重集合输入和输出都是元组的多重集合n如果在每个合法的数据库实例上如果在每个合法的数据库实例上, 两个关系代数表达式都生成两个关系代数表达式都生成同样的元组多重集合同样的元组多重集合, 则这两个表达式在关系代数的多重集合则这两个表达式在关系代数的多重集合版本下称为等价的版本下称为等价的n等价规则等价规则说明了两种形式的表达式是等价的说明了两种形式的表达式是等价的n可以用一个表达式替换另一个可以用一个表达式替换另一个n12条等价规则条等价规则6.2 关系关系DBS的查询优化的查询优化1.合取选择操作可以分解成个体选择的序列合取选择操作可以分解成个体选择的序列.2.选择操作是可交换的选择操作是可交换的.3.一个投影操作序列中只有最后一个是必要的一个投影操作序列中只有最后一个是必要的, 其余其余皆可省略皆可省略.4.选择可与笛卡儿积及选择可与笛卡儿积及 连接结合连接结合.a. (E1 X E2) = E1 E2 b. 1(E1 2 E2) = E1 1 2 E2 6.2 关系关系DBS的查询优化的查询优化5. 连接操作 (及自然连接) 可交换.E1 E2 = E2 E16.(a) 自然连接操作是可结合的: (E1 E2) E3 = E1 (E2 E3)(b) 连接按如下方式是可结合的: (E1 1 E2) 2 3 E3 = E1 2 3 (E2 2 E3) 其中2 仅涉及来自E2 和E3的属性.6.2 关系关系DBS的查询优化的查询优化7.在下面两个条件下, 选择操作对 连接操作有分配律:(a) 当0中的所有属性仅涉及被连接表达式之一(E1)的属性时. 0E1 E2) = (0(E1) E2 (b) 当1 仅涉及E1的属性且2仅涉及E2的属性时. 1 E1 E2) = (1(E1) ( (E2)6.2 关系关系DBS的查询优化的查询优化8.投影操作对 连接操作的分配律如下:(a) 若 仅涉及来自L1 L2的属性:(b) 考虑连接 E1 E2. n若 L1 和 L2 分别是来自E1和E2的属性集合. n令 L3 是连接条件中涉及的E1的属性, 但不在L1 L2中, 并且n令 L4是连接条件中涉及的E2的属性,但不在L1 L2中.6.2 关系关系DBS的查询优化的查询优化9.集合运算并和交都是可交换的 E1 E2 = E2 E1 E1 E2 = E2 E1 n(集合差不是可交换的).10. 集合并和交都是可结合的. (E1 E2) E3 = E1 (E2 E3) (E1 E2) E3 = E1 (E2 E3)11. 选择操作对, 和可分配. (E1 E2) = (E1) (E2) 类似地可用和 替换同样: (E1 E2) = (E1) E2 类似地可用 替换 , 但不能用 12. 投影操作对并可分配 L(E1 E2) = (L(E1) (L(E2) n连接次序例连接次序例 对所有关系 r1, r2, 及r3,(r1 r2) r3 = r1 (r2 r3 ) 若r2 r3 很大且r1 r2 较小, 我们选择 (r1 r2) r3 从而我们计算并存储一个较小的临时关系.6.2 关系关系DBS的查询优化的查询优化4. 4. 关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法关系代数表达式的优化算法n算法：关系表达式的优化。算法：关系表达式的优化。 输入：一个关系表达式的语法树。输入：一个关系表达式的语法树。 输出：计算该表达式的程序。输出：计算该表达式的程序。（1）用规则）用规则4把形如把形如: F1F2. (E) 变为变为: F1(F2.(E) 再利用规则再利用规则5 58 8 把每一个选择运算尽可能移到树的叶端。把每一个选择运算尽可能移到树的叶端。 （2 2）对每一个投影利用规则）对每一个投影利用规则3 3、5 5、9 9、l0l0，尽可能把它移向树的尽可能把它移向树的叶端。叶端。（3 3）利用规则）利用规则3 35 5把选择和投影的串接合并成单个选择、单个把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成，或在一次扫描中全部完成，（4 4）使用规则）使用规则12 12 使选择运算与笛卡尔积结合成连接运算。使选择运算与笛卡尔积结合成连接运算。 （5 5）对语法树中的内节点进行分组。）对语法树中的内节点进行分组。（6 6）找出查询树中的公共子树。）找出查询树中的公共子树。（7 7）输出由分组结果得到的优化语法树。）输出由分组结果得到的优化语法树。例例P278SRA F五种基本五种基本运算表示运算表示6.4 关系关系DBS的查询优化的查询优化n生成、选择查询计划。生成、选择查询计划。用到用到查询优化查询优化的的一般策略一般策略n n5.5.查询优化的一般步骤：查询优化的一般步骤：查询优化的一般步骤：查询优化的一般步骤：n将查询表示成关系代数语法树。将查询表示成关系代数语法树。n根据变换规则将其转换成标准优化形式。根据变换规则将其转换成标准优化形式。n选择低层的操作算法。选择低层的操作算法。 对语法树中的每一操作需要根据存取路径、数据的分布、对语法树中的每一操作需要根据存取路径、数据的分布、聚簇等信息来选择具体的执行算法。聚簇等信息来选择具体的执行算法。6.3 6.3 关系关系关系关系DBMSDBMS的发展的发展的发展的发展一、关系一、关系DBMSDBMS的发展阶段的发展阶段n第一阶段第一阶段是关系数据库理论研究和原型开发的时代是关系数据库理论研究和原型开发的时代: :奠定了关系模型的理论基础。奠定了关系模型的理论基础。研究了关系数据语言。研究了关系数据语言。研制了大量关系研制了大量关系DBMSDBMS的原型。的原型。n第二阶段第二阶段是关系是关系DBMSDBMS的实用阶段的实用阶段: : 攻克了查询优化，并发控制，完整性机制等一系列重大攻克了查询优化，并发控制，完整性机制等一系列重大技术问题。从而使得数据库走向商业化。技术问题。从而使得数据库走向商业化。 n第三阶段第三阶段是关系是关系DBMSDBMS的成熟与发展阶段的成熟与发展阶段: : 应用领域由集中到分布，由单机到网络，由信息管理，应用领域由集中到分布，由单机到网络，由信息管理，辅助决策到企业级的联机事务处理。辅助决策到企业级的联机事务处理。表表表表6.1 6.1 6.1 6.1 关系关系关系关系DBMSDBMSDBMSDBMS的发展阶段及相关技术支持的发展阶段及相关技术支持的发展阶段及相关技术支持的发展阶段及相关技术支持 第一阶段第一阶段第二阶段第二阶段第三阶段第三阶段对关系对关系模型的模型的支持支持表结构表结构支持支持支持支持支持支持关系操作关系操作不完善不完善支持支持支持支持完整性完整性无无不完善不完善支持支持运行运行环境环境单单机机单用户单用户有有 有有 有有多用户多用户无无有有有有网网络络单机联网单机联网无无有有有有分布分布DBDB无无有有有有C/S C/S 环境环境无无无无有有开放开放网络异质网络异质DBDB无无无无有有系统系统构成构成RDBMSRDBMS核心核心有有有有有有扩充部分扩充部分OSOS功能功能 无无 无无有有集成、扩充工具集成、扩充工具无无有有有有对对应应用用的支持的支持信息管理与决策信息管理与决策不完善不完善支持支持支持支持联机事务处理联机事务处理(OLTP)(OLTP)无无支持支持支持支持整个行业的整个行业的OLTPOLTP无无不完善不完善支持支持6.3 6.3 关系关系关系关系DBMSDBMS的发展的发展的发展的发展二、关系二、关系DBMSDBMS的发展趋势的发展趋势产品系列化产品系列化支持高速互联网应用支持高速互联网应用智能化集成化智能化集成化三、关系三、关系DBMSDBMS产品的选择产品的选择n应用对关系应用对关系DBMS的要求的要求具有高可伸缩性及高可用性具有高可伸缩性及高可用性高可靠性和高安全性高可靠性和高安全性高速互联互访高速互联互访高效协同服务高效协同服务高度平台开放高度平台开放6.3 6.3 关系关系关系关系DBMSDBMS的发展的发展的发展的发展n关系关系DBMS产品选择的因素产品选择的因素数据库应用的规模、类型和用户的数量数据库应用的规模、类型和用户的数量速度指标速度指标软件、硬件平台性能与价格比软件、硬件平台性能与价格比开发者的经验和习惯开发者的经验和习惯安全性安全性第六章第六章 数据库管理系统数据库管理系统小结：小结：1. DBMS的定义、特点及功能的定义、特点及功能2. 关系关系DBS的的查询优化查询优化目标、一般策略目标、一般策略关系代数等价变换规则及优化算法关系代数等价变换规则及优化算法优化的步骤优化的步骤练习：练习：P290第第4、6题题