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

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  查询处理的执行步骤§ 语法分析与翻译§ 优化§ 执行语法分析与翻译语法分析与翻译关系代数表达式关系代数表达式执行计划执行计划优化器优化器查询语句查询语句执行引擎执行引擎查询结果查询结果有关数据的统计值有关数据的统计值数据数据74.1.3 相关基本概念§查询代价§查询处理对各种资源的使用情况•磁盘存取 （简化为磁盘块传送数）•CPU时间•通信开销•内存开销 COSTCPU(PLAN)COSTI/O(PLAN)PLAN19.2 CPU seconds103 readsPLAN21.7CPU seconds890 reads84.1.3 相关基本概念(续)§部分用于估计代价的目录信息§有关关系的统计信息•nr：关系R中的元组数目•br：含有关系R的元组的块数目•sr ：关系R中一个元组的大小•fr ：关系R的块因子，即一个块中能存放的关系R的元组数若假定关系R的元组物理上存于同一文件中，则： 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：外存：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：连接方法：基于数据块的嵌套循环法4.1.4 查询优化概述 1 查询优化的必要性(续)124.1.4 查询优化概述1 查询优化的必要性(续)几种不同的实现方法：1） Q1＝ ПSname(бStudent.Sno=SC.Sno ∧SC.Cno='2' (Student×SC))2）Ｑ2＝ ПＳname(бSC.Cno=' 2' (Student SC))3）Ｑ3＝ ПSname(Student бSC.Cno=' 2' (SC)) 131 Q1＝  ПSname(бStudent.Sno=SC.Sno ∧SC.Cno='2' (Student×SC)) ① Student×SC   读取总块数= 读Student表块数 + 读SC表遍数                          *每遍块数(读SC表遍数=Student表的总元组数/在内存中的元组数) =1000/10+(1000/(10×5)) ×(10000/100)             =100+20×100=2100   读数据时间=2100/20=105秒1 查询优化的必要性(续)4.1.4查询优化概述 14中间结果大小 = 1000*10000 = 107       (1千万条元组)写中间结果时间 = 10000000/10/20 = 50000秒（设每块能装10个中间结果元组） ②б读数据时间 = 50000秒 ③П总时间 =105＋50000＋50000秒 = 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秒 ③П 总时间＝105＋50＋50秒＝205秒=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秒 ③ П 总时间＝5＋5秒＝10秒 （减少中间结果,且全部在内存）1 查询优化的必要性(续)4.1.4查询优化概述 174. Ｑ4＝ ПＳname(Student     бSC.Cno='2' (SC))假设SC表在Cno上有索引，Student表在Sno上有索引 ①б  读SC表索引=（发现2号课程只有50条元组）读SC表总块数= 50/100<1块读数据时间:1/20=0.5 中间结果大小=50条  不必写入外存1 查询优化的必要性(续)4.1.4查询优化概述 18②  读Student表索引=(根据索引发现只有50个学生)读Student表总块数= 50/10=5块读数据时间 ：5/20=0.5秒③ П总时间<1~2秒（不必遍历所有的元组记录）1 查询优化的必要性(续)4.1.4查询优化概述 19§用户不必考虑如何最好地表达查询以获得较好的效率。

§关系数据语言的级别很高，使DBMS可以从关系表达式中分析查询语义§系统可以比用户程序的优化做得更好2 查询优化的可能性4.1.4查询优化概述 20Student×SC（做SC×Student）     读取总块数= 读SC表块数 + 读Student表遍数                          *每遍块数(读Student表遍数=SC表的总元组数/在内存中的元组数)=10000/100+(10000/(100×1)) ×(1000/10)          =100+100×100=10100   读数据时间=10100/20=505秒2 查询优化的可能性(续)4.1.4查询优化概述 214.1.4查询优化概述 2 查询优化的可能性(续)(1)优化器可以从数据字典中获取许多信息(包括统计信息和索引信息)，而用户程序则难以获得这些信息2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划    在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的3)优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性4)优化器中包括了很多复杂的优化技术22§查询优化的总目标    选择有效策略，求得给定关系表达式的值4.1.4查询优化概述 3 查询优化的目标23代价模型：§集中式数据库•单用户系统总代价 = I/O代价 + CPU代价•多用户系统总代价 = I/O代价 + CPU代价 + 内存代价§分布式数据库 总代价 = I/O代价 + CPU代价[+ 内存代价] + 通信代价 4.1.4查询优化概述 3 查询优化的目标（续）244.2 基本运算实现举例§1. 运算特点§每一个基本的代数运算都有多种不同的实现算法•适用于不同的情况•执行代价不同§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               测试元组对(tr,ts)是否满足连接条件θ              如果满足，把tr  ts加到结果中            end      end284.2 基本运算实现举例(续)§3. 连接运算的实现§嵌套循环连接•优点：对参加运算的关系没有要求，适合于任何连接条件•代价： 最坏情况（缓冲区只能够容纳每个关系的一个块） 最好情况（内层关系S能完全放在内存中） bs + br294.2 基本运算实现举例(续)§3. 连接运算的实现§排序-归并连接•类似于外排序的归并算法的思路，进行连接运算。

•前提：两个关系的元组已按连接属性排好序•适用于自然连接和等值连接30•排序-归并连接a3b1d8d13f7m5q6aAaGcLdNmB r sa1a2a1a3 在归并连接中使用的已排序关系在归并连接中使用的已排序关系rs314.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 < 2500customeraccount|><|关系代数表达式的语法树：Пcustomer_name（（σbalance < 2500(account)|><|customer））354.3.1 表达式等价(续)§2. 表达式等价的定义§定义•两个表达式等价：产生的结果关系具有相同的属性集和相同的元组集。

