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

• pdf 下载：明码 7281
• 专栏目录首页：【专栏必读】（考研复试）数据库系统概论第五版（王珊）专栏学习笔记目录导航及课后习题答案详解

一：查问优化概述

（1）查问优化的位置和重要性

关系零碎的查问优化既是关系数据库管理系统实现的 关键技术 ，又是关系零碎的 长处所在 。 用户只有提出“干什么”，而不用指出“怎么干”。

在非关系零碎中，用户必须理解存取门路，零碎提供用户抉择存取门路的伎俩，查问的效率由用户的存取策略决定，且零碎是无奈加以优化的。这就要求用户须要具备较高的数据库技术和程序设计程度

查问优化的长处不仅在于用户不用思考如何最好地表白查问以取得较高的效率，而且在于零碎能够比用户程序的“优化”做得更好。这是因为：

• 优化器能够从数据字典中取得很多统计信息，然而用户程序难以获得
• 即使数据库物理统计信息扭转，零碎也能够进行优化从而抉择相应的执行打算，然而对于非关系零碎则必须要重写程序
• 优化器能够思考数百种不同的执行打算，但程序员个别仅能思考无限的几种可能性
• 优化器蕴含了很多简单的优化技术，这样就等同于所用的使用者间接领有了这些技术

（2）执行代价

目前关系数据库管理系统通过某种代价模型计算出各种查问执行策略的执行代价，而后选取 代价最小的执行计划 。一般来说： 总代价 =I/ O 代价 +CPU 代价 + 内存代价 + 通信代价

• 计算查问代价时个别用 查询处理读写的块数 作为掂量单位

二：一个例子

能够通过“求选修了 2 号课程的学生姓名”这样一个例子来阐明为什么要进行查问优化

以下是一些 零碎假如

• 假设学生 - 课程数据库中有1 000 个学生记录，10 000 个选课记录（均匀每一个学生了选了 10 门课），其中选修 2 号课程的选课记录为 50 个
• 有 7 个内存块（其中 调配 5 块用于装入 Student 表，1 块用于装入 SC 表，1 块用于装入两头后果）
• 其中 一块能够装入 10 个 student 元组 （或 10 个student 与 SC 笛卡尔积元组）；一块也能够 装入 50 个 SC 元组（因为 SC 的列数较少）
• 连贯办法为：基于数据块的嵌套循环法。
• 之所以这样调配的起因：因为嵌套循环算法须要选用占用内存少的表作为表面，student 表有 1000 行，每块装 10 行，所以须要 100 块；SC 表有 10000 行，每块装 50 行，所以须要 200 块。
• 因为 student 表须要 100 个内存块，而调配给它的只有 5 个，所以不可能一次全副装入内存，每次只能装入一部分，比拟完了再装入另外一部分。每换一批数据，内标就须要全副从新装入以便，所以为了缩小内表循环装入的次数，就必须尽可能的分配内存给表面
• 连贯后的元组 装满一块 后就写到两头文件上

SELECT Student.name
FROM Student,SC
WHERE Student.Sno=SC.Sno AND SC.Cno='2';

零碎能够用多种等价的 关系代数表达式 来实现这一查问，这里只举三种状况

（1）状况 1

Student与 Sc 作笛卡尔积 ，而后作 行抉择 运算（抉择条件为 Student.Sno=SC.Sno AND SC.Cno='2'），最初进行 投影操作

①：计算狭义笛卡尔积

操作：

• 在内存中尽可能多地装入某个表 (如Student 表)的若干块，留出一块寄存另一个表 (如SC 表)的元组；
• 而后把 SC 中的每个元组和 Student 中每个元组 连贯 ，连贯后的元组 装满一块后就写到两头文件上 ，再从SC 中读入一块和内存中的 Student 元组连贯，直到 SC 表处理完；
• 这时再一次读入若干块 Student 元组，读入一块 SC 元组，反复上述处理过程，直到把 Student 表处理完

块数：

• 读一遍 Student 表所需块数为 =$\frac{1000}{10}=100$ 块
• 读一遍 SC 表所须要块数为 =$\frac{10000}{50}=200$ 块
• 因为 Student 表可用块数为 5 块，所以分 $\frac{100}{5}=20$ 次读入
• 同时，Student表的每一部分读入内存时，SC表都须要从新读一遍，以此实现与 Student 表的连贯。所以须要读入 200×20=4000 块
• 所以笛卡尔积读取总块数为 100+4000=4100 块
• Student表和 SC 表作笛卡尔积共有 $10^{7}$ 行，每块装 10 行，所以两头后果块数为 $10^{6}$ 块（写入）

②：作抉择操作

块数：

• 所读块数为 $10^{6}$ 块
• 抉择后的后果只有 50 个（无需读写）

③：作投影操作

• 无需读写

状况 1 读取总块数：

4100（读）+$10^{6}$（写）+$10^{6}$（读）。约为 200 万块

（2）状况 2

Student与 Sc 作天然连贯 ，而后作 行抉择 运算（抉择条件为 Student.Sno=SC.Sno AND SC.Cno='2'），最初进行 投影操作

①：计算天然连贯

块数：

• 首先读 Student 和SC，与状况 1 统一。因而 总块数 =4100 块
• Student和 SC 天然连贯后右 10000 行，所以 两头后果块数 $\frac{10000}{10}$=1000块

②：作抉择操作

块数：

• 读入两头后果，块数 =1000 块

③：作投影操作

• 50 个后果能够不必写入

状况 2 读取总块数：

4100（读）+$1000$（写）+$1000$（读）。共计 6100 块

• 代价约为状况 1 的 $\frac{1}{488}$

（3）状况 3

首先 Sc 作行抉择 （抉择条件为SC.Cno='2'），而后作 天然连贯 运算，最初进行 投影操作

块数：

• 先对 SC 表作 抉择操作 ， 只需读一遍 SC 表，存取块数为 100 块 ，因为满足条件的元组仅 50 个， 不用应用两头文件
• 读取 Student 表，把读入的 Student 元组和内存中的 SC 元组作连贯。也只需读一遍 Student 表，共 100 块，把连贯后果投影输入

状况 3 读取总块数：

100（读）+200（读）。共计 300 块

• 代价约为状况 1 的的万分之一
• 代价约为状况 2 的 $\frac{1}{20}$

三：代数优化和物理优化

通过下面的那个例子能够看到：通过优化，磁盘 I / O 波及块数 从 200 万降落至 300，效率晋升显著，这阐明查问优化是十分有必要的。上述三种状况其有些操作是能够优化的，例如

• 状况一 ：明知在笛卡尔积后要做行抉择，那 为什么不在连贯时就把抉择做了，这样只会留下 50 个元组，也即省去了 100 万个块的读写操作
• 状况二：也是如此，在作天然连贯时如果也把抉择做了，就会省去 1000 个块的读写操作
• 状况三：它是先作抉择再作连贯，所以大大减少了块数

因而，由状况 1 到状况 2 再到状况 3 这样的优化称之为代数优化；而如果对底层门路或算法进行优化则称之为物理优化。例如对于状况三，能够增加索引，持续减小代价