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

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

《数据库 课程设计 实验报告.docx》由会员分享，可在线阅读，更多相关《数据库 课程设计 实验报告.docx（17页珍藏版）》请在冰点文库上搜索。

数据库课程设计实验报告

Project：

01

Students：

08386051孙梦石

08386059荣钰

08386090王思思

Date：

2010-11-27

DBMSProject1

Task1:

UsetwoalternativesofExternalMergeSorttosorttheLINEITEMtable

算法简介

外排序包括两部分，第一步是生成初始有序段，第二步是不断归并有序段，直到有序段数目为1。

程序说明

程序以lineitem.tbl文件作为输入，以res.tbl文件作为输出，中间产程temp1，temp2两个临时文件。

输出包括所用的轮数以及每轮结束时的时间。

伪代码

生成有序段的伪代码：

假设buff内的页的数目为N；

打开原数据文件

While（文件没有到尾）

{

读取N-1个页的数据到buff；

为数据建立索引，为RecordIndexs；

使用内排序对索引进行排序；

For（i=0；i

{

如果第N个Page已满，则将其写到临时文件Gen中；

将RecordIndexs[i]对应的数据项拷贝到第N个Page内；

}

将第N个Page写到临时文件Gen中；

在有序段列表Gen中记录当前有序段的信息，包括起始偏移，长度；

}

归并的伪代码：

While（不是最后一轮）

{

将有序段表Gen和有序段表Process进行交换；

将临时文件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；

将当前取出的有序段从有序段表Process中弹出；

将有序段Gen添加到有序段表Gen中；

跳出循环；

}

有序段Gen的长度+=索引项min对应的记录的长度；

如果第N个页无法容纳min，则将第N个页写到临时文件Gen；

将min对应的记录拷贝到第N个页中；

从min所在的页中将min弹出；

}

}

}

此代码对单缓冲与双缓冲均适用，单双缓冲的区别主要在于如何从有序段中读取一个页。

双缓冲

建立一个线程ReadThread，用于数据的读取；

定义两个Event，g_hEventRead与g_hEventReadReady用于同步两个线程；

ReadThread循环等待g_hEventRead，当需要读取数据时，父线程触发该事件，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的处理页与请求页，根据当前段的信息构造读线程所需的参数，激发g_hEventRead，通知读线程开始工作。

然后使用当前的处理页来构造Page，并加入到Page集合中。

几个特殊情况：

1、有序段刚调入内存的时候，它的两个页都是空的，此时需要先请求读线程读满一个页，并等待他读完，然后再按照正常的步骤进行。

2、最初的时候要等到建立完索引才能知道读取的实际长度，才能开始进行下一次的操作。

后来发现可以从读取数据的末尾向前扫描换行符，这样可以快速知道所读数据的实际长度，从而在建立索引之前就可以进行下一次的读取操作。

3、当段全部读取完时，则不发送读取请求。

具体的伪代码在下面会有介绍。

主要数据结构

记录索引：

每一条记录都对应一个索引，排序的时候也是对索引进行排序。

typedefstruct_RecordIndex

{

char*head;

unsignedintlength;

intindexColumnOffset[2];

intindexColumnLength[2];

}RecordIndex;

head：

记录了对应记录在BUFF中的首地址；

length：

记录了此条记录的长度；

indexColumnOffset：

记录索引列的偏移；

indexColumnLength：

记录索引列的长度；

相关操作：

intcompareIndex（constvoid*a,constvoid*o）;

比较两个记录索引对应的记录的大小；

缓冲页：

用于记录BUFF中的页的信息，每个页包含记录的索引

typedefstruct_Page

{

intlength;

char*head;

RecordIndexrecordIndexsDefault[defaultMaxCount];

RecordIndex*recordIndexs;

intindexCount;

intindexHead;

}Page;

length:

记录当前页的长度；

head：

当前页在BUFF中的首地址；

recordIndexsDefault：

默认用来存储当前页内记录索引的数组；

recordIndexs：

用来访问当前页内记录索引的数组；

indexCount：

记录当前页索引的数目；

indexHead：

记录当前页索引的首索引；

相关操作：

clearPage（page）（宏）：

清空一个页

initPage（page）（宏）：

初始化一个页

pageAddRecordIndex1（page）（宏）：

向页中增添一个新的记录索引

pageAddRecordIndex2（page,o）（宏）：

向页中增添一个已存在的记录索引

pagePopFront（page）（宏）：

将页中的第一个记录弹出

pagePopBack（page）（宏）：

将页中的最后一个记录弹出

copyToPage（index,page）（宏）：

将一条索引拷贝到页的缓冲内

页的集合：

用于记录当前在BUFF中的页

typedefstruct_Pages

{

intpageCount;

intpageHead;

Pagepages[PAGE_COUNT];

}Pages;

pageCount：

BUFF中页的数目；

pageHead：

第一个页在数组中的索引；

Pages：

用于存放页的数组；

相关操作：

addPage（_pages）（宏）：

向集合中添加一个页

clearPages（_pages）（宏）：

清空集合

getPage（_pages,index）（宏）：

从集合中获取一个页