Пcustomer_name (σbranch-city=””Brooklyn” (branch|><|(account |><| depositor))) 等价于等价于 Пcustomer_name ((σbranch-city=””Brooklyn” (branch))|><|(account |><| depositor))364.3.1 表达式等价(续)§3. 常用等价变换规则说明：E、E1、E2等表示关系代数表达式§连接、笛卡尔积交换律§连接、笛卡尔积的结合律§投影的串接定律§选择的串接定律§选择与投影的交换律§选择与笛卡尔积的交换律§选择与并的交换§选择与差运算的交换§投影与笛卡尔积的交换§投影与并的交换37§关系代数表达式等价§指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的§上面的优化策略大部分都涉及到代数表达式的变换4.3.1 表达式等价(续)38设E1、E2等是关系代数表达式，F是条件表达式 l. 连接、笛卡尔积交换律E1× E2≡ E2×E1E1      E2≡E2     E1         E1  F   E2≡E2  F   E1      4.3.1 表达式等价(续)39 2. 连接、笛卡尔积的结合律    (E1×E2) × E3 ≡ E1 × (E2×E3)    (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. 选择与投影的交换律(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 (E1×E2)≡бF (E1)×E2 (2) 假设：F=F1∧F2，并且F1只涉及E1中的属性，                 F2只涉及E2中的属性  则由上面的等价变换规则1，4，6可推出：       бF(E1×E2) ≡б F1(E1)×бF2 (E2) 4.3.1 表达式等价(续)44(3) 假设： F=F1∧F2，                   F1只涉及E1中的属性，                   F2涉及E1和E2两者的属性  бF(E1×E2)≡б F2(бF1(E1)×E2)            它使部分选择在笛卡尔积前先做 4.3.1 表达式等价(续)457. 选择与并的交换假设：E=E1∪E2，E1，E2有相同的属性名бF(E1∪E2)≡ б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 （E1×E2)≡π A1,A2, …,An（E1)× π B1,B2, …,Bm(E2)4.3.1 表达式等价(续)47l0. 投影与并的交换假设：E1和E2 有相同的属性名       π A1,A2, …,An(E1∪E2)≡    π A1,A2, …,An(E1)∪ π A1,A2, …,An(E2) 4.3.1 表达式等价(续)48l0. 投影与并的交换假设：E1和E2 有相同的属性名       π A1,A2, …,An(E1∪E2)≡    π A1,A2, …,An(E1)∪ π A1,A2, …,An(E2) 4.3.1 表达式等价(续)494.3.1 表达式等价(续)§3. 常用等价变换规则说明：  规则只说明两个表达式等价，并不说明哪一个更好。

 连接的次序很重要，好的连接次序序列产生小的中间结果504.3.2 两类主要的优化算法§1. 两类主要的优化算法§ 基于代价的方法•通过使用等价规则为给定的查询语句产生一系列查询执行计划，并选择其中代价最小或接近最小的§ 启发式方法•运用启发式规则，对关系代数表达式进行等价变换514.3.3 启发式优化§1. 启发式优化的常用规则§选择运算应尽可能先做§投影运算应尽可能先做§在执行连接前对关系适当地预处理§把投影运算和选择运算同时进行§把投影同其前或其后的双目运算结合起来§找出公共子表达式524.3.3 启发式优化§2. 启发式优化的步骤§使用选择串接律，将合取选择分解为单个选择运算的序列这有助于将选择运算往查询树下层移动§使用规则4~8尽可能把查询操作移到树的叶端 §每一个投影利用规则(3)，(9)，(l0)，(5)中的一般形式尽可能把它移向树的叶端§利用规则(3)～(5)把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影使多个选择或投影能同时执行，或在一次扫描中全部完成§使用规律(2)重新安排叶节点，使得具有最小操作选择的叶节点最先执行§ 把笛卡儿积和相继的选择操作连接起来形成连接操作§把最后的查询树划分为多个子树，使得每个子树上的操作可以由单个存取程序一次完成。

§产生一个计算最后查询树的程序，每一步计算一个子树534.3.4 查询优化的一般步骤§1. 把查询转换成某种内部表示§2.把语法树转换成标淮(优化)形式§3.选择低层的存取路径§4.生成查询计划，选择代价最小的544.4 sql语句优化§目标   有利于DBMS选择代价最小的查询执行计划§依据   DBMS优化器支持的优化策略   554.4 sql语句优化Sql语句一般优化策略§充分利用索引§尽量避免表搜索§减少不必要的运算 564.4 sql语句优化1. 搜索参数化   带有=、＜、＞、＞=、＜=等操作符的条件查询就可以直接使用索引 如：   id = "T0001",salary＞30000,a = 1 and c = 7   下列则不是搜索参数：   salary = commission,dept != 10,salary *12 ＞= 30000,age<>21574.4 sql语句优化在查询中可以提供一些冗余的搜索参数,使优化器有更多的选择余地如title和titleauthor两张表是一对多的关系,同样的查询条件我们有以下三种表现方法: ●SELECT title_id, 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.title_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)) = ‘90’5.避免不同数据类型间的连接运算 59604.4 sql语句优化6.避免where子句中的“=”左边进行函数、算术运算或其他表达式运算，否则系统将可能无法正确使用索引    where Left(xsbh,2) = ‘01’   where xsbh = like ’01%’61。