优化

Question 0

RDBMS查询处理的阶段

Answer 0

查询分析，查询检查，查询优化和查询执行。

Question 1

查询处理的任务

Answer 1

把用户提交给RDBMS的查询语句转换为高效的执行计划。

Question 2

查询分析

Answer 2

对查询语句进行扫描、词法分析和语法分析。从查询语句中识别出语言符号，如SQL关键字、属性名和关系名等，进行语法检查和语法分析，即判断查询语句是否符合SQL语法规则。

Question 3

查询检查

Answer 3

根据数据字典对合法的查询语句进行语义检查，即检查语句中的数据库对象，如属性名、关系名，是否存在和是否有效。
还要根据数据字典中的用户权限和完整性约束定义对用户的存取权限进行检查。如果该用户没有相应的访问权限或违反了完整性约束，就拒绝执行该查询。检查通过后便把SQL查询语句转换成等价的关系代数表达式。
RDBMS一般都用查询树，也称为语法分析树，来表示扩展的关系代数表达式。这个过程中要把数据库对象的外部名称转换为内部表示。

Question 4

查询树

Answer 4

SQL语句经过查询分析、查询检查后变换为查询树，它是关系代数表达式的内部表示。

Question 6

查询优化

Answer 6

每个查询都会有许多可供选择的执行策略和操作算法，查询优化就是选择一个高效执行的查询处理策略。

Question 10

查询执行

Answer 10

依据优化器得到的执行策略生成查询计划，由代码生成器生成执行这个查询计划的代码。

Question 11

选择操作的实现（算法思想）

Answer 11

SELECT语句功能十分强大，有许多选项，因此实现的算法和优化策略也很复杂。下面以简单的选择操作为例介绍典型的实现方法。
1。简单的全表扫描方法
2。索引（或散列）扫描方法

Question 12

简单的全表扫描方法

Answer 12

对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足选择条件的元组作为结果输出。

对于小表，这种方法简单有效。对于大表，顺序扫描十分费时，效率很低。

Question 13

索引（或散列）扫描方法

Answer 13

如果选择条件中的属性上有索引（例如B+树索引或Hash索引），可以用索引扫描方法。通过索引先找到满足条件的元组主码或元组指针，再通过元组指针直接在查询的基本表中找到元组。

Question 14

连接操作的实现（算法思想）

Answer 14

连接操作是查询处理中最耗时的操作之一。这里只讨论等值连接（或自然连接）最常用的实现算法。
1。循环嵌套方法（nested loop）
2。排序-合并方法（sort-merge join或merge join）
3。索引连接方法（index join）
4。Hash Join方法

Question 15

循环嵌套方法（nested loop）

Answer 15

这是最简单可行的算法。对外层循环的每一个元组，检索内层循环中的每一个元组，并检查这两个元组在连接属性上是否相等。如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止。

Question 16

排序-合并方法（sort-merge join或merge join）

Answer 16

这也是常用的算法，尤其适合连接的诸表已经排好序的情况。
步骤：
1。如果连接的表没有排好序，首先对Student表和SC表按连接属性Sno排序。
2。取Student表中第一个Sno，依次扫描SC表中具有相同Sno的元组，把它们连接起来。
3。当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表中具有相同Sno的元组，把它们连接起来。
重复上述步骤直到Student表扫描完。
这样Student表和SC表都只要扫描一遍。当然，如果2个表原来无序，执行时间要加上对两个表的排序时间。即使这样，对于2个大表，先排序后使用sort-merge join方法执行连接，总的时间一般仍会大大减少。

Question 17

索引连接方法（index join）

Answer 17

步骤：
1。在SC表上建立属性Sno的索引，如果原来没有的话。
2。对Student中每一个元组，由Sno值通过SC的索引查找相应的SC元组。
3。把这些SC元组和Student元组连接起来。
循环执行2、3，直到Student表中的元组处理完为止。

Question 18

Hash Join方法

Answer 18

把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中。
第一步，划分阶段，对包含较少元素的表（比如R）进行一遍处理，把它的元组按hash函数分散到hash表的桶中。
第二步，试探阶段，也称为连接阶段，对另一个表（S）进行一遍处理，把S的元组散列到适当的hash桶中，并把元组与桶中所有来自R并与之相配的元组连接起来。
上面hash join算法假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中。

Question 19

查询优化在关系数据库系统中的重要性

Answer 19

关系系统的查询优化既是RDBMS实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出＂干什么＂，不必指出＂怎么干＂。
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的＂优化＂做得更好。

Question 20

查询优化概述

Answer 20

对比一下非关系系统中的情况：用户使用过程化的语言表达查询要求，执行何种记录级的操作，以及操作的序列是由用户而不是由系统来决定的。因此用户必须了解存取路径，系统要提供用户选择存取路径的手段，查询效率由用户的存取策略决定。如果用户做了不当的选择，系统是无法对此加以改进的。这就要求用户有较高的数据库技术和程序设计水平。

