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