有序段：

用于记录一个有序段的信息

typedefstruct_Seg

{

intfileOffset;

intlength;

intbytesProcessed;

intbytesRead;

}Seg;

fileOffset：

有序段头在文件中的偏移；

length：

有序段的长度；

bytesProcessed：

有序段已经被处理的长度；

bytesRead:

有序段已经读取的长度；

有序段的集合：

用于存放有序段

typedefstruct_Segs

{

intsegCount;

intsegHead;

Segsegs[SEG_COUNT];

}Segs;

segCount：

有序段的数目；

segHead：

有序段的在数组中的起始索引；

segs：

存放有序段的数组；

相关操作

addSeg（segs）（宏）：

向集合中添加一个新的有序段；

clearSegs（_segs）（宏）清空集合；

getSeg（_segs,index）（宏）获取集合中的一个有序段；

segsPopFront（segs）（宏）弹出集合中的第一个有序段；

控制函数：

定义了一组用来控制排序逻辑的函数，如下

为所读的数据建立索引

voidconstructRecordIndex（char*buff,int*fileOffset,intcurrentBuffOffset,intlength,Page*page,intflag）;

内排序

voidshellSort（RecordIndex*a,intlen）;

读取一个页的数据到读数据缓冲区

intreadFilePage（HANDLEfile,int*fileOffset,char*buff,intbuffOffset,intpageSize,Page*page）;

从指定的有序段中读取一个页的数据岛数据缓冲区

voidreadSegPage（Seg*seg,intsegOffset,intpageId,Page*page）;

用页将BUFF填满

voidreadBuff（HANDLEfile,intfileOffset,Page*page）;

将一个页写会文件

voidwritePage（HANDLEfile,int*fileOffset,Page*page,char*outBuff,intbuffOffset,intflag）;

初始化缓冲区

voidinitBuff（size_tsize）;

释放缓冲区

voidfreeBuff（）;

读线程

unsigned__stdcallreadThread（LPVOIDarg）;

下面对最重要的readSegPage函数进行介绍

voidreadSegPage（Seg*seg,intsegOffset,intpageId,Page*page）;

此函数为将单缓冲修改为双缓冲的核心所在。

伪代码如下：

等待读取完成事件；

如果上次读取的数据不为0

{

从后向前扫描，得出数据的有效长度；

所读的段的bytesRead+=有效长度；

}

如果当前的段是第一次读

{

构造请求参数；

请求读线程读取该段的一个页；

等待读取完成事件；

计算有效长度，并加到bytesRead上；

}

交换当前段的请求页与处理页；

构造请求参数；

如果要读的数据的长度为0

{

激发读取完成事件；

}

否则

{

请求读线程读取该段的一个页；

}

使用当前的处理页构造索引；

性能测试

1.测试平台：

CPU：

Core2E75002.93GHz

内存：

2G

分区格式：

NTFS；

分区可用空间：

60.3G；

操作系统：

Windows7旗舰版

测试数据：

724M

2.测试结果（以下数据均为最佳成绩）：

130页双缓冲：

77秒3轮

12页双缓冲：

268秒6轮

130页单缓冲:

83秒3轮

12页单缓冲：

211秒5轮

经实验，测试结果与当前系统的状态，分区剩余空间，操作系统版本，分区格式等关系非常密切，因此在不同时候测得的数据结果可能大相径庭，所以所列数据均为最佳成绩。

性能优化

1、纯C语言实现

不使用C++，本次Project相同的代码生成的可执行文件C语言实现的要小一半；

2、使用WinAPI代替C库函数

直接调用WinAPI：

CreateFile，ReadFile，WriteFile，SetFilePointer。

效率要比使用fread等高不少。

使用WinAPI会降低程序的可移植性，但是对于数据库这种对性能要求较高的系统，必然会针对平台进行优化，所以使用WinAPI是很正确的做法。

3、数组引用改为指针引用

对数组的遍历改为使用指针来遍历。

4、优化Buff利用，减少有序段的数目

第一轮使用N-1个页来生成有序段，能够减少一轮，大大节约了时间；

5、将调用次数较多的函数改为宏函数；

对段和页数据结构的读写非常频繁，将对这两个数据结构进行基本操作的函数改为宏函数，减少函数调用时的开销。

6、使用双临时文件

保证无论轮数是奇数次还是偶数次，最后一轮总是写到结果文件中，而避免了轮数书奇数次时使用但临时文件最后需要完成一次拷贝；

7、优化内排序的方法

C++中有std:

:

sort函数进行排序，其中结合了快排、归并等众多方法，效率相当的高，但是C中无法调用此函数，C中有qsort，但是其只是简单的快速排序，效率比较低。

考虑到此次数据的特点为基本有序，经过实验对比，发现使用希尔排序能取得比较好的效果。

8、优化归并

由于本次数据基本为有序，采用通常的方法选取最小值的时候需要对所有段进行遍历，非常耗时间。

