数据库原理关系系统及其查询优化课件

数据库原理关系系统及其查询优化数据库系统原理(第4章)四川大学计算机学院张天庆数据库原理关系系统及其查询优化第四章 关系系统及查询优化要求：了解关系系统及其定义、分类；了解查询优化的目的、概念和一般策略。本章内容比较“理论”，对于设计一个DBMS比较有用。数据库原理关系系统及其查询优化4.1 关系系统不确切地说法：“支持关系模型的系统”。关系系统和关系模型是两个密切相关而有不同的概念。支持关系模型的数据库管理系统称为关系系统。但是关系模型中并非每一部分都是同等重要的，所以我们不苛求完全支持关系模型的系统才能称为关系系统。因此，我们给出一个关系系统的最小要求以及分类的定义。数据库原理关系系统及其查询优化4.1.1 关系系统的定义给出配称为关系系统的最小要求。一个系统可定义为关系系统，当且仅当它：1.支持关系数据库（关系数据结构）2.支持选择、投影和（自然）连接运算，对这些运算不必要求定义任何物理存取路径 注：1.对完整性无要求；2.选、连、投三种运算最有用；3.不能依赖物理路径，使之具有物理独立性。数据库原理关系系统及其查询优化4.1.2 关系系统的分类表式系统：只支持关系(表)数据结构，不支持选择、连接、投影等关系操作。(最小)关系系统：(刚好)满足关系系统定义的系统。关系上完备的系统：支持关系数据结构和全部队关系代数操作。全关系系统，在3基础上，还支持数据结构中域的概念和数据的完整性约束。目前，大多数关系系统已不同程度上接近或达到了这个目标。数据库原理关系系统及其查询优化表式系统数据库原理关系系统及其查询优化最小关系系统数据库原理关系系统及其查询优化关系完备的数据库原理关系系统及其查询优化全关系的数据库原理关系系统及其查询优化4.1.3 全关系系统十二条准则基本了解。4.2 关系系统的查询优化关系数据理论出现较早(70年代初)，但商品化系统出现较晚，重要原因就在于系统查询效率需要优化。这是本章重点。数据库原理关系系统及其查询优化4.2.1 关系系统及其查询优化思想：由系统代替用户优化。关系查询优化是影响RDBMS性能的关键因素。关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出干什么，不必指出怎么干。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。数据库原理关系系统及其查询优化实际系统对查询优化的具体实现一般可以归纳为四个步骤：1、将查询转换成某种内部表示，通常是语法树。2、根据一定的等价变换规则把语法树转换成标准（优化）形式。3、选择低层的操作算法。4、生成查询计划。数据库原理关系系统及其查询优化4.2.2 从实例看查询优化的意义SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2；此查询求选了2号课程的学生姓名。有以下四个等价的关系代数表达式可完成此查询：Q1=Sname(Student.sno=o=2(StudentSC)Q2=Sname(o=2(Student SC)Q3=Sname(Student o=2(SC)Q4=Sname(Sname，SnoStudent So=2(SC)数据库原理关系系统及其查询优化假设：n只计I/O时间，不计CPU时间n每内存块能装10个Student元组或100个SC元组n每秒读写20块nStudent表有1000个元组，SC有10000元组n内存中用5块放Student元组，一块放SC元组数据库原理关系系统及其查询优化对于Q1n读Student和SC：1000/10+(1000/10)/5(10000/100)=2100块S12100/20=105sn中间结果10,000,000个元组，读写共两次：S2=(10,000,000/10)*2/20=100,000sn总时间S1+S2，约10万秒，超过1天！数据库原理关系系统及其查询优化对于Q2n读Student和SC不变，仍为105秒；n中间结果10,000个元组，读写共两次：S2=(10,000/10)*2/20=100sn总时间S1+S2，约205秒，降低了3个数量级！数据库原理关系系统及其查询优化对于Q3n先对SC进行选择，读100块，时间5s，满足条件的元组50个，直接放在1个内存块中；n接着读Student表，与内存块中的SC元组连接，读Student表1遍时间为5s；n连接结果输出，不占I/O时间；n总时间10秒，再降低了1个数量级！数据库原理关系系统及其查询优化对于Q4n类似于Q3，但不需要读取SC和Student元组全部属性，只读Student的Sno和Sname，SC的Sno，读写块数进一步减少，从而I/O时间还可减少数据库原理关系系统及其查询优化分析它们，从Q1到Q4,一个比一个效率高，感性地告诉我们：笛卡儿集运算最好能和相应的选择一起构成连接运算；选择能早做就尽量早做；在双目运算前增加投影，只保留必要的字段。数据库原理关系系统及其查询优化4.2.3 优化的一般策略1.选择尽可能早做；2.在连接前尽可能地预处理；3.投影和选择同时进行；4.选择和它前面要进行的笛卡儿集运算结合成一个连接运算；5.把投影和其前或后的双目运算结合；6.找出公共子表达式。数据库原理关系系统及其查询优化4.2.4 等价变换规则连接、笛卡儿集交换律E1E2=E2E1E1 E2=E2 E1E1 E2=E2 E1 F F数据库原理关系系统及其查询优化2.连接、笛卡儿集的结合律3.投影的串接定律注意：常常从右向左用，把一次投影变成两次投影。4.选择的串接定律注意：常常从右向左用，把一次复杂条件选择变成多次投影。5.选择与投影的交换律注意一般形式的正用。6.选择与笛卡儿集的交换律(实现选择早做)数据库原理关系系统及其查询优化7.选择与并的交换8.选择与差的交换9.投影与笛卡儿集的交换注意：实现投影早做，只保留必要的字段。重要的：3.4.5.6.9。数据库原理关系系统及其查询优化4.2.5 关系代数表达式的优化算法 六大步：选择变串连尽可能先做选择尽可能先做投影同时执行多个选择和投影分组1.分组计算数据库原理关系系统及其查询优化4.2.6 优化的一般步骤各个关系系统的优化方法不尽相同,大致的步骤可以归纳如下:1.把查询转换成某种内部表示2.把语法树转换成标淮(优化)形式3.选择低层的存取路径，充分考虑索引、数据的存储分布等存取路径。利用它们进一步改善查询效率。4.生成查询计划，选择代价最小的。数据库原理关系系统及其查询优化例4.5 SELECT Student.Sname FROM Student，SC WHERE Student.Sno=SC.Sno AND SC.Cno=2；Q1=Sname(Student.sno=o=2(StudentSC)数据库原理关系系统及其查询优化初始语法树 Sname Student.sno=o=2 Student SC数据库原理关系系统及其查询优化选择变串接 Sname Student.sno=sc.sno o=2 Student SC数据库原理关系系统及其查询优化选择尽可能早作（选择与笛卡儿集交换）Sname Student.sno=sc.sno Student o=2 SC数据库原理关系系统及其查询优化投影尽可能早作 Sname Student.sno=sc.sno Sno，Sname Sno Student o=2 SC数据库原理关系系统及其查询优化实例分析。书上给出的例4.5还不是一个完整的标准(优化)形式。还需增加投影早做。再给一个例子。有以下查询，写出关系代数表示的语法树，并利用关系代数表达式优化算法对其进行优化。SELECT SnameFROM Student,SC,CourseWHERE Student.Sno=SC.Sno ANDSC.Cno=Course.Cno AND Cname=C语言;数据库原理关系系统及其查询优化 Sname Student.sno=sc.sno Sno，Sname Sno Student SC.Cno=Course.Cno Sno,Cno Cno SC Cname=C语言语言 Course数据库原理关系系统及其查询优化本章作业P166，4