第5章 查询处理.ppt

《第5章 查询处理.ppt》由会员分享，可在线阅读，更多相关《第5章 查询处理.ppt（66页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第5章章 查询处理查询处理Silberschatz,Korth and Sudarshan13.2Database System Concepts本章内容特色n实实：在实现：在实现DBMS和高级应用中有用和高级应用中有用，是数据库，是数据库管理员必备知识管理员必备知识n细细：细致：细致，有有一定一定难度难度，课堂上不一定能完全理，课堂上不一定能完全理解解，需，需课课后仔后仔细细体会体会n定定：定量分析，：定量分析，比比较较不同方案用数字来作不同方案用数字来作结论结论n模模：定量分析需要数学模型：定量分析需要数学模型(先先作一些假定，忽略作一些假定，忽略一些次要的因素，用一套符号表示一些度量，

2、一些次要的因素，用一套符号表示一些度量，然然后计算除结果，可学到建立定量分析模型的方法后计算除结果，可学到建立定量分析模型的方法)Silberschatz,Korth and Sudarshan13.3Database System Concepts主要内容主要内容n查询处理基本步骤查询处理基本步骤n查询代价度量查询代价度量n选择操作选择操作n排序排序n连接操作连接操作n其他操作其他操作n表达式求值表达式求值Silberschatz,Korth and Sudarshan13.4Database System ConceptsDBMS ArchitectureQuery ExecutorBuf

3、fer ManagerStorage ManagerStorageTransaction ManagerLogging&RecoveryLock ManagerBuffersLock TablesMain MemoryUser/Web Forms/Applications/DBAquerytransactionQuery OptimizerQuery RewriterQuery ParserFiles&Access MethodsPast lecturesSilberschatz,Korth and Sudarshan13.5Database System Concepts查询处理基本步骤查询

4、处理基本步骤1.词法分析与翻译词法分析与翻译(本章本章)2.优化优化(下章下章)3.求值求值(本章本章)Silberschatz,Korth and Sudarshan13.6Database System Concepts查询处理基本步骤查询处理基本步骤 n词法分析与翻译词法分析与翻译将查询翻译成内部形式将查询翻译成内部形式,再翻译成关系代数表达式再翻译成关系代数表达式词法分析器检查语法词法分析器检查语法,验证关系验证关系n求值求值查询执行引擎以查询求值方案为输入查询执行引擎以查询求值方案为输入,执行该方案执行该方案,并返回查询结果并返回查询结果Silberschatz,Korth and

5、Sudarshan13.7Database System Concepts查询处理的基本步骤查询处理的基本步骤n求值计求值计划划在表达式上加标注以说明详细求值策略在表达式上加标注以说明详细求值策略,称为称为求值计划求值计划例如例如,可利用可利用balance上的索引来查找余额小上的索引来查找余额小于于2500的账户的账户,或者也可以执行完全的关系扫或者也可以执行完全的关系扫描描,丢弃那些余额丢弃那些余额 2500的账户的账户n查询优化查询优化在所有等价的求值计划中选择代价最低者在所有等价的求值计划中选择代价最低者利用数据库目录中的统计信息来求值代价利用数据库目录中的统计信息来求值代价如每个关系

6、的元组数如每个关系的元组数,元组大小等元组大小等Silberschatz,Korth and Sudarshan13.8Database System Concepts查询处理的基本步骤查询处理的基本步骤:优化优化n本章研究本章研究如何度量查询代价如何度量查询代价关系代数运算的求值算法关系代数运算的求值算法如何将单个运算的算法结合起来以对整个表达式求如何将单个运算的算法结合起来以对整个表达式求值值n下章研究下章研究如何优化查询如何优化查询,即如何找到具有最低求值代价的求值即如何找到具有最低求值代价的求值计划计划Silberschatz,Korth and Sudarshan13.9Databa

7、se System Concepts查询代价的度量查询代价的度量n查询代价通常用回答查询所耗费总时间来度量查询代价通常用回答查询所耗费总时间来度量n许多因素影响时间代价许多因素影响时间代价磁盘存取磁盘存取(I/O),CPU,网络通信网络通信n一般来说一般来说,磁盘存取对代价起决定性作用磁盘存取对代价起决定性作用,并且相对并且相对容易求值，磁盘存取代价的度量要考虑容易求值，磁盘存取代价的度量要考虑:寻址次数寻址次数 *average-seek-cost读块数读块数*average-block-read-cost写块数写块数*average-block-write-cost写一块的代价大于读一块的