考虑到如果本次从有序段n中取出的是最小值，那么下次取的最小值很大概率也是从n中取出，所以定义两个最小值，一个为本次的最小值，一个为本次的次小值，在选取最小值时，先把上次选出最小值的那个段的第一个值与上次的次小值进行比对，如果比次小值小，那么就说明这个段的第一个值就是最小值，省去了遍历的过程；如果比次小值大，则按照原来的方法进行遍历。

经实验能够取得比较好的效果。

9、使用异步IO

双缓冲的实现可以使用多线程，也可以使用异步IO。

异步IO实际也属于多线程，但是IO线程不再由用户程序来控制，而是有内核来控制，性能应该更优一些。

但是由于时间关系还没有修改成异步IO，不过猜想应该能够提升一部分性能。

10、优化数据结构

不使用STL的模板类等数据结构，因为经实验STL中的模板类在对性能要求比较高的情况下性能非常差，不适合这种情况。

所用的集合全部重新实现，并且都分配了初始空间，添加删除等操作只涉及指针的移动，不会对实际数据进行移动，这大大提高了执行效率。

11、让BUFF在空间上连续

申请BUFF时候，让所有页位于一个连续的空间内，这样能够显著提高Cache的命中率，最终能够明显提升成绩。

结果分析

结果还是很出乎意外的，双缓冲相对于单缓冲来说优势并不明显。

实际上可以预测到，在很多情况下单缓冲会优于双缓冲，因为单缓冲可能会比双缓冲少一轮，比如此次在12页buff的情况下。

但是在此次实验中，单缓冲与双缓冲在130页buff的情况下均为3轮完成，所以最后是这种结果还是让人惊讶的。

分析可能的原因

1、线程的挂起和切换可能造成一定的性能损失，不过可能影响不大。

2、不同线程对共享数据的访问可能存在内存映射的开销。

3、双缓冲对内存的访问可能存在一些跳跃性，而单缓冲对内存的访问则相对比较连续，是这个原因的可能性比较大。

4、程序有问题，对双缓冲优化的力度不如单缓冲，这个也很有可能。

心得体会

本次实验可谓一波三折，从第一次运行需要3个小时，到现在的接近1分钟，每一次成绩的提升都经过了异常纠结的过程。

如果还有时间，我想我们能够优化到1分钟以内。

另外在双缓冲时还遇到了著名的临界区问题。

因为最初在ReadThread计算了很多参数，而使同步出现问题。

解决方法是将参数的计算移到主线程中，使其同步。

另外非常感谢周盈莹同学分享她的用来测试结果是否正确的小程序。

Task2:

OrganizingthesortedLINEITEMtableintodiskpages

Analysis:

Fromthetaskdescription,thepageislikethefollowinggraph:

AndthedatainDatablockisstoredastext;datainSlotblockisstoredasbinary.

Implementation:

Toaccomplishthistask,writeacprogram:

OrganizePage.c.

SomeImportantpoints:

ØShouldopentheoutputfileas“wb”mode,becausewebothwritetextandbinaryinthesamefile.

ØUseavariable‘pageSize’torecordthesizeofonepageinmemory,whenitischanged（forexample:

readanewrecordintemporarybuffers）,checkwhetherithasexceed1024.ifexceed,writethispagetooutputfileanddon’tchangethepage,thencleanalltemporaryvariableandbeginanewreadingloop;ifnot,continuetowritedataintomemorypages.

ØPointtwocauseanproblem:

assumethereisanewrecordisreadinttemporarybuffer,butthepageSizehasexceed1024.underthiscircumstances,thisnewrecordmaybecleanedwithoutwritingtofiles.Tosolvethisproblem,setavariable‘isWritten’tomarkaspecificrecordwetheriswrittenintopageornot.ifitisfalse,thebeginningofnextreadingloopwillusingthedataofcurrenttemporarybuffersinsteadofcleanit.

ØGenerallyspeaking,thepageSizewillnotfixedto1024,sobetweenrecorddataandslotdata,therewillbesomeemptyspacefilledinblanktomakethepagesizeinthediskbe1024Byte.

ØSlotDatashouldbewrittenininvertedsequenceforretrieval.

Pseudocode:

while（fileisnotend）

{

While（pageSize<=1024）

{

If（isWritten）

Readarecordintomemoryandcalculateitssize.

Generatetheslottomarktherecordandcalculate.

AddtwosizeinpageSize.

If（pageSize>1024）

Writerecordintofile.

isWritten=true;

}

Writeblankstofillintheleftspace.

Writesoltdataininvertedsequenceintofile.

Resetallvariable.

}

Pleaseseemoredetailinthesourcecode.

ImplementationResult:

ExecuteOrganizePage（Inwindows）

Theorganizedfile（pageone）:

WINHEX

Wecanseeonepagesizeis400（inHEX）/1024（inDEC）.

Let’sseeslotone:

Lenth:

Offset:

Fromthesescreenshotwecanknow:

Therecordoneisbeginat0,It’slengthis107Byte.

Record:

Therealsizeofrecordoneis6B（inHEX）/107（inDEC）.Sothedatainslotisright.

Whatwelearn

FromthistaskwegetdeeperunderstandinthestoringdataaspageformatinDBMS,

andhowtoreadthefiledatamoreefficientlyinC.