第9章关系查询处理和查询优化

1、9.1 关系数据库系统的查询处理关系数据库系统的查询处理9.2 关系数据库系统的查询优化关系数据库系统的查询优化9.3 代数优化代数优化9.4 物理优化物理优化9.5 小结小结9.1.1 查询处理的步骤查询处理的步骤 RDBMS查询处理可以分为查询处理可以分为4个阶段：个阶段：查询分析查询分析查询检查查询检查查询优化查询优化查询执行查询执行 查询处理的任务是把用户提交给查询处理的任务是把用户提交给RDBMS的的查询语句转换为高效的执行计划。查询语句转换为高效的执行计划。1、查询分析、查询分析 对查询语句进行扫描、词法分析和语法分析，对查询语句进行扫描、词法分析和语法分析， 即判断查询语句是否符

2、合即判断查询语句是否符合SQL的语法规则。的语法规则。2、查询检查、查询检查 （1）根据数据字典对合法的查询语句进行语义检查。）根据数据字典对合法的查询语句进行语义检查。 检查语句中的数据库对象（如属性名、关系名）检查语句中的数据库对象（如属性名、关系名） 是否存在和是否有效。是否存在和是否有效。（2） 根据数据字典中的用户权限和完整性约束定义根据数据字典中的用户权限和完整性约束定义 对用户的存取权限进行检查。对用户的存取权限进行检查。（3）将检查通过的查询语句转换成等价的关系代数）将检查通过的查询语句转换成等价的关系代数 表达式。（语法分析树）表达式。（语法分析树）3、查询优化、查询优化(Q

3、uery Optimization) 每个查询都会有许多可供选择的执行策略和操作每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询策略。算法，查询优化就是选择一个高效执行的查询策略。 查询优化有多种途径：查询优化有多种途径：（1）代数优化）代数优化 将查询语句转换成为相应的关系代数表达式，然将查询语句转换成为相应的关系代数表达式，然后按照一定的规则，改变关系代数表达式的操作次序后按照一定的规则，改变关系代数表达式的操作次序和组合进行优化，借此来改变基本操作的次序，使查和组合进行优化，借此来改变基本操作的次序，使查询语句执行起来更有效。询语句执行起来更有效。 这种

4、查询优化仅涉及查询语句本身，而不涉及存这种查询优化仅涉及查询语句本身，而不涉及存取路径，是独立于存取路径的优化。取路径，是独立于存取路径的优化。（2）物理优化）物理优化 根据系统提供的存取路径，选择合理的存取路径根据系统提供的存取路径，选择合理的存取路径 和底层操作算法和底层操作算法(例如选用顺序搜索或索引进行查找例如选用顺序搜索或索引进行查找)， 是依赖于存取路径的优化。是依赖于存取路径的优化。（3）规则优化）规则优化 查询的优化仅根据启发式规则选择执行的策略。查询的优化仅根据启发式规则选择执行的策略。（4）代价估算优化）代价估算优化 对各种可供选择的策略进行代价估算，从中选用对各种可供选择

5、的策略进行代价估算，从中选用代价最小的执行策略。代价最小的执行策略。 实际实际RDBMS中的查询优化器都综合运用了这些中的查询优化器都综合运用了这些优化技术，以获得最好的查询优化效果。优化技术，以获得最好的查询优化效果。4、查询执行、查询执行 依据优化器得到的执行策略生成查询计划，由代码依据优化器得到的执行策略生成查询计划，由代码生成器（生成器（code generator）生成执行这个查询计划的代）生成执行这个查询计划的代码。码。 本节简单介绍实现选择操作和连接操作的几种本节简单介绍实现选择操作和连接操作的几种 主要算法。主要算法。一、选择操作的实现一、选择操作的实现例例Select * f

