查询优化
 
在关系数据库系统中有着非常重要的地位 
 关系查询优化是影响RDBMS性能的关键因素 
 由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性 
 
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好 
 (1) 优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息 
 (2)如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。 
 (3)优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。 
 (4)优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术
 
RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案 
 集中式数据库 
 执行开销主要包括： 
 磁盘存取块数(I/O代价) 
 处理机时间(CPU代价) 
 查询的内存开销 
 I/O代价是最主要的 
 分布式数据库 
 总代价=I/O代价+CPU代价+内存代价＋通信代价 
 
查询优化的总目标：
选择有效的策略
求得给定关系表达式的值
使得查询代价最小(实际上是较小) 
 
[例3] 求选修了2号课程的学生姓名。用SQL表达：
      SELECT  Student.Sname
       FROM  Student，SC
       WHERE  Student.Sno=SC.Sno AND                 SC.Cno=‘2’； 

假定学生-课程数据库中有1000个学生记录，10000个选课记录
其中选修2号课程的选课记录为50个 
 
系统可以用多种等价的关系代数表达式来完成这一查询
Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno='2' (Student×SC))
Q2=πSname(σSc.Cno='2' (Student     SC))
Q3=πSname(Student      σSc.Cno='2'(SC))
 
一、第一种情况 
 Q1=πSname(σStudent.Sno=SC.Sno∧Sc.Cno=’2’ (Student×SC)) 
 1. 计算广义笛卡尔积 
 把Student和SC的每个元组连接起来的做法： 
 在内存中尽可能多地装入某个表(如Student表)的若干块，留出一块存放另一个表(如SC表)的元组。 
 把SC中的每个元组和Student中每个元组连接，连接后的元组装满一块后就写到中间文件上 
 从SC中读入一块和内存中的Student元组连接，直到SC表处理完。 
 再读入若干块Student元组，读入一块SC元组 
 重复上述处理过程，直到把Student表处理完 
 2. 作选择操作 
 依次读入连接后的元组，按照选择条件选取满足要求的记录 
 假定内存处理时间忽略。读取中间文件花费的时间(同写中间文件一样)需5×104s 
 满足条件的元组假设仅50个，均可放在内存 
 3. 作投影操作 
 把第2步的结果在Sname上作投影输出，得到最终结果 
 第一种情况下执行查询的总时间≈105+2×5×104≈105s 
 所有内存处理时间均忽略不计 
 
二、 第二种情况 
 Q2=πSname(σSc.Cno=’2’ (Student SC)) 
 1. 计算自然连接 
 执行自然连接，读取Student和SC表的策略不变，总的读取块数仍为2100块花费105 s 
 自然连接的结果比第一种情况大大减少，为104个 
 写出这些元组时间为104/10/20=50s，为第一种情况的千分之一 
 2. 读取中间文件块，执行选择运算，花费时间也为50s。 
 3. 把第2步结果投影输出。 
 第二种情况总的执行时间≈105+50+50≈205s 
 
三、 第三种情况 
 Q3=πSname(Student σSc.Cno=’2’(SC)) 
 1. 先对SC表作选择运算，只需读一遍SC表，存取100块花费时间为5s，因为满足条件的元组仅50个，不必使用中间文件。 
 2. 读取Student表，把读入的Student元组和内存中的SC元组作连接。也只需读一遍Student表共100块，花费时间为5s。 
 3. 把连接结果投影输出 
 第三种情况总的执行时间≈5+5≈10s 
 
假如SC表的Cno字段上有索引 
 第一步就不必读取所有的SC元组而只需读取Cno=‘2’的那些元组(50个) 
 存取的索引块和SC中满足条件的数据块大约总共3～4块
 
若Student表在Sno上也有索引 
 第二步也不必读取所有的Student元组 
 因为满足条件的SC记录仅50个，涉及最多50个Student记录 
 读取Student表的块数也可大大减少 
 
总的存取时间将进一步减少到数秒 
 
把代数表达式Q1变换为Q2、 Q3， 
 即有选择和连接操作时，先做选择操作，这样参加连接的元组就可以大大减少，这是代数优化 
 在Q3中 
 SC表的选择操作算法有全表扫描和索引扫描2种方法，经过初步估算，索引扫描方法较优 
 对于Student和SC表的连接，利用Student表上的索引，采用index join代价也较小，这就是物理优化 
 
代数优化策略
 
：通过对关系代数表达式的等价变换来提高查询效率 
 
关系代数表达式的等价：指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的
 
两个关系表达式E1和E2是等价的，可记为E1≡E2 
 
