复旦大学：《数据库系统引论》PPT教学课件_查询处理

查询处理

查询处理

查询处理 ●外排序 ●关系操作的执行 ●查询优化 个典型的关系查询优化器

查询处理 ⚫外排序 ⚫关系操作的执行 ⚫查询优化 ⚫一个典型的关系查询优化器

外部排序操作 ●排序操作是数据库中常用的操作 ○用户需要查询的结果是排序的 ○排序是 Bulk Loading的第一步 ○排序可用于删除重复纪录 ○在联接操作中经常使用排序操作 ●由于数据库中的数据量经常超过内存的大 小,所以需要用外部排序

外部排序操作 ⚫排序操作是数据库中常用的操作 用户需要查询的结果是排序的 排序是Bulk Loading的第一步 排序可用于删除重复纪录 在联接操作中经常使用排序操作 ⚫由于数据库中的数据量经常超过内存的大 小，所以需要用外部排序

外部排序操作 ●简单的两路 Merge排序 ●外部 Merge排序 ●提高性能的几点考虑 ●利用B+树进行排序

外部排序操作 ⚫简单的两路Merge排序 ⚫外部Merge 排序 ⚫提高性能的几点考虑 ⚫利用B+树进行排序

简单两路 Merge排序 ●使用3个页的内存进行排序 ●基本思想 ○将大的文件转换成小的块 ○对这些块进行排序 ○使用最小的空间进行 Merge排序 每个排过序的小文件为 ●在内存中可以用各种排序方法

简单两路Merge排序 ⚫使用3个页的内存进行排序 ⚫基本思想 将大的文件转换成小的块 对这些块进行排序 使用最小的空间进行Merge排序 ⚫每个排过序的小文件为一个run ⚫在内存中可以用各种排序方法

算法 Proc 2-way-exsort(file Read each page into memory, sort it, write it out While the number of runs at end of previous pass> 1 while there are runs to be merge from previous pass is choose next two runs(from previous pass) read each run into an input buffer; Merge the runs and write to the output buffer force output buffer to disk one page at a time wndproc

算法 Proc 2-way-exsort(file) Read each page into memory, sort it, write it out While the number of runs at end of previous pass>1 while there are runs to be merge from previous pass is choose next two runs(from previous pass) read each run into an input buffer; Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc

计算量分析 ●若输入文件大小为2k,k为一个整数 Pass0,产生2个run,每个1页 Pass1,产生2k1个run,每个2页 ○Pass2,产生2k2个run,每个4页 ●总共需要og2N+1次pasN为文件的页数, 对每一页做一次读,一次写 ●总共的开销为:2NogN+1)

计算量分析 ⚫若输入文件大小为2 k ,k为一个整数 Pass 0，产生2 k个run，每个1页 Pass 1，产生2 k-1个run，每个2页 Pass 2，产生2 k-2个run，每个4页 ⚫总共需要log2N +1次pass,N为文件的页数， 对每一页做一次读，一次写 ⚫总共的开销为：2N*(log2N +1)

例子 3462948,75,63,12 3426497.856 2 2,3464,78,91,356 2 2,3446,78,9 2|3,56 122334456,67,8

例子 3,4 6,2 9,4 8,7 5,6 3,1 2 3,4 2,6 4,9 7,8 5,6 1,3 2 2,3 4,6 4,7 8,9 1,3 5,6 2 2,3 4,4 6,7 8,9 1,2 3,5 6 1,2 2,3 3,4 4,5 6, 6 7,8 9

外部 Merge排序 ●若内存中有B个 pages。如何利用2路 Merge 排序的思想,进行排序操作? O在pass0一次性读入B个页的数据进行排序 在pass1,2,一次性读入B个页的数据进行排序 利用B-1个 Buffer页作为输入,将最后一个 Buffer 页作为输出的缓冲区,进行B-1路的 Merge排序

外部Merge排序 ⚫若内存中有B个pages。如何利用2路Merge 排序的思想，进行排序操作？ 在pass 0一次性读入B个页的数据进行排序。 在pass 1,2,…一次性读入B个页的数据进行排序。 利用B-1个Buffer页作为输入，将最后一个Buffer 页作为输出的缓冲区，进行B-1路的Merge排序

算法 Proc export(file) Read B page into memory, sort them, write out a run While the number of runs at end of previous pass >1 while there are runs to be merged from previous pass choose next B-1 runs(from previous pass) read each run into an input buffer; page at at time Merge the runs and write to the output buffer force output buffer to disk one page at a time wndproc

算法 Proc exsort(file) Read B page into memory, sort them, write out a run While the number of runs at end of previous pass >1 while there are runs to be merged from previous pass choose next B-1 runs(from previous pass) read each run into an input buffer; page at at time Merge the runs and write to the output buffer force output buffer to disk one page at a time endproc