数据库基础与应用 第2版 王珊 李盛恩 第4章_查询处理及优化

《数据库基础与应用 第2版 王珊 李盛恩 第4章_查询处理及优化》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第四章查询处理及优化4.1查询处理的步骤4.2查询处理算法4.3查询优化4.4小结4.1查询处理的步骤DBMS接收到SQL查询后，它的查询处理系统要将查询转换为操作代码，一般分为四个步骤：1.查询分析2.查询检查3.查询优化4.查询执行4.2查询处理算法关系的逻辑存储结构是二维表，表的元素是元组。不同的DBMS使用不同的物理存储结构存放关系。一般地讲，DBMS向操作系统申请若干个文件，把这些文件占用的磁盘空间作为一个整体进行段页式管理，一个页面又叫做一块（Block）。不同系统的块的大小也不一样，块是DBMS的I/O单位。一个关系的元组被存储在一个或多个块中。4.2查询处理算法为便于

2、描述和讨论，首先引入一些记号。用B(R)表示关系R占用的块数，用T(R)表示R中元组的数目，用V(R，A)表示关系R在属性A上不同值的个数。在查询处理中，需要内存和磁盘操作，由于磁盘I/O操作涉及机械动作，需要的时间与内存操作相比要高几个数量级。因此，在评估查询处理算法时，一般用算法读写的I/O块数作为衡量单位。4.2查询处理算法4.2.1外部排序排序是数据库中最基本的操作之一。很多语句中执行DISTINCT、GROUPBY和ORDERBY子句等都要使用排序操作。在数据库环境下，排序操作对象的数量十分巨大，例如，对一个有几百万元组的关系进行排序就要使用外部排序算法。4.2查询处理算法

3、4.2.1外部排序一个典型的外部排序算法分为内部排序阶段和归并阶段。其核心思想是根据内存的大小，将存放在磁盘上待排序的关系逻辑上分为若干个段（run），一个段的大小以可使用的内存大小为上限。在内部排序阶段，从磁盘上把一个段中的全部元组读入内存，使用我们熟悉的内部排序算法，如快速排序，将这些元组排序，然后把它们写到磁盘临时存放。处理完所有的段后，进入归并排序阶段，采用多路归并排序算法，经过1趟或2趟归并排序后，就完成对关系的排序。4.2查询处理算法2000012王林……2000113张大民…2000278姜凡……2000256顾芳……2000014葛波……2000467……200021

4、0……2000623……2000756……2000213……2000012……2000113……2000256……2000278……2000014……2000210……2000467……2000623……2000213……2000756……图4.1对Student关系的内部排序阶段4.2查询处理算法2000012200011320002562000278200001420002102000467200062320002132000756输入缓冲区输入缓冲区输入缓冲区选择算法输出缓冲区图4.2对Student关系的多路归并阶段200001220000142000113200021020

5、002132000256200027820004674.2查询处理算法图4.1是内部排序示意图，学号是排序属性，假设可用内存大小为4个元组，10个元组分3次读入内存，排序后在磁盘上有3个有序的段。图4.2是3路归并示意图，选择算法从输入缓冲区中选择最小的学号，把该学号所在的元组放到输出缓冲区，待缓冲区满后，将缓冲区中的元组在输出到磁盘。图中为了节省空间，只给出了每个元组的学号属性。一个输入缓冲区和输出缓冲区是一个或多个块，选择算法一般使用堆。4.2查询处理算法如果可用内存为M块，则外部排序的I/O次数大约为：所有的DBMS都对外部排序算法进行了最大限度的优化，理论计算表明，对绝大数应

6、用而言，多路归并阶段只需要一趟即可。4.2查询处理算法4.2.2集合操作算法在SQL中，集合有两种语义，即传统的集合语义和包语义，二者的差别在于是否允许出现重复的元素。我们首先给出包语义的并、交和差运算的定义。为了叙述方便，用记号tm表示元组t在集合中的出现次数，m>0表示t重复出现了m次，m=0，表示t没有出现在集合中。4.2查询处理算法1、包并两个集合R和S包并的结果要包含R和S中的所有元组，用公式表示为：R∪BS={tm+n

7、tmR∧tnS}图4.3中关系R和S中都有元组（a2，b2，c1），这个元组在结果中重复出现了2次。ABCABCABCa1b1c1a1b2c2a1b1

8、c1a1b2c2∪Ba1b3c2a1b2c2a2b2c1a2b2c1a2b2c1a1b2c2a1b3c2a2b2c1图4.3包并运算4.2查询处理算法2、包交在传统的集合中，如果t∈R∩S，则t∈R并且t∈S，即如果t出现在交的结果中，t在R和S中至少各出现一次。包中允许元组重复出现，因此，包交的定义如下：R∩BS={tk

9、tmR∧tnS,k=min(m,n)}包交的例子如下图所示：4.2查询处理算法图4.4包交运算ABCa2b2c1a1b1c1a2b