关系系统及其查询优化全解

,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,关系系统及其查询优化全解,4.1 考虑题,关系系统的定义？如何理解关系系统？,关系系统分类？常用的关系系统例如,什么是表式系统？最小关系系统？关系完备系统？全关系系统？,准那么的含义？,信息准那么的含义？,保证访问准那么？空值的含义？,统一的数据子语言准那么？,视图更新准那么？,数据物理独立性数据逻辑独立性,数据完好性独立性？,关系系统及其查询优化,关系系统:,关系模型的根本要素:关系数据构造 、关系的完好性、关系操作,支持关系数据构造表,支持选择、投影、连接运算，对这些运算不必要定义任何物理存储途径,关系系统的分类,表式系统：仅支持表数据构造,不支持集合操作,最小关系系统:仅支持关系数据构造和3种关系操作,关系完备的系统:支持关系数据构造和所有的关系代数操作,全关系系统:支持关系模型的所有特征,关系系统及其查询优化,全关系系统的12条准那么,0. 一个关系的DBMS必须能完全通过它的关系才能来管理数据库.,关系的DBMS必须在关系级别上支持数据的插入修改删除,关系的DBMS必须保证信息准那么和访问准那么.,1.信息准那么:关系的DBMS的所有信息都应该在逻辑一级上用一种方法即表中的值显式地表示.,2.保证访问准那么.,3.空值的系统化处理.,4.基于关系模型的动态的联机数据字典.,5.统一的数据子语言的准那么.,6.视图更新准那么.,关系系统及其查询优化,全关系系统的12条准那么,7. 高级的删除插入修改操作,10.数据完好性独立性.,11.分布独立性.,在第一次引入分布式数据时,当数据重新分布时,12.无破坏准那么.,关系系统及其查询优化,关系数据库系统的查询优化,查询处理:从查询语句出发到获得查询结果的处理过程,包括:代数优化物理优化规那么优化等,包括4个步骤:,将查询转换成某种内部表示,通常是语法树,根据等价变化规那么将语法树转化为标准(优化)形式,选择低层的算法,生成查询方案:,关系系统及其查询优化,一个例如:,求选修了2号课程的学生的姓名.,SELECT S.Sname FROM S,SC,WHERE S.sno=SC.Sno AND SC.Cno=2,等价的关系代数:,关系系统及其查询优化,假设有1000个学生记录,10000个选课记录,选2号课程的选课记录有50个,第一种情况:,计算笛卡儿积：设一个块可以装入10个S元组和100个SC元组，在内存里存放5块S元组和1块SC元组。,那么读取总块数为： 1000/10+1000/10*5*10000/100,设每秒读20块，那么读数据时间为105秒,连接后的元组为10000000个，设可以装10个元组每块。写进中间文件的时间为：10000000/10/20=50000秒,做选择操作：忽略处理时间。读入数据时间为50000秒,做投影：,总时间为：105+50000*2=100105秒。,关系系统及其查询优化,第二种情况:,计算自然连接：设一个块可以装入10个S元组和100个SC元组，在内存里存放5块S元组和1块SC元组。,那么读取总块数为： 1000/10+1000/10*5*10000/100,设每秒读20块，那么读数据时间为105秒,连接后的元组为10000个，设可以装10个元组每块。写进中间文件的时间为：10000/10/20=50秒,读取中间 文件块：忽略处理时间。执行选择运算，时间也是50秒,做投影：,总时间为：105+50+50=205秒。,关系系统及其查询优化,第三种情况:,先对SC表做选择运算：,读SC表5秒。,读取S表：,时间也是5秒,连接结果做投影：,总时间为：,5+5=10秒,查询优化的一般准那么,选择运算应该尽可能先做：使计算的中间结果由大变小,在执行连接之前对关系进展适当的预处理,在连接属性上建立索引或对关系排序。P161,把投影运算和选择运算同时进展。防止重复扫描关系,把投影同其前或后的双目运算结合起来。,把某些选择同它在前面要执行的笛卡儿积结合起来成为一个连接运算,找出公共子表达式,关系系统及其查询优化,关系代数等价变换规那么,1 连接、笛卡儿积交换律,2 连接、笛卡儿积结合律,3 投影的串接定律,4 选择的串接定律,5 选择与投影的交换律,6 选择与笛卡儿积的交换律,7 选择与并的交换,8 选择与差的交换,9 投影与笛卡儿积的交换,10 投影与并的交换,关系系统及其查询优化,关系代数表达式的优化算法,算法:关系表达式的优化,输入:一个关系表达式的语法树,输出:计算表达式的程序,方法:,1 规那么4:选择的串接定律进展变换,2 对每个选择尽量安排在叶端(规那么4-8),3 对每个投影尽可能移到叶端(规那么3 9 10 5),4 把选择和投影串接合并成单个选择单个投影或一个选择后跟一个投影 P164,关系系统及其查询优化,优化的一般步骤,将查询转换成某种内部表示,通常是语法树,根据等价变化规那么将语法树转化为标准(优化)形式,结果,Project(Sname),Select(Sc.Cno=2),join(S.sno=sc.sno),SC,S,SC,S,关系系统及其查询优化,选择低层的算法,生成查询方案:,SC,S,关系系统及其查询优化,代数优化:对查询进展等价交换.,设有: S(SNUM,SNAME,CITY) 供给商,P(PNUM,PNAME,WEIGHT,SIZE) 零件,SP(SNUM,PNUM,DEPT,QUAN) 供给关系,查询: 查询供给一个部门10000个以上螺栓并且位于南京的供给商的名字.,SELECT SNAME FROM S,P,SP,AND S.CITY=NAJING,AND P.PNAME=BOLT,AND SP.QUAN10000;,关系系统及其查询优化,语法树:,AND S.CITY=NAJING,AND P.PNAME=BOLT,AND SP.QIAN10000;,SP,S,p,关系系统及其查询优化,尽可能将选择操作,沿语法树下压,那么有:,P,S,Sp,关系系统及其查询优化,将连接条件与笛卡儿积,组合成连接操作,P,S,Sp,关系系统及其查询优化,用投影操作取消对查询,无用的属性,P,S,Sp,关系系统及其查询优化,代数优化总结：,以SELECT子句对应投影操作，以FROM子句对应笛卡儿积，以WHERE子句对应选择操作，生成原始查询树,尽可能将选择条件移向树叶,应用连接、笛卡儿积的结合律，按照小关系先做的原那么，重新安排连接笛卡儿积的次序。,假设笛卡儿积后还需要按连接条件进展选择操作，可以将2者组合成连接操作,对每个叶节点加必要的投影操作，以消除对查询无用的属性。,关系系统及其查询优化,规那么优化:结合存储途径的分析,讨论各种根本操作执行的策略及选择原那么.,选择操作的实现与优化:与选择条件存取途径选取元组占整个关系的比例有关系,最原始的实现方法是-顺序扫描(不需要特殊的存取途径),适用于小的关系,DBMS支持建立各种存取途径,B+树,索引:无序索引/排序索引,关系系统及其查询优化,优化策略:,小的关系直接扫描,对于主键上的等值条件查询,最多只有一个元组可以满足条件应优先用主键上的索引,对于非主键上的等值条件查询,需要估计中选的元组的在关系中站的比例,比例小(15%)可以用无序索引,否那么可以用有序索引或顺序扫描,对于有and连接的复合选择,应有复合索引,对于用or 连接的选择条件,只能按其中各个条件分别选出一个元组集,在求并运算. 无好的优化方法,应该尽量少用.,有些选择操作只要访问索引就可以得到结果.如,查询索引属性的最大值等.,关系系统及其查询优化,连接操作的实现与优化:,嵌套循环法:设有关系R和S进展连接操作,原始的方法就是选取R的一个元组,与S的所有的元组比较,满足连接条件的就输出,再选取R下一个元组重复上述过程.,详细算法如下:,关系系统及其查询优化,/*r有n个元组,s有m个元组*/,I1,j1,While (I=n),Do while (J=m),do if r(I)a=s(j)b,then 输出 R(I),s(j)到T;,j=j+1,J=1,I=I+1,利用索引寻找匹配元组的方法:在内关系上建立索引,具有适宜的存取途径,以取代顺序扫描,关系系统及其查询优化,排序归并法:,原理P161,.,/*r有n个元组,按属性A排序,s有m个元组,按属性B排序*/,I,1,j,1,While (I=n) and (js(j)b,then j=j+1;,else if r(I)as(j)b,then I=I+1;,else ,/* r(I)a=s(j)b,输出连接元组*/,输出 R(I),s(j)到T;,/*输出r(I)与S中除S(j)外的其他元组所组成的连接元组*/,p,-j+1,while (p=m) and (r(i)a=s(p)b),关系系统及其查询优化,do 输出R(i),s(p)到T,p=p+1;,/*输出S(J)与r中除r(I)外的其他元组所组成的连接元组*/,K,-I+1,while (K=N) and (r(K)a=s(J)b),do 输出R(K),s(J)到T,K,K+1;,I,I+1, J,1+1;,关系系统及其查询优化,投影操作的实现:,注意投影后消除重复元组,可以用排序等方法消除重复元组.,集合操作的实现:,笛卡儿积并交差,笛卡儿积用嵌套循环实现.,并/交/差的算法如下:,并操作算法,将RS按主键升序排序,I,1,j,1,While (I=n) and (js(j),/*指的R(i)主键大于S(j)的主键,下同*/,then 输出 s(j)到T;,j,j+1;,else if r(I) s(j),then 输出 R(i)到T;,I,I+1,else j,j+1;,/*跳过一个重复的元组*/,if (I=n) then 把R(i)到 R(n)的元组输出到 T;,if (j=m) then 把S(j)到 S(m)的元组输出到 T;,交操作算法,将RS按主键升序排序,I,1,j,1,While (I=n) and (js(j),/*指的R(i)主键大于S(j)的主键,下同*/,then j,j+1;,else if r(I) s(j),then I,I+1,else 输出R(i)到T;/*R(i)=S(j),输出一元组*/,I,I+1,j,j+1;,差操作算法,将RS按主键升序排序,I,1,j,1,While (I=n) and (js(j),/*指的R(i)主键大于S(j)的主键,下同*/,then j,j+1;,else if r(I) s(j),then 输出R(i)到T;,I,I+1;,else I,I+1,j,j+1;,If (I=20可以查询的元组个数为:5000,Cage=L+5000/200=2+25=27,C=6+27+500=533,用其中一个条件选出元组,再用其他条件挑选这些元组,cq2=82,Cdno=108=cdno+500=506,cq3=2000,