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

1、第八章 关系数据库查询优化学习内容容8.1查询处理理概述8.2基本运算算实现举举例8.3查询优化化的选择择执行8.4sql语句优化化参考：B3第十二章章学习目标标了解查询询处理的的过程了解查询询优化的的步骤掌握关系系代数等等价变换换规则了解启发发式优化化的方法法8.1查询处理理概述8.1.1查询处理理的定义义8.1.2查询处理理的执行行步骤8.1.3相关基本本概念8.1.1查询处理理的定义义1.定定义从数据库库中提取取数据的的一系列列活动2.包包括的主主要内容容表达式转换执行3.输入、输输出8.1.2查询处理理的执行行步骤语法分析析与翻译译优化执行语法分析与翻译关系代数表达式执行计划优化器查询

2、语句执行引擎查询结果有关数据的统计值数据8.1.3相关基本本概念查询代价价查询处理理对各种种资源的的使用情情况磁盘存取取 （简简化为磁磁盘块传传送数）CPU时间通信开销销内存开销销COSTCPU(PLAN)COSTI/O(PLAN)PLAN19.2 CPU seconds103 readsPLAN21.7CPU seconds890 reads8.1.3相关基本本概念(续)部分用于于估计代代价的目目录信息息有关关系系的统计计信息nr：关系R中的元组组数目br：含有关系系R的元组的的块数目目sr：关系R中一个元元组的大大小fr：关系R的块因子子，即一一个块中中能存放放的关系系R的元组数数若假定关

3、关系R的元组物物理上存存于同一一文件中中，则：br=nr/ fr一个重要要的影响响因素：主存中中缓冲区区的大小小M最好的情情形最坏的情情形8.1.3相关基本本概念(续)查询优化化为关系代代数表达达式的计计算选择择最有效效的查询询计划的的过程。查询执行行计划用于计算算一个查查询的原原语序列列。执行原语语加了“如如何执行行”注释释的关系系代数运运算。查询优化化的过程程代数优化化物理优化化详细策略略的选择择优化器8.1.4查询优化化概述例：求选选修了2号课程程的学生生姓名SELECTStudent.SnameFROMStudent,SCWHEREStudent.Sno=SC.SnoANDSC.Cno

4、=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

