择运算&外部排.ppt

《择运算&外部排.ppt》由会员分享，可在线阅读，更多相关《择运算&外部排.ppt（31页珍藏版）》请在三一办公上搜索。

1、选择运算&外部排序,选择运算概述,选择运算,外部排序,选择运算&外部排序,1,2,3,查询实例SELECT*FROM students WHERE;条件表达式的几种情况C1：无条件C2：Sno=2011003;C3：Sage 20;C4：Sdept=CS ANDSage 20;,选择运算概述选择运算的查询处理,查询实例SELECT*FROM students;全表顺序扫描优点：简单有效,选择运算概述选择运算的查询处理C1,2011001,2011002,2011003,2011004,2011005,Students,查询实例SELECT*FROM studentsWHERE Sno=2011

2、003;选择条件的属性上有索引索引/散列扫描,选择运算概述选择运算的查询处理C2,2011001,2011002,2011003,2011004,2011005,Students,Sno是主码,内存中,磁盘上,选择运算概述选择运算的查询处理C3,查询实例SELECT*FROM studentsWHERE Sage20;选择条件是范围查询或非等值查询，或非主属性等值的查询查询结果数目不明确估算查询结果的元组数量如果查询结果的元组数量10%，且选择列上有索引使用索引扫描否则，使用全表顺序扫描,选择运算概述选择运算的查询处理C4,查询实例SELECT*FROM studentsWHERE Sdept

3、=CS AND Sage20;,选择运算概述选择运算的查询处理C4,查询实例SELECT*FROM studentsWHERE Sdept=CS AND Sage20;合取选择查询分别找到符合各个条件的元组指针，取指针的交集；或者找到符合第一个条件的元组指针，在此范围内检查另一条件是否满足析取选择查询：使用全表顺序扫描,选择运算处理的代价可以通过该查询对各种资源的使用情况进行度量，主要包括磁盘存取时间、执行一个查询所用的CPU时间、以及在并行/分布式数据库系统中的通信开销等。对于大型数据库系统而言，在磁盘上存取数据的代价通常是最重要的代价，可以通过传输磁盘块数以及搜索磁盘次数来度量。例如，一个

4、传输b块并作s次磁盘搜索的操作将耗时b*tT+s*tS 毫秒(ms)，其中，tT表示传输一块数据的平均耗时，tS表示搜索一次磁盘的平均定位时间(包括搜索时间加旋转时间)。,选择运算概述代价度量,线性搜索算法A1 线性搜索中，系统扫描每一个磁盘块，对所有记录进行测试，看它们是否满足选择条件。开始时需作一次磁盘搜索来定位文件的第一个磁盘块。线性搜索的代价为EA1=tS+br*tT，码属性等值比较平均代价EA1=tS+（br/2）*tT，其中br代表文件中的磁盘块数。优点：可用于任何文件，不管该文件是否有序，是否有索引，也不管何种类型的选择操作；缺点：线性搜索比其他实现选择操作的算法速度慢。,选择运

5、算文件扫描,二分搜索算法A1 搜索过程是针对磁盘的数据块进行，而不是针对记录进行最坏情况下，找到包含所需记录的磁盘块所需访问和检查的磁盘块数目为log2(br)，而且每一个这样的磁盘块都需要一次磁盘搜索定位，因此算法A1的时间代价为 EA1=log2(br)*(tT+tS)。,选择运算文件扫描,主索引码属性上的等值比较算法A2 具有主索引的码属性上的等值比较算法，可以通过主索引检索到指向满足相应等值条件的唯一记录的指针，再根据该指针到数据文件中访问磁盘块。若使用B+树索引，则访问索引块的数量等于树高度HTi，访问文件块的数量为1；而且每一次I/O操作都需要一次磁盘搜索定位和一次磁盘块传输。因此

6、，算法A2的时间代价为：EA2=(hi+1)*(tT+tS)。,选择运算索引扫描,主索引非码属性上的等值比较算法A3 具有主索引的非码属性上的等值比较算法，通过主索引检索到指向满足相应等值条件的第一条记录（可能有多条记录，但它们在物理上顺序存放）的指针，再根据该指针到数据文件中访问磁盘块。算法A3的时间代价为 EA3=hi*(tT+tS)+b*tT,选择运算索引扫描,辅助索引的等值比较算法A4 如果是码属性上的等值条件，算法A5的时间代价与算法A2相同，EA4=(hi+1)*(tT+tS)。如果是非码属性上的等值条件，每条记录可能存在于不同的磁盘块中：B+树索引检索每条记录都需要一次I/0操作

7、，以及读取每条记录都需要一次I/0操作，最坏情况开销甚至会比线性搜索更差。最坏情况下，算法A4的时间代价为：EA4=(hi+n)*(tT+tS),选择运算索引扫描,主索引上的范围比较算法A5 对于形如Av或Av的比较条件，首先通过主索引（如B+树索引）搜索，定位在满足Av或Av条件的第一个索引项，该索引项中的指针指向满足查询条件的所有记录中的第一条，然后通过该指针到文件中搜索磁盘块，并从该磁盘块开始顺序访问所有的磁盘块，直到文件结束。其时间代价可估算为 EA5=hi*(tT+tS)+b*tT 对于形如Av或Av的比较条件，没有必要查找索引，时间代价为：EA5=tS+b*tT,选择运算范围比较,