6、rom student where 考虑考虑 的几种情况：的几种情况： C1: 无条件；无条件； C2: Sno=200215121； C3: Sage20; C4: Sdept=CS AND Sage 20;对查询的基本表顺序扫描，逐一检查每个元组对查询的基本表顺序扫描，逐一检查每个元组 是否满足选择条件，把满足条件的元组作为结果是否满足选择条件，把满足条件的元组作为结果 输出。输出。对于小表，这种方法简单有效。对于小表，这种方法简单有效。对于大表，顺序扫描十分费时，效率很低。对于大表，顺序扫描十分费时，效率很低。1、简单的全表扫描方法、简单的全表扫描方法如果选择条件中的属性上有索引（例如树

7、如果选择条件中的属性上有索引（例如树 索引或者索引或者ash索引），可以用索引扫描方法。索引），可以用索引扫描方法。通过索引先找到满足条件的元组主码或元组通过索引先找到满足条件的元组主码或元组 指针，再通过元组指针直接在查询的基本表中找指针，再通过元组指针直接在查询的基本表中找 到元组。到元组。2、索引（或散列）扫描方法、索引（或散列）扫描方法例例1-C3以以C3为例，为例，Sage20 , 并且并且Sage上有上有B+树树 索引。索引。可以使用可以使用B+树索引找到树索引找到Sage20的索引项，以此的索引项，以此为入口点在为入口点在B+树的顺序集上得到树的顺序集上得到Sage20的所有元组

8、的所有元组指针，然后通过这些元组指针到指针，然后通过这些元组指针到student 表中检索所表中检索所有年龄大于有年龄大于20的学生。的学生。例例1-C2以以C2为例，为例，Sno=200215121，并且，并且Sno 上有索引。上有索引。可以使用索引得到可以使用索引得到 Sno为为200215121元组的指元组的指针，然后通过元组指针在针，然后通过元组指针在 student 表中检索到该学表中检索到该学生。生。例例1-C4以以C4为例，为例， Sdept=CS AND Sage 20 , 假设假设Sdept和和Sage 上都有索引。上都有索引。算法算法1：分别用上面两种方法分别找到：分别用上

9、面两种方法分别找到Sdept=CS 的一组元组指针和的一组元组指针和Sage 20的另一组元组指的另一组元组指 针，求这组指针的交集，再到针，求这组指针的交集，再到 student表中表中 检索。检索。算法算法2：找到：找到 Sdept=CS的一组元组的指针，通的一组元组的指针，通 过这些元组指针到过这些元组指针到student表中检索，并表中检索，并 对得到的元组检查另一个选择条件对得到的元组检查另一个选择条件 （Sage20 ）是否满足，把满足条件的元组作）是否满足，把满足条件的元组作 为结果输出。为结果输出。二、连接操作的实现二、连接操作的实现连接操作是查询处理中最耗时的操作之一。不连接

10、操作是查询处理中最耗时的操作之一。不失一般性，这里只讨论等值连接（或自然连接）最失一般性，这里只讨论等值连接（或自然连接）最常用的实现算法。常用的实现算法。例例 SELECT * FROM Student , SC WHERE Student.Sno SC.Sno算法：嵌套循环方法算法：嵌套循环方法这是最简单可行的算法。对外层循环（这是最简单可行的算法。对外层循环（Student）的每一个元组（的每一个元组（s），检索内层循环（），检索内层循环（SC）中的每一）中的每一个元组（个元组（sc），并检查这两个元组在连接属性（），并检查这两个元组在连接属性（Sno）上是否相等。如果满足连接条件，则串

11、接后作为结果上是否相等。如果满足连接条件，则串接后作为结果输，直到外层循环表中的元组处理完毕为止。输，直到外层循环表中的元组处理完毕为止。算法：排序合并方法算法：排序合并方法这也是常用的算法，尤其适合连接的诸表已经排好这也是常用的算法，尤其适合连接的诸表已经排好序的情况。步骤如下：序的情况。步骤如下：（）如果连接的表没有排好序，首先对两个表都按（）如果连接的表没有排好序，首先对两个表都按 连接属性连接属性Sno排序。排序。（）取（）取Student表中第一个表中第一个Sno，依次扫描，依次扫描SC表中具表中具 有相同有相同Sno的元组；把它们连接起来（如图）；的元组；把它们连接起来（如图）；9