5、Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC)2）2name(SC.Cno=2(StudentSC)3）3Sname(StudentSC.Cno=2(SC)1Q1Sname(Student.Sno=SC.SnoSC.Cno=2(StudentSC) StudentSC读取总块块数=读读Student表块数+读读SC表遍数*每遍块块数(读SC表遍数=Student表的总元元组数/在内存存中的元元组数)=1000/10+(1000/(105) (10000/100)=100+20100=2100读数据时时间=2100/20=105秒秒1 查询询优化的的必要性

6、性(续)8.1.4查询优化化概述中间结果果大小=1000*10000 =107(1千万万条元组组)写中间结结果时间间= 10000000/10/20 =50000秒秒（设每块能能装10个中间间结果元元组）读数据时时间= 50000秒总时间=1055000050000秒= 100105秒= 27.8小小时8.1.4查询优化化概述1 查询询优化的的必要性性(续)2.2name(SC.Cno=2(StudentSC)读取总块块数=2100块（Q1的结果）读数据时时间=2100/20=105秒秒因为只有有SC只有10000条元组组，故等等值连接接的结果果,即:中间结果果大小=10000（减减少1000

7、倍倍）写中间结结果时间间=10000/10/20=50秒秒读数据时时间=50秒秒总时间1055050秒205秒秒=3.4分（减少了了中间结结果）8.1.4查询优化化概述1 查询询优化的的必要性性(续)3.3Sname(StudentSC.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.4name(Stude

8、ntSC.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查询优化化概述用户不必必考虑如如何最好好地表达达查询以以获得较较好

9、的效效率。关系数据据语言的的级别很高高，使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 查询询优化的的可能

10、性性(续)优化器可可以从数数据字典典中获取取许多信信息(包包括统计计信息和和索引信信息)，而用户户程序则则难以获获得这些些信息。如果数据据库的物物理统计计信息改改变了，系统可可以自动动对查询询重新优化化以选择相相适应的的执行计计划。在在非关关系系统统中必须须重写程程序，而而重写程程序在实实际应用用中往往往是不太太可能的的。优化器可可以考虑虑数百种种不同的的执行计计划，而而程序员员一般只只能考虑虑有限的的几种可可能性。优化器中中包括了了很多复复杂的优优化技术术查询优化化的总目目标选择有效效策略，求得给给定关系系表达式式的值8.1.4查询优化化概述3 查询询优化的的目标代价模型型：集中式数数据库单

11、用户系系统总代价=I/O代价+CPU代价多用户系系统总代价=I/O代价+CPU代价+ 内存存代价分布式数数据库总代价=I/O代价+CPU代价+ 内存存代价 +通通信代代价8.1.4查询优化化概述3 查询询优化的的目标（续）8.2基本运算算实现举举例1.运运算特点点每一个基基本的代代数运算算都有多多种不同同的实现现算法适用于不不同的情情况执行代价价不同2.选选择运算算的实现现3.连连接运算算的实现现8.2基本运算算实现举举例(续续)2.选选择运算算的实现现全表扫描描方法：依依次访问问表的每每一个块块，对于于每一个个元组，测试它它是否满满足选择择条件。代价：E =br索引扫描描条件：表表在选择择条

12、件的的属性上上建有索索引。方法：访访问索引引，根据据索引项项的指示示去访问问数据元元组。代价：8.2基本运算算实现举举例(续续)3.连连接运算算的实现现嵌套循环环连接块嵌套循循环连接接索引嵌套套循环连连接排序-归归并连接接散列连接接8.2基本运算算实现举举例(续续)3.连连接运算算的实现现嵌套循环环连接foreach元组trinR dobeginforeach元组tsinS dobegin测试元组组对(tr,ts)是否满足足连接条条件如果满足足，把tr ts加到结果果中endend8.2基本运算算实现举举例(续续)3.连连接运算算的实现现嵌套循环环连接优点：对对参加运运算的关关系没有有要求，适

13、合于于任何连连接条件件。代价：最坏情况况（缓冲冲区只能能够容纳纳每个关关系的一一个块）最好情况况（内层层关系S能完全放放在内存存中）bs+ br8.2基本运算算实现举举例(续续)3.连连接运算算的实现现排序-归归并连接接类似于外外排序的的归并算算法的思思路，进进行连接接运算。前提：两两个关系系的元组组已按连连接属性性排好序序。适用于自自然连接接和等值值连接。排序-归归并连接接a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3 在归并连接中使用的已排序关系rs8.3查询优化化的选择择执行8.3.1表达式等等价S#(C#= 001C#= 002(SC)S#(C#= 001(

14、SC)S#(C#= 002(SC)8.3.2两类主要要的优化化算法8.3.3启发式优优化8.3.4查询优化化的一般般步骤8.3.1表达式等等价1.语语法树2.表表达式等等价的定定义3.表表达式的的等价规规则8.3.1表达式等等价(续续)语法树（查询树树）叶子节点点：关系系内节点：关系代代数操作作执行方式式：自底底向上 customer_namebalance |关系代数数表达式式的语法法树：customer_name（balance |depositor)8.3.1表达式等等价(续续)3.常常用等价价变换规规则说明：E、E1、E2等表示关关系代数数表达式式连接、笛笛卡尔积积交换律律连接、笛笛卡

15、尔积积的结合合律投影的串串接定律律选择的串串接定律律选择与投投影的交交换律选择与笛笛卡尔积积的交换换律选择与并并的交换换选择与差差运算的的交换投影与笛笛卡尔积积的交换换投影与并并的交换换关系代数数表达式式等价指用相同同的关系系代替两两个表达达式中相相应的关关系所得得到的结结果是相相同的上面的优优化策略略大部分分都涉及及到代数数表达式式的变换换8.3.1表达式等等价(续续)设E1、E2等是关系系代数表表达式，F是条件表表达式 l.连接、笛笛卡尔积积交换律律E1E2 E2E1E1E2E2E1E1FE2E2FE18.3.1表达式等等价(续续)2.连连接、笛笛卡尔积积的结合合律(E1E2)E3 E1

16、(E2E3)(E1E2)E3 E1(E2E3)(E1E2)E3 E1(E2E3)FFFF8.3.1表达式等等价(续续)3. 投影影的串接接定律A1,A2,An(B1,B2,Bm(E)A1,A2,An(E)假设：1)E是关系代代数表达达式2)Ai(i=1，2，n),Bj(j=l，2，m)是属性名名3)A1, A2, , An构成Bl，B2，Bm的子集8.3.1表达式等等价(续续)8.选择的串串接定律律F1（F2（E）F1F2(E)选择的串串接律说说明选选择择条件可可以合并并这样一次次就可检检查全部部条件。8.3.1表达式等等价(续续)5.选选择与投投影的交交换律(1)假假设:选选择条条件F只涉及

17、属属性A1，AnF(A1,A2,An(E)A1,A2,An(F(E)(2)假设:F中有不属属于A1,An的属性B1,BmA1,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中的属性性，

18、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表达式等等

19、价(续续)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.两两类主要要的优化化算法基于代价价的方

20、法法通过使用用等价规规则为给给定的查查询语句句产生一一系列查查询执行行计划，并选择择其中代代价最小小或接近近最小的的启发式方方法运用启发发式规则则，对关关系代数数表达式式进行等等价变换换8.3.3启发式优优化1.启启发式优优化的常常用规则则选择运算算应尽可可能先做做投影运算算应尽可可能先做做在执行连连接前对对关系适适当地预预处理把投影运运算和选选择运算算同时进进行把投影同同其前或或其后的的双目运运算结合合起来找出公共共子表达达式8.3.4关系代数数表达式式的优化化算法算法：关关系表达达式的优优化输入：一一个关系系表达式式的语法法树。输出：计计算该表表达式的的程序。方法：（1）分分解选择择运算利

21、用规则则4把形形如F1F2 Fn(E)变换为F1(F2(Fn(E)8.3.4关系代数数表达式式的优化化算法（2）通通过交换换选择运运算，将将其尽可可能移到到叶端对每一个个选择，利用规规则48尽可可能把它它移到树树的叶端端。（3）通通过交换换投影运运算，将将其尽可可能移到到叶端对每一个个投影利利用规则则3，9，l0，5中的一般般形式尽尽可能把把它移向向树的叶叶端。8.3.4关系代数数表达式式的优化化算法（4）合合并串接接的选择择和投影影，以便便能同时时执行或或在一次次扫描中中完成利用规则则35把选择择和投影影的串接接合并成成单个选选择、单单个投影影或一个个选择后后跟一个个投影。使多个选选择或投投

22、影能同同时执行行，或在在一次扫扫描中全全部完成成尽管这种种变换似似乎违背背“投影影尽可能能早做”的原则则，但这这样做效效率更高高。8.3.4关系代数数表达式式的优化化算法（5）对对内结点点分组把上述得得到的语语法树的的内节点点分组。每一双目目运算(，-)和它所所有的直直接祖先先为一组组(这些些直接祖祖先是，运算)。如果其后后代直到到叶子全全是单目目运算，则也将将它们并并入该组组，但当当双目运运算是笛笛卡尔积积()，而且且其后的的选择不不能与它它结合为为等值连连接时除除外。把把这些单单目运算算单独分分为一组组。8.3.4关系代数数表达式式的优化化算法（6）生生成程序序生成一个个程序，每组结结点的

23、计计算是程程序中的的一步。各步的顺顺序是任任意的，只要保保证任何何一组的的计算不不会在它它的后代代组之前前计算。例子考虑应用用：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）由由于选择

24、择和投影影的可交交换，把把条件date960101移到最下下端title(date960101(loans)borrowers)books)例子例子（4）分分组查询询树8.3.4查询优化化的一般般步骤1.把把查询转转换成某某种内部部表示2.把语语法树转转换成标标淮(优优化)形形式3.选择择低层的的存取路路径8.生成查询询计划，选择代代价最小小的举例求选修了了2号课程的的学生姓姓名。8.4sql语句优优化目标有利于DBMS选择代价价最小的的查询执执行计划划依据DBMS优化器支支持的优优化策略略 8.4sql语句优优化Sql语句一般般优化策策略充分利用索引引尽量避免免表搜索索减少不必必要的运运算8

25、.4sql语句优优化1.搜搜索参数数化带有=、=、=等操作作符的条条件查询询就可以以直接使使用索引引。如：id= T0001,salary30000,a=1 andc =7。下列则不不是搜索索参数：salary=commission,dept!=10,salary *12=30000,age218.4sql语句优优化在查询中中可以提提供一些些冗余的的搜索参参数,使使优化器器有更多多的选择择余地。如title和titleauthor两张表是是一对多多的关系系,同样样的查询询条件我我们有以以下三种种表现方方法:SELECTtitle_id, title FROMtitles,titleauthor

26、WHEREtitle.title_id= titleauthor.title_idANDtitleauthor.title_id=T81002SELECT title_id,titleFROM titles,titleauthorWHEREtitle.title_id= titleauthor.title_idANDtitle.title_id=T81002SELECT title_id,titleFROM titles,titleauthorWHEREtitle.title_id= titleauthor.title_idANDtitle.title_id=T81002ANDtitleaut

27、hor.title_id=T81002三种方法法一种比比一种要要好,因因为后者者为优化化器提供供了更多多的选择择机会。8.4sql语句优优化2.避免使用用不兼容容的数据据类型SELECTnameFROM employee WHERE salary 600003.ISNULL与ISNOTNULL在where子句中使使用isnull或isnotnull的语句优优化器是是不允许许使用索索引的8.在海量查查询时尽尽量少用用格式转转换wherecast(salaryaschar(2)= 905.避免不不同数据据类型间间的连接接运算 8.4sql语句优优化6.避免免where子句中的的“=”左边进进行函数

28、数、算术术运算或或其他表表达式运运算，否否则系统统将可能能无法正正确使用用索引。whereLeft(xsbh,2)=01wherexsbh =like01%SQL优优化实例例oracle例1：RLWT(STCD,TM,LV)水位表表查询当前前时间前前一个小小时的时时刻的水水位记录录SELECT*FROMRLWTWHERETM+1 =SYSDATE;SELECT*FROMRLWTWHERETM=SYSDATE1;SELECT*FROMRLWTWHERETM= TO_DATE(2006-04-267:00:00,YY-MM-DDHH24:MI:SS)SELECTSTCD,TM,LVFROMRLWTWHERETM= TO_DATE(2006-04-267:00:00,YY-MM-DDHH24:MI:SS)例2：查查选修了了01号课程程的学生生姓名。SELECTSNAMEFROMSTUDENTWHERE01IN(SELECT CNOFROM SCWHERESNO=STUDENT.SNO);SELECTSNAMEFROMSTUDENT,SCWHERESC.SNO=STUDENT.SNOANDSC.CNO=01例3：