8、代价写一块的代价大于读一块的代价写数据后要读回，以确保写成功写数据后要读回，以确保写成功Silberschatz,Korth and Sudarshan13.10Database System Concepts查询代价的度量查询代价的度量n为简单起见为简单起见,我们仅用我们仅用磁盘块传送数磁盘块传送数作为代价的度量作为代价的度量忽略忽略顺序顺序与与随机随机I/O之间的代价不同之处之间的代价不同之处忽略忽略CPU代价代价n代价依赖于内存缓冲区的大小代价依赖于内存缓冲区的大小内存多可以减少磁盘存取数内存多可以减少磁盘存取数可用于缓冲区的实际内存量取决于其他并发可用于缓冲区的实际内存量取决于其他并发

9、OS进程进程,在实际执行在实际执行之前难以确定之前难以确定我们经常用最坏情形求值我们经常用最坏情形求值,故假定只有操作所需的最小内存量可用故假定只有操作所需的最小内存量可用n实际系统要考虑实际系统要考虑CPU代价代价,区分顺序与随机区分顺序与随机I/O,考虑缓冲考虑缓冲区大小区大小n在代价公式中不包括将输出写到磁盘的代价在代价公式中不包括将输出写到磁盘的代价Silberschatz,Korth and Sudarshan13.11Database System Concepts插曲：插曲：科研方法科研方法(10/12)n借本章内容为载体，介绍一些作科研的方法借本章内容为载体，介绍一些作科研的方

10、法n原创工作原创工作 vs 非原创工作非原创工作 vs delta 研究研究1.建立模型：引入记号，变量，确定变量之间关系建立模型：引入记号，变量，确定变量之间关系，常常常简化模型，忽略次要因素，抓主要矛盾常简化模型，忽略次要因素，抓主要矛盾2.分而治之，分而治之，先先推导局部公式推导局部公式综合公式综合公式3.从公式分析，改进方向从公式分析，改进方向4.改进，试验，结论改进，试验，结论论文或成果论文或成果n建立数学模型是深入建立数学模型是深入研究研究的开始的开始Silberschatz,Korth and Sudarshan13.12Database System Concepts插曲：插曲

