• 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.nameFROM Student,SCWHERE 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这样的优化称之为代数优化；而如果对底层门路或算法进行优化则称之为物理优化。例如对于状况三，能够增加索引，持续减小代价