12、500195002950039500119295001285950013889500229095002380（）当扫描到（）当扫描到Sno不相同的第一个不相同的第一个SC元组时，返回元组时，返回到到Student表扫描它的下一个元组，再扫描表扫描它的下一个元组，再扫描SC表中具表中具有相同有相同Sno的元组，把它们连接起来。的元组，把它们连接起来。9500195002950039500119295001285950013889500229095002380重复上述步骤直到重复上述步骤直到Student表扫描完毕。表扫描完毕。 这样这样Student表和表和SC表只要扫描一遍。当然，如果表只要扫

13、描一遍。当然，如果个表原来无序，执行时间还要加上对两个表的排序个表原来无序，执行时间还要加上对两个表的排序时间。即使这样，对于个大表，先排序后使用时间。即使这样，对于个大表，先排序后使用sort-merge join 方法执行连接，总的时间一般仍会大大减方法执行连接，总的时间一般仍会大大减少。少。算法：索引连接方法算法：索引连接方法（）在（）在SC表上建立属性表上建立属性Sno的索引（没有的话）；的索引（没有的话）；（）对（）对Student表中每一个元组，由表中每一个元组，由Sno值通过值通过SC的的索引查找相应的索引查找相应的SC元组；元组；（）把这些（）把这些SC元组和元组和Studen

14、t表中的元组连接起来。表中的元组连接起来。循环执行（）（），直到循环执行（）（），直到Student表中的表中的元组处理完为止。元组处理完为止。算法算法4：Hash Join 方法方法把连接属性把连接属性Sno作为作为Hash码，用同一个码，用同一个hash函数函数把把R和和S中的元组散列到同一个中的元组散列到同一个hash文件中。文件中。第一步，划分阶段，对包含较少元组的表（比如第一步，划分阶段，对包含较少元组的表（比如R）进行一遍处理，把它的元组按）进行一遍处理，把它的元组按hash函数分散到函数分散到hash表的桶中；表的桶中；第二步，试探阶段，也称为连接阶段，对另一个第二步，试探阶段，

15、也称为连接阶段，对另一个表（表（S）进行一遍处理，把）进行一遍处理，把S的元组散列到适当的的元组散列到适当的hash桶中，并把元组与桶中所有来自桶中，并把元组与桶中所有来自R并与之相匹配的元并与之相匹配的元组连接起来。组连接起来。备注：备注：上述上述hashjoin算法假设两个表中较小的算法假设两个表中较小的表在第一阶段后完全放入内存的表在第一阶段后完全放入内存的hash桶中。桶中。关系系统的查询优化既是关系系统的查询优化既是RDBMS实现的关键实现的关键技术，也是关系系统的优点所在。它减轻了用户选技术，也是关系系统的优点所在。它减轻了用户选择存取路径的负担，用户只须提出择存取路径的负担，用户

16、只须提出“干什么干什么”，而，而不必指出不必指出“怎么干怎么干”。查询优化的优点不仅在于用户不必考虑如何最查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得最高效率，而且还在于系统可好地表达查询以获得最高效率，而且还在于系统可以比用户程序的以比用户程序的“优化优化”做得更好。做得更好。关系数据库系统的查询优化关系数据库系统的查询优化9.2(1) 优化器可以从数据字典中获取许多统计信息，而优化器可以从数据字典中获取许多统计信息，而 用户程序则难以获得这些信息。用户程序则难以获得这些信息。(2) 如果数据库的物理统计信息改变了，系统可以自动如果数据库的物理统计信息改变了，系统可以自动 对查

17、询重新优化以选择相适应的执行计划。对查询重新优化以选择相适应的执行计划。 在非关系系统中必须重写程序，而重写程序在实际在非关系系统中必须重写程序，而重写程序在实际 应用中往往是不太可能的。应用中往往是不太可能的。(3) 优化器可以考虑数百种不同的执行计划，而程序员优化器可以考虑数百种不同的执行计划，而程序员 一般只能考虑有限的几种可能性。一般只能考虑有限的几种可能性。(4)优化器中包括了很多复杂的优化技术。优化器中包括了很多复杂的优化技术。关系数据库系统的查询优化关系数据库系统的查询优化9.2、查询优化的总目标、查询优化的总目标 选择有效策略，求得给定关系表达式的值，使得选择有效策略，求得给定