常用的等价变换规则：
1.  连接、笛卡尔积交换律
   设E1和E2是关系代数表达式，F是连接运算的条件，则有
    E1  × E2≡E2  × E1
    E1      E2≡E2      E1
    E1      E2≡E2      E1
2. 连接、笛卡尔积的结合律
   设E1，E2，E3是关系代数表达式，F1和F2是连接运算的条件，则有
    (E1  × E2) × E3≡E1 × (E2 × E3)
    (E1      E2)      E3≡E1      (E2      E3)
    (E1     E2)      E3≡E1     (E2      E3) 
3. 投影的串接定律
                 (            (E))≡            (E)
    这里，E是关系代数表达式，Ai(i=1，2，…，n)，Bj(j=1，2，…，m)是属性名且{A1，A2，…，An}构成{B1，B2，…，Bm}的子集。
4. 选择的串接定律
           (     (E))≡           (E)
    这里，E是关系代数表达式，F1、F2是选择条件。
    选择的串接律说明选择条件可以合并。这样一次就可检查全部条件
5. 选择与投影操作的交换律
    σF(          (E))≡            (σF(E))
    选择条件F只涉及属性A1，…，An。
    若F中有不属于A1，…，An的属性B1，…，Bm则有更一般的规则：
                (σF(E))≡          (σF(                       (E)))

6. 选择与笛卡尔积的交换律
    如果F中涉及的属性都是E1中的属性，则
         (E1×E2)≡     (E1)×E2
    如果F=F1∧F2，并且F1只涉及E1中的属性，F2只涉及E2中的属性，则由上面的等价变换规则1，4，6可推出：
         (E1×E2)≡     (E1)×     (E2)
    若F1只涉及E1中的属性，F2涉及E1和E2两者的属性，则仍有
        (E1×E2)≡      (     (E1)×E2)
    它使部分选择在笛卡尔积前先做。 

7. 选择与并的分配律
    设E=E1∪E2，E1，E2有相同的属性名，则
    σF(E1∪E2)≡σF(E1)∪σF(E2)
8. 选择与差运算的分配律
    若E1与E2有相同的属性名，则
    σF(E1-E2)≡σF(E1)-σF(E2)
9. 选择对自然连接的分配律
    σF(E1    E2)≡σF(E1)      σF(E2)
    F只涉及E1与E2的公共属性 
10. 投影与笛卡尔积的分配律
    设E1和E2是两个关系表达式，A1，…，An是E1的属性，B1，…，Bm是E2的属性，则
                        (E1×E2)≡            (E1)×            (E2)
11. 投影与并的分配律
    设E1和E2有相同的属性名，则
                  (E1∪E2)≡            (E1)∪            (E2)
 
查询树的启发式优化
 
典型的启发式规则： 
 1. 选择运算应尽可能先做。在优化策略中这是最重要、最基本的一条 
 2. 把投影运算和选择运算同时进行（pipelining技术） 
 如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描此关系的同时完成所有的这些运算以避免重复扫描关系，也避免存储中间关系 
 3. 把投影同其前或其后的双目运算结合起来执行（pipelining技术） 
 4. 把某些选择同在它前面要执行的笛卡尔积结合起来成为一个连接运算 
 5. 找出公共子表达式 
 如果这种重复出现的子表达式的结果不是很大的关系并且从外存中读入这个关系比计算该子表达式的时间少得多，则先计算一次公共子表达式并把结果写入中间文件是合算的 
 当查询的是视图时，定义视图的表达式就是公共子表达式的情况 
 遵循这些启发式规则，应用9.3.1的等价变换公式来优化关系表达式的算法。 
 算法：关系表达式的优化 
 输入：一个关系表达式的查询树 
 输出：优化的查询树 
 方法： 
 (1) 利用等价变换规则4把形如σF1∧F2∧…∧Fn(E)变换为σF1(σF2(…(σFn(E))…))。 
 (2) 对每一个选择，利用等价变换规则4～9尽可能把它移到树的叶端。 
 (3) 对每一个投影利用等价变换规则3，5，10，11中的一般形式尽可能把它移向树的叶端。 
 注意： 
 等价变换规则3使一些投影消失 
 规则5把一个投影分裂为两个，其中一个有可能被移向树的叶端 
 (4) 利用等价变换规则3～5把选择和投影的串接合并成单个选择、单个投影或一个选择后跟一个投影。使多个选择或投影能同时执行，或在一次扫描中全部完成 
 (5) 把上述得到的语法树的内节点分组。每一双目运算(×， ，∪，-)和它所有的直接祖先为一组(这些直接祖先是(σ，π运算)。 
 如果其后代直到叶子全是单目运算，则也将它们并入该组 
 但当双目运算是笛卡尔积(×)，而且后面不是与它组成等值连接的选择时，则不能把选择与这个双目运算组成同一组，把这些单目运算单独分为一组 
 
例[5] 查询语句：检索学习课程名为MATH的女学生学号和姓名。
该查询语句的关系代数表达式如下：
   πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(C   SC   S))
