选择运算.ppt

选择运算&外部排序
1
精选可编辑ppt
选择运算概述
选择运算
外部排序
选择运算&外部排序
1
2
3
2
精选可编辑ppt
查询实例
SELECT *
FROM students
WHERE <条件表达式>;
条件表达式的几种情况
C1：无条件
C2：Sno = ‘2011003’;
C3：Sage > 20;
C4：Sdept = ‘CS’ AND Sage > 20;
选择运算概述
选择运算的查询处理
3
精选可编辑ppt
查询实例
SELECT *
FROM students;
全表顺序扫描
优点：简单有效
选择运算概述
选择运算的查询处理—C1
2011001, …
2011002, …
2011003, …
2011004, …
2011005, …
…
Students
4
精选可编辑ppt
查询实例
SELECT *
FROM students
WHERE Sno=‘2011003’;
选择条件的属性上有索引
索引/散列扫描
选择运算概述
选择运算的查询处理—C2
2011001, …
2011002, …
2011003, …
2011004, …
2011005, …
…
Students
Sno是主码
内存中
磁盘上
5
精选可编辑ppt
选择运算概述
选择运算的查询处理—C3
查询实例
SELECT *
FROM students
WHERE Sage>20;
选择条件是范围查询或非等值查询，或非主属性等值的查询
查询结果数目不明确估算查询结果的元组数量
如果查询结果的元组数量<10%，且选择列上有索引
使用索引扫描
否则，使用全表顺序扫描
6
精选可编辑ppt
选择运算概述
选择运算的查询处理—C4
查询实例
SELECT *
FROM students
WHERE Sdept=‘CS’ AND Sage>20;
Sdept
Sage
2011001, 21, CS, …
2011002, 19, MA, …
2011003, 22, CS, …
2011004, 20, CS, …
2011005, 21, IS, …
…
7
精选可编辑ppt
选择运算概述
选择运算的查询处理—C4
查询实例
SELECT *
FROM students
WHERE Sdept=‘CS’ AND Sage>20;
合取选择查询
分别找到符合各个条件的元组指针，取指针的交集；或者
找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足
析取选择查询：使用全表顺序扫描
8
精选可编辑ppt
选择运算处理的代价可以通过该查询对各种资源的使用情况进行度量，主要包括磁盘存取时间、执行一个查询所用的CPU时间、以及在并行/分布式数据库系统中的通信开销等。
对于大型数据库系统而言，在磁盘上存取数据的代价通常是最重要的代价 ，可以通过传输磁盘块数以及搜索磁盘次数来度量。
例如，一个传输b块并作s次磁盘搜索的操作将耗时b*tT+s*tS 毫秒(ms)，其中，tT表示传输一块数据的平均耗时，tS表示搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)。
选择运算概述
代价度量
9
精选可编辑ppt
线性搜索算法A1
线性搜索中，系统扫描每一个磁盘块，对所有记录进行测试，看它们是否满足选择条件。开始时需作一次磁盘搜索来定位文件的第一个磁盘块。
线性搜索的代价为EA1=tS + br*tT，码属性等值比较平均代价EA1=tS +（br /2）*tT ，其中br代表文件中的磁盘块数。
优点：可用于任何文件，不管该文件是否有序，是否有索引，也不管何种类型的选择操作；
缺点：线性搜索比其他实现选择操作的算法速度慢。
选择运算
文件扫描
10
精选可编辑ppt