关系系统及其查询优化课件

1、关系系统及其查询优化 第4章 关系系统 关系系统的定义 关系系统的分类 关系系统的查询优化 关系系统及其查询优化 查询优化的一般准则 关系代数等价变换规则 关系代数表达式的优化算法 优化的一般步骤 2022/10/171数据库原理关系系统及其查询优化 第4章 关系系统2022/10/1514.1 关系系统支持关系模型的关系数据库管理系统简称关系系统。 下述关系的DBMS不能称为关系系统 不支持关系数据结构的系统 支持关系数据结构，但无、 运算功能的系统 支持关系数据结构，有、 运算，但要求定义物理 存取路径的系统可称为关系系统的DBMS，当且仅当1）支持关系数据结构（关系数据库）2）支持、 运

2、算，且不要求用户定义任何物理存取路径4.1.1 关系系统的定义2022/10/172数据库原理4.1 关系系统支持关系模型的关系数据库管理系统简称关系系统4.1.2 关系系统的分类4全关系系统： 支持关系模型的所有特征。在关系完备系统的基础上，进一步支持实体完整性和参照完整性等。DB,ORACLE,SYBASE, 已接近这个目标。目前尚无全关系系统。1表式系统： 仅支持关系数据结构，不支持集合级的操作。（不能算关系系统）2（最小）关系系统： 支持关系数据结构，支持、 运算，且不定义物理路径。3关系完备系统： 支持关系数据结构和所有关系代数操作（或功能上与关系代数等价）。DB,ORACLE,SY

3、BASE,属于这一类。2022/10/173数据库原理4.1.2 关系系统的分类4全关系系统：1表式系统：2 关系系统分类数据结构数据操作完整性约束表式系统表(最小)关系系统表选择、投影、连接关系完备的系统表全关系系统2022/10/174数据库原理 关系系统分类数据结构数据操作完整性约束表式系统表(最4.2 关系数据库系统的查询优化4.2.1 关系系统及其查询优化 查询处理的过程查询语句查询输出关系代数表达式执行计划语法分析与翻译执行引擎优化器有关数据的统计信息数据2022/10/175数据库原理4.2 关系数据库系统的查询优化4.2.1 关系系统及其查询系统优化 优化器可以从数据字典中获取

4、许多统计信息，从而选择有效的执行计划； 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划； 优化器可以考虑数百种不同的执行计划； 优化器中包括了很多复杂的优化技术。2022/10/176数据库原理系统优化 优化器可以从数据字典中获取许多统计信息，从而选择 实际系统的查询优化步骤1. 将查询转换成某种内部表示，通常是语法树2. 根据一定的等价变换规则把语法树转换成标准（优化）形式3. 选择低层的操作算法 对于语法树中的每一个操作 根据存取路径、数据的尺寸、数据的存储分布、存储数据的聚簇等信息来计算各种执行算法的执行代价 选择代价小的执行算法4. 生成查询计划(

5、查询执行方案)2022/10/177数据库原理 实际系统的查询优化步骤1. 将查询转换成某种内部表示，通 常用查询优化技术 用启发式规则来缩减查询计划的搜索空间 利用统计信息估算执行代价 基于代价（目前商品化RDBMS大都采用） 代价模型 集中式数据库 单用户系统：总代价 = I/O代价 + CPU代价 多用户系统：总代价 = I/O代价 + CPU代价 + 内存代价 分布式数据库 总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价 2022/10/178数据库原理 常用查询优化技术 代价模型2022/10/158数据库4.2.2 一个实例 例. 求选2号课程的学生姓名SELE

6、CT Student.Sname FROM Student，SCWHERE Student.Sno = SC.Sno AND Cno = 2； 数据量：Student:1000条；SC:10000条；选修2号课程:50条 一个内存块装元组:10个Student或100个SC，内存中可以 存放:5块Student元组和1块SC元组 读写速度：20块/秒假设：2022/10/179数据库原理4.2.2 一个实例 例. 求选2号课程的学生姓名SELEC1. 1 Sname(Student.Sno=SC.Sno SC.Cno=c2 (StudentSC) 计算广义笛卡尔积(StudentSC) 读取总

7、块数 = 读Student表块数 + 读SC表遍数 * 每遍块数 = 1000/10+(1000/(105) (10000/100) = 2100 读数据时间=2100/20=105秒 中间结果大小 = 1000*10000 = 107 (1千万条元组) 写中间结果时间 = 10000000/10/20 = 50000秒 选择操作() 读数据时间 = 50000秒 投影() 总时间 =1055000050000秒 = 100105秒 = 27.8小时2022/10/1710数据库原理1. 1 Sname(Student.Sno=SC2. 2 name(SC.Cno= 2 (Student SC

8、)自然连接( ) 读取总块数= 2100块 读数据时间=2100/20=105秒 中间结果大小=10000（即SC表中记录条数，减少1000倍） 写中间结果时间=10000/10/20=50秒选择操作() 读数据时间=50秒投影() 总时间1055050秒205秒=3.4分2022/10/1711数据库原理2. 2 name(SC.Cno= 2 (St3. 2 Sname(Student SC.Cno= 2 (SC)选择操作()读SC表总块数= 10000/100=100块读数据时间=100/20=5秒中间结果大小=50条 （不必使用中间文件）自然连接（ ）读Student表总块数= 1000

9、/10=100块读数据时间=100/20=5秒 投影()总时间55秒10秒 2022/10/1712数据库原理3. 2 Sname(Student SC.C4.2.3 查询优化的一般准则选择运算应尽可能先做 在执行连接操作前对关系适当进行预处理 （索引连接方法和排序合并连接方法）投影运算和选择运算同时做将投影运算与其前后的双目运算结合（连接、并、差、交等）选择运算和笛卡尔积运算结合（等值连接比笛卡儿积省时间）提取公共子表达式（例如，定义视图的表达式）2022/10/1713数据库原理4.2.3 查询优化的一般准则选择运算应尽可能先做 4.2.4 关系代数等价变换规则l. 连接、笛卡尔积交换律2

10、. 连接、笛卡尔积的结合律3. 投影的串接定律4. 选择的串接定律5. 选择与投影的交换律6. 选择与笛卡尔积的交换律7. 选择与并的交换8. 选择与差运算的交换9. 投影与笛卡尔积的交换l0. 投影与并的交换2022/10/1714数据库原理4.2.4 关系代数等价变换规则l. 连接、笛卡尔积交换律24.2.5 关系代数表达式的优化算法分解选择运算通过交换选择运算，将其尽可能移到叶端通过交换投影运算，将其尽可能移到叶端合并串接的选择和投影，以便能同时执行或在一次扫描中完成对内结点分组生成程序2022/10/1715数据库原理4.2.5 关系代数表达式的优化算法分解选择运算2022/14.2.6 优化的一般步骤1把查询转换成某种内部表示2代数优化：把语法树转换成标准（优化）形式3物理优化：选择低层的存取路径4生成查询计划，选择代价最小的 2022/10/1716数据库原理4.2.6 优化的一般步骤1把查询转换成某种内部表示202StudentSCJoin(Student.Sno=SC.Sno)Select(SC.Cno=2)Project(Sname)结 果Student.Sno=Sc.SnoSc.Sno=2Student SCSnameStudent.Sno=Sc.SnoSc.Sno=2SnameSCStudent2022/