选择操作的实现(续) 令[例1C4]以C4为例, Sdept=‘ CS AND Sage>20, 如果 Sdept和Sage上都有索引: 算法一:分别用上面两种方法分别找到 Sdept=“CS的 组元组指针和Sage>20的另一组元组指针 求这2组指针的交集 到 student表中检索 得到计算机系年龄大于20的学生 算法二:找到 Sdept=‘CS'的一组元组指针, 通过这些元组指针到 student表中检索 >对得到的元组检查另一些选择条件(如Sage>20)是否满足 >把满足条件的元组作为结果输出。 An Introduction to Database System
An Introduction to Database System 选择操作的实现（续） ❖［例1-C4］ 以C4为例，Sdept＝‘CS’ AND Sage>20， 如果Sdept和Sage上都有索引： ▪ 算法一：分别用上面两种方法分别找到Sdept＝‘CS’的一 组元组指针和Sage>20的另一组元组指针 ➢求这2组指针的交集 ➢到student表中检索 ➢得到计算机系年龄大于20的学生 ▪ 算法二：找到Sdept＝‘CS’的一组元组指针， ➢通过这些元组指针到student表中检索 ➢对得到的元组检查另一些选择条件(如Sage>20)是否满足 ➢把满足条件的元组作为结果输出
二、连接操作的实现 ◆连接操作是査询处理中最耗时的操作之 ☆本节只讨论等值连接(或自然连接)最常用的实现 算法 ☆[例2] SELECT* FROM Student,SC WHERE Student Sno=SC Sno An Introduction to Database System
An Introduction to Database System 二、 连接操作的实现 ❖连接操作是查询处理中最耗时的操作之一 ❖本节只讨论等值连接(或自然连接)最常用的实现 算法 ❖ ［例2］ SELECT * FROM Student，SC WHERE Student.Sno=SC.Sno；
连接操作的实现(续) ☆1.嵌套循环方法 nested loop) 2排序合并方法 sort-merge join或 merge joIn) 3.索引连接( index joir)方法 4. Hash joir方法 An Introduction to Database System
An Introduction to Database System 连接操作的实现（续） ❖1. 嵌套循环方法(nested loop) ❖2. 排序-合并方法(sort-merge join 或merge join) ❖3. 索引连接(index join)方法 ❖4. Hash Join方法
连接操作的实现(续) 1.嵌套循环方法( nested loop) 对外层循环( Studen的每一个元组(s),检索内层循环 (SC)中的每一个元组(c) 检査这两个元组在连接属性(Sno)上是否相等 如果满足连接条件,则串接后作为结果输出,直到外 层循环表中的元组处理完为止 An Introduction to Database System
An Introduction to Database System 连接操作的实现（续） 1. 嵌套循环方法(nested loop) ▪ 对外层循环(Student)的每一个元组(s)，检索内层循环 (SC)中的每一个元组(sc) ▪ 检查这两个元组在连接属性(sno)上是否相等 ▪ 如果满足连接条件，则串接后作为结果输出，直到外 层循环表中的元组处理完为止
连接操作的实现(续) 2排序合并方法( sort-merge join或 merge join 适合连接的诸表已经排好序的情况 排序一合并连接方法的步骤: 如果连接的表没有排好序,先对 Student表和SC表按连接 属性Sno排序 取 Student表中第一个Sno,依次扫描SC表中具有相同 Sno的元组 An Introduction to Database System
An Introduction to Database System 连接操作的实现（续） 2. 排序-合并方法(sort-merge join 或merge join) ▪ 适合连接的诸表已经排好序的情况 ▪ 排序－合并连接方法的步骤： ➢如果连接的表没有排好序，先对Student表和SC表按连接 属性Sno排序 ➢取Student表中第一个Sno，依次扫描SC表中具有相同 Sno的元组