关系数据库CoDB中XML全文检索的设计与实现
毕业论文
5.1索引的存储
我们使用和数据库存储分离的方式来保存全文检索.我们使用文件系统将索引的结果按词作为文件名来存储,假设索引目录为%INDEX%.我们对于中英文的分词处理也不同.对于中文按字索引所以不需要字典,英文单词之间由于有空格分开可以很容易的分词.中文索引文件名为十6进制的编码.例如"大"字对应的索引文件为00F3B4H.英文单词的索引文件较简单,例如单词word对应的索引文件为%INDEX%/word.我们设置了最大词长度MAX_WORD_LENGTH,当词的实际长度超过此长度时,该词被忽略.自索引文件我们使用%INDEX%/word_idx作为文件名来存储.
文件中的每条记录的结构如下:TID ElementOffset OffsetToElement DeweyId
其中TID可以唯1的标记文档, ElementOffset为该词所在的XML节点的起始位置(按字节),OffsetToElement 为该词相对于该XML节点的偏移量(按字节).该词在文档中的实际出现位置(按字节)为ElementOffset + OffsetToElement.DeweyId为所在节点在XML文档中的DeweyId.DeweyId可以参看XML的编码1节.
为提高建立索引的速度,我们在写索引文件的时候使用Cache技术.建立索引时使用Cache和不使用Cache速度上可以差十倍之多.目前Cache块数为16k,每块大小为8k,每块Cache对应1个词.
Xfti为Cache的结构体,整个过程中只使用1个,由CreateXftiIndex函数生成,由CloseXftiIndex函数释放.该结构体其中包含索引目录cDir,1个Cache结构体数组pCache和1个指向Cache数组的指针数组.该数组用于对Cache按词序排序,以便2分法查找.iCacheCount为使用中的Cache块个数(总是出现在前面).其中每个Cache块的结构体包括:Cache内容开始偏移量iStart(之前为该词)及结束偏移量 iEnd,以及块cBuf(前面存储词,后面是Cache内容,如cBuf="secret\01 2 3 4 5 6 ", iStart=7, iEnd=19).
结构体find_data为parse出的结果信息.其中cWord为结果单词,pText指向当前文档iLength为该词长度,iOffset为当前单词在XML节点中的相对偏移量,iPositoin为词序,iPathLength为当前DeweyId的长度,数组iPath为当前DeweyId,数组iStartOffset为当前DeweyId上每个节点对应的开始偏移量,iStatus和iXmlStatus用于标示当前parse状态.
自索引文件的存储采用按块存储的方法,每个块存储1个内部节点,1个块不够存储时使用溢出块并连接起来.
主要函数的说明:
InitFindData
对struct find_data的初始化,只被IndexFile调用
CheckXml
检查文档是否为Xml文档(只检查xml头)对非xml文档不使用DeweyId,但现在实际上已经放弃了,所有返回值均相同(在struct find_data中),即对所有文档均按xml处理.
SeekToNextWord
定位到文档中下1词,其中包含比较复杂的parse过程,以及设置当前DeweyId等.
CopyWord
将定位到的词复制到find_data结构体中.
FindNextWord
查找下1词,结果放到find_data结构体中.
CreateXftiIndex
创建Cache,用于建索引,必须的.须指定索引目录.
FlushXftiCache
将Cache中的内容写回磁盘
LocateXftiCache
定位到指定的词对应的Cache,Cache使用替换最满的策略
WriteXftiCache
将1个整数写入定位到的Cache
CloseXftiCache
写盘和并释放Cache内存
IndexFile
对指定字符串(pFile)建索引.
5.2利用索引进行检索
我们分开处理单个词和多个单词组合的情况.多个关键字调用单个词的检索函数并使用合并算法进行合并.
我们采用检索单个单词的结构体result:
struct result
{
unsigned int dwBid; // 文档的TID中的块号
unsigned short wPid; // 文档的TID中的块内偏移号
unsigned
int dwNextBid; // 为下次检索保留的块号
unsigned short wNextPid; // 为下次检索保留的块内偏移
int bEndFlag; // 结束标志
POCCUR pOccur; // 出现位置的数组
int iOccurCount; // 位置数组的个数
int iOccurMax; // 数组可以容纳的最大个数,不够的时候会自动调整
int iCurrentOccur; // 为多关键字检索时使用,记录当前数组的下标.
int* pPathBuf; // DeweyID的内存,pOccur中所有DeweyId存在这里
int iPathLength; // DeweyID内存的大小
int iPathMax; // DeweyID内存的最大上限,会自动调整.
FILE* hFile; // 文件句柄
char* pFileBuf; // 读取文件的缓冲区
int iCurrent; // 当前缓冲区的指针
int iEnd; // 指针到达缓冲区结束的标志
int iWord; // 为多关键字检索时使用,保留检索词
int iFirst; // 检索词是中文还是英文的标记
}
这个结构体中包含了所有的位置信息OCCUR.OCCUR结构的定义如下:
struct occur
{
int iPosition; // 词的位置
int iStartOffset; // 当前XML节点的偏移量
int iOffset; // 相对于当前节点的偏移量
int iPathOffset; // 在DeweyId内存中的位置
int iPathLength; // DeweyId的长度
}
这部分主要函数说明:
CreateResult
初始化result结构并初始化
DeleteResult
释放result结构
SearchOpen
开始1个检索.传入关键字作为参数.它在CreateResult之后调用.
ReadBuffer
从文件中读入数据到缓冲区中.
ReadNext
从缓冲区中读入1条索引记录.
SearchNext
检索1条满足条件的结果.结果信息放在Result结构中返回0表示成功.
SearchClose
结束检索时要调用得函数.
多关键字检索的时候我们使用的是Result2结构,他包含了多个单关键字的Result结构,它的定义如下:
struct result2
{
unsigned int dwBid; // 文档的块号
unsigned short wPid; // 文档的块内偏移
PNRESULT pNResult; // Result数组每个词对应1个关键词
int iNResultCount; // 数组的长度
int iNResultMax; // 数组的最大长度
POCCUR2 pOccur2; // 位置信息的数组Occur2,pNResult中的数据实际存储在这里
int iOccur2Count; // 数组的长度
int iOccur2Max; // 最大数组长度
PRESULT* pResult; // 所有的result结构的数组.每个结构对应1个检索词
int iResultCount; // 数组的长度
int iResultAllocated; // 数组中有效数组的个数
int iResultMax; // 最大数组长度
char* pWords; // 所有的检索词例如:"word1\0word2\0word3\0"
};
多个关键字检索的结果信息存储在OCCUR2结构和nresult结构中,它的定义如下:
struct occur2
{
int iOffset; // 相对于文档的偏移量
int iWid; // 词的id
int iDepth; // 相对于节点的偏移量
}typedef OCCUR2, *POCCUR2;
struct nresult // XML节点的结构
{
int iOccur2; // 在Occur数组中的开始下标
int iOccur2Count; // 在Occure数组中的个数
int* pPath; // DeweyId内容的指针
int iPathLength; // 长
度
float fRank; // Ranking值
}typedef NRESULT, *PNRESULT;
每次查询Result2中返回的是1篇文档中的所有满足条件的子节点.每个子节点存在pNResult中,每个关键字的位置信息存在pOccur2中.通过访问nresult结构中的iOccur2和iOccur2Count就可以从Occur2数组中获得每个关键字的位置信息.
这部分主要函数的说明:
EnlargeArray
用于调整数组大小
CreateResult2
类似CreateResult
DeleteResult2
类似DeleteResult
Search2Open
类似SearchOpen
Search2Close
类似SearchClose
ReadFromIndex
将所有词对应的result定位到相同的TID
CheckPosition
检查结果中中文短语是否连续,将不连续的结果做标记(如查找"侦探","探侦"或"侦察探"都不是合法结果)
ComparePath
比较两个DeweyId是否相等
GetPathLength
返回两个DeweyId的公共部分长度
MergeResult
合并多个检索词的结果
SetRank
计算Rank值
Search2Next
类似SearchNext
算法5.1为多关键字的检索算法.
算法5.1多关键字的检索算法:
多个关键字需要合并单关键字的'结果.我们使用算法5.2进行合并.该算法的时间代价是O(mn),m和n分别是A和B的结果个数.
算法5.2 合并两个检索结果
5.3 CoDB中增加索引类型
上面讲到CoDB中增加索引需要实现各种接口函数ftibuild,ftidelete,fticostestimate,ftibeginscan,ftigettuple,ftiendscan,ftiinsert.
CoDB还要求对于新增加的索引类型要在codb_am系统表中注册这些函数.目前CoDB拥有Hash,Btree,Rtree,Gist等4种索引.我们需要增加1种新的索引类型FTI就要在catalog/codb_am.h中增加下面1句:
#DATA(insert OID = 111 ( fti CODBUID 1 1 0 f f f t ftigettuple ftiinsert ftibeginscan ftirescan ftiendscan ftimarkpos ftirestrpos ftibuild ftibulkdelete fticostestimate ));
codb_am结构的具体定义可以参看附录5.
下面我们讲1下建立索引,检索的实现.
5.3.1建立索引
首先每种搜索引擎都有自己的建立函数build.例如Gist索引有gistbuild函数,Btree索引有btreebuild函数.每个Build函数会调用IndexBuildHeapScan函数,这个函数需要传入1个buildCallback回调函数最为参数.这个函数在每次扫描到1个元组的时候会调用这个buildCallback回调函数.通常回调函数会调用index_formtuple形成索引,然后调用形成调用特殊索引的方法形成自己索引格式.例如hash索引调用_hash_formitem生成自己索引,最后调用_hash_doinsert插入索引.我们的fti也采用类似的方法.我们将ftibuildcallback作为参数传入IndexBuildHeapScan.Ftibuildcallback再调用前面见到的索引建立函数IndexFile.
我们定义FtiBuildCallback回调函数如下:
static void FtiBuildCallback(Relation index, HeapTuple htup, Datum *attdata, char *nulls, bool tupleIsAlive, void *state)
需要说明的是回调函数的参数格式是统1的.它包括了索引关系index,当前的元组htup,该元组中的数据attdata等信息.其中attdata是(varattrib *)的数组. attdata[0]是第1个属性的数据,attdata[1]是第2属性的数据,依此类推.CoDB中大文本数据采用压缩的方法存储,需要调用heap_tuple_untoast_attr来得到原始的元组.回调函数ftibuildCallba
ck会对元组中的要索引的属性进行语法分析并建立倒排索引.上面讲到全文检索的存储需要得到文档的TID.TID的获得可以使用htup->t_data->t_ctid.ip_blkid和htup->t_data->t_ctid.ip_posid来获得.
对于关系表中原有的数据我们可以使用build来建立索引,对于后面插入的数据我们可以使用insert来建立索引.ftiinsert函数在每插入1个元组的时候会被调用,该函数的实现和回调函数的实现同出1辙.
索引的删除会调用delete函数,我们实现了对倒排索引的删除操作,这个操作可能会比较耗时,因为需要删除他所有包含词对应的倒排文件中索引项.更新操作相当于现删除后增加.
5.3.2 使用索引进行检索
前面讲的是索引建立相关的函数,下面讲1下FTI如何和查询引擎的结合.前面讲到查询计划中有1种节点是Indexscan,它会根据关系表中的索引调用相应索引类型的扫描函数来得到元组.所以关键就是实现查询接口函数:beginscan,gettuple,endscan.其中的Gettuple函数是核心,这个函数会被调用来获得1个元组直到返回false.另外查询过程中IndexScanDescData是1个重要的数据结构(参看附录6),返回的元组信息和状态信息都存在这里.它贯穿于beginscan,gettuple,endscan函数的参数中.这个结构对于每种索引类型都是相同的.其中的opaque可以存储了和具体索引相关的1些特有的信息.
查询的时候我们需要为FTI索引我们记录1些扫描的临时信息,就是PResult2结构.beginscan和endscan比较简单,主要是申请和释放PResult2所用的空间.重点是gettuple函数,它会调用Search2函数进行检索.该函数的返回值的真假表示是否还有元组满足条件.gettuple函数根据Search2中的信息填写IndexScanDescData结构中的currentItemData(TID)为满足条件的元组TID,并且设置got_tuple(表示是否有元组)为true,否则设置为false.最重要的是还要设置t_self为元组的TID.
5.4实现界面
我们采用CoDB的XML全文检索编写了1个简单的XML文档的搜索引擎.如图5.1和图5.2所示.我们采用的是默认的重要度排序算法.当然用户也可以使用扩展的SQL语句直接在CoDB的客户端中进行查询.
图5.1 查询界面
图5.2 检索界面
从图5.2中可以看到我们的检索粒度在元素的级别而不是文档的级别,并且我们支持用户查看整篇文档.
测试结果
我们将CoDB的系统和SQL Server的全文检索系统进行了比较.我们使用的测试集是dblp的测试集[31].测试机器配置为CPU P4 2.0G, 内存512M, 硬盘80G.CoDB的测试环境为Redhat Linux 8.0操作系统,SQL Server的测试环境为Windows 2000 Server.
我们测试了建立索引,查询单关键字和多关键字的耗时.
图 6.1 建立索引时间比较
图 6.2 检索关键字"database"用时比较
图 6.3 检索关键字"database"和"xml"的用时比较
从图中可以看到我们的索引建立时间和SQL Server差不多,但是我们的查询时间要比SQL Server快两倍.实验的结果说明我们CoDB系统实用性还是很强的.
另外我们还测试了1些带连接,聚集的复杂查询,CoDB的速度依然要快于SQL Server两倍左右,这说明我们的全文检索可以很好的和数据库查询结合到了1起.在删除索引和更新索引方面CoDB和SQL Server速度查不多.总之,我们对目前的功能还是十分的满意的.
总结和展望
本文主要的工作在于在关系数据库CoDB中实现XML全文检索功能.对于XML数据的检索需求日趋强烈的情况下,本文的工作还是有1定意义的.我们将XML全文检索这1功能和数据库的存储,查询紧密的结合,用户可以执行1些传统搜索引擎不能实现的复杂查询.同时我们还支持了不同粒度的检索,可以在元素级别,也可以在文档级别,用户可以根据需要进行选择.此外我们还实现了简单重要度排序.
目前为止,我们已经在关系数据库CoDB中实现了XML全文检索.XML全文检索功能还有需要完善的地方.首先可以进1步提高建立索引和查询的速度,实现动态更新索引的功能.其次随着关系数据库的发展,会有越来越多的
[1]
【关系数据库CoDB中XML全文检索的设计与实现】相关文章：