计算机理论论文关系数据库CODB中XML全文检索的设计与实现.doc
《计算机理论论文关系数据库CODB中XML全文检索的设计与实现.doc》由会员分享,可在线阅读,更多相关《计算机理论论文关系数据库CODB中XML全文检索的设计与实现.doc(11页珍藏版)》请在三一文库上搜索。
1、关系数据库CoDB中XML全文检索的设计与实现 5.1索引的存储我们使用和数据库存储分离的方式来保存全文检索.我们使用文件系统将索引的结果按词作为文件名来存储,假设索引目录为%INDEX%.我们对于中英文的分词处理也不同.对于中文按字索引所以不需要字典,英文单词之间由于有空格分开可以很容易的分词.中文索引文件名为十6进制的编码.例如”大”字对应的索引文件为00F3B4H.英文单词的索引文件较简单,例如单词word对应的索引文件为%INDEX%/word.我们设置了最大词长度MAX_WORD_LENGTH,当词的实际长度超过此长度时,该词被忽略.自索引文件我们使用%INDEX%/word_idx
2、作为文件名来存储.文件中的每条记录的结构如下:TID ElementOffset OffsetToElement DeweyId其中TID可以唯1的标记文档, ElementOffset为该词所在的XML节点的起始位置(按字节),OffsetToElement 为该词相对于该XML节点的偏移量(按字节).该词在文档中的实际出现位置(按字节)为ElementOffset + OffsetToElement.DeweyId为所在节点在XML文档中的DeweyId.DeweyId可以参看XML的编码1节.为提高建立索引的速度,我们在写索引文件的时候使用Cache技术.建立索引时使用Cache和不使用
3、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(前面存储词,后面
4、是Cache内容,如cBuf=“secret01 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个内部节点
5、,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结构体中.
6、CreateXftiIndex创建Cache,用于建索引,必须的.须指定索引目录.FlushXftiCache将Cache中的内容写回磁盘LocateXftiCache定位到指定的词对应的Cache,Cache使用替换最满的策略WriteXftiCache将1个整数写入定位到的CacheCloseXftiCache写盘和并释放Cache内存IndexFile对指定字符串(pFile)建索引. 5.2利用索引进行检索我们分开处理单个词和多个单词组合的情况.多个关键字调用单个词的检索函数并使用合并算法进行合并.我们采用检索单个单词的结构体result:struct resultunsigned i
7、nt dwBid; / 文档的TID中的块号unsigned short wPid; / 文档的TID中的块内偏移号unsignedint dwNextBid; / 为下次检索保留的块号 unsigned short wNextPid; / 为下次检索保留的块内偏移int bEndFlag; / 结束标志POCCUR pOccur; / 出现位置的数组 int iOccurCount; / 位置数组的个数 int iOccurMax; / 数组可以容纳的最大个数,不够的时候会自动调整int iCurrentOccur; / 为多关键字检索时使用,记录当前数组的下标.int* pPathBuf;
8、 / DeweyID的内存,pOccur中所有DeweyId存在这里int iPathLength; / DeweyID内存的大小int iPathMax; / DeweyID内存的最大上限,会自动调整.FILE* hFile; / 文件句柄char* pFileBuf; / 读取文件的缓冲区int iCurrent; / 当前缓冲区的指针 int iEnd; / 指针到达缓冲区结束的标志int iWord; / 为多关键字检索时使用,保留检索词int iFirst; / 检索词是中文还是英文的标记这个结构体中包含了所有的位置信息OCCUR.OCCUR结构的定义如下:struct occuri
9、nt iPosition; / 词的位置int iStartOffset; / 当前XML节点的偏移量int iOffset; / 相对于当前节点的偏移量int iPathOffset; / 在DeweyId内存中的位置int iPathLength; / DeweyId的长度这部分主要函数说明:CreateResult初始化result结构并初始化DeleteResult释放result结构SearchOpen开始1个检索.传入关键字作为参数.它在CreateResult之后调用.ReadBuffer从文件中读入数据到缓冲区中.ReadNext从缓冲区中读入1条索引记录.SearchNext
10、检索1条满足条件的结果.结果信息放在Result结构中返回0表示成功.SearchClose结束检索时要调用得函数.多关键字检索的时候我们使用的是Result2结构,他包含了多个单关键字的Result结构,它的定义如下:struct result2 unsigned int dwBid; / 文档的块号unsigned short wPid; / 文档的块内偏移 PNRESULT pNResult; / Result数组每个词对应1个关键词int iNResultCount; / 数组的长度int iNResultMax; / 数组的最大长度 POCCUR2 pOccur2; / 位置信息的数
11、组Occur2,pNResult中的数据实际存储在这里int iOccur2Count; / 数组的长度int iOccur2Max; / 最大数组长度PRESULT* pResult; / 所有的result结构的数组.每个结构对应1个检索词int iResultCount; / 数组的长度int iResultAllocated; / 数组中有效数组的个数int iResultMax; / 最大数组长度char* pWords; / 所有的检索词例如:”word10word20word30”;多个关键字检索的结果信息存储在OCCUR2结构和nresult结构中,它的定义如下:struct
12、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篇
13、文档中的所有满足条件的子节点.每个子节点存在pNResult中,每个关键字的位置信息存在pOccur2中.通过访问nresult结构中的iOccur2和iOccur2Count就可以从Occur2数组中获得每个关键字的位置信息.这部分主要函数的说明:EnlargeArray用于调整数组大小CreateResult2类似CreateResultDeleteResult2类似DeleteResultSearch2Open类似SearchOpenSearch2Close类似SearchCloseReadFromIndex将所有词对应的result定位到相同的TID CheckPosition检查结果
14、中中文短语是否连续,将不连续的结果做标记(如查找”侦探”,”探侦”或”侦察探”都不是合法结果)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中增加索引需要实现
15、各种接口函数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
16、ftiendscan ftimarkpos ftirestrpos ftibuild ftibulkdelete fticostestimate );codb_am结构的具体定义可以参看附录5.下面我们讲1下建立索引,检索的实现.5.3.1建立索引首先每种搜索引擎都有自己的建立函数build.例如Gist索引有gistbuild函数,Btree索引有btreebuild函数.每个Build函数会调用IndexBuildHeapScan函数,这个函数需要传入1个buildCallback回调函数最为参数.这个函数在每次扫描到1个元组的时候会调用这个buildCallback回调函数.通常回调函数
17、会调用index_formtuple形成索引,然后调用形成调用特殊索引的方法形成自己索引格式.例如hash索引调用_hash_formitem生成自己索引,最后调用_hash_doinsert插入索引.我们的fti也采用类似的方法.我们将ftibuildcallback作为参数传入IndexBuildHeapScan.Ftibuildcallback再调用前面见到的索引建立函数IndexFile.我们定义FtiBuildCallback回调函数如下:static void FtiBuildCallback(Relation index, HeapTuple htup, Datum *attda
18、ta, char *nulls, bool tupleIsAlive, void *state)需要说明的是回调函数的参数格式是统1的.它包括了索引关系index,当前的元组htup,该元组中的数据attdata等信息.其中attdata是(varattrib *)的数组. attdata0是第1个属性的数据,attdata是第2属性的数据,依此类推.CoDB中大文本数据采用压缩的方法存储,需要调用heap_tuple_untoast_attr来得到原始的元组.回调函数ftibuildCallback会对元组中的要索引的属性进行语法分析并建立倒排索引.上面讲到全文检索的存储需要得到文档的TID
19、.TID的获得可以使用htup->t_data->t_ctid.ip_blkid和htup->t_data->t_ctid.ip_posid来获得.对于关系表中原有的数据我们可以使用build来建立索引,对于后面插入的数据我们可以使用insert来建立索引.ftiinsert函数在每插入1个元组的时候会被调用,该函数的实现和回调函数的实现同出1辙.索引的删除会调用delete函数,我们实现了对倒排索引的删除操作,这个操作可能会比较耗时,因为需要删除他所有包含词对应的倒排文件中索引项.更新操作相当于现删除后增加.5.3.2 使用索引进行检索前面讲的是索引建立相关的函数,下
20、面讲1下FTI如何和查询引擎的结合.前面讲到查询计划中有1种节点是Indexscan,它会根据关系表中的索引调用相应索引类型的扫描函数来得到元组.所以关键就是实现查询接口函数:beginscan,gettuple,endscan.其中的Gettuple函数是核心,这个函数会被调用来获得1个元组直到返回false.另外查询过程中IndexScanDescData是1个重要的数据结构(参看附录6),返回的元组信息和状态信息都存在这里.它贯穿于beginscan,gettuple,endscan函数的参数中.这个结构对于每种索引类型都是相同的.其中的opaque可以存储了和具体索引相关的1些特有的信
21、息.查询的时候我们需要为FTI索引我们记录1些扫描的临时信息,就是PResult2结构.beginscan和endscan比较简单,主要是申请和释放PResult2所用的空间.重点是gettuple函数,它会调用Search2函数进行检索.该函数的返回值的真假表示是否还有元组满足条件.gettuple函数根据Search2中的信息填写IndexScanDescData结构中的currentItemData(TID)为满足条件的元组TID,并且设置got_tuple(表示是否有元组)为true,否则设置为false.最重要的是还要设置t_self为元组的TID.5.4实现界面我们采用CoDB的X
22、ML全文检索编写了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
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 计算机 理论 论文 关系 数据库 CODB XML 全文 检索 设计 实现
链接地址:https://www.31doc.com/p-3970334.html