数据库 课程设计 实验报告.docx

1、数据库 课程设计 实验报告Project ：01Students：08386051 孙梦石08386059 荣钰08386090 王思思Date：2010-11-27DBMS Project 1Task 1: Use two alternatives of External Merge Sort to sort the LINEITEM table算法简介 外排序包括两部分，第一步是生成初始有序段，第二步是不断归并有序段，直到有序段数目为1。程序说明 程序以lineitem.tbl文件作为输入，以res.tbl文件作为输出，中间产程temp1，temp2两个临时文件。输出包括所用的轮数以及每轮

2、结束时的时间。伪代码生成有序段的伪代码：假设buff内的页的数目为N；打开原数据文件While（文件没有到尾） 读取N-1个页的数据到buff； 为数据建立索引，为RecordIndexs； 使用内排序对索引进行排序； For（i=0；iRecordIndexs.length；i+） 如果第N个Page已满，则将其写到临时文件Gen中； 将RecordIndexsi对应的数据项拷贝到第N个Page内；将第N个Page写到临时文件Gen中；在有序段列表Gen中记录当前有序段的信息，包括起始偏移，长度；归并的伪代码：While（不是最后一轮） 将有序段表Gen和有序段表Process进行交换； 将

3、临时文件Gen和临时文件Process进行交换； 如果（有序段表Process中有序段的数目=N/2-1）则临时Gen =文件Res；标记此轮为最后一轮； While（有序段表Process内的有序段数目不等于0） 从有序段表Process内的前N/2-1个有序段中各自读取一个页到BUFF中； 定义有序段Gen； 记录有序段Gen的起始偏移为临时文件Gen当前的偏移； While（真） 定义最小项索引min为-1； 如果某个页已经消耗 如果所在的段没有消耗完毕，则从中读取一个页； 否则跳过； 从Buff内的所有页中取出最小的记录的索引； 如果（min仍为-1），则将第N页写到临时文件Gen；将

4、当前取出的有序段从有序段表Process中弹出；将有序段Gen添加到有序段表Gen中；跳出循环； 有序段Gen的长度+=索引项min对应的记录的长度； 如果第N个页无法容纳min，则将第N个页写到临时文件Gen； 将min对应的记录拷贝到第N个页中； 从min所在的页中将min弹出；此代码对单缓冲与双缓冲均适用，单双缓冲的区别主要在于如何从有序段中读取一个页。双缓冲建立一个线程ReadThread，用于数据的读取；定义两个Event，g_hEventRead与g_hEventReadReady用于同步两个线程；ReadThread循环等待g_hEventRead，当需要读取数据时，父线程触发该

5、事件，ReadThread开始读取数据，读完之后，ReadThread会触发事件g_hEventReadReady，通知父线程数据已经读取完毕。将BUFF分为等大的两个区域A和B，A和B又各自分成N/2个子页A1，B1，A2，B2.A2N，B2N。进行归并时，所选取的N/2-1个有序段中的每一个有序段Sn，对应BUFF中的页An与Bn，一个段的两个页有两种，一个为请求页，一个为处理页。请求页为正在读取或将要读取的页面；处理页为正在进行归并的页。An与Bn轮流当做Sn的请求页与处理页。当一个段Sn的处理页消耗完时，主线程会先判断Sn的请求页有没有读完，没有读完则等待，读完则交换Sn的处理页与请求

6、页，根据当前段的信息构造读线程所需的参数，激发g_hEventRead，通知读线程开始工作。然后使用当前的处理页来构造Page，并加入到Page集合中。几个特殊情况：1、有序段刚调入内存的时候，它的两个页都是空的，此时需要先请求读线程读满一个页，并等待他读完，然后再按照正常的步骤进行。2、最初的时候要等到建立完索引才能知道读取的实际长度，才能开始进行下一次的操作。后来发现可以从读取数据的末尾向前扫描换行符，这样可以快速知道所读数据的实际长度，从而在建立索引之前就可以进行下一次的读取操作。3、当段全部读取完时，则不发送读取请求。具体的伪代码在下面会有介绍。主要数据结构记录索引：每一条记录都对应一

7、个索引，排序的时候也是对索引进行排序。typedef struct _RecordIndex char* head; unsigned int length; int indexColumnOffset2; int indexColumnLength2;RecordIndex;head： 记录了对应记录在BUFF中的首地址；length： 记录了此条记录的长度；indexColumnOffset： 记录索引列的偏移；indexColumnLength： 记录索引列的长度；相关操作：int compareIndex(const void *a,const void *o);比较两个记录索引对应的

8、记录的大小；缓冲页：用于记录BUFF中的页的信息，每个页包含记录的索引typedef struct _Page int length; char* head; RecordIndex recordIndexsDefaultdefaultMaxCount; RecordIndex *recordIndexs; int indexCount; int indexHead;Page;length: 记录当前页的长度；head： 当前页在BUFF中的首地址；recordIndexsDefault： 默认用来存储当前页内记录索引的数组；recordIndexs： 用来访问当前页内记录索引的数组；inde

