关于数据库:数据库系统概论王珊第九章关系查询处理和关系优化第一节查询处理

查询处理是关系数据库管理系统执行查问语句的过程，其工作是把用户提交给关系数据库管理系统的查问语句转换为高效的查问执行打算

关系数据库管理系统查询处理能够分为 4 个阶段：

工作：对查问语句进行扫描，剖析词法、语法是否合乎 SQL 语法规定

工作：

工作：每个查问都会有许多可供选择的执行策略和操作算法，查问优化就是抉择一个高效执行的查询处理策略。依照优化的档次个别能够将查问优化分为

代数优化 ：是指 关系代数表达式 的优化，也即依照肯定规定，通过对关系代数表达式进行 等价变换 ，扭转代数表达式中操作的 秩序和组合，使查问更高效
物理优化 ：是指 存取门路 和底层操作算法 的抉择。抉择根据能够是 基于规定的 (rule based)、 基于代价的(cost based)、基于语义的(semantic based)

根据优化器失去的执行策略生成查问执行打算，由 代码生成器(code generator) 生成执行这个查问打算的代码，而后加以执行，回送查问后果。

以简略的单表抉择为例，如下

SELECT* FROM STUDENT WHERE< 条件表达式 >

< 条件表达式 >能够有以下几种状况

抉择操作只波及一个关系，典型的实现办法有

思维：假如能够应用的内存块为 $M$ 块

优缺点：

思维：如果抉择条件中的属性上有索引（例如 $B$+ 树索引或 $hash$ 索引），能够用索引扫描。通过索引先找到满足条件的元组指针，再通过元组指针在查问的根本表中找到元组。一般来说，当选择率低于 10% 时建设索引才有意义

以 $case$ 2 为例：Sno=’201215121’，并且 Sno 上有索引，则能够应用索引失去 Sno 为 ’201215121’ 元组的指针，而后通过元组指针在 Student 表中检索到该学生
以 $case$ 3 为例 ：Sage>20，并且 Sage 上有 B + 树索引，则能够应用 B + 树索引找到 Sage=20 的索引项，以此为入口点在 B + 树的程序集上失去 Sage>20 的所有元组指针，而后通过这些元组指针到Student 表中检索到所有年龄大于 20 的学生
以 $case$ 4 为例 ：Sdept=’CS’ AND Sage>20, 如果Sdept 和Sage 上都有索引，一种算法是 ，别离用下面两种办法找到 Sdept=’CS’ 的一组元组指针和 Sage>20 的另一组元组指针，求这两组指针的交加，再到 Student 表中检索，就失去计算机系年龄大于 20 岁的学生； 另一种算法是，找到 Sdept=’CS’ 的一组元组指针，通过这些元组指针到 Student 表中检索，并对失去的元组查看另一些抉择条件(如 Sage>20) 是否满足，把满足条件的元组作为后果输入

连贯操作是查询处理中最罕用也是最耗时的操作之一 。不失一般性，这里通过例子简略介绍 等值连贯(或天然连贯) 最罕用的几种算法思维

SELECT * FROM Student,SC WHERE Student.Sno=SC.Sno;

思维：对外层循环 (Student 表)的每一个元组，检索内层循环 (SC 表)中的每一个元组，并查看这两个元组在连贯属性(Sno) 上是否相等。如果满足连贯条件，则串接后作为后果输入，直到外层循环表中的元组解决完为止

思维：

如果参加连贯的表没有排好序，首先对 Student 表和 SC 表按连贯属性 Sno 排序
取 Student 表中第一个 Sno,顺次扫描 SC 表中具备雷同 Sno 的元组，把它们连接起来
当扫描到 Sno 不雷同的第一个 SC 元组 时，返回 Student 表扫描它的下一个元组，再扫描SC 表中具备雷同 Sno 的元组，把它们连接起来

反复上述步骤直至 Student 扫描结束

思维：

循环执行第二步和第三步，直至 Student 中的元组处理完毕

思维：它把连贯属性作为 hash 码，用同一个 hash 函数把 Student 表和 SC 表中的元组散列到 hash 表中

划分阶段（创立阶段）：即创立 hash 表。对蕴含较少元组的表 (如Student 表)进行一遍解决，把它的元组按 hash 函数 (hash 码是连贯属性) 扩散到 hash 表的桶中
试探阶段（连贯阶段）：对另一个表 (SC 表)进行一遍解决，把 SC 表的元组也按同一个 hash 函数 (hash 码是连贯属性) 进行散列，找到适当的 hash 桶，并把 SC 元组与桶中来自Student 表并与之相匹配的元组连接起来。

一：查询处理步骤