《数据库课件关系系统及其查询优化.ppt》由会员分享，可在线阅读，更多相关《数据库课件关系系统及其查询优化.ppt（19页珍藏版）》请在金锄头文库上搜索。
1、4.1 4.1 关系系统关系系统关系系统的定义关系系统的定义关系系统的分类关系系统的分类全关系系统全关系系统12条准则条准则4.2 4.2 关系系统的查询优化关系系统的查询优化查询优化概述查询优化概述查询优化的一般准则查询优化的一般准则关系代数等价变换规则关系代数等价变换规则关系代数表达式的优化算法关系代数表达式的优化算法优化的一般步骤优化的一般步骤第第4章章关系系统及其查询优化关系系统及其查询优化第4章4.1 关关系系系系统统关系系统定义关系系统定义支持关系模型的关系数据库管理系统简称关系系统。支持关系模型的关系数据库管理系统简称关系系统。1下述关系的下述关系的DBMS不能称为关系系统不能称
2、为关系系统1）不支持关系数据结构的系统）不支持关系数据结构的系统2）支持关系数据结构，但无）支持关系数据结构，但无、运算功能的系统运算功能的系统3）支持关系数据结构，有）支持关系数据结构，有、运算，但要求定义物理存运算，但要求定义物理存取路径的系统取路径的系统可称为关系系统的可称为关系系统的DBMSDBMS，当且仅当当且仅当1）支持关系数据结构（关系数据库）支持关系数据结构（关系数据库）2）支持）支持、运算，且不要求用户定义任何物理存取路径运算，且不要求用户定义任何物理存取路径4.1 关关系系系系统统关系系统分类关系系统分类4全关系系统：全关系系统：支持关系模型的所有特征。在关系完备系统的基础
3、上，进一步支支持关系模型的所有特征。在关系完备系统的基础上，进一步支持实体完整性和参照完整性等。持实体完整性和参照完整性等。DB,ORACLE,SYBASE,DB,ORACLE,SYBASE,已接近这个目标。目前尚无全关系系统。已接近这个目标。目前尚无全关系系统。1表式系统：表式系统：仅支持关系数据结构，不支持关系操作。仅支持关系数据结构，不支持关系操作。2（最小）关系系统：（最小）关系系统：支持关系数据结构，支持支持关系数据结构，支持、运算，且不定义物理路径。运算，且不定义物理路径。3关系完备系统：关系完备系统：支持关系数据结构和所有关系代数操作（或功能上与关系代数等价）。支持关系数据结构和
4、所有关系代数操作（或功能上与关系代数等价）。DB,ORACLE,SYBASE,DB,ORACLE,SYBASE,属于这一类属于这一类4.1 关关系系系系统统关系系统分类关系系统分类数据结构数据结构数据操作数据操作完整性约束完整性约束表式系统表式系统表表(最小最小)关系系统关系系统表表选择、投影、选择、投影、连接连接关系完备的系统关系完备的系统表表全关系系统全关系系统4.1关关系系系系统统全关系系统全关系系统12条准则条准则0.一个关系型的一个关系型的DBMS必须能完全通过它的关系能力来管理数据库必须能完全通过它的关系能力来管理数据库准则准则1：信息准则。信息准则。关系型关系型DBMS的所有信息
5、都应在逻辑一级上用一种的所有信息都应在逻辑一级上用一种方法即表中的值显式地表示方法即表中的值显式地表示准则准则2：保证访问准则。保证访问准则。依表名、主码、列名的组合，保证能以逻辑方依表名、主码、列名的组合，保证能以逻辑方式访问关系数据库中的每个数据项。（独立于物理结构）式访问关系数据库中的每个数据项。（独立于物理结构）准则准则3：空值的系统化处理。空值的系统化处理。支持支持NULL的概念的概念准则准则4：基于关系模型的动态的联机数据字典。基于关系模型的动态的联机数据字典。（以关系的形式存储元（以关系的形式存储元数据）数据）准则准则5：统一的数据子语言准则。统一的数据子语言准则。一体化的统一的
6、数据子语言一体化的统一的数据子语言4.1 关关系系系系统统全关系系统全关系系统12条准则条准则1.准则准则6：视图准则。视图准则。所有理论上可更新的视图也应该允许由系统更新。所有理论上可更新的视图也应该允许由系统更新。2.准则准则7：高级的插入、修改、删除操作。高级的插入、修改、删除操作。以关系为对象进行操作以关系为对象进行操作3.准则准则8：数据物理独立性数据物理独立性4.准则准则9：数据逻辑独立性数据逻辑独立性5.准则准则10：数据完整性的独立性。数据完整性的独立性。用用DDL定义并存储在数据字典中，独立定义并存储在数据字典中，独立于应用程序于应用程序6.准则准则11：分布独立性分布独立性
7、7.准则准则12：无破坏准则无破坏准则4.2 关系系统的查询优化关系系统的查询优化查查询询优优化化概概述述 查询处理的过程查询处理的过程查询处理的过程查询处理的过程查询语句查询语句查询输出查询输出关系代数表达式关系代数表达式执行计划执行计划语法分析与语法分析与翻译翻译执行引擎执行引擎优化器优化器数据数据有关数据的统计有关数据的统计信息信息4.2 关系系统的查询优化关系系统的查询优化查查询询优优化化概概述述 实际系统的查询优化步骤实际系统的查询优化步骤实际系统的查询优化步骤实际系统的查询优化步骤1.将查询转换成某种内部表示，通常是语法树将查询转换成某种内部表示，通常是语法树2.根据一定的等价变换
8、规则把语法树转换成标准（优化）形式根据一定的等价变换规则把语法树转换成标准（优化）形式3.选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作对于语法树中的每一个操作根据存取路径、数据的尺寸、数据的存储分布、存储数据根据存取路径、数据的尺寸、数据的存储分布、存储数据的聚簇等信息来计算各种执行算法的执行代价的聚簇等信息来计算各种执行算法的执行代价选择代价小的执行算法选择代价小的执行算法4.生成查询计划生成查询计划(查询执行方案查询执行方案)4.2 关系系统的查询优化关系系统的查询优化查查询询优优化化概概述述 常用查询优化技术常用查询优化技术常用查询优化技术常用查询优化技术 用启发式规则来
9、缩减查询计划的搜索空间用启发式规则来缩减查询计划的搜索空间用启发式规则来缩减查询计划的搜索空间用启发式规则来缩减查询计划的搜索空间 利用统计信息估算执行代价利用统计信息估算执行代价利用统计信息估算执行代价利用统计信息估算执行代价 基于代价基于代价基于代价基于代价 代价模型代价模型集中式数据库集中式数据库单用户系统：总代价单用户系统：总代价=I/O代价代价+CPU代价代价多用户系统：总代价多用户系统：总代价=I/O代价代价+CPU代价代价+内存代价内存代价分布式数据库分布式数据库总代价总代价=I/O代价代价+CPU代价代价+内存代价内存代价+通信代价通信代价4.2 关系系统的查询优化关系系统的查
10、询优化查查询询优优化化概概述述 一个实例一个实例一个实例一个实例: :求选求选C2课程的学生名课程的学生名SELECTSNAMEFROM Student，SCWHEREStudent.Sno=SC.SnoANDCno=C2；外存：外存：Student:1000条条,SC:10000条条,选修选修2号课程号课程:50条条一个内存块装元组一个内存块装元组:10个个Student,或或100个个SC,内存中一次可以存放内存中一次可以存放:5块块Student元组元组,1块块SC元组和若干块连接结果元组元组和若干块连接结果元组读写速度：读写速度：20块块/秒秒连接方法：基于数据块的嵌套循环法连接方法：
11、基于数据块的嵌套循环法假设假设4.2 关系系统的查询优化关系系统的查询优化查查询询优优化化概概述述 一个实例一个实例一个实例一个实例1.1Sname(Student.Sno=SC.SnoSC.Cno=c2(StudentSC)StudentSC读取总块数读取总块数=读读Student表块数表块数+读读SC表遍数表遍数*每遍块数每遍块数=1000/10+(1000/(105)(10000/100)=2100读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=1000*10000=107(1千万条元组千万条元组)写中间结果时间写中间结果时间=10000000/10/20=50
12、000秒秒读数据时间读数据时间=50000秒秒总时间总时间=1055000050000秒秒=100105秒秒=27.8小时小时4.2 关系系统的查询优化关系系统的查询优化查查询询优优化化概概述述2.2name(SC.Cno=2(StudentSC)读取总块数读取总块数=2100块块读数据时间读数据时间=2100/20=105秒秒中间结果大小中间结果大小=10000（减少（减少1000倍）倍）写中间结果时间写中间结果时间=10000/10/20=50秒秒读数据时间读数据时间=50秒秒总时间总时间1055050秒秒205秒秒=3.4分分 一个实例一个实例一个实例一个实例4.2 关系系统的查询优化关
13、系系统的查询优化查查询询优优化化概概述述3.2Sname(StudentSC.Cno=2(SC)读读SC表总块数表总块数=10000/100=100块块读数据时间读数据时间=100/20=5秒秒中间结果大小中间结果大小=50条条不必写入外存不必写入外存读读Student表总块数表总块数=1000/10=100块块读数据时间读数据时间=100/20=5秒秒总时间总时间55秒秒10秒秒 一个实例一个实例一个实例一个实例4.2 关系系统的查询优化关系系统的查询优化查询优化的一般准则查询优化的一般准则1. 1.选择运算应尽可能先做选择运算应尽可能先做选择运算应尽可能先做选择运算应尽可能先做2. 2.在
14、执行连接操作前对关系适当进行预处理在执行连接操作前对关系适当进行预处理在执行连接操作前对关系适当进行预处理在执行连接操作前对关系适当进行预处理3. 3.投影运算和选择运算同时做投影运算和选择运算同时做投影运算和选择运算同时做投影运算和选择运算同时做4. 4.将投影运算与其前后的双目运算结合将投影运算与其前后的双目运算结合将投影运算与其前后的双目运算结合将投影运算与其前后的双目运算结合5. 5.选择运算和笛卡尔积运算选择运算和笛卡尔积运算选择运算和笛卡尔积运算选择运算和笛卡尔积运算 结合结合结合结合6. 6.提取公共子表达式提取公共子表达式提取公共子表达式提取公共子表达式4.2 关系系统的查询优
15、化关系系统的查询优化关系代数等价变换规则关系代数等价变换规则l.连接、笛卡尔积交换律连接、笛卡尔积交换律2.连接、笛卡尔积的结合律连接、笛卡尔积的结合律3.投影的串接定律投影的串接定律4.选择的串接定律选择的串接定律5.选择与投影的交换律选择与投影的交换律6.选择与笛卡尔积的交换律选择与笛卡尔积的交换律7.选择与并的交换选择与并的交换8.选择与差运算的交换选择与差运算的交换9.投影与笛卡尔积的交换投影与笛卡尔积的交换l0.投影与并的交换投影与并的交换4.2 关系系统的查询优化关系系统的查询优化关系代数表达式的优化算法关系代数表达式的优化算法1.分解选择运算分解选择运算2.通过交换选择运算，将其
16、尽可能移到叶端通过交换选择运算，将其尽可能移到叶端3.通过交换投影运算，将其尽可能移到叶端通过交换投影运算，将其尽可能移到叶端4.合并串接的选择和投影，以便能同时执行或在一次扫描中完成合并串接的选择和投影，以便能同时执行或在一次扫描中完成5.对内结点分组对内结点分组6.生成程序生成程序4.2 关系系统的查询优化关系系统的查询优化优化的一般步骤优化的一般步骤1把查询转换成某种内部表示把查询转换成某种内部表示2代数优化：把语法树转换成标准（优化）形式代数优化：把语法树转换成标准（优化）形式3物理优化：选择低层的存取路径物理优化：选择低层的存取路径4生成查询计划，选择代价最小的生成查询计划，选择代价
17、最小的4.2 关系系统的查询优化关系系统的查询优化优化的一般步骤优化的一般步骤student.Sno=Sc.SnoSc.Sno=2XStudent SCSnamex student.Sno=Sc.SnoSc.Sno=2SnameSCStudentstudentSCJoin(student.Sno=SC.Sno)Select(SC.Cno=2)Project(Sname)小小小小结结结结4.1 4.1 关系系统关系系统关系系统的定义关系系统的定义关系系统的分类关系系统的分类全关系系统全关系系统12条准则条准则4.2 4.2 关系系统的查询优化关系系统的查询优化查询优化概述查询优化概述查询优化的一般准则查询优化的一般准则关系代数等价变换规则关系代数等价变换规则关系代数表达式的优化算法关系代数表达式的优化算法优化的一般步骤优化的一般步骤