11、：科研方法科研方法n简化模型：简化模型：(即即忽略次要因素，抓主要矛盾）忽略次要因素，抓主要矛盾）1.传输块数传输块数number of block transfers（盘：内存）（盘：内存）2.忽略顺序和随机忽略顺序和随机I/O 的差别，忽略的差别，忽略CPU的花销的花销3.花销大小依赖于缓存大小花销大小依赖于缓存大小缓存大，磁盘传输快缓存大，磁盘传输快OS 管理缓存（进程）管理缓存（进程）常用最坏情形估计常用最坏情形估计worst case estimates在工程中的实际系统不忽略在工程中的实际系统不忽略CPU 花销，要考虑随机花销，要考虑随机和顺序的影响和顺序的影响输出时写盘的时间也忽

12、略输出时写盘的时间也忽略Silberschatz,Korth and Sudarshan13.13Database System Concepts用于代价估算的统计信息用于代价估算的统计信息nnr:关系关系r 中的元组个数中的元组个数nbr:包含包含r 中元组的块数中元组的块数nsr:r 中元组的大小中元组的大小nfr:r 的块因子的块因子 即即,能放入一块之中的能放入一块之中的r 的元组数的元组数nV(A,r):r 中出现的中出现的A属性上的不同值的个数属性上的不同值的个数,等于等于A(r)的大小的大小nSC(A,r):关系关系r 中属性中属性A的的选择基数选择基数,满足满足A上等值上等值条

13、件的平均记录数条件的平均记录数n若若r 中元组在文件中中元组在文件中连续存放连续存放,则则:Silberschatz,Korth and Sudarshan13.14Database System Concepts关于索引的目录信息关于索引的目录信息nfi:索引索引i 的内节点的平均扇出的内节点的平均扇出,适用于树适用于树结构索引结构索引,如如B+树树nHTi:索引索引i 的层数的层数 即高度即高度对于关系对于关系r上上A 属性的平衡树索引属性的平衡树索引(如如B+-树树),HTi=logfi(V(A,r)n对于散列索引对于散列索引,HTi 为为1nLBi:索引索引i 的底层索引块数的底层索引

14、块数 即索引叶即索引叶子层的块数子层的块数Silberschatz,Korth and Sudarshan13.15Database System Concepts选择操作选择操作n文件扫描文件扫描 定位并读取满足选择条件的记录的搜索算定位并读取满足选择条件的记录的搜索算法法n算法算法A1(线性搜索线性搜索):扫描每个文件块并测试所有记录是扫描每个文件块并测试所有记录是否满足选择条件否满足选择条件求值代价求值代价(扫描磁盘块数扫描磁盘块数)=br br 表示包含有关系表示包含有关系r 的记录的块数的记录的块数若选择是针对键属性的若选择是针对键属性的,则代价则代价=(br/2)找到记录后终止找到

15、记录后终止线性搜索的可用性不受下列因素影响线性搜索的可用性不受下列因素影响选择条件选择条件文件中记录的顺序文件中记录的顺序有无索引有无索引Silberschatz,Korth and Sudarshan13.16Database System Concepts选择操作选择操作(续续)n算法算法A2(二叉搜索二叉搜索):如果文件有序且选择条件如果文件有序且选择条件是在排序属性上的相等性比较即可用是在排序属性上的相等性比较即可用n假设关系的块连续存储假设关系的块连续存储n求值代价求值代价(扫描的磁盘块数扫描的磁盘块数):log2(br)通过对块的二叉搜索来定位通过对块的二叉搜索来定位第一条元组的代

16、价第一条元组的代价再加上包含满足选择条件的记录的块数再加上包含满足选择条件的记录的块数第第6章讨论如何求这个代价章讨论如何求这个代价Silberschatz,Korth and Sudarshan13.17Database System Concepts利用索引的选择利用索引的选择n索引扫描索引扫描 使用索引的搜索算法使用索引的搜索算法选择条件必须针对索引的搜索键选择条件必须针对索引的搜索键nA3(候选键上的主索引候选键上的主索引,相等相等):检索满足对应等式条件的单个记录检索满足对应等式条件的单个记录Cost=HTi+1nA4(非键属性上的主索引非键属性上的主索引,相等相等):检索多条记录检

17、索多条记录记录位于连续的块上记录位于连续的块上Cost=HTi+包含检索记录的块数包含检索记录的块数nA5(辅助索引搜索键上的相等辅助索引搜索键上的相等)若搜索键是候选键则检索单个记录若搜索键是候选键则检索单个记录Cost=HTi+1若搜索键不是候选键则检索多个记录若搜索键不是候选键则检索多个记录Cost=HTi+检索到的记录数检索到的记录数可能非常昂贵可能非常昂贵!各记录可能位于不同的块上各记录可能位于不同的块上 对每条检索到的记录都有一次块存取对每条检索到的记录都有一次块存取Silberschatz,Korth and Sudarshan13.18Database System Conce

18、pts涉及比较的选择涉及比较的选择n为实现形如为实现形如 A V(r)或者或者 A V(r)的选择的选择,可以使用可以使用线性文件扫描或二叉搜索线性文件扫描或二叉搜索n或者按如下方式使用索引或者按如下方式使用索引:nA6(主索引主索引,比较比较)(关系在关系在A上排序上排序)对对 A V(r)利用索引找到第一条利用索引找到第一条 v 的元组的元组,再从该处顺序再从该处顺序扫描关系扫描关系对对 A V(r)顺序扫描关系直至第一条顺序扫描关系直至第一条 v 的元组的元组;不用索引不用索引nA7(辅助索引辅助索引,比较比较)对对 A V(r)利用索引找到第一条利用索引找到第一条 v 的索引项的索引项

19、,再从该处顺再从该处顺序扫描索引序扫描索引,查处指向记录的指针查处指向记录的指针.对对 A V(r)只需扫描索引的叶页来找出指向记录的指针只需扫描索引的叶页来找出指向记录的指针,直直至第一条至第一条 v 的项的项在每种情况下在每种情况下,检索被指向的记录时检索被指向的记录时:每条记录需要一次每条记录需要一次I/O如果有很多记录需要取出如果有很多记录需要取出,则线性文件扫描可能更廉价则线性文件扫描可能更廉价!Silberschatz,Korth and Sudarshan13.19Database System Concepts复杂选择的实现复杂选择的实现合取合取:1 2.n(r)nA8(利用一

20、个索引的合取选择利用一个索引的合取选择)选择一个选择一个 i 和算法和算法A1到到A7的组合使得的组合使得 i(r)的代价最小的代价最小将元组取进内存缓冲区之后再测试其他条件将元组取进内存缓冲区之后再测试其他条件nA9(利用多键索引的合取选择利用多键索引的合取选择)如果可能如果可能,使用合适的复合使用合适的复合(多键多键)索引索引nA10(求标识符交集的合取选择求标识符交集的合取选择)需要带有记录指针的索引需要带有记录指针的索引对每个条件使用对应的索引对每个条件使用对应的索引,再求所有得到的记录指针集合的交集再求所有得到的记录指针集合的交集然后从文件读取记录然后从文件读取记录如果某些条件没有对

21、应的索引如果某些条件没有对应的索引,则对已读取记录进行该条件的测试则对已读取记录进行该条件的测试.Silberschatz,Korth and Sudarshan13.20Database System Concepts复杂选择的算法复杂选择的算法析取析取:1 2.n(r)nA11(利用标识符的并集求析取选择).应用于所有条件都有可用的索引的情况应用于所有条件都有可用的索引的情况.否则使用线性扫描否则使用线性扫描利用每个条件的对应索引利用每个条件的对应索引,再求所得到的各记录指针集再求所得到的各记录指针集的并集的并集然后从文件读取记录然后从文件读取记录Silberschatz,Korth an

22、d Sudarshan13.21Database System Concepts排序排序(略略)n小关系排序，内存能装下，用小关系排序，内存能装下，用quicksort等内存等内存排序算法排序算法n大文件排序，由于内存装不下，可以先在关系大文件排序，由于内存装不下，可以先在关系上建立一个索引上建立一个索引,然后利用该索引来按排好的顺然后利用该索引来按排好的顺序读入关系序读入关系n可能导致每条元组需要一次磁盘块存取可能导致每条元组需要一次磁盘块存取n对不能放进内存的大关系对不能放进内存的大关系,外排序是一个好的选外排序是一个好的选择择Silberschatz,Korth and Sudarsha

23、n13.22Database System Concepts排序排序n下面将介绍用于大文件的归并排序法下面将介绍用于大文件的归并排序法n思想：设三个班已经分别排序，现全年级思想：设三个班已经分别排序，现全年级排序，在各班第一中选第一名，移动到年排序，在各班第一中选第一名，移动到年级第一名位置，以此类推（递归）级第一名位置，以此类推（递归）,如果要如果要排全校序，再归并排全校序，再归并Silberschatz,Korth and Sudarshan13.23Database System Concepts外排序外排序-归并归并1.创建有序创建有序序段序段(run):令 i 初始为0重复下列步骤直

24、至关系末尾:(a)将关系的M 块读入内存 (b)对内存块排序 (c)将以排序数据写到序段 Ri;递增 i设i 的最后的值为N令令M 表示内存大小表示内存大小(以页为单位以页为单位)Silberschatz,Korth and Sudarshan13.24Database System Concepts外排序外排序-归并归并2.归并序段归并序段(N路归并路归并):目前假设 N Silberschatz,Korth and Sudarshan13.50Database System Concepts复杂连接复杂连接n带有合取条件的连接带有合取条件的连接:r 1 2.n sn使用嵌套循环使用嵌套循环

25、/块嵌套循环块嵌套循环,或者或者n计算一个简单连接的结果计算一个简单连接的结果 r i sn最终结果由中间结果中满足下列剩余条件的元组组成最终结果由中间结果中满足下列剩余条件的元组组成 1 .i 1 i+1 .nn带有析取条件的连接带有析取条件的连接 r 1 2 .n s n使用使用嵌套循环嵌套循环/块嵌套循环块嵌套循环,或者或者n计算各简单连接计算各简单连接r i s的结果中记录的并集的结果中记录的并集:(r 1 s)(r 2 s).(r n s)Silberschatz,Korth and Sudarshan13.51Database System Concepts其它操作：投影其它操作：

26、投影n投影的实现方法投影的实现方法:在每个元组上执行投影在每个元组上执行投影,再进行重复再进行重复元组删除元组删除n删除重复元组可通过散列或排序实现删除重复元组可通过散列或排序实现n排序后排序后,重复元组将相邻重复元组将相邻,保留一个保留一个,其余删除即可其余删除即可n优化优化:在外归并排序中在外归并排序中,删除重复元组可以在序段生成删除重复元组可以在序段生成和中间结果归并阶段进行和中间结果归并阶段进行n散列的情况类似散列的情况类似 重复元组将进入相同桶重复元组将进入相同桶Silberschatz,Korth and Sudarshan13.52Database System Concepts

27、其它操作其它操作:aggregationnaggregation的实现方法与重复元组删除类似的实现方法与重复元组删除类似n排序或散列可以用来将同组元组聚到一起排序或散列可以用来将同组元组聚到一起,然后然后即可对每一组应用合计函数即可对每一组应用合计函数.n优化优化:通过计算部分合求值通过计算部分合求值,可在序段生成与中可在序段生成与中间结果归并阶段合并同组元组间结果归并阶段合并同组元组n对对count,min,max,sum:保存组中当前已找保存组中当前已找到的元组的合求值到的元组的合求值n当合并当合并count的部分合求值时的部分合求值时,相加即可相加即可n对对avg,保存保存sum和和co

28、unt,最后求最后求sum/countSilberschatz,Korth and Sudarshan13.53Database System Concepts其它操作其它操作:集合运算集合运算n集合运算集合运算(,and):可以排序后使用合并连接的可以排序后使用合并连接的变种变种,或者使用散列连接的变种或者使用散列连接的变种n例如例如,使用散列的集合运算使用散列的集合运算:1.利用相同的散列函数划分两个关系利用相同的散列函数划分两个关系,从而创建了从而创建了r1,.,rn r0,和和 s1,s2.,sn 2.如下处理每个分组如下处理每个分组i.ri 读进内存后读进内存后,用一个不同的散列函数

29、用一个不同的散列函数构造构造ri 上的内存散列索引上的内存散列索引3.r s:将将si 中的元组加入散列索引中的元组加入散列索引(如果不在其中的话如果不在其中的话).最后将散列索引中的元组加入到结果中最后将散列索引中的元组加入到结果中 4.r s:将将si 中的元组输出到结果中的元组输出到结果,如果它们已经在散列索引如果它们已经在散列索引中中 5.r s:对对si 中的每个元组中的每个元组,如果已经在散列索引中如果已经在散列索引中,则从索引则从索引中删除之中删除之.6.在在si 之末将散列索引中的剩余元组加到结果中之末将散列索引中的剩余元组加到结果中Silberschatz,Korth and

30、 Sudarshan13.54Database System Concepts其它操作其它操作:外联接外联接n外连接可如下计算外连接可如下计算连接后加入填充空值的未参加连接的元组连接后加入填充空值的未参加连接的元组修改连接算法修改连接算法n修改合并连接算法来计算修改合并连接算法来计算r s在在r s中中,未参加联接的元组都在未参加联接的元组都在r R(r s)中中修改合并连接算法计算修改合并连接算法计算 r s:在合并时在合并时,对每个来自对每个来自r 的并且的并且不能匹配不能匹配s中任何元组的元组中任何元组的元组tr,输出输出tr 并用空值填充并用空值填充右外连接和完全外连接可类似计算右外连

31、接和完全外连接可类似计算n修改散列连接算法来计算修改散列连接算法来计算r s如果如果 r 是探测关系是探测关系,输出输出r 中不能匹配的元组并填充空值中不能匹配的元组并填充空值如果如果 r 是构建关系是构建关系,探测时记录哪些探测时记录哪些r 元组匹配元组匹配s 元组元组.在在si 之之末输出无匹配末输出无匹配r 元组并填充空值元组并填充空值Silberschatz,Korth and Sudarshan13.55Database System ConceptsJoin 研究方法小结研究方法小结n建立了数学模型，包括建立了数学模型，包括:符号体系，符号体系，抓抓主要矛盾，以及忽略原则主要矛盾，

32、以及忽略原则然后分情况，加定语，把问题特化，分而治之然后分情况，加定语，把问题特化，分而治之一次作一个小问题，深入地导出多个公式一次作一个小问题，深入地导出多个公式真正有用，可以指导实践真正有用，可以指导实践n不怕不怕有问题，有问题，就怕找不到问题就怕找不到问题n只要有问题只要有问题就可能出成果就可能出成果Silberschatz,Korth and Sudarshan13.56Database System Concepts表达式求值表达式求值n迄今为止，我们讨论的是单个运算的算法迄今为止，我们讨论的是单个运算的算法n计算整个表达式树的可选方法计算整个表达式树的可选方法:物化物化(Mater

33、ialization):生成输入为关系或已计算生成输入为关系或已计算结果的表达式的结果结果的表达式的结果,在磁盘上物化在磁盘上物化(存储存储),重复此重复此过程过程流水线化流水线化(Pipelining):当一个操作正在执行中就当一个操作正在执行中就将部分输出元组送到父运算，子树结果传给父结点将部分输出元组送到父运算，子树结果传给父结点Silberschatz,Korth and Sudarshan13.57Database System Concepts物化物化n物化求值物化求值:从最底层开始每次计算一个运算，将中间结果从最底层开始每次计算一个运算，将中间结果物化成临时关系物化成临时关系,再

34、进行下一层运算再进行下一层运算n例如例如,在下图中计算并存储在下图中计算并存储然后计算并存储它与然后计算并存储它与customer 的联接的联接,最后计算最后计算 customer-name上的投影上的投影Silberschatz,Korth and Sudarshan13.58Database System Concepts物化物化n优点：物化求值总是可行的优点：物化求值总是可行的n缺点：将结果写到磁盘并读回来可能代价很高缺点：将结果写到磁盘并读回来可能代价很高n前面我们的代价公式都忽略了将结果写到磁盘去的代价前面我们的代价公式都忽略了将结果写到磁盘去的代价,故故总代价总代价 =各操作代价之

35、和各操作代价之和+中间结果写到磁盘的代价中间结果写到磁盘的代价n双缓冲双缓冲(Double buffering):对每个操作使用两个输出缓对每个操作使用两个输出缓冲区冲区,当一个满的时候即写入磁盘当一个满的时候即写入磁盘,同时使用另一个输同时使用另一个输出出n允许磁盘写与计算重叠进行允许磁盘写与计算重叠进行,减少执行时间减少执行时间Silberschatz,Korth and Sudarshan13.59Database System Concepts流水线流水线n流水线求值流水线求值:同时计算多个运算,将一个运算的结果传到下一个运算Silberschatz,Korth and Sudarsh

36、an13.60Database System Concepts流水线流水线n优点：比物化廉价很多，不需要将临时关系存储优点：比物化廉价很多，不需要将临时关系存储到磁盘到磁盘n缺点：有时流水线不可用，如排序和散列联接缺点：有时流水线不可用，如排序和散列联接n为了使流水线有效为了使流水线有效,使用能在接受输入元组的同使用能在接受输入元组的同时生成输出元组的求值算法时生成输出元组的求值算法n流水线可以两种方式执行流水线可以两种方式执行:拉式：需求驱动拉式：需求驱动（买方市场）有人买，才生产买方市场）有人买，才生产推式：生产者驱动（卖方市场）生产出来，再等买推式：生产者驱动（卖方市场）生产出来，再等买

37、Silberschatz,Korth and Sudarshan13.61Database System Concepts流水线流水线 n在需求驱动或在需求驱动或惰性惰性(lazy)求值求值中中n系统从顶层操作重复请求下一元组系统从顶层操作重复请求下一元组n每个操作向子操作请求下一元组每个操作向子操作请求下一元组,以便输出它自己的下一元组以便输出它自己的下一元组n在调用之间在调用之间,操作必须维护操作必须维护“状态状态”以便知道下一步返回什么以便知道下一步返回什么n每个操作以每个操作以迭代子迭代子 的形式实现下列操作：的形式实现下列操作：open()例如对文件扫描例如对文件扫描:初始化文件扫描

38、初始化文件扫描,在文件开始处存储指针作为状态在文件开始处存储指针作为状态例如对合并连接例如对合并连接:对关系排序并在已排序关系开始处存储指针作为状态对关系排序并在已排序关系开始处存储指针作为状态 next()例如对文件扫描例如对文件扫描:输出下一元组输出下一元组,前移并存储文件指针前移并存储文件指针例如对合并连接例如对合并连接:从前面的状态继续合并直至找到下一输出元组从前面的状态继续合并直至找到下一输出元组.保存指保存指针作为迭代子状态针作为迭代子状态close()Silberschatz,Korth and Sudarshan13.62Database System Concepts流水线流

39、水线n在生产者驱动或急迫在生产者驱动或急迫eager流水线中流水线中n操作迫切地产生元组并向上传送到父操作操作迫切地产生元组并向上传送到父操作n在操作之间维护缓冲区在操作之间维护缓冲区,子操作将元组放入缓冲区子操作将元组放入缓冲区,父父操作将元组移出缓冲区操作将元组移出缓冲区n如果缓冲区满如果缓冲区满,子操作等待直至缓冲区有空间子操作等待直至缓冲区有空间,然后生然后生成更多的元组成更多的元组n系统调度在输出缓冲区中有空间的操作系统调度在输出缓冲区中有空间的操作,可以处理更多可以处理更多的输入元组的输入元组Silberschatz,Korth and Sudarshan13.63Database

40、 System Concepts流水线的求值算法流水线的求值算法n某些算法即使获得了输入元组也不能输出结果，例如合某些算法即使获得了输入元组也不能输出结果，例如合并连接或者散列连接并连接或者散列连接n这导致了将中间结果写到磁盘然后读回这导致了将中间结果写到磁盘然后读回n某些算法变种可以在读入输入元组时即时某些算法变种可以在读入输入元组时即时(on the fly)生生成成(至少部分至少部分)结果结果n例如例如,混合散列连接即可在读入内存分划混合散列连接即可在读入内存分划(分划分划0)中的探中的探测关系元组时生成输出元组测关系元组时生成输出元组n流水线连接技术流水线连接技术:修改混合散列连接将两

41、个关系的分划修改混合散列连接将两个关系的分划0的元组都放入内存缓冲区的元组都放入内存缓冲区,可用时读入之可用时读入之,输出两个分划输出两个分划0元组之间的任何匹配作为结果元组之间的任何匹配作为结果n当新的当新的r0 元组找到时元组找到时,将它与现存的将它与现存的s0 元组匹配元组匹配,输出匹输出匹配并保存在配并保存在r0中中n对称地处理对称地处理s0 元组元组Silberschatz,Korth and Sudarshan13.64Database System Concepts复杂连接复杂连接n涉及三个关系的连接涉及三个关系的连接:loan depositor customern策略策略1：

42、计算计算 depositor customer;利用其结果计算利用其结果计算 loan (depositor customer)n策略策略2：计算：计算 loan depositor,再将结果与再将结果与customer 连接连接n策略策略3：同时执行一对连接同时执行一对连接.在在loan上为上为loan-number 建一索建一索引引,在在customer 上为上为customer-name 建一索引建一索引n对对depositor 中的每个元组中的每个元组 t,在在customer 中查找对应的元中查找对应的元组组,在在loan中查找对应的元组中查找对应的元组.n deposit 中每个元

43、组只检查一次中每个元组只检查一次n策略策略3 结合两个操作为一个特殊目的的操作结合两个操作为一个特殊目的的操作,它比实现两个连它比实现两个连接更高效接更高效Silberschatz,Korth and Sudarshan13.65Database System Concepts任务任务:Derby 查询处理实现分析查询处理实现分析n任务任务1:Derby SQL Parser分析分析n任务任务2:Derby Query Execution分析分析n参考资料参考资料:Derby On Disk Page Format Derby Type SystemHow Things Workorg_apache_derby_impl_store_access_btreeIntersect&Except Design Derby v10 source codeEnd of Chapter