Question 22

查询优化在关系数据库系统中的可能性

Answer 22

1。优化器可以从数据字典中获取许多统计信息，例如每个关系表中的元组数、关系中每个属性值的分布情况、哪些属性上已经建立了索引等。优化器可以根据这些信息作出正确的估算，选择高效的执行计划，而用户程序则难以获得这些信息。
2。如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
3。优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。
4。优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些技术。目前RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。
在集中式数据库中，查询的执行开销主要包括磁盘存取块数（I/O代价），处理机时间（CPU代价），查询的内存开销。
在分布式数据库中还要加上通信代价，即总代价=I/O代价+CPU代价+内存代价+通信代价。
一般地，集中式数据库中I/O代价是最主要的。

Question 23

查询优化的总目标

Answer 23

选择有效的策略，求得给定关系表达式的值，使得查询代价最小（实际上是较小）。

Question 24

等价变换规则

Answer 24

（笔记本）
1。连接、笛卡尔积交换律
2。连接、笛卡尔积的结合律
3。投影的串接定律
4。选择的串接定律
5。选择与投影操作的交换律
6。选择与笛卡尔积的交换律
7。选择与并的分配率
8。选择与差运算的分配率
9。选择对自然连接的分配率
10。投影与笛卡尔积的分配率
11。投影与并的分配率

Question 25

典型的启发式规则

Answer 25

1。选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条。它常常可使执行时节约几个数量级，因为选择运算一般使计算的中间结果大大变小。
2。把投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系。
3。把投影同其前或其后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。
4。把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算，连接特别是等值连接运算要比同样关系上的笛卡尔积省很多时间。
5。找出公共子表达式。如果这种重复出现的子表达式的结果不是很大的关系，并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的。当查询的是视图时，定义视图的表达式就是公共子表达式的情况。

Question 26

遵循这些启发式规则，应用等价变换公式来优化关系表达式的算法

Answer 26

算法：关系表达式的优化
输入：一个关系表达式的查询树
输出：优化的查询树
方法：
1。利用等价变换规则4把合并的选择操作先后执行。
2。对每一个选择，利用等价变换规则4-9尽可能把它移到树的叶端。
3。对每一个投影利用等价变换规则3，5，10，11中的一般形式尽可能把它移向树的叶端。
等价变换规则3使一些投影消失，而规则5把一个投影分裂为两个，其中有一个有可能被移向树的叶端。
4。利用等价变换规则3-5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投运能同时进行，或在一次扫描中全部完成，尽管这种变换似乎违背＂投运尽可能早做＂的原则，但这样做效率更高。
5。把上述得到的语法树的内节点分组。每一双目运算（笛卡尔积，连接，并，差）和它所有的直接祖先（选择、投影）为一组。如果其后代直到叶子全是单目运算，则也将它们并入该组，但当双目运算是笛卡尔积，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组。把这些单目运算单独分为一组。

Question 27

物理优化的选择的方法

Answer 27

1。基于规则的启发式优化。启发式规则是指那些在大多数情况下都适用，但不是在每种情况下都是适用的规则。
2。基于代价估算的优化。优化器估算不同执行策略的代价，并选出具有最小代价的执行计划。
3。两者结合的优化方法。查询优化器通常会把这两种技术结合在一起使用。因为可能的执行策略很多，要穷尽所有的策略进行代价估算往往是不可行的，会造成查询优化本身付出的代价大于获得的益处。为此，常常先使用启发式规则，选取若干较优的候选方案，减少代价估算的工作量；然后分别计算这些候选方案的执行代价，较快地选出最终的优化方案。

Question 28

选择操作的启发式规则

Answer 28

1。对于小关系，使用全表顺序扫描，即使选择列上有索引。
对于大关系，启发式规则有：
2。对于选择条件是主码=值的查询，查询结果最多是一个元组，可以选择主码索引。一般的RDBMS会自动建立主码索引。
3。对于选择条件是非主属性=值的查询，并且选择列上有索引，则要估算查询结果的元组数目，如果比例较小（＜10%）可以使用索引扫描方法，否则还是使用全表顺序扫描。
4。对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组数目，如果比例较小（＜10%）可以使用索引扫描方法，否则还是使用全表顺序扫描。
5。对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，则优先采用组合索引扫描方法，如果某些属性上有一般的索引，则可以用索引扫描方法，否则还是使用全表顺序扫描。
6。对于用OR连接的析取选择条件，一般使用全表顺序扫描。

Question 29

连接操作的启发式规则

Answer 29