18、关系表达式的值，使得查询代价最小（较小）。查询代价最小（较小）。、实际系统的查询优化步骤、实际系统的查询优化步骤1） 将查询转换成某种内部表示，通常是语法树。将查询转换成某种内部表示，通常是语法树。2） 根据一定的等价变换规则把语法树转换成标准根据一定的等价变换规则把语法树转换成标准 （优化）形式。（优化）形式。3） 选择低层的操作算法选择低层的操作算法对于语法树中的每一个操作：对于语法树中的每一个操作：（）计算各种执行算法的执行代价；（）计算各种执行算法的执行代价；（）选择代价小的执行算法；（）选择代价小的执行算法；关系数据库系统的查询优化关系数据库系统的查询优化9.24） 生成查询计划生成

19、查询计划(查询执行方案查询执行方案) 查询计划是由一系列内部操作组成的。查询计划是由一系列内部操作组成的。代价计算公式如下：代价计算公式如下： 集中式数据库集中式数据库 单用户系统单用户系统 总代价总代价 = I/O代价代价 + CPU代价代价 多用户系统多用户系统 总代价总代价 = I/O代价代价 + CPU代价代价 + 内存代价内存代价 一般地，集中式数据库中一般地，集中式数据库中I/O代价是最主要的。代价是最主要的。 分布式数据库分布式数据库 总代价总代价 = I/O代价代价 + CPU代价代价+ 内存代价内存代价 + 通信代价通信代价 关系数据库系统的查询优化关系数据库系统的查询优化9

20、.2通过一个简单的例子，说明为什么要进行查询优化。通过一个简单的例子，说明为什么要进行查询优化。【例例】：求选修了求选修了2号课程的学生姓名。号课程的学生姓名。用用SQL语言实现如下：语言实现如下：SELECTSname FROM Student,SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;假设学生课程库中有：假设学生课程库中有： 1000条条Student记录记录 10000条条SC记录记录 其中，其中，50条选修条选修2号课程记录。号课程记录。关系数据库系统的查询优化关系数据库系统的查询优化9.2 系统可用下列系统可用下列3种等价的关系代数表达式来实现

21、这种等价的关系代数表达式来实现这一查询操作。一查询操作。.2Q1()SnameStudent Sno SC Sno SC CnoStudentSCSnameSC.Cno 2Q2(Student SC)SnameSC.Cno 2Q3(SC)Student 到底哪一种策略效率最优？到底哪一种策略效率最优？关系数据库系统的查询优化关系数据库系统的查询优化9.2假假 设设1、外存：、外存：Student：1000条条 SC ： 10000条条 其中，选修其中，选修2号课程：号课程： 50条条2、一个内存块可以装元组、一个内存块可以装元组: 10个个Student , 或或100个个SC 内存中一次可以

