【从零开始学习计算机科学】数据库系统（五）DBMS查询处理

DBMS查询处理

选择操作的实现

选择操作典型实现方法主要有以下两种：

简单的全表扫描方法。对查询的基本表顺序扫描，逐一检查每个元组是否满足选择条件，把满足条件的元组作为结果输出。其适合小表，不适合大表。

索引(或散列)扫描方法。其适合选择条件中的属性上有索引(例如B+树索引或Hash索引) 。其通过索引先找到满足条件的元组指针，再通过元组指针直接在查询的基本表中找到元组。

考虑以下查询Select * from student where <条件表达式>，考虑<条件表达式>的几种情况：C1：无条件；C2：Sno＝’200215121’；C3：Sage>20；C4：Sdept=‘CS’ AND Sage>20；

以C2为例，Sno＝‘200215121’，并且Sno上有索引(或Sno是散列码)。使用索引(或散列)得到Sno为‘200215121’ 元组的指针，然后通过元组指针在student表中检索到该学生。

以C3为例，Sage>20，并且Sage 上有B+树索引。其使用B+树索引找到Sage＝20的索引项，以此为入口点在B+树的顺序集上得到Sage>20的所有元组指针。通过这些元组指针到student表中检索到所有年龄大于20的学生。

以C4为例，Sdept＝‘CS’ AND Sage>20，如果Sdept和Sage上都有索引：
算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一组元组指针和Sage>20的另一组元组指针，然后求这2组指针的交集，在到student表中检索，最后得到计算机系年龄大于20的学生。

算法二：找到Sdept＝‘CS’的一组元组指针，通过这些元组指针到student表中检索，对得到的元组检查另一些选择条件(如Sage>20)是否满足，最后把满足条件的元组作为结果输出。

连接操作的实现

连接操作是查询处理中最耗时的操作之一。本章仅讨论等值连接(或自然连接)的最常用的实现算法。目前，等值连接的实现主要有以下几种方法：嵌套循环方法(nested loop) 、排序-合并方法(sort-merge join 或merge join)、索引连接(index join)方法 、Hash Join方法。

考虑以下语句：SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno；

在嵌套循环方法(nested loop)

首先对外层循环(Student)的每一个元组(s)，检索内层循环(SC)中的每一个元组(sc)，检查这两个元组在连接属性(sno)上是否相等，如果满足连接条件，则串接后作为结果输出，直到外层循环表中的元组处理完为止

排序-合并方法(sort-merge join 或merge join)

其适合连接的诸表已经排好序的情况。

排序－合并连接方法的步骤主要有：如果连接的表没有排好序，先对Student表和SC表按连接属性Sno排序，然后取Student表中第一个Sno，依次扫描直到找到SC表中具有相同Sno的元组，当扫描到Sno不相同的第一个SC元组时，返回Student表扫描它的下一个元组，再扫描SC表直到找到具有相同Sno的元组，把它们连接起来。重复上述步骤直到Student 表扫描完。
此方法的是优点是Student表和SC表都只要扫描一遍。如果2个表原来无序，执行时间要加上对两个表的排序时间。对于2个大表，先排序后使用sort-merge join方法执行连接，总的时间一般仍会大大减少。

索引连接(index join)方法

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

Hash Join方法

其把连接属性作为hash码，用同一个hash函数把R和S中的元组散列到同一个hash文件中。
其步骤主要分为划分阶段和试探阶段。

划分阶段(partitioning phase)。其对包含较少元组的表(比如R)进行一遍处理，把它的元组按hash函数分散到hash表的桶中。

试探阶段(probing phase)。也称为连接阶段(join phase) ，对另一个表(S)进行一遍处理。
把S的元组散列到适当的hash桶中（不需放入桶中），然后把元组与桶中所有来自R并与之相匹配的元组连接起来。

hash join算法前提是假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中。并且，以上的算法思想可以推广到更加一般的多个表的连接算法上。

表达式计算(SQL查询)

(表达式计算中的)物化计算

当采用物化方法时，我们从表达式的最底层的运算(在树的底部)开始。在该例子中，只有一个底层运算: department 上的选择运算。底层运算的输人是数据库中的关系。我们用前面研究过的算法执行这些运算，并将结果存储在临时关系中。在树的高层中，使用这些临时关系来进行计算;这时的输人要么是临时关系，要么是来自数据库的关系。
物化即是将中间计算结果作为临时关系存放，用以支持上一层计算。

(表达式计算中的)流水线计算

通过减少查询执行中产生的临时文件数，可以提高查询执行的效率。减少临时文件数是通过将多个关系操作组合成一个操作的流水线来实现的，其中一个操作的结果将传送到下一个操作。这样的计算叫做流水线计算pipelined evaluation)。
流水线作用是避免中间结果表的创建，提供执行效率。

