1、2022年11月24日0时32分数据库原理1关系系统及其查询优化关系系统及其查询优化 第第4章章n n 关系系统的定义关系系统的定义n 关系系统的分类关系系统的分类n n 关系系统及其查询优化关系系统及其查询优化n 查询优化的一般准则查询优化的一般准则n 关系代数等价变换规则关系代数等价变换规则n 关系代数表达式的优化算法关系代数表达式的优化算法n 优化的一般步骤优化的一般步骤 2022年11月24日0时32分数据库原理24.1 4.1 关系系统关系系统支持关系模型的关系数据库管理系统简称关系系统。支持关系模型的关系数据库管理系统简称关系系统。n 下述关系的下述关系的DBMSDBMS不能称为关
2、系系统不能称为关系系统n 不支持关系数据结构的系统不支持关系数据结构的系统n 支持关系数据结构，但无支持关系数据结构，但无、运算功能的系统运算功能的系统n 支持关系数据结构，有支持关系数据结构，有、运算，但要求定义物理运算，但要求定义物理 存取路径的系统存取路径的系统可称为关系系统的可称为关系系统的DBMSDBMS，当且仅当当且仅当1）支持关系数据结构（关系数据库）支持关系数据结构（关系数据库）2）支持）支持、运算，且不要求用户定义任何物理存取路径运算，且不要求用户定义任何物理存取路径4.1.1 4.1.1 关系系统的定义关系系统的定义2022年11月24日0时32分数据库原理34.1.2 4
3、.1.2 关系系统的分类关系系统的分类 支持关系模型的所有特征。在关系完备系统的基础上，进一步支支持关系模型的所有特征。在关系完备系统的基础上，进一步支持实体完整性和参照完整性等。持实体完整性和参照完整性等。DB,ORACLE,SYBASE,DB,ORACLE,SYBASE,已接近这个已接近这个目标。目前尚无全关系系统。目标。目前尚无全关系系统。仅支持关系数据结构，不支持集合级的操作。仅支持关系数据结构，不支持集合级的操作。支持关系数据结构，支持支持关系数据结构，支持、运算，且不定义物理路径。运算，且不定义物理路径。支持关系数据结构和所有关系代数操作（或功能上与关系代数等支持关系数据结构和所有
4、关系代数操作（或功能上与关系代数等价）。价）。DB,ORACLE,SYBASE,DB,ORACLE,SYBASE,属于这一类。属于这一类。2022年11月24日0时32分数据库原理4 关系系统分类关系系统分类数据结构数据结构数据操作数据操作完整性约束完整性约束表表表表选择、投选择、投影、连接影、连接表表2022年11月24日0时32分数据库原理54.2 4.2 关系数据库系统的查询优化关系数据库系统的查询优化4.2.1 4.2.1 关系系统及其查询优化关系系统及其查询优化l 查询处理的过程查询处理的过程查询语句查询语句查询输出查询输出关系代数表达式关系代数表达式执行计划执行计划语法分析与语法分
5、析与翻译翻译执行引擎执行引擎优化器优化器有关数据的有关数据的统计信息统计信息数据数据2022年11月24日0时32分数据库原理6n 优化器可以从数据字典中获取许多统计信息，从而选择优化器可以从数据字典中获取许多统计信息，从而选择有效的执行计划；有效的执行计划；n 如果数据库的物理统计信息改变了，系统可以自动对查如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划；询进行重新优化以选择相适应的执行计划；n 优化器可以考虑数百种不同的执行计划；优化器可以考虑数百种不同的执行计划；n 优化器中包括了很多复杂的优化技术。优化器中包括了很多复杂的优化技术。2022年11月
6、24日0时32分数据库原理71.1.将查询转换成某种内部表示，通常是语法树将查询转换成某种内部表示，通常是语法树2.2.根据一定的等价变换规则把语法树转换成标准（优化）形式根据一定的等价变换规则把语法树转换成标准（优化）形式3.3.选择低层的操作算法选择低层的操作算法n 对于语法树中的每一个操作对于语法树中的每一个操作n 根据存取路径、数据的尺寸、数据的存储分布、存储根据存取路径、数据的尺寸、数据的存储分布、存储数据的聚簇等信息来计算各种执行算法的执行代价数据的聚簇等信息来计算各种执行算法的执行代价n 选择代价小的执行算法选择代价小的执行算法4.4.生成查询计划生成查询计划(查询执行方案查询执
7、行方案)2022年11月24日0时32分数据库原理8n 常用查询优化技术常用查询优化技术n 用启发式规则来缩减查询计划的搜索空间用启发式规则来缩减查询计划的搜索空间n 利用统计信息估算执行代价利用统计信息估算执行代价n 基于代价（目前商品化基于代价（目前商品化RDBMSRDBMS大都采用）大都采用）n 代价模型代价模型n 集中式数据库集中式数据库n 单用户系统：总代价单用户系统：总代价 =I/O=I/O代价代价 +CPU+CPU代价代价n 多用户系统：总代价多用户系统：总代价 =I/O=I/O代价代价 +CPU+CPU代价代价 +内存代价内存代价n 分布式数据库分布式数据库 总代价总代价 =I
8、/O=I/O代价代价 +CPU+CPU代价代价 +内存代价内存代价+通信代价通信代价 2022年11月24日0时32分数据库原理94.2.2 4.2.2 一个实例一个实例SELECTSELECT Student.SnameStudent.Sname FROM FROM Student Student，SCSCWHEREWHERE Student.SnoStudent.Sno=SC.SnoSC.Sno ANDAND CnoCno=2=2；u 数据量：数据量：Student:1000Student:1000条；条；SC:10000SC:10000条；选修条；选修2 2号课程号课程:50:50条条u
9、 一个内存块装元组一个内存块装元组:10:10个个StudentStudent或或100100个个SCSC，内存中可以，内存中可以 存放存放:5:5块块StudentStudent元组和元组和1 1块块SCSC元组元组u 读写速度：读写速度：2020块块/秒秒2022年11月24日0时32分数据库原理101.1.1 1 SnameSname(Student.SnoStudent.Sno=SC.SnoSC.Sno SC.CnoSC.Cno=c2=c2(Student(StudentSC)SC)计算广义笛卡尔积计算广义笛卡尔积(StudentStudentSCSC)读取总块数读取总块数 =读读St
10、udentStudent表块数表块数 +读读SCSC表遍数表遍数 *每遍块数每遍块数 =1000/10+(1000/(10=1000/10+(1000/(105)5)(10000/100)=2100(10000/100)=2100 读数据时间读数据时间=2100/20=105=2100/20=105秒秒 中间结果大小中间结果大小 =1000=1000*10000=1010000=107 7 (1 (1千万条元组千万条元组)写中间结果时间写中间结果时间 =10000000/10/20=50000=10000000/10/20=50000秒秒 选择操作选择操作()读数据时间读数据时间 =50000
11、=50000秒秒 投影投影()总时间总时间 =105=10550000500005000050000秒秒 =100105=100105秒秒 =27.8=27.8小时小时2022年11月24日0时32分数据库原理112.2.2 2 namename(SC.CnoSC.Cno=2=2(Student SC)(Student SC)自然连接自然连接()()读取总块数读取总块数=2100=2100块块 读数据时间读数据时间=2100/20=105=2100/20=105秒秒 中间结果大小中间结果大小=10000=10000（即（即SCSC表中记录条数，减少表中记录条数，减少10001000倍）倍）写中
12、间结果时间写中间结果时间=10000/10/20=50=10000/10/20=50秒秒 选择操作选择操作()读数据时间读数据时间=50=50秒秒 投影投影()总时间总时间10510550505050秒秒205205秒秒=3.4=3.4分分 2022年11月24日0时32分数据库原理123.3.2 2 SnameSname(Student(Student SC.CnoSC.Cno=2=2(SC)(SC)选择操作选择操作()读读SCSC表总块数表总块数=10000/100=100=10000/100=100块块读数据时间读数据时间=100/20=5=100/20=5秒秒 中间结果大小中间结果大小
13、=50=50条条 （不必使用中间文件）（不必使用中间文件）自然连接（自然连接（）读读StudentStudent表总块数表总块数=1000/10=100=1000/10=100块块读数据时间读数据时间=100/20=5=100/20=5秒秒 投影投影()总时间总时间5 55 5秒秒1010秒秒 2022年11月24日0时32分数据库原理134.2.3 4.2.3 查询优化的一般准则查询优化的一般准则1.1.选择运算应尽可能先做选择运算应尽可能先做 2.2.在执行连接操作前对关系适当进行预处理在执行连接操作前对关系适当进行预处理 （索引连接方法和排序合并连接方法）（索引连接方法和排序合并连接方法
14、）3.3.投影运算和选择运算同时做投影运算和选择运算同时做4.4.将投影运算与其前后的双目运算结合（连接、并、差、交等）将投影运算与其前后的双目运算结合（连接、并、差、交等）5.5.选择运算和笛卡尔积运算结合（等值连接比笛卡儿积省时间）选择运算和笛卡尔积运算结合（等值连接比笛卡儿积省时间）6.6.提取公共子表达式（例如，定义视图的表达式）提取公共子表达式（例如，定义视图的表达式）2022年11月24日0时32分数据库原理144.2.4 4.2.4 关系代数等价变换规则关系代数等价变换规则l.l.连接、笛卡尔积交换律连接、笛卡尔积交换律2.2.连接、笛卡尔积的结合律连接、笛卡尔积的结合律3.3.
15、投影的串接定律投影的串接定律4.4.选择的串接定律选择的串接定律5.5.选择与投影的交换律选择与投影的交换律6.6.选择与笛卡尔积的交换律选择与笛卡尔积的交换律7.7.选择与并的交换选择与并的交换8.8.选择与差运算的交换选择与差运算的交换9.9.投影与笛卡尔积的交换投影与笛卡尔积的交换l0.l0.投影与并的交换投影与并的交换2022年11月24日0时32分数据库原理154.2.5 4.2.5 关系代数表达式的优化算法关系代数表达式的优化算法1.分解选择运算分解选择运算2.通过交换选择运算，将其尽可能移到叶端通过交换选择运算，将其尽可能移到叶端3.通过交换投影运算，将其尽可能移到叶端通过交换投
16、影运算，将其尽可能移到叶端4.合并串接的选择和投影，以便能同时执行或在一次扫描合并串接的选择和投影，以便能同时执行或在一次扫描中完成中完成5.对内结点分组对内结点分组6.生成程序生成程序2022年11月24日0时32分数据库原理164.2.6 4.2.6 优化的一般步骤优化的一般步骤1 1把查询转换成某种内部表示把查询转换成某种内部表示2 2代数优化：把语法树转换成标准（优化）形式代数优化：把语法树转换成标准（优化）形式3 3物理优化：选择低层的存取路径物理优化：选择低层的存取路径4 4生成查询计划，选择代价最小的生成查询计划，选择代价最小的 2022年11月24日0时32分数据库原理17St
17、udentStudentSCSCJoin(Student.SnoJoin(Student.Sno=SC.SnoSC.Sno)Select(SC.CnoSelect(SC.Cno=2)=2)Project(SnameProject(Sname)结结 果果 Student.SnoStudent.Sno=Sc.SnoSc.Sno Sc.SnoSc.Sno=2=2Student SCStudent SC SnameSname Student.SnoStudent.Sno=Sc.SnoSc.Sno Sc.SnoSc.Sno=2=2 SnameSnameSCSCStudentStudent2022年11月24日0时32分数据库原理18小小 结结n n 关系系统的定义关系系统的定义n 关系系统的分类关系系统的分类n n 关系系统及其查询优化关系系统及其查询优化n 查询优化的一般准则查询优化的一般准则n 关系代数等价变换规则关系代数等价变换规则n 关系代数表达式的优化算法关系代数表达式的优化算法n 优化的一般步骤优化的一般步骤