上式中， 符号用π、σ、×操作表示，可得下式
 πS#，SNAME(σCNAME=’MATH’∧SEX=’F’(πL
          (σC.C# = SC.C#∧SC.S# = S.S#(C×SC×S))))
此处L是C、SC、S中全部属性,去除重复属性。

关系查询处理和查询优化
 1.关系数据库管理系统的查询处理步骤
 2.查询优化的概念
 3.基本方法和技术
 代数优化：指关系代数表达式的优化
 物理优化：指存储路径和底层操作算法的选择
 
 
 SQL语句处理过程
 查询处理步骤：
 四个阶段
 1.查询分析
 2.查询检查
 3.查询优化
 4.查询执行
 
 
 查询语句->词法分析/语法分析->有效性检查/视图转换/安全性检查/完整性检查->查询树->代数优化/物理优化等->查询执行计划->代码生成->查询计划/执行代码
 （数据字典）

第9章 关系查询处理和查询优化
 
9.1 关系数据库系统的查询处理
 
9.1.1 查询处理步骤 
 
关系数据库管理系统查询处理可以分为4个阶段：查询分析、查询检查、查询优化和查询执行
 
查询分析：词法分析、语法分析
查询检查：语义分析、是否有权限、是否破坏完整性、视图转换
查询优化：代数优化（逻辑优化）和物理优化（基于规则、代价、语义），生成查询计划树
查询执行：自底向上/自顶向下策略
 
9.1.2 实现查询操作的算法示例
 
选择操作的实现：全表扫描/索引扫描
连接操作的实现：查询处理中最常用最耗时的操作之一 
  
嵌套循环算法：最简单最通用，实际上都是基于数据块的循环(m*n)
排序-合并算法：常用与等值连接，尤其适合各个表已经排好序的情况。（m+n） 
    
第一步：如果参与连接的表没有排好序，根据连接属性排序
第二步：sorted_merge
索引连接算法：根据表上已经建立好的索引，根据索引查找匹配的元组
hash join 算法：等值连接，要求内存足够大，小表的hash表要全部能够放进内存。分成两个阶段 
    
第一步，划分阶段，为小表建立hash表，根据连接属性作为hash码
第二步，试探阶段，对另外一张表的连接属性hash一遍，将匹配的元组连接起来
9.2 关系数据库系统的查询优化
 
9.2.1 查询优化概述
 
重要性：关系系统的查询优化即是关系数据库管理系统实现的关键技术，又是关系系统的优点所在。它减轻了用户选择存取路径的负担，用户只要提出“干什么”，而不必指出“怎么干”，
 
由DBMS进行查询优化的好处：
 
查询优化的优点不仅在于用户不必考虑如何最好的表达查询以获得较高的效率，而且在于系统可以比用户程序的“优化”做得更好。
 
可能性：
 
优化器可以从数据字典中获取许多统计信息，
如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。
优化器可以考虑数百种不同的执行计划，而程序员一般只考虑有限的几种可能性。
优化器中包括了很多复杂的优化技术。
在集中式数据库中，查询执行开销主要包括磁盘存取块数（IO代价）、处理机时间（CPU代价）以及查询的内存开销
 
计算查询代价时一般用查询处理读写的块数作为衡量单位
 
9.3 代数优化
 
9.3.1 关系代数表达式等价变换规则
 
 
 
9.3.2 查询树的启发式优化
 
选择运算应尽可能先做
把投影运算和选择运算同时进行：这两者都是一元操作，一个元组能不能成为结果只取决于其本身
把投影同其前或后的双目运算结合起来
把某些选择同在它前面要执行的笛卡儿积结合起来称为一个连接运算
找出公共子表达式
 
9.4 物理优化
 
9.4.1 基于启发式规则的存取路径选择优化
 
选择操作的启发式规则：
 对于小关系，全表扫描
 对于大关系：
 1. 若选择条件是主码，则可以选择主码索引，因为主码索引一般是被自动建立的
 2. 若选择条件是非主属性的等职查询，并且选择列上有索引，如果选择比例较小（10%）可以使用索引扫描，否则全表扫描
 3. 若选择条件是属性上的非等职查询或者范围查询，同上
 4. 对于用and连接的合取选择条件，若有组合索引，优先用组合索引方法；如果某些属性上有一般索引，则用索引扫描，否则全表扫描
 5. 对于用OR连接的析取选择条件，全表扫描
 
连接操作的启发式规则
 1. 若两个表都已经按连接属性排序，则选用排序-合并算法
 2. 若一个表在连接属性上有索引，则使用索引连接方法
 3. 若其中一个表较小，则选用hash join
 4. 最后可以使用嵌套循环，小表坐外表
 
9.4.2 基于代价估算的优化
 
统计信息：数据字典中存储了优化器需要的优化信息，包括基本表的元组总数、长度、占用块数，每个列的不同值的个数、最大/小值、是否有索引，索引的层数、个数、选择基数等
 代价估算实例
 
 
 
习题
 
1 ．试述查询优化在关系数据库系统中的重要性和可能性。
 
答：重要性：关系系统的查询优化既是 RDBMS 实现的关键技术又是关系系统的优点所在。它减轻了用户选择存取路径的负担。用户只要提出“干什么”，不必指出“怎么干”。查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化’夕做得更好。
 
可能性：这是因为：
 
( l ）优化器可以从数据字典中获取许多统计信息，例如关系中的元组数、关系中每个属性值的分布情况、这些属性上是否有索引、是什么索引（ B ＋树索引还是 HASH 索引或惟一索引或组合索引）等。优化器可以根据这些信息选择有效的执行计划，而用户程序则难以获得这些信息。
( 2 ）如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。
( 3 ）优化器可以考虑数十甚至数百种不同的执行计划，从中选出较优的一个，而程序员一般只能考虑有限的几种可能性。
( 4 ）优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。
 
2 ．对学生一课程数据库有如下的查询： SEI 王 CT Cn 即 ne FROM Student , Cou 拐 e , SC WHERE Student . Sno = SC . Sno AND SC . Cllo = Coll 拐 e . Cllo AND Stu 击 nt . Sdept = ! 15 ! ; 此查询要求信息系学生选修了的所有课程名称。试画出用关系代数表示的语法树，并用关系代数表达式优化算法对原始的语法树进行优化处理，画出优化后的标准语法树。
 
答：
 
 
 
 
 
 
 
3 ．试述查询优化的一般准则。
 
答：下面的优化策略一般能提高查询效率：
 
( l ）选择运算应尽可能先做；
( 2 ）把投影运算和选择运算同时进行；
( 3 ）把投影同其前或其后的双目运算结合起来执行；
( 4 ）把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算；
( 5 ）找出公共子表达式；
( 6 ）选取合适的连接算法。
4 ．试述查询优化的一般步骤。
 
答：各个关系系统的优化方法不尽相同，大致的步骤可以归纳如下：
 
( l ）把查询转换成某种内部表示，通常用的内部表示是语法树。
( 2 ）把语法树转换成标准（优化）形式。即利用优化算法，把原始的语法树转换成优化的形式。
( 3 ）选择低层的存取路径。
( 4 ）生成查询计划，选择代价最小的。
 
 
 

 
 
关系查询优化是影响关系数据库管理系统性能的关键因素。
 
 
一、查询优化概述
 
查询优化的优点不仅在于用户不必考虑如何最好地表达查询以获得较高的效率，而且在于系统可以比用户程序的“优化”做得更好。 
 1. 优化可以从数据字典中获得更多统计信息。 
 2. 如果数据库的物理统计信息改变了，系统可以自动对查询进行重新优化以选择相适应的执行计划。在非关系系统中则必须重写程序，而重写程序在实际应用中往往是不太可能的。 
 3. 优化器可以考虑数百种不同的执行计划，而程序员一般只能考虑有限的几种可能性。 
 4. 优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。 
 在集中式数据库中，查询执行开销主要包括磁盘存取块数（I/O代价）、处理机时间（CPU代价）以及查询的内存开销。在分布式数据库中还要加上通信代价，即： 
 总代价=I/O代价+CPU代价+内存代价+通信代价。 
 由于磁盘I/O操作涉及机械动作，需要时间与内存操作相比要高几个数量级，在计算查询代价时一般用查询处理读写的块数作为衡量单位。 
 查询优化的总目标是选择有效的策略，求得给定关系表达式的值，使得查询代价较小，因为查询优化的搜索空间有时非常大，实际系统选择的策略不一定是最优的，而是较优的。
 
二、代数优化
 
代数优化是基于关系代数等价变换规则的优化方法。 
 代数优化策略是通过对关系代数表达式的等价变换来提高查询效率。所谓关系代数表达式的等价是指用相同的关系代替两个表达式中相应的关系所得到的结果是相同的。两个关系表达式E1和E2是等价的。
 
查询树的启发式优化
 
典型的启发式规则： 
 1. 选择运算应尽可能先做。 
 2. 把投影运算和选择运算同时进行。如有若干投影和选择运算，并且它们都对同一个关系操作，则可以在扫描次关系的同时完成所有这些运算以避免重复扫描关系。 
 3. 把投影同其前或后的双目运算结合起来，没有必要为了去掉某些字段而扫描一遍关系。 
 4. 把某些选择同在它前面要执行的笛卡儿积结合起来成为一个连接运算，连接（特别是等值连接）运算要啊比同样关系上的笛卡儿积省很多时间。 
 5. 找出公共子表达式。
 
三、物理优化
 
代数优化改变查询语句中操作的次序和组合，但不涉及底层的存取路径。物理优化就是要选择高效合理的操作算法或存取路径，求得优化的查询计划，达到查询优化的目标。 
 选择的方法可以是： 
 1. 基于规则的启发式优化。 
 2. 基于代价估算的优化。 
 3. 两者结合的优化方法。常常先使用启发式规则选取若干个较优的候选方案，减少代价估算的工作量，然后分别计算这些候选方案的执行代价，较快地选出最终的优化方法。
 
基于启发式规则的存取路径选择优化
 
选择操作的启发式规则 
 对于小关系，使用全表顺序扫描，即使选择列上有索引。 
 对于大关系，启发式规则有： 
 1. 对于选择条件是“主码=值”的查询，查询结果最多是一个元组，可以选择主码索引，一般都关系数据库管理系统会自动建立主码索引。 
 2. 对于选择条件是“非主属性=值”的查询，并且选择列上有索引，则要估算查询结果的元组数目，如果比例较小（<10%）可以使用索引扫描方法，否则还是使用全表顺序扫描。 
 3. 对于选择条件是属性上的非等值查询或者范围查询，并且选择列上有索引，同样要估算查询结果的元组数目，如果选择率<10%可以使用索引扫描方法，否则使用全表顺序扫描。 
 4. 对于用AND连接的合取选择条件，如果有涉及这些属性的组合索引，则优先采用组合索引扫描方法；如果某些属性上有一般索引，则可以使用索引扫描方法，否则使用全表顺序扫描。 
 5. 对于OR连接的析取选择条件，一般使用全表顺序扫描。
 
基于代价估算的优化
 
启发式规则优化是定性的选择，比较粗糙，但是实现简单而且优化本身的代价较小，适合解释执行的系统。因为解释执行的系统，其优开销包含在查询总开销之中，在编译执行的系统中，一次编译优化，多次执行，查询优化和查询执行是分开的，因此，可以用精细复杂一些的基于代价的优化方法。
 
四、查询计划的执行
 
查询优化完成后，关系数据库管理系统为用户查询生成了一个查询计划。该计划的执行可以分为自顶向下和自底向上两种执行方法。 
 1. 自顶向下 
 系统反复向查询计划顶端的操作符发出需要查询结果元组的请求，操作符收到请求后，就试图计算下一个（几个）元组并返回这些元组。在计算时，如果操作符的输入缓冲区为空，它就会向其孩子操作符发送需求元组的请求……这种需求元组的请求会一直传到叶子节点，启动叶子操作符运行，并返回其父操作符一个（几个）元组，父操作符再计算自己的输出返回给上层操作符，直至顶端操作符。重复这一过程，直到处理完整个关系。 
 2. 自底向上 
 查询计划从叶结点开始执行，叶节点操作符不断地产生元组并将它们放入其输出缓冲区中，直到缓冲区填满为止，这时它必须等待其父操作符将元组从该缓冲区中取走才能急促执行，然后其父结点操作符开始执行，利用下层的输入元组来产生它自己的输出元组，直到其输出缓冲区满为止，重复这个过程，直到产生所有的输出元组。
 
 
 
向下的执行方式是一种被动的、需求驱动的执行方式。而自底向上的执行方式是一种主动的执行方式。
 
 
总结： 
 对于比较复杂的查询，尤其是涉及连接和嵌套的查询，不要把优化的任务全部放在关系数据库管理系统上，应该找出关系数据库管理系统的优化规律，以写出适合关系数据库管理系统自动优化的SQL语句，对于关系数据库管理系统不能优化的查询需要重写查询语句，进行手工调整以优化性能。