时间：2022-12-23 16:30:01 | 来源：信息时代
时间：2022-12-23 16:30:01 来源：信息时代
关系操作的实现 : DBMS内部实现具体关系操作符的过程。在关系数据库执行引擎中,每个关系操作符都有多种不同的实现算法供查询优化器选择。
1.选择操作的实现
选择操作主要有两种实现方法:
(1)全表扫描方法: 对查询的基本表从头到尾进行扫描,逐一检查每条元组是否满足选择条件,把满足条件的元组作为结果输出。对于小表,这种方法简单有效。对于大表,顺序扫描十分费时,效率很低。
(2)索引(或散列)扫描方法:如果选择条件中的属性上有索引,可以用索引扫描方法。通过索引先找到满足条件的元组主键或元组指针,再通过元组指针直接在基本表中找到元组。
设有关系R(A,B,C),对于查询:
SELECT*FROM R WHERE〈条件表达式〉;
如果要在R表中查询满足R.A=125的元组,假设A属性上有索引(或A是散列码),则可以使用索引(或散列)得到R.A为125的元组指针,然后通过元组指针在R表中检索到该元组。
如果要在R表中查询满足R.B>=20的元组,假设在R.B上有B+树索引,则可以使用B+树索引找到R.B=20的索引项,以此为入口点在B+树的顺序集上得到R.B>=20的所有元组指针,然后通过这些元组指针到R表中检索到所有满足R.B>20的元组。
如果要在R表中查询满足R.C='CS'并且R.B>=20的元组,若R.C和R.B上都有索引,一种算法是:分别用上面两种方法找到R.C='CS'的一组元组指针和R.B>=20的另一组元组指针,求这两组指针的交集,再到R表中检索,就可以检索到所有满足R.C='CS'AND R.B>=20条件的元组。
另一种算法是: 找到R.C=’CS’的一组元组指针,通过这些元组指针到R表中检索,并对得到的元组检查其余选择条件(如R.B>=20)是否满足,把满足条件的元组作为结果输出。
2.连接操作的实现
连接操作是查询处理中最耗时的操作之一。以R(X,Y)和S(Y,Z)等值连接(或自然连接)为例,对于查询:
SELECT*FROM R,S WHERE R.Y=S.Y;
常用的实现算法有:
(1)嵌套循环方法(nested loop): 嵌套循环方法是一个很常用的连接算法,它采用一个双层循环来实现,这也是嵌套循环连接方法得名的原因。嵌套循环连接方法包括基于元组的连接方法和基于块的连接方法。
(2)排序-合并方法(sort-merge join或merge join): 排序-合并方法也是常用的连接算法,尤其适合各个连接对象表已经排好序的情况。对于要连接的关系R(X,Y)和S(Y,Z),已知有M块内存用作缓冲区,排序-合并连接的基本过程为: ①用Y作为排序键,使用两阶段多路归并对R排序,并写回到磁盘;②对S进行类似排序,并写回到磁盘;③归并排好序的R和S,通常仅使用两个缓冲区,一个给R的当前块,另一个给S的当前块,重复执行以下步骤,直到表R或表S中的全部元组都处理完毕为止:对当前缓冲区中的R和S块,从头开始扫描,找到连接属性Y的最小值y,因为已经按Y排好序,所以它一定是某个关系(比如R)在内存中的第一元组;扫描另一个关系(比如S),如果其在内存中的第一条元组的Y值大于y,则说明S中没有Y值等于y的元组,从R的内存块中删除具有排序键y的所有元组;否则,找出两个关系中具有排序键y的所有元组,进行连接,并输出; 如果一个关系在内存中的所有元组都已处理过,就为其读入下一块。
如果将排序的第二阶段与连接过程合并,对每个块可以节约两次磁盘I/O,即: ①用Y作为排序键,分别为R和S创建大小为M块的排序子表。即每次读入的M块数据进入缓冲区,在内存中排序,然后写回磁盘,直到R全部处理完。对S做相同处理。②假设R和S的排序子表个数总和不超过M个,将每一个子表的第一块调进缓冲区。③重复地在所有子表的第一个可以得到的元组中查找最小的Y值y。识别两个关系中具有Y值y的所有元组。输出R和S中具有此公共Y值的所有元组的连接。如果一个子表的缓冲区处理完毕,则从磁盘中读入新的块进来。
在这个算法中,如果R和S的排序子表个数总和超过了M个,则算法无法运行,可以把该算法扩充为基于多趟排序的连接算法。即首先将这两个关系分成总数为M的子表;然后对每一个子表进行递归排序,从而形成M个有序子表; 最后,将这M个子表的每一个子表的第一块调进缓冲区,并且按相应的基于两趟排序的算法所描述的方式来执行操作。
(3) Hash连接方法(Hash Join): Hash连接方法将连接过程分为两个阶段: 划分阶段(partitioning phase)和试探阶段(probing phase),第二阶段也称为连接阶段(join phase)。
假设有M块缓冲区,对于R(X,Y)和S(Y,Z)的连接操作,当其中一个表较小(不仿假设为R),可以完全读入内存时,其Hash连接过程为:第一步划分阶段,把连接属性作为Hash码,用一个Hash函数把R中的元组散列到M—1个桶中; 第二步试探阶段,对另一个表(S),每次读入一个块,对每一条元组分别用相同的Hash函数计算其连接属性的Hash值,得到桶号,到相应的桶中寻找R的相匹配元组,并进行连接。
当R和S都不能一次放入内存时,需要进行两趟或多趟Hash连接。即首先用连接属性Y作散列键,将R和S划分为可独立连接对,保证每个可独立连接对中,有一个子关系能放入内存;然后对对应桶对进行一趟连接。
(4)索引连接方法(index join): 对于R(X,Y)和S(Y,Z)的索引连接操作,其基本过程为: ①如果原来S表Y属性上没有索引,则建立索引; ②对R中每一条元组,根据其Y值查找S的索引,寻找具有该Y值的S元组;③把这些S元组和R元组连接起来。循环执行②和③,直到S表中的元组处理完为止。
去除重复值、分组聚集、集合操作等其他操作符的实现也分为一次读入内存的算法、基于排序的算法和基于Hash的算法等几类算法。
在线咨询