例如，考虑表达式$({\Pi }_{a_1,a_2}(r\bowtie s))$。如果采用物化方法，在执行中将创建存放连接结果的临时关系，然后在执行投影时又从连接结果中读入。这些操作可按如下方式组合:当连接操作产生一个结果元组时，该元组马上传送给投影操作去处理。通过将连接操作与投影操作组合起来，我们可以避免中间结果的创建，从而直接产生最终结果。

流水线的实现

通过将所有操作组合起来构成流水线，构造一个单独的复合操作，我们可以实现流水线。尽管对于各种频繁发生的情况，这个方法是可行的；但一般而言，希望在构造一个流水线时能重用各个操作的代码。

在上图的例子中，三个操作均可放入一条流水线中;其中，选择操作的结果产生后传送给连接操作。接着，连接操作的结果产生后又传送给投影操作。由于一个操作的结果不必长时间保存，因此对内存的要求不高。然而，由于采用流水线，各个操作并非总是能立即获得输人来进行处理。

关系数据库系统的查询优化

查询优化在关系数据库系统中有着非常重要的地位，关系查询优化是影响RDBMS性能的关键因素。

由于关系表达式的语义级别很高，使关系系统可以从关系表达式中分析查询语义，提供了执行查询优化的可能性。

查询优化器的优点不仅在于用户不必考虑如何最好地表达查询以获得较好的效率，而且在于系统可以比用户程序的“优化”做得更好。

优化器可以从数据字典中获取许多统计信息，而用户程序则难以获得这些信息，如果数据库的物理统计信息改变了，系统可以自动对查询重新优化以选择相适应的执行计划。在非关系系统中必须重写程序，而重写程序在实际应用中往往是不太可能的。

优化器可以考虑数百种不同的执行计划，程序员一般只能考虑有限的几种可能性。

优化器中包括了很多复杂的优化技术，这些优化技术往往只有最好的程序员才能掌握。系统的自动优化相当于使得所有人都拥有这些优化技术。

RDBMS通过某种代价模型计算出各种查询执行策略的执行代价，然后选取代价最小的执行方案。

对于集中式数据库，执行开销主要包括：磁盘存取块数(I/O代价)、处理机时间(CPU代价)、查询的内存开销 。其中，I/O代价是最主要的。

对于分布式数据库，总代价 = I/O代价 + CPU代价 + 内存代价 + 通信代价。
查询优化的总目标是选择有效的策略、求得给定关系表达式的值以及使得查询代价最小(实际上是较小)。

实际系统的查询优化步骤

1. 将查询转换成某种内部表示，通常是语法树。

2. 根据一定的等价变换规则把语法树转换成标准（优化）形式，得到某一颗最优树(执行效率最佳)。

3. 选择低层的操作算法。对于语法树中的每一个操作，计算各种执行算法的执行代价，选择代价小的执行算法。

4. 生成查询计划(查询执行方案)。查询计划是由一系列内部操作组成的。

考虑以下查询：2009年有课的Music系的所有教师名字以及每个教师所教授的课程名称。SQL语句为：

select name,title from instuctor,teaches,course  where instructor.ID=teaches.ID and teaches.course_id=course.course_id and instructor.dept_name=‘Music’ and year=2009

1，SQL转换为关系代数

${\Pi }_{name,title}({\sigma }_{dept\_name="Music"\wedge year=2009}(instructor\bowtie (teaches\bowtie {\Pi }_{course\_id,title}(course))))$

2，关系代数转换为查询树(表示式树)

3，查询树变换

这两棵树为等价表达式，但它们的执行效果不同。

4，生成执行计划

优化查询树结合标注（确定复合操作及确定各基本操作的执行算法）即为执行计划。

关系表达式的转换

用于表达式转换的等价规则主要有：

1，合取选择运算可分解为单个选择运算的序列。该变换称为$\sigma$的级联：${\sigma }_{{\theta }_1\wedge {\theta }_2}(E)$ = ${\sigma }_{{\theta }_1}({\sigma }_{{\theta }_2}(E))$

2，选择运算满足交换律( commutative )：${\sigma }_{{\theta }_1}({\sigma }_{{\theta }_2}(E))$ = ${\sigma }_{{\theta }_2}({\sigma }_{{\theta }_1}(E))$

3，一系列投影运算中只有最后一个运算是必需的，其余的可省略。该转换也可称为$\Pi$的级联：${\Pi }_{L_1}({\Pi }_{L_2}(\cdots ({\Pi }_{L_n}(E))\cdots ))$ = ${\Pi }_{L_1}(E)$

4，选择操作可与笛卡儿积以及$\theta$连接相结合：${\sigma }_{\theta }(E_1\times E_2)$ = $E_1{\bowtie }_{\theta }{E}_2$

该表达式就是$\theta$连接的定义。

${\sigma }_{{\theta }_1}(E_1{\bowtie }_{{\theta }_2}{E}_2$