8、辅助索引上的范围比较算法A6 对于“”“”情形，扫描是从v开始直到最大值为止。辅助索引每条记录可能存在于不同的磁盘块中：B+树索引检索每条记录都需要一次I/0操作，以及读取每条记录都需要一次I/0操作。如果满足查询条件的记录数很多，使用辅助索引的代价甚至比线性搜索还要大。辅助索引只适合于满足查询条件的记录很少时使用。,选择运算范围比较,合取()选择操作一般形式为：利用一个索引的合取选择算法A7 首先确定一个选择属性Ai上存在索引。如果存在，则首先用选择算法A2A6中的一个来检索该条件的记录；然后在内存缓冲区中，通过测试每条检索到的记录是否满足其余的选择谓词，所有满足其余选择谓词的记录都是该合取

9、选择操作的最后结果。为了减少代价，选择某个i及A2A6的算法之一，它们的组合可使的代价达到最小，并且所选算法的代价就是算法A8的代价。,选择运算合取选择,利用组合索引的合取选择算法A8组合索引在多个属性上建立的一个索引如果选择指定的是两个或多个属性上的等值选择，并且在这些属性字段的组合上存在组合索引，此时可以直接搜索索引。索引的类型将决定使用A2、A3、A4算法中的哪一个,选择运算合取选择,通过记录标识的交实现合取选择的算法A9首先，对每一个选择属性上均存在带记录指针的索引，对每个索引进行扫描，获取那些指向满足单个条件的记录的指针；然后，得到这些指针的交集；第三，根据交集中的每一个指针到文件中

10、去访问磁盘块并检索相关记录，这些记录就是满足所有这些带索引谓词的合取条件的记录。算法A9的代价是扫描各个单独索引的代价的总和，加上获取指针列表Li的交集列表L中的指针所指向记录的代价。,选择运算复杂选择的实现,析取选择操作的一般形式为：通过记录标识的并实现析取选择的算法A10 如果析取选择中的所有条件上都存在相应的索引，则首先逐个扫描索引来获取满足单个条件的元祖指针；然后，得到这些指针的并集；最后根据并集中的每一个指针到文件中去访问磁盘块并检索相关记录。算法A10的代价是扫描各个单独索引的代价的总和，加上获取检索到的指针列表Li的并集列表L中的指针所指向记录的代价。然而，即使只有其中一个条件不

11、存在索引，也不得不对这个关系进行一次线性扫描。因此，若析取中存在这样的条件，最有效的存取方法就是线性扫描。,选择运算析取选择,SQL查询会指明对结果进行排序当输入的关系已排序时，关系运算中的一些运算能够得到高效实现排序码上建立索引，仅仅在逻辑上通过索引对关系排序，而没有在物理上排序,外部排序数据排序的重要作用,待排序的记录数量巨大，无法一次调入内存，只能驻留在外存上（磁带、磁盘、CD-ROM）上。此时不能使用内部排序的方法进行排序，否则将引起频繁访问外存。外部排序主要的时间开销用在信息的内、外存交换上，所以减少 I/O 时间成为要解决的主要问题。,外部排序外部排序使用原因,将文件中的数据分段读

12、取到内存中，在内存中利用内部排序方法对其进行排序，排序完的文件段称为“归并段”，然后将其写回外存中；对这些初始归并段采用某种归并方法，进行多遍归并，最后在外存中形成整个文件的单一归并段，也就完成了这个文件的外排序，这个过程中的每次归并都伴随I/O操作。,外部排序外部排序基本步骤,创建有序归并段:令 i 初始为0重复下列步骤直至关系末尾:(a)将关系的M 块读入内存(b)在内存中对关系的这一部分进行排序(c)将排好序的数据写到归并段文件 Ri 中;递增 i设i 的最后的值为N,外部排序外部排序步骤,对归并段进行归并(N路归并):目前假设 N M利用内存的 N 块来缓冲输入归并段，一块缓冲输出。按

13、序将各归并段的第一块读入其缓冲页repeat缓冲页进行排序，挑选缓冲页中第一条记录(按排序顺序)将该记录作为输出写出，将其写入磁盘从输入缓冲页删除该记录If 任何一个归并段文件Ri的缓冲块为空并且没有达到末尾 then 将该归并段的下一块读入缓冲块until 所有输入缓冲块都为空:,外部排序外部排序步骤,若N M,需要若干归次并在每一次归并中,归并 M-1 个归并段（M-1路归并）此时内存缓冲区中的M块，头M-1块用作输入，1块缓冲输出每一趟归并后归并段数目减少为原来的 1/(M-1)例如 若M=11,并有90个序段,则一趟就将序段数减少到9，而归并段长度则是初始归并段的10倍重复执行若干趟直

14、至所有归并段被归并为一个归并段,外部排序外部排序步骤,外部排序示例,初始阶段的归并段创建所需磁盘存取次数为2br所需总的归并趟数:logM1(br/M)对最后一趟,我们不计算写代价我们对所有操作都忽略最后的写代价,因为操作的输出可能送往父操作,不许要写到磁盘因此外排序的总的磁盘存取数为:br(2 logM1(br/M)+1),外部排序外部排序磁盘传输代价分析,初始阶段需要为读取每个归并段作磁盘搜索，也要为写回归并段作磁盘搜索，共2 br/M 次所需总的归并趟数:logM1(br/M)对最后一趟,我们不计算写回磁盘的搜索代价因此外排序的总的磁盘搜索次数为:考虑bb的情况：2 br/M+br(2 logM1(br/M)1)不考虑bb的情况：2 br/M+br/bb(2 logM/bb1(br/M)1),外部排序外部排序代价分析,分别计算示例中外部排序磁盘搜索产生的磁盘传输代价和磁盘搜索代价思考如果在初始阶段产生的归并段长度不一，在归并阶段用什么方法进行归并，产生的代价最少。,外部排序思考题,谢谢大家!,