22、存放内存中一次可以存放: 5块块Student元组元组, 1块块SC元组元组, 10块连接结果元组块连接结果元组3、读写速度：、读写速度：20块块/秒秒4、连接方法：基于数据块的嵌套循环法、连接方法：基于数据块的嵌套循环法关系数据库系统的查询优化关系数据库系统的查询优化9.2 StudentSC 读取总块数读取总块数 = 读读Student表块数表块数 + 读读SC表遍数表遍数*每遍块数每遍块数 =1000/10+(1000/(105) (10000/100) =100+20100=2100块块 读数据时间读数据时间=2100/20=105秒秒.2Q1()SnameStudent Sno SC

23、 Sno SC CnoStudentSC关系数据库系统的查询优化关系数据库系统的查询优化9.2中间结果写入内存时间（处理时间忽略不计）中间结果写入内存时间（处理时间忽略不计）中间结果大小中间结果大小 = 1000*10000 = 107写中间结果时间写中间结果时间 = 107/10/20 = 50000秒秒Student.Sno=SC.SnoSC.Cno=2时间读入中间结果时间读入中间结果时间 （处理时间忽略不计）（处理时间忽略不计）读数据时间读数据时间 = 50000秒秒（结果为（结果为50条元组，直接放在内存，不消耗存取条元组，直接放在内存，不消耗存取 时间）时间）时间：处理时间忽略不计，

24、为。时间：处理时间忽略不计，为。Sname关系数据库系统的查询优化关系数据库系统的查询优化9.2总时间总时间=1055000050000 = 100105秒秒= 27.8小时小时.2Q1()SnameStudent Sno SC Sno SC CnoStudentSC关系数据库系统的查询优化关系数据库系统的查询优化9.2SnameSC.Cno2Q2(Student SC)Student SC 时间时间读取总块数读取总块数= 1000/10+(1000/(105) (10000/100) =2100块块读数据时间读数据时间=2100/20=105秒秒中间结果写入内存时间（处理时间忽略不计）中间结

25、果写入内存时间（处理时间忽略不计）中间结果大小中间结果大小=10000 （减少（减少1000倍）倍）写中间结果时间写中间结果时间=10000/10/20=50秒秒 关系数据库系统的查询优化关系数据库系统的查询优化9.2SC.Cno=2时间读入中间结果时间读入中间结果时间 （处理时间忽略不计）（处理时间忽略不计）读数据时间读数据时间 = 50秒秒（结果为（结果为50条元组，直接放在内存，不消耗存取时间）条元组，直接放在内存，不消耗存取时间）时间：处理时间忽略不计，为。时间：处理时间忽略不计，为。Sname总时间总时间=1055050 = 205秒秒= 3.4分钟分钟SnameSC.Cno2Q2(

26、Student SC)关系数据库系统的查询优化关系数据库系统的查询优化9.2SnameSC.Cno 2Q3(SC)Student 时间时间读读SC表总块数（一遍）表总块数（一遍）= 10000/100=100块块读数据时间读数据时间=100/20=5秒秒 （中间结果大小中间结果大小=50条条 不必写入外存，不耗时不必写入外存，不耗时 ）自然连接时间自然连接时间读读Student表总块数（一遍）表总块数（一遍）= 1000/10=100块块读数据时间读数据时间=100/20=5秒秒 总时间总时间55秒秒10秒秒 关系数据库系统的查询优化关系数据库系统的查询优化9.2)(Q1 2 .SCStude

27、ntCnoSCSnoSCSnoStudentSnameSC) (Student (Q22SC.CnoSname(SC)(Q3 Student 2SC.CnoSname三种执行策略中，第三种最优！三种执行策略中，第三种最优！这充分说明了查询优化的必要性！这充分说明了查询优化的必要性！为什么？从中我们可以发现什么规律？为什么？从中我们可以发现什么规律？关系数据库系统的查询优化关系数据库系统的查询优化9.2把代数表达式把代数表达式Q1变化成变化成Q2、Q3，即有选择和连接操作时，应，即有选择和连接操作时，应当先做选择操作，这样连接的元当先做选择操作，这样连接的元组就可以大大减少，这就是组就可以大大减

28、少，这就是代数代数优化优化。在在Q3中，中，SC表的选择操作算法表的选择操作算法有全表扫描和索引扫描有全表扫描和索引扫描2种方法，经种方法，经过初步估算，索引扫描方法较优。过初步估算，索引扫描方法较优。同样对于同样对于Student和和SC的连接，利用的连接，利用Student表上的索引，采用表上的索引，采用index join代价也较小，这就是代价也较小，这就是物理优化物理优化。SQL查询语句查询语句代数表达式代数表达式代数优化代数优化物理优化物理优化执行执行转换转换关系数据库系统的查询优化关系数据库系统的查询优化9.2（局限性）（局限性）代数优化代数优化9.3关系代数表达式等价：关系代数表

29、达式等价：用相同的关系代替两个表达式用相同的关系代替两个表达式 中相应的关系所得到的结果相中相应的关系所得到的结果相 同。同。两个关系表达式两个关系表达式E1、E2等价，记为：等价，记为：E1E2下面介绍常用的关系代数等价变换规则下面介绍常用的关系代数等价变换规则代数优化代数优化 等价变化规则等价变化规则9.31.1.连接、笛卡尔积交换律连接、笛卡尔积交换律 设设E1、E2为关系代数表达式，为关系代数表达式，F为连接运算的条件。为连接运算的条件。 E1E2E2E1 E1E2E2E1 E1E2E2E1FF2.2.连接、笛卡尔积的结合律连接、笛卡尔积的结合律 设设E1、E2 、E3为关系代数表达式

30、，为关系代数表达式，F1、F2为连接运为连接运算的条件。算的条件。 (E1E2 )E3E1(E2E3) (E1E2 )E3E1(E2E3) (E1E2 )E3E1(E2E3)F1F2F1F2 3.3.投影的串接定律投影的串接定律 A1,A2,AnA1,A2,An( (B1,B2,BmB1,B2,Bm(E)(E)A1,A2,AnA1,A2,An(E)(E) 这里，这里，E E是关系代数表达式。是关系代数表达式。 属性组属性组 A A1 1,A,A2 2,A,An n 是属性组是属性组 B B1 1,B,B2 2,B,Bm m 的子集。的子集。 如：如：sno(sno,sname(Stuent)

31、sno(Stuent)代数优化代数优化 等价变化规则等价变化规则9.34.4.选择的串接定律选择的串接定律 F1F1(F2F2(E)(E)F1F2F1F2(E)(E)如：如：JNO=J1(PNO=P1(SPJ) JNO=J1PNO=P1(SPJ)5.5.选择与投影的交换律选择与投影的交换律 F F(A1,A2,AnA1,A2,An(E)(E)A1,A2,AnA1,A2,An (F F(E)(E)这里，选择条件这里，选择条件F只涉及属性只涉及属性A1,A2,An 。代数优化代数优化 等价变化规则等价变化规则9.3若若F中有不属于中有不属于A1,A2,An的属性的属性B1,B2,Bm,则则 A1,

32、A2,An (F(E)A1,A2,An (F(A1,A2,An,B1,B2,Bm(E) 6.6.选择与笛卡尔积的交换律选择与笛卡尔积的交换律1 1）若）若F F中涉及的属性都是中涉及的属性都是E E1 1中的属性中的属性, ,则则 F F( (E1E2 ) )F F(E(E1) )E2 2 2）若）若F=FF=F1 1FF2 2，且且F F1 1只涉及只涉及E E1 1中的属性，中的属性，F F2 2只涉及只涉及E E2 2 中的属性，则中的属性，则 F F( (E1E2 ) )F1F1(E(E1) )F2F2(E2) ) 代数优化代数优化 等价变化规则等价变化规则9.3F F( (E1E2

33、) )F2F2( (F1F1(E(E1) )E2) ) 它使部分笛卡尔积先做。它使部分笛卡尔积先做。3）若）若F=F1F2，F1只涉及只涉及E1中的属性，中的属性，F2涉及涉及 E1和和E2两者的属性，则两者的属性，则7.7.选择与并的选择与并的分配律分配律 设设E=E=E1E2 ， E1、E2有相同的属性名有相同的属性名 F F( (E1E2 ) )F F( (E1) )F F( (E2) )8.8.选择与差的选择与差的分配律分配律 设设E1与与E2有相同的属性名有相同的属性名 F F( (E1-E2 ) )F F( (E1) )-F F( (E2) )代数优化代数优化 等价变化规则等价变化

34、规则9.39.9.选择对自然连接的选择对自然连接的分配律分配律 F F( (E1 E2 ) )F F( (E1) ) F F( (E2) )10.10.投影与笛卡尔积的分配律投影与笛卡尔积的分配律 设设A1 ,An是关系表达式是关系表达式E1的属性，的属性，B1 ,Bm是是 关系表达式关系表达式E2的属性的属性 A1,AnA1,An,B1,BmB1,Bm ( (E1E2) ) A1,AnA1,An( (E1) )B1,BmB1,Bm( (E2) )代数优化代数优化 等价变化规则等价变化规则9.311.11.投影与并的投影与并的分配律分配律 设设E1和和E2具有相同的属性名具有相同的属性名 A1

35、,AnA1,An( (E1 E2) )A1,AnA1,An( (E1) )A1,AnA1,An( (E2) )代数优化代数优化启发式规则启发式规则9.3本节讨论应用启发式规则的代数优化。这是对关本节讨论应用启发式规则的代数优化。这是对关系代数表达式的查询树进行优化的方法。系代数表达式的查询树进行优化的方法。典型的启发式优化规则有：典型的启发式优化规则有：一、选择运算应尽可能先做。一、选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。因为选在优化策略中这是最重要、最基本的一条。因为选择运算一般能使计算的中间结果大大减少，所以常常择运算一般能使计算的中间结果大大减少，所以常常可使执行查询

36、的时间降低几个数量级。可使执行查询的时间降低几个数量级。二、将投影运算和选择运算同时进行。二、将投影运算和选择运算同时进行。三、将投影同其前或其后的双目运算结合起来，三、将投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系没有必要为了去掉某些字段而扫描一遍关系四、将某些选择运算同在其前面要执行的笛四、将某些选择运算同在其前面要执行的笛卡尔积运算结合起来成为一个连接运算。卡尔积运算结合起来成为一个连接运算。五、找出公共子表达式。五、找出公共子表达式。先求出公共子表达式的值，然后将此值存先求出公共子表达式的值，然后将此值存入中间文件中。入中间文件中。代数优化代数优化启发式规

37、则启发式规则9.3Student.Sno=SC.SnoStudent.Sno=SC.Sno(Student(StudentSC)SC)StudentSCStudentSC代数优化代数优化 等价变化规则等价变化规则9.3【例例】：求选修了求选修了2号课程的学生姓名。号课程的学生姓名。用用SQL语言实现如下：语言实现如下：SELECTSname FROM Student,SC WHERE Student.Sno=SC.Sno AND SC.Cno=2;代数优化示例代数优化示例一、将查询转换成某种内部表示一、将查询转换成某种内部表示“内部表示内部表示”一般采用语法树。一般采用语法树。结果结果Proj

38、ect(Sname)Select(SC.Cno=2)join(Student.Sno=SC.Sno)StudentSC为了进一步使用关系代数表达式的优化准则，为了进一步使用关系代数表达式的优化准则，须将以上语法树转换成关系代数语法树。须将以上语法树转换成关系代数语法树。SnameSC.Cno=2Student.Sno=SC.SnoStudentSC二、将语法树转换成标准优化形式二、将语法树转换成标准优化形式SnameSC.Cno=2Student.Sno=SC.SnoStudentSCSnameSname(Student(StudentSC.Cno=2SC.Cno=2(SC)(SC)）l代数优

39、化改变查询语句中操作的次序和组合，不涉及底层的存取路径l对于一个查询语句有许多存取方案，它们的执行效率不同， 仅仅进行代数优化是不够的 l物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划 l选择的方法：选择的方法： 基于规则的启发式优化基于规则的启发式优化基于代价估算的优化基于代价估算的优化两者结合的优化方法两者结合的优化方法l一、一、 选择操作的启发式规则选择操作的启发式规则: 1. 对于小关系，使用全表顺序扫描，即使选对于小关系，使用全表顺序扫描，即使选 择列上有索引择列上有索引 对于大关系，启发式规则有：对于大关系，启发式规则有：l 2. 对于选择条件是主码值的查询对于

40、选择条件是主码值的查询l查询结果最多是一个元组，可以选择主码索引查询结果最多是一个元组，可以选择主码索引l一般的一般的RDBMS会自动建立主码索引。会自动建立主码索引。3. 对于选择条件是非主属性值的查询，并且选择列对于选择条件是非主属性值的查询，并且选择列上有索引上有索引n要估算查询结果的元组数目要估算查询结果的元组数目如果比例较小如果比例较小(10%)可以使用索引扫描方法可以使用索引扫描方法否则还是使用全表顺序扫描否则还是使用全表顺序扫描4. 对于选择条件是属性上的非等值查询或者范围查询，并对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引且选择列上有索引n要估算查询结果的元

41、组数目要估算查询结果的元组数目如果比例较小如果比例较小(10%)可以使用索引扫描方法可以使用索引扫描方法否则还是使用全表顺序扫描否则还是使用全表顺序扫描 5. 对于用对于用AND连接的合取选择条件连接的合取选择条件n如果有涉及这些属性的组合索引如果有涉及这些属性的组合索引,则优先采用组则优先采用组合索引扫描方法合索引扫描方法n如果某些属性上有一般的索引，则可以用例如果某些属性上有一般的索引，则可以用例1-C4中介绍的索引扫描方法，否则使用全表顺中介绍的索引扫描方法，否则使用全表顺序扫描。序扫描。6. 对于用对于用OR连接的析取选择条件，一般使用全表顺连接的析取选择条件，一般使用全表顺序扫描序扫

42、描l二、二、 连接操作的启发式规则：连接操作的启发式规则：1. 如果如果2个表都已经按照连接属性排序个表都已经按照连接属性排序n 选用排序选用排序-合并方法合并方法2. 如果一个表在连接属性上有索引如果一个表在连接属性上有索引n 选用索引连接方法选用索引连接方法3. 如果上面如果上面2个规则都不适用，其中一个表较小个规则都不适用，其中一个表较小n 选用选用Hash join方法方法4. 可以选用嵌套循环方法，并选择其中较小的表，确可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数切地讲是占用的块数(b)较少的表，作为外表较少的表，作为外表(外循外循环的表环的表) 。 理由：理由：设

43、连接表设连接表R与与S分别占用的块数为分别占用的块数为Br与与Bs连接操作使用的内存缓冲区块数为连接操作使用的内存缓冲区块数为K分配分配K-1块给外表块给外表如果如果R为外表，则嵌套循环法存取的块数为为外表，则嵌套循环法存取的块数为Br+( Br/K-1)Bs显然应该选块数小的表作为外表显然应该选块数小的表作为外表 l启发式规则优化是定性的选择，适合解释执行的系统启发式规则优化是定性的选择，适合解释执行的系统解释执行的系统，优化开销包含在查询总开销之中解释执行的系统，优化开销包含在查询总开销之中 l编译执行的系统中查询优化和查询执行是分开的编译执行的系统中查询优化和查询执行是分开的可以采用精细

44、复杂一些的基于代价的优化方法可以采用精细复杂一些的基于代价的优化方法 一、一、 统计信息统计信息l基于代价的优化方法要计算各种操作算法的执行代基于代价的优化方法要计算各种操作算法的执行代价，与数据库的状态密切相关价，与数据库的状态密切相关 l数据字典中存储的优化器需要的统计信息：数据字典中存储的优化器需要的统计信息： 1. 对每个基本表对每个基本表n该表的元组总数该表的元组总数(N)n元组长度元组长度(l)n占用的块数占用的块数(B)n占用的溢出块数占用的溢出块数(BO)2. 对基表的每个列对基表的每个列n该列不同值的个数该列不同值的个数(m)n选择率选择率(f)如果不同值的分布是均匀的，如果不同值的分布是均匀的，f1/m如果不同值的分布不均匀，则每个值的选择如果不同值的分布不均匀，则每个值的选择率具有该值的元组数率具有该值的元组数/Nn该列最大值该列最大值n该列最小值该列最小值n该列上是否已经建立了索引该列上是否已经建立了索引n索引类型索引类型(B+树索引、树索引、Hash索引、聚集索引索引、聚集索引)3. 对索引对索引(如如B+树索引树索引)n索引的层数索引的层数(L)n不同索引值的个数不同索引值的个数n索引的选择基数索引的选择基数S(有有S个元组具有某个索个元组具有某个索引值引值)n索引的叶结点数索引