PPT《第九章 关系查询处理和查询优化》

201215121'

假设Sno上有索引(或Sno是散列码)算法:使用索引(或散列)得到Sno为'

201215121'

元组的指针通过元组指针在Student表中检索到该学生 选择操作的实现(续) [例9.1-C3] SELECT FROM Student WHERE Sage>

20假设Sage 上有B+树索引算法:使用B+树索引找到Sage=20的索引项,以此为入口点在B+树的顺序集上得到Sage>

20的所有元组指针通过这些元组指针到student表中检索到所有年龄大于20的学生. 选择操作的实现(续) [例9.1-C4] SELECT FROM Student WHERE Sdept='

CS'

AND Sage>

20;

假设Sdept和Sage上都有索引算法一:分别用Index Scan找到Sdept='

CS'

的一组元组指针和Sage>

20的另一组元组指针求这两组指针的交集到Student表中检索得到计算机系年龄大于20的学生 选择操作的实现(续) 算法二:找到Sdept='

CS'

的一组元组指针,通过这些元组指针到Student表中检索并对得到的元组检查另一些选择条件(如Sage>

20)是否满足把满足条件的元组作为结果输出. 2.连接操作的实现 连接操作是查询处理中最耗时的操作之一 本节只讨论等值连接(或自然连接)最常用的实现算法 [例9.2] SELECT FROM Student, SC WHERE Student.Sno=SC.Sno;

连接操作的实现(续) (1)嵌套循环算法(nested loop join) (2)排序-合并算法(sort-merge join 或merge join)(3)索引连接(index join)算法 (4)Hash Join算法 连接操作的实现(续) (1)嵌套循环算法(nested loop join)对外层循环(Student表)的每一个元组(s),检索内层循环(SC表)中的每一个元组(sc)检查这两个元组在连接属性(Sno)上是否相等如果满足连接条件,则串接后作为结果输出,直到外层循环表中的元组处理完为止.参见爱课程网9.1节动画《连接操作的实现(1)--嵌套循环》 连接操作的实现(续) (2)排序-合并算法(sort-merge join 或merge join) 如果连接的表没有排好序,先对Student表和SC表按连接属性Sno排序 取Student表中第一个Sno,依次扫描SC表中具有相同Sno的元组 当扫描到Sno不相同的第一个SC元组时,返回Student表扫描它的下一个元组,再扫描SC表中具有相同Sno的元组,把它们连接起来 重复上述步骤直到Student 表扫描完 连接操作的实现(续)

201215121 …201215122 …201215123 …201215125 …...

201215121 1

92201215121 2

85201215121 3

88201215122 2

90201215122 3 80... 图9.2 排序-合并连接方法示意图 连接操作的实现(续) Student表和SC表都只要扫描一遍如果两个表原来无序,执行时间要加上对两个表的排序时间对于大表,先排序后使用排序-合并连接算法执行连接,总的时间一般仍会减少 参见爱课程网9.1节动画《连接操作的实现(2)--排序合并 》 连接操作的实现(续) (3)索引连接(index join)算法步骤:① 在SC表上已经建立属性Sno的索引.② 对Student中每一个元组,由Sno值通过SC的索引查找相应的SC元组. ③ 把这些SC元组和Student元组连接起来 循环执行②③,直到Student表中的元组处理完为止 参见爱课程网9.1节动画《连接操作的实现(4)-- 索引连接 》 连接操作的实现(续) (4)Hash Join算法 把连接属性作为hash码,用同一个hash函数把Student表和SC表中的元组散列到hash表中.划分阶段(building phase, 也称为partitioning phase)对包含较少元组的表(如Student表)进行一遍处理把它的元组按hash函数分散到hash表的桶中试探阶段(probing phase,也称为连接阶段join phase) 对另一个表(SC表)进行一遍处理把SC表的元组也按同一个hash函数(hash码是连接属性)进行散列把SC元组与桶中来自Student表并与之相匹配的元组连接起来 连接操作的实现(续) 上面hash join算法前提:假设两个表中较小的表在第一阶段后可以完全放入内存的hash桶中 参见爱课程网9.1节动画《连接操作的实现(3)--散列连接 》