关系数据库查询优化相关教材

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第八章 关系数据库查询优化,学习内容,8.1,查询处理概述,8.2,基本运算实现举例,8.3,查询优化的选择执行,8.4 sql,语句优化,参考：,B3,第十二章,学习目标,了解查询处理的过程,了解查询优化的步骤,掌握关系代数等价变换规则,了解启发式优化的方法,8.1,查询处理概述,8.1.1,查询处理的定义,8.1.2,查询处理的执行步骤,8.1.3,相关基本概念,8.1.1,查询处理的定义,1. 定义,从数据库中提取数据的一系列活动,2. 包括的主要内容,表达式,转换,执行,3.,输入、输出,8.1.2,查询处理的执行步骤,语法分析与翻译,优化,执行,语法分析与翻译,关系代数表达式,执行计划,优化器,查询语句,执行引擎,查询结果,有关数据的统计值,数据,8.1.3,相关基本概念,查询代价,查询处理对各种资源的使用情况,磁盘存取 （简化为磁盘块传送数）,CPU,时间,通信开销,内存开销,COST,CPU,(PLAN),COST,I/O,(PLAN),PLAN1,9.2,CPU seconds,103,reads,PLAN2,1.7,CPU seconds,890,reads,8.1.3,相关基本概念(续),部分用于估计代价的目录信息,有关关系的统计信息,n,r,：,关系,R,中的元组数目,b,r,：,含有关系,R,的元组的块数目,s,r,：,关系,R,中一个元组的大小,f,r,：,关系,R,的块因子，即一个块中能存放的关系,R,的元组数,若假定关系,R,的元组物理上存于同一文件中，则：,b,r,=,n,r,/ f,r,一个重要的影响因素：主存中缓冲区的大小,M,最好的情形,最坏的情形,8.1.3,相关基本概念(续),查询优化,为关系代数表达式的计算选择最有效的查询计划的过程。,查询执行计划,用于计算一个查询的原语序列。,执行原语,加了“如何执行”注释的关系代数运算。,查询优化的过程,代数优化,物理优化,详细策略的选择,优化器,8.1.4,查询优化概述,例：求选修了2号课程的学生姓名,SELECT Student.Sname,FROM Student, SC,WHERE Student.Sno=SC.Sno,AND SC.Cno=2;,1 查询优化的必要性（续）,假设1：外存：,Student:1000,条,SC:10000,条, 选修2号课程:50条,一个硬盘块放10个,student,或者100个,SC,假设2：一次,I/O,交换元组:10个,Student,或100个,SC,内存中一次可以存放: 5块,Student,元组（即50个,Student）,1,块,SC,元组（即100个,SC）,和若干块连接结果元组,假设3：读写速度：20块/秒,假设4：连接方法：,基于数据块,的嵌套循环法,8.1.4,查询优化概述,1 查询优化的必要性(续),8.1.4,查询优化概述,1 查询优化的必要性(续),几种不同的实现方法：,1）,Q1 ,Sname,(,Student.Sno=SC.Sno SC.Cno=2,(StudentSC),2）2,name,(,SC.Cno= 2,(Student SC),3）3,Sname,(Student ,SC.Cno= 2,(SC),1,Q1 ,Sname,(,Student.Sno=,SC.Sno,SC.Cno=2,(StudentSC), StudentSC,读取总块数= 读,Student,表块数 + 读,SC,表遍数,*每遍块数,(,读,SC,表遍数=,Student,表的总元组数/在内存中的元组数,),=1000/10+(1000/(105) (10000/100),=100+20100=2100,读数据时间,=2100/20=105秒,1 查询优化的必要性(续),8.1.4,查询优化概述,中间结果大小 = 1000*10000 = 10,7,(1千万条元组),写中间结果时间,= 10000000/10/20 = 50000秒,（,设每块能装10个中间结果元组）,读数据时间,= 50000秒,总时间,=1055000050000秒 = 100105秒,= 27.8小时,8.1.4,查询优化概述,1 查询优化的必要性(续),2. 2,name,(,SC.Cno= 2,(Student SC),读取总块数= 2100块（,Q1,的结果）,读数据时间,=2100/20=105秒,因为只有,SC,只有10000条元组，故等值连接的结果,即:,中间结果大小=10000 （减少1000倍）,写中间结果时间,=10000/10/20=50秒,读数据时间,=50秒,总时间,1055050秒205秒=3.4分（减少了中间结果）,8.1.4,查询优化概述,1 查询优化的必要性(续),3. 3,Sname,(Student,SC.Cno= 2,(SC),读,SC,表总块数= 10000/100=100块,读数据时间,=100/20=5秒,中间结果大小=50条 不必写入外存,读,Student,表总块数= 1000/10=100块,读数据时间,=100/20=5秒,总时间,55秒10秒 （减少中间结果,且全部在内存）,1 查询优化的必要性(续),8.1.4,查询优化概述,8.,4,name,(S,tudent,SC.Cno=2,(SC),假设,SC,表在,Cno,上有索引，,Student,表在,Sno,上有索引,读,SC,表索引=（发现2号课程只有50条元组）,读,SC,表总块数= 50/1001块,读数据时间:1/20=0.5,中间结果大小=50条 不必写入外存,1 查询优化的必要性(续),8.1.4,查询优化概述,读,Student,表索引=(根据索引发现只有50个学生),读,Student,表总块数= 50/10=5块,读数据时间 ：5/20=0.5秒,总时间12秒（不必遍历所有的元组记录）,1 查询优化的必要性(续),8.1.4,查询优化概述,用户不必考虑如何最好地表达查询以获得较好的效率。,关系数据语言的,级别很高,，使,DBMS,可以从关系表达式中分析查询,语义,。,系统可以比用户程序的,优化,做得更好。,2 查询优化的可能性,8.1.4,查询优化概述,StudentSC（,做,SCStudent）,读取总块数= 读,SC,表块数 + 读,Student,表遍数,*每遍块数,(,读,Student,表遍数=,SC,表的总元组数/在内存中的元组数,),=10000/100+(10000/(1001) (1000/10),=100+100100=10100,读数据时间,=10100/20=505秒,2 查询优化的可能性(续),8.1.4,查询优化概述,8.1.4,查询优化概述,2 查询优化的可能性(续),优化器可以从数据字典中获取许多信息(包括统计信息和索引信息)，而用户程序则难以获得这些信息。,如果数据库的物理统计信息改变了，系统可以自动对查询,重新优化,以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。,优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性,。,优化器中包括了很多复杂的优化技术,查询优化的总目标,选择有效策略，求得给定关系表达式的值,8.1.4,查询优化概述,3 查询优化的目标,代价模型：,集中式数据库,单用户系统,总代价 =,I/O,代价 +,CPU,代价,多用户系统,总代价 =,I/O,代价 +,CPU,代价 + 内存代价,分布式数据库,总代价,=,I/O,代价 +,CPU,代价+ 内存代价 + 通信代价,8.1.4,查询优化概述,3 查询优化的目标（续）,8.2,基本运算实现举例,1. 运算特点,每一个基本的代数运算都有多种不同的实现算法,适用于不同的情况,执行代价不同,2. 选择运算的实现,3. 连接运算的实现,8.2,基本运算实现举例(续),2. 选择运算的实现,全表扫描,方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。,代价：,E = b,r,索引扫描,条件：表在选择条件的属性上建有索引。,方法：访问索引，根据索引项的指示去访问数据元组,。,代价：,8.2,基本运算实现举例(续),3. 连接运算的实现,嵌套循环连接,块嵌套循环连接,索引嵌套循环连接,排序-归并连接,散列连接,8.2,基本运算实现举例(续),3. 连接运算的实现,嵌套循环连接,for each,元组,t,r,in R do,begin,for each,元组,t,s,in S do,begin,测试元组对(,t,r,t,s,),是否满足连接条件,如果满足，把,t,r, t,s,加到结果中,end,end,8.2,基本运算实现举例(续),3. 连接运算的实现,嵌套循环连接,优点：对参加运算的关系没有要求，适合于任何连接条件。,代价：,最坏情况（缓冲区只能够容纳每个关系的一个,块,）,最好情况（内层关系,S,能完全放在内存中）,b,s,+ b,r,8.2,基本运算实现举例(续),3. 连接运算的实现,排序-归并连接,类似于外排序的归并算法的思路，进行连接运算。,前提：两个关系的元组已按连接属性排好序。,适用于自然连接和等值连接。,排序-归并连接,a,3,b,1,d,8,d,13,f,7,m,5,q,6,a,A,a,G,c,L,d,N,m,B,r,s,a1,a2,a,1,a3,在归并连接中使用的已排序关系,r,s,8.3,查询优化的选择执行,8.3.1,表达式等价,S#,(,C# = 001,C# = 002,(SC),S#,(,C# = 001,(SC),S#,(,C# = 002,(SC),8.3.2,两类主要的优化算法,8.3.3,启发式优化,8.3.4,查询优化的一般步骤,8.3.1,表达式等价,1. 语法树,2. 表达式等价的定义,3. 表达式的等价规则,8.3.1,表达式等价(续),语法树（查询树）,叶子节点：关系,内节点：关系代数操作,执行方式：自底向上,customer_name,balance |,关系代数表达式的语法树：,customer_name,（,balance | depositor),),8.3.1,表达式等价(续),3. 常用等价变换规则,说明：,E、E,1,、E,2,等表示关系代数表达式,连接、笛卡尔积交换律,连接、笛卡尔积的结合律,投影的串接定律,选择的串接定律,选择与投影的交换律,选择与笛卡尔积的交换律,选择与并的交换,选择与差运算的交换,投影与笛卡尔积的交换,投影与并的交换,关系代数表达式等价,指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的,上面的优化策略大部分都涉及到代数表达式的变换,8.3.1,表达式等价(续),设,E1、E2,等是关系代数表达式，,F,是条件表达式,l.,连接、笛卡尔积交换律,E1 E2 E2E1,E1 E2E2 E1,E1,F,E2E2,F,E1,8.3.1,表达式等价(续),2. 连接、笛卡尔积的结合律,(,E1E2) E3 E1 (E2E3),(E1 E2) E3 E1 (E2 E3),(E1 E2) E3 E1 (E2 E3),F,F,F,F,8.3.1,表达式等价(续),3,. 投影的串接定律,A1,A2,An,(,B1,B2,Bm,(E),A1,A2,An,(E),假设：,1),E,是关系代数表达式,2),A,i,(i=1，2，n), B,j,(j=l，2，m),是属性名,3),A,1, A,2, , A,n,构成,B,l,，B,2,，B,m,的子集,8.3.1,表达式等价(续),8.,选择的串接定律,F1,（,F2,（E）,F1 F2,(E),选择的串接律说明 选择条件可以合并,这样一次就可检查全部条件。,8.3.1,表达式等价(续),5. 选择与投影的交换律,(1)假设: 选择条件,F,只涉及属性,A1，An,F,(,A1,A2,An,(,E),A1,A2,An,(,F,(E),(2),假设:,F,中有不属于,A1, ,An,的属性,B1,Bm,A1,A2,An,(,F,(,E),A1,A2,An,(,F,(,A1,A2,An,B1,B2,Bm,(E),8.3.1,表达式等价(续),6. 选择与笛卡尔积的交换律,(1),假设：,F,中涉及的属性都是,E1,中的属性,F,(E1E2),F,(E1)E2,(2),假设：,F=F1F2，,并且,F1,只涉及,E1,中的属性，,F2,只涉及,E2,中的属性,则由上面的等价变换规则1，4，6可推出：,F,(E1E2) ,F1,(E1),F2,(E2),8.3.1,表达式等价(续),(3) 假设：,F=F1F2，,F1,只涉及,E1,中的属性，,F2,涉及,E1,和,E2,两者的属性,F,(E1E2),F2,(,F1,(E1)E2),它使部分选择在笛卡尔积前先做,8.3.1,表达式等价(续),7. 选择与并的交换,假设：,E=E1E2，E1，E2,有相同的属性名,F,(E1E2) ,F,(E1) ,F,(E2),8.,选择与差运算的交换,假设：,E1,与,E2,有相同的属性名,F,(E1-E2) ,F,(E1) - ,F,(E2),8.3.1,表达式等价(续),9. 投影与笛卡尔积的交换,假设：,E1,和,E2,是两个关系表达式，,A1，An,是,E1,的属性，,B1，Bm,是,E2,的属性,A1,A2,An,B1,B2,Bm,（E1E2),A1,A2,An,（E1) ,B1,B2,Bm,(E2),8.3.1,表达式等价(续),l0.,投影与并的交换,假设：,E1,和,E2,有相同的属性名,A1,A2,An,(E1E2),A1,A2,An,(E1) ,A1,A2,An,(E2),8.3.1,表达式等价(续),l0.,投影与并的交换,假设：,E1,和,E2,有相同的属性名,A1,A2,An,(E1E2),A1,A2,An,(E1) ,A1,A2,An,(E2),8.3.1,表达式等价(续),8.3.1,表达式等价(续),3. 常用等价变换规则,说明：,规则只说明两个表达式等价，并不说明哪一个更好。,连接的次序很重要，好的连接次序序列产生小的中间结果。,8.3.2,两类主要的优化算法,1. 两类主要的优化算法,基于代价的方法,通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的,启发式方法,运用启发式规则，对关系代数表达式进行等价变换,8.3.3,启发式优化,1. 启发式优化的常用规则,选择运算应尽可能先做,投影运算应尽可能先做,在执行连接前对关系适当地预处理,把投影运算和选择运算同时进行,把投影同其前或其后的双目运算结合起来,找出公共子表达式,8.3.4,关系代数表达式的优化算法,算法：关系表达式的优化,输入：一个关系表达式的语法树。,输出：计算该表达式的程序。,方法：,（1）分解选择运算,利用规则4把形如,F1 F2 , Fn,(E),变换为,F1,(,F2,( (,Fn,(E) ),8.3.4,关系代数表达式的优化算法,（2）通过交换选择运算，将其尽可能移到叶端,对每一个选择，利用规则48尽可能把它移到树的叶端。,（3）通过交换投影运算，将其尽可能移到叶端,对每一个投影利用规则3，9，,l0，5,中的一般形式尽可能把它移向树的叶端。,8.3.4,关系代数表达式的优化算法,（4）合并串接的选择和投影，以便能同时执行或在一次扫描中完成,利用规则35把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。,使多个选择或投影能同时执行，或在一次扫描中全部完成,尽管这种变换似乎违背“投影尽可能早做”的原则，但这样做效率更高。,8.3.4,关系代数表达式的优化算法,（5）对内结点分组,把上述得到的语法树的内节点分组。,每一双目运算(， ，-)和它所有的直接祖先为一组(这些直接祖先是,，,运算)。,如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积()，而且其后的选择不能与它结合为等值连接时除外。把这些单目运算单独分为一组,。,8.3.4,关系代数表达式的优化算法,（6）生成程序,生成一个程序，每组结点的计算是程序中的一步。,各步的顺序是任意的，只要保证任何一组的计算不会在它的后代组之前计算,。,例子,考虑应用：,Books(title,author,pname,lc-no),Publishers(pname,paddr,pcity),Borrowers(name,addr,city,card-no),Loans(card-no,lc-no,date),查询：列出1992年1月1日以前借出的所有书名,，,title,(,date960101,(Xloans),例子,例子,（1）选择运算,有三个选择运算，分解,（2）使用定律48把三个选择运算尽量移向树的叶端,（3）由于选择和投影的可交换，把条件,date960101,移到最下端,title,(,date3,SELECT * FROM SC,WHERE CNO=4,例7：,SELECT ACCOUNT_NAME FROM TRANSACTION WHERE AMOUNT !=0;,不使用索引,SELECT ACCOUNT_NAME FROM TRANSACTION WHERE AMOUNT 0;,使用索引:,索引只能告诉你什么存在于表中, 而不能告诉你什么不存在于表中。,例8：SELECT SNAME, GRADE,FROM STUDENT, SC,WHERE STUDENT.SNO=SC.CNO AND SC.CNO = 001,SELECT A.SNAME, B.GRADE,FROM STUDENT A, SC B,WHERE A.SNO=B.SNO AND B.CNO = 001,