数据库技术与应用课件第四章关系数据库查询优化.ppt

1、1第四章 关系数据库查询优化2 学习内容4.1 查询处理概述4.2 基本运算实现举例4.3 查询优化的选择执行4.4 sql语句优化参考：B3第十二章3 学习目标了解查询处理的过程了解查询优化的步骤掌握关系代数等价变换规则了解启发式优化的方法44.1 查询处理概述4.1.1 查询处理的定义4.1.2 查询处理的执行步骤4.1.3 相关基本概念54.1.1 查询处理的定义1.定义2.包括的主要内容 表达式 转换 执行3.输入、输出64.1.2 查询处理的执行步骤 语法分析与翻译 优化 执行语法分析与翻译语法分析与翻译关系代数表达式关系代数表达式执行计划执行计划优化器优化器查询语句查询语句执行引擎

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

3、上存于同一文件中，则：br =nr/fr 一个重要的影响因素：主存中缓冲区的大小M 最好的情形 最坏的情形94.1.3 相关基本概念(续)查询优化 为关系代数表达式的计算选择最有效的查询计划的过程。查询执行计划 用于计算一个查询的原语序列。执行原语 加了“如何执行”注释的关系代数运算。查询优化的过程 代数优化 物理优化 详细策略的选择优化器104.1.4 查询优化概述 例：求选修了2号课程的学生姓名 SELECT Student.SnameFROM Student,SCWHERE Student.Sno=SC.SnoAND SC.Cno=2;1 查询优化的必要性（续）11假设1：外存：Stud