9、xCount： 记录当前页索引的数目；indexHead： 记录当前页索引的首索引；相关操作：clearPage(page)（宏）： 清空一个页initPage(page) （宏）： 初始化一个页pageAddRecordIndex1(page)（宏）： 向页中增添一个新的记录索引pageAddRecordIndex2(page,o) （宏）：向页中增添一个已存在的记录索引pagePopFront(page) （宏）： 将页中的第一个记录弹出pagePopBack(page) （宏）： 将页中的最后一个记录弹出copyToPage(index,page) （宏）： 将一条索引拷贝到页的缓冲内页

10、的集合：用于记录当前在BUFF中的页typedef struct _Pages int pageCount; int pageHead; Page pagesPAGE_COUNT;Pages;pageCount： BUFF中页的数目；pageHead： 第一个页在数组中的索引；Pages： 用于存放页的数组；相关操作：addPage(_pages)（宏） ： 向集合中添加一个页clearPages(_pages) （宏）： 清空集合getPage(_pages,index)（宏）： 从集合中获取一个页有序段：用于记录一个有序段的信息typedef struct _Seg int fileOff

11、set; int length; int bytesProcessed; int bytesRead;Seg;fileOffset： 有序段头在文件中的偏移；length： 有序段的长度；bytesProcessed：有序段已经被处理的长度；bytesRead: 有序段已经读取的长度；有序段的集合：用于存放有序段typedef struct _Segs int segCount; int segHead; Seg segsSEG_COUNT;Segs;segCount： 有序段的数目；segHead： 有序段的在数组中的起始索引；segs： 存放有序段的数组；相关操作addSeg(segs)（

12、宏）： 向集合中添加一个新的有序段；clearSegs(_segs) （宏） 清空集合；getSeg(_segs,index) （宏） 获取集合中的一个有序段；segsPopFront(segs) （宏） 弹出集合中的第一个有序段；控制函数：定义了一组用来控制排序逻辑的函数，如下为所读的数据建立索引void constructRecordIndex(char* buff,int* fileOffset,int currentBuffOffset,int length,Page *page,int flag);内排序void shellSort(RecordIndex *a,int len);读

13、取一个页的数据到读数据缓冲区int readFilePage(HANDLE file,int* fileOffset,char* buff,int buffOffset ,int pageSize,Page *page);从指定的有序段中读取一个页的数据岛数据缓冲区void readSegPage(Seg* seg,int segOffset,int pageId,Page* page);用页将BUFF填满void readBuff(HANDLE file,int fileOffset,Page *page);将一个页写会文件void writePage(HANDLE file,int *fi

14、leOffset,Page* page,char* outBuff,int buffOffset,int flag);初始化缓冲区void initBuff(size_t size); 释放缓冲区void freeBuff(); 读线程 unsigned _stdcall readThread(LPVOID arg);下面对最重要的readSegPage函数进行介绍void readSegPage(Seg* seg,int segOffset,int pageId,Page* page);此函数为将单缓冲修改为双缓冲的核心所在。伪代码如下：等待读取完成事件；如果上次读取的数据不为0从后向前扫描

15、，得出数据的有效长度；所读的段的bytesRead+=有效长度；如果当前的段是第一次读构造请求参数；请求读线程读取该段的一个页；等待读取完成事件；计算有效长度，并加到bytesRead上；交换当前段的请求页与处理页；构造请求参数；如果要读的数据的长度为0激发读取完成事件；否则请求读线程读取该段的一个页；使用当前的处理页构造索引；性能测试1. 测试平台：CPU：Core 2 E7500 2.93GHz 内存：2G分区格式：NTFS；分区可用空间：60.3G；操作系统：Windows 7旗舰版测试数据：724M2. 测试结果（以下数据均为最佳成绩）： 130页双缓冲： 77秒 3轮 12页双缓冲：

16、 268秒 6轮 130页单缓冲: 83秒 3轮 12页单缓冲： 211秒 5轮经实验，测试结果与当前系统的状态，分区剩余空间，操作系统版本，分区格式等关系非常密切，因此在不同时候测得的数据结果可能大相径庭，所以所列数据均为最佳成绩。性能优化 1、纯C语言实现 不使用C+，本次Project相同的代码生成的可执行文件C语言实现的要小一半； 2、使用Win API代替C库函数 直接调用Win API：CreateFile，ReadFile，WriteFile，SetFilePointer。效率要比使用fread等高不少。使用Win API会降低程序的可移植性，但是对于数据库这种对性能要求较高的系

17、统，必然会针对平台进行优化，所以使用Win API是很正确的做法。 3、数组引用改为指针引用 对数组的遍历改为使用指针来遍历。 4、优化Buff利用，减少有序段的数目第一轮使用N-1个页来生成有序段，能够减少一轮，大大节约了时间； 5、将调用次数较多的函数改为宏函数； 对段和页数据结构的读写非常频繁，将对这两个数据结构进行基本操作的函数改为宏函数，减少函数调用时的开销。 6、使用双临时文件保证无论轮数是奇数次还是偶数次，最后一轮总是写到结果文件中，而避免了轮数书奇数次时使用但临时文件最后需要完成一次拷贝；7、优化内排序的方法C+中有std:sort函数进行排序，其中结合了快排、归并等众多方法，