1。如果2个表都已经按照连接属性排序，则选用排序-合并方法。
2。如果一个表在连接属性上有索引，则可以选用索引连接方法。
3。如果上面2个规则都不适用，其中一个表较小，则可以选用Hash Join方法。
4。最后可以选用嵌套循环方法，并选择其中较小的表，确切地讲是占用的块数（b）较少的表，作为外表（外循环的表）。

Question 30

嵌套循环连接算法的代价

Answer 30

设连接表R与S分别占用的块数为Br与Bs，连接操作使用的内存缓冲区块数为K，分配K-1块给外表。如果R为外表，则嵌套循环法存取的块数为Br+（Br/K-1）Bs，显然应选块数小的表作为外表。

Question 31

基于代价的优化

Answer 31

启发式规则优化是定性的选择，比较粗糙，但是实现简单而且优化本身的代价较小，适合解释执行的系统。因为解释执行的系统，优化开销包含在查询总开销之中。在编译执行的系统中，一次编译优化，多次执行，查询优化和查询执行是分开的。因此，可以采用精细复杂的一些基于代价的优化方法。

Question 32

统计信息

Answer 32

基于代价的优化方法要计算各种操作算法的执行代价，它与数据库的状态密切相关。为此在数据字典中存储了优化器需要的统计信息。主要包括：
1。对每个基本表，该表的元组总数（N）、元组长度（l）、占用的块数（B）、占用的溢出块数（BO）；
2。对基表的每个列，该列不同值的个数（m）、选择率（f）（如果不同值的发布是均匀的，f=1/m；如果不同值的发布不均匀，则每个值的选择率=具有该值的元组数/N）、该列最大值、最小值，该列上是否已经建立了索引，是哪种索引（B+树索引、Hash索引、聚集索引）；
3。对索引，例如B+树索引，该索引的层数（L）、不同索引值的个数、索引的选择基数S（有S个元组具有某个索引值）、索引的叶结点数（Y）；
等等。

Question 33

全表扫描算法的代价估算公式

Answer 33

如果基本表大小为B块，全表扫描算法的代价cost=B；如果选择条件是码=值，那么平均搜索代价cost=B/2。

Question 34

索引扫描算法的代价估算公式

Answer 34

如果选择条件是码=值，则采用该表的主索引，若为B+树，层数为L，需要存取B+树中从根结点到叶结点L块，再加上基本表中该元组所在的那一块，所以cost=L+1。
如果选择条件涉及非码属性，若为B+树索引，选择条件是相等比较，S是索引的选择基数（有S个元组满足条件）。因为满足条件的元组可能会保存在不同的块上，所以（最坏的情况）cost=L+S。
如果比较条件是>，>=，<=操作，假设有一半的元组满足条件，那么就要存取一半的叶结点，并通过索引访问一半的表存储块。所以cost=L+Y/2+B/2。如果可以获得更准确的选择基数，可以进一步修正Y/2与B/2。

Question 35

嵌套循环连接算法的代价估算公式

Answer 35

嵌套循环连接算法的代价cost=Br+BrBs（K-1）。如果需要把连接结果写回磁盘，则cost=Br+BrBs（K-1）+(FrsNrNs)/Mrs。其中Frs为连接选择性，表示连接结果元组数的比例，Mrs是存放连接结果的块因子，表示每块中可以存放的结果元组数目。

Question 36

RDBMS查询优化的一般步骤

Answer 36

1。把查询转换成某种内部表示，通常所用的内部表示是语法树。
2。把语法树转换成标准（优化）形式，即利用优化算法，把原始语法树转换成优化形式。
3。选择低层的存取路径。
4。生成查询计划，选择所需代价最小的。

Question 37

排序-合并连接算法的代价估算公式

Answer 37

如果连接表已经按照连接属性排好序，则cost=Br+Bs+(FrsNrNs)/Mrs。

如果必须对文件排序，那么还需要在代价函数中加上排序的代价。对于包含B个块的文件排序的代价大约是(2B)+(2B*log2B)。

Question 38

说明为什么要进行查询优化的实例

Answer 38

书P268

Question 40

查询优化按照优化的层次可分为

Answer 40

查询优化有多种方法。按照优化的层次一般可分为代数优化和物理优化。

实际RDBMS中的查询优化器都综合运用了这些优化技术，以获得最好的查询优化效果。

Question 41

代数优化

Answer 41

关系代数表达式的优化，即按照一定的规则，改变代数表达式中操作的次序和组合，使查询执行更高效。
通过对关系代数表达式的等价变换来提高查询效率。所谓关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。
代数优化改变查询语句中操作的次序和组合，不涉及底层的存取路径。

Question 42

物理优化

Answer 42

选择高效合理的存取路径和底层操作算法，求得优化的查询计划，达到查询优化的目标。选择的依据可以是基于规则的，也可以是基于代价的，还可以是基于语义的。