4、ent: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：连接方法：基于数据块的嵌套循环法4.1.4 查询优化概述 1 查询优化的必要性(续)124.1.4 查询优化概述1 查询优化的必要性(续)几种不同的实现方法：1）Q1 Sname(Student.Sno=SC.Sno SC.Cno=2(StudentSC)2）2 na

5、me(SC.Cno=2(Student SC)3）3 Sname(Student SC.Cno=2(SC)131 Q1 S n a m e(S t u d e n t.S n o=S C.S n o S C.C n o=2 (StudentSC)StudentSC 读取总块数=读Student表块数+读SC表遍数 *每遍块数(读SC表遍数=Student表的总元组数/在内存中的元组数)=1000/10+(1000/(105)(10000/100)=100+20100=2100 读数据时间=2100/20=105秒1 查询优化的必要性(续)4.1.4查询优化概述 14中间结果大小=1000*10

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

7、秒=3.4分（减少了中间结果）4.1.4查询优化概述 1 查询优化的必要性(续)163.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 查询优化的必要性(续)4.1.4查询优化概述 174.4 name(Student SC.Cno=2(SC)假设SC表在Cno上有索引，Student表在Sno上有索引 读SC表索引=（发现2号课程只有50条元

8、组）读SC表总块数=50/1001块读数据时间:1/20=0.5 中间结果大小=50条 不必写入外存1 查询优化的必要性(续)4.1.4查询优化概述 18 读Student表索引=(根据索引发现只有50个学生)读Student表总块数=50/10=5块读数据时间：5/20=0.5秒 总时间12秒（不必遍历所有的元组记录）1 查询优化的必要性(续)4.1.4查询优化概述 19 用户不必考虑如何最好地表达查询以获得较好的效率。关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义。系统可以比用户程序的优化做得更好。2 查询优化的可能性4.1.4查询优化概述 20StudentSC（做SC

9、Student）读取总块数=读SC表块数+读Student表遍数 *每遍块数(读Student表遍数=SC表的总元组数/在内存中的元组数)=10000/100+(10000/(1001)(1000/10)=100+100100=10100 读数据时间=10100/20=505秒2 查询优化的可能性(续)4.1.4查询优化概述 214.1.4查询优化概述 2 查询优化的可能性(续)(1)优化器可以从数据字典中获取许多信息(包括统计信息和索引信息)，而用户程序则难以获得这些信息。(2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重

10、写程序在实际应用中往往是不太可能的。(3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术22 查询优化的总目标 选择有效策略，求得给定关系表达式的值4.1.4查询优化概述 3 查询优化的目标23代价模型：集中式数据库 单用户系统总代价=I/O代价+CPU代价 多用户系统总代价=I/O代价+CPU代价+内存代价 分布式数据库 总代价=I/O代价+CPU代价+内存代价+通信代价 4.1.4查询优化概述 3 查询优化的目标（续）244.2 基本运算实现举例1.运算特点 每一个基本的代数运算都有多种不同的实现算法 适用于不同的情况 执行

11、代价不同2.选择运算的实现3.连接运算的实现254.2 基本运算实现举例(续)2.选择运算的实现 全表扫描 方法：依次访问表的每一个块，对于每一个元组，测试它是否满足选择条件。代价：E=br 索引扫描 条件：表在选择条件的属性上建有索引。方法：访问索引，根据索引项的指示去访问数据元组。代价：264.2 基本运算实现举例(续)3.连接运算的实现 嵌套循环连接 块嵌套循环连接 索引嵌套循环连接 排序-归并连接 散列连接274.2 基本运算实现举例(续)3.连接运算的实现 嵌套循环连接 for each元组tr in R do begin for each元组ts in S do begin 测试元

12、组对(tr,ts)是否满足连接条件 如果满足，把tr ts加到结果中 end end284.2 基本运算实现举例(续)3.连接运算的实现 嵌套循环连接 优点：对参加运算的关系没有要求，适合于任何连接条件。代价：最坏情况（缓冲区只能够容纳每个关系的一个块）最好情况（内层关系S能完全放在内存中）bs+br294.2 基本运算实现举例(续)3.连接运算的实现 排序-归并连接 类似于外排序的归并算法的思路，进行连接运算。前提：两个关系的元组已按连接属性排好序。适用于自然连接和等值连接。30排序-归并连接a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3 在归并连接中使用的已排序

13、关系在归并连接中使用的已排序关系rs314.3 查询优化的选择执行4.3.1 表达式等价 S#(C#=001 C#=002(SC)S#(C#=001(SC)S#(C#=002(SC)4.3.2 两类主要的优化算法4.3.3 启发式优化4.3.4 查询优化的一般步骤324.3.1 表达式等价1.语法树2.表达式等价的定义3.表达式的等价规则334.3.1 表达式等价(续)语法树（查询树）叶子节点：关系 内节点：关系代数操作 执行方式：自底向上34 customer_name balance|关系代数表达式的语法树：customer_name（balance|depositor)364.3.1 表

14、达式等价(续)3.常用等价变换规则说明：E、E1、E2等表示关系代数表达式 连接、笛卡尔积交换律 连接、笛卡尔积的结合律 投影的串接定律 选择的串接定律 选择与投影的交换律 选择与笛卡尔积的交换律 选择与并的交换 选择与差运算的交换 投影与笛卡尔积的交换 投影与并的交换37 关系代数表达式等价 指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的 上面的优化策略大部分都涉及到代数表达式的变换4.3.1 表达式等价(续)38设E1、E2等是关系代数表达式，F是条件表达式 l.连接、笛卡尔积交换律E1 E2 E2E1E1 E2E2 E1 E1 F E2E2 F E1 4.3.1 表达式等价

15、(续)39 2.连接、笛卡尔积的结合律 (E1E2)E3 E1 (E2E3)(E1 E2)E3 E1 (E2 E3)(E1 E2)E3 E1 (E2 E3)F F F F4.3.1 表达式等价(续)403.投影的串接定律 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的子集 4.3.1 表达式等价(续)414.选择的串接定律 F1（F2（E）F1 F2(E)选择的串接律说明 选择条件可以合并 这样一次就可检查全部条件。4.3.1 表达式等价(续)425.

16、选择与投影的交换律(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)4.3.1 表达式等价(续)436.选择与笛卡尔积的交换律(1)假设：F中涉及的属性都是E1中的属性 F(E1E2)F(E1)E2(2)假设：F=F1F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性 则由上面的等价变换规则1，4，6可推出：F(E1E2)F1(E1)F2(E2)4.3.1 表达式等价(续)44(3)假设：F=F1F2，F

17、1只涉及E1中的属性，F2涉及E1和E2两者的属性 F(E1E2)F2(F1(E1)E2)它使部分选择在笛卡尔积前先做 4.3.1 表达式等价(续)457.选择与并的交换假设：E=E1E2，E1，E2有相同的属性名F(E1E2)F(E1)F(E2)8.选择与差运算的交换假设：E1与E2有相同的属性名F(E1-E2)F(E1)-F(E2)4.3.1 表达式等价(续)469.投影与笛卡尔积的交换假设：E1和E2是两个关系表达式，A1，An是E1的属性，B1，Bm是E2的属性 A1,A2,An,B1,B2,Bm（E1E2)A1,A2,An（E1)B1,B2,Bm(E2)4.3.1 表达式等价(续)4

18、7l0.投影与并的交换假设：E1和E2 有相同的属性名 A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)4.3.1 表达式等价(续)48l0.投影与并的交换假设：E1和E2 有相同的属性名 A1,A2,An(E1E2)A1,A2,An(E1)A1,A2,An(E2)4.3.1 表达式等价(续)494.3.1 表达式等价(续)3.常用等价变换规则说明：规则只说明两个表达式等价，并不说明哪一个更好。连接的次序很重要，好的连接次序序列产生小的中间结果。504.3.2 两类主要的优化算法1.两类主要的优化算法 基于代价的方法 通过使用等价规则为给定的查询语句产生一系列查询执

19、行计划，并选择其中代价最小或接近最小的 启发式方法 运用启发式规则，对关系代数表达式进行等价变换514.3.3 启发式优化1.启发式优化的常用规则 选择运算应尽可能先做 投影运算应尽可能先做 在执行连接前对关系适当地预处理 把投影运算和选择运算同时进行 把投影同其前或其后的双目运算结合起来 找出公共子表达式524.3.3 启发式优化2.启发式优化的步骤使用选择串接律，将合取选择分解为单个选择运算的序列。这有助于将选择运算往查询树下层移动。使用规则48尽可能把查询操作移到树的叶端。每一个投影利用规则(3)，(9)，(l0)，(5)中的一般形式尽可能把它移向树的叶端。利用规则(3)(5)把选择和投

20、影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成使用规律(2)重新安排叶节点，使得具有最小操作选择的叶节点最先执行。把笛卡儿积和相继的选择操作连接起来形成连接操作把最后的查询树划分为多个子树，使得每个子树上的操作可以由单个存取程序一次完成。产生一个计算最后查询树的程序，每一步计算一个子树。534.3.4 查询优化的一般步骤1.把查询转换成某种内部表示2.把语法树转换成标淮(优化)形式3.选择低层的存取路径4.生成查询计划，选择代价最小的544.4 sql语句优化 目标 有利于DBMS选择代价最小的查询执行计划 依据 DBMS优化器支持的

21、优化策略 554.4 sql语句优化Sql语句一般优化策略 充分利用索引 尽量避免表搜索 减少不必要的运算 564.4 sql语句优化1.搜索参数化 带有=、=、=等操作符的条件查询就可以直接使用索引。如：id=T0001,salary30000,a=1 and c=7。下列则不是搜索参数：salary=commission,dept!=10,salary*12=30000,age21574.4 sql语句优化在查询中可以提供一些冗余的搜索参数,使优化器有更多的选择余地。如title和titleauthor两张表是一对多的关系,同样的查询条件我们有以下三种表现方法:SELECT title_i

22、d,title FROM titles,titleauthor WHERE title.title_id=titleauthor.title_id AND titleauthor.title_id=T81002 SELECT title_id,title FROM titles,titleauthor WHERE title.title_id=titleauthor.title_id AND title.title_id=T81002 SELECT title_id,title FROM titles,titleauthor WHERE title.title_id=titleauthor.t

23、itle_id AND title.title_id=T81002 AND titleauthor.title_id=T81002 三种方法一种比一种要好,因为后者为优化器提供了更多的选择机会。584.4 sql语句优化2.避免使用不兼容的数据类型 SELECT name FROM employee WHERE salary 60000 3.IS NULL 与 IS NOT NULL 在where子句中使用is null或is not null的语句优化器是不允许使用索引的4.在海量查询时尽量少用格式转换 where cast(salary as char(2)=905.避免不同数据类型间的连接运算 59604.4 sql语句优化6.避免where子句中的“=”左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引。where Left(xsbh,2)=01 where xsbh=like 01%61