18、效率相当的高，但是C中无法调用此函数，C中有qsort，但是其只是简单的快速排序，效率比较低。考虑到此次数据的特点为基本有序，经过实验对比，发现使用希尔排序能取得比较好的效果。8、优化归并由于本次数据基本为有序，采用通常的方法选取最小值的时候需要对所有段进行遍历，非常耗时间。考虑到如果本次从有序段n中取出的是最小值，那么下次取的最小值很大概率也是从n中取出，所以定义两个最小值，一个为本次的最小值，一个为本次的次小值，在选取最小值时，先把上次选出最小值的那个段的第一个值与上次的次小值进行比对，如果比次小值小，那么就说明这个段的第一个值就是最小值，省去了遍历的过程；如果比次小值大，则按照原来的方法

19、进行遍历。经实验能够取得比较好的效果。9、使用异步IO双缓冲的实现可以使用多线程，也可以使用异步IO。异步IO实际也属于多线程，但是IO线程不再由用户程序来控制，而是有内核来控制，性能应该更优一些。但是由于时间关系还没有修改成异步IO，不过猜想应该能够提升一部分性能。10、优化数据结构不使用STL的模板类等数据结构，因为经实验STL中的模板类在对性能要求比较高的情况下性能非常差，不适合这种情况。所用的集合全部重新实现，并且都分配了初始空间，添加删除等操作只涉及指针的移动，不会对实际数据进行移动，这大大提高了执行效率。11、让BUFF在空间上连续申请BUFF时候，让所有页位于一个连续的空间内，这

20、样能够显著提高Cache的命中率，最终能够明显提升成绩。结果分析结果还是很出乎意外的，双缓冲相对于单缓冲来说优势并不明显。实际上可以预测到，在很多情况下单缓冲会优于双缓冲，因为单缓冲可能会比双缓冲少一轮，比如此次在12页buff的情况下。但是在此次实验中，单缓冲与双缓冲在130页buff的情况下均为3轮完成，所以最后是这种结果还是让人惊讶的。分析可能的原因1、线程的挂起和切换可能造成一定的性能损失，不过可能影响不大。2、不同线程对共享数据的访问可能存在内存映射的开销。3、双缓冲对内存的访问可能存在一些跳跃性，而单缓冲对内存的访问则相对比较连续，是这个原因的可能性比较大。4、程序有问题，对双缓冲

21、优化的力度不如单缓冲，这个也很有可能。心得体会本次实验可谓一波三折，从第一次运行需要3个小时，到现在的接近1分钟，每一次成绩的提升都经过了异常纠结的过程。如果还有时间，我想我们能够优化到1分钟以内。另外在双缓冲时还遇到了著名的临界区问题。因为最初在ReadThread计算了很多参数，而使同步出现问题。解决方法是将参数的计算移到主线程中，使其同步。另外非常感谢周盈莹同学分享她的用来测试结果是否正确的小程序。Task 2: Organizing the sorted LINEITEM table into disk pages Analysis:From the task description,

22、 the page is like the following graph:And the data in Data block is stored as text; data in Slot block is stored as binary.Implementation:To accomplish this task, write a c program: OrganizePage.c.Some Important points: Should open the output file as “wb” mode, because we both write text and binary

23、in the same file. Use a variable pageSize to record the size of one page in memory, when it is changed(for example: read a new record in temporary buffers), check whether it has exceed 1024.if exceed ,write this page to output file and dont change the page, then clean all temporary variable and begi

24、n a new reading loop; if not ,continue to write data into memory pages. Point two cause an problem: assume there is a new record is read int temporary buffer, but the pageSize has exceed 1024.under this circumstances, this new record may be cleaned without writing to files. To solve this problem, se

25、t a variable isWritten to mark a specific record wether is written into page or not. if it is false, the beginning of next reading loop will using the data of current temporary buffers instead of clean it. Generally speaking, the pageSize will not fixed to 1024,so between record data and slot data,t

26、here will be some empty space filled in blank to make the page size in the disk be 1024 Byte. Slot Data should be written in inverted sequence for retrieval.Pseudocode: while (file is not end) While(pageSize1024) Write record into file. isWritten = true; Write blanks to fill in the left space. Write

27、 solt data in inverted sequence into file. Reset all variable. Please see more detail in the source code.Implementation Result:Execute OrganizePage(In windows )The organized file(page one):WINHEXWe can see one page size is 400(in HEX)/1024(in DEC).Lets see slot one:Lenth:Offset: From these screensho

28、t we can know: The record one is begin at 0,Its length is 107Byte.Record: The real size of record one is 6B(in HEX)/107(in DEC).So the data in slot is right.What we learnFrom this task we get deeper understand in the storing data as page format in DBMS,and how to read the file data more efficiently in C.