计算机理论论文关系数据库CODB中XML全文检索的设计与实现

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

23、 2000 server.我们测试了建立索引,查询单关键字和多关键字的耗时.图 6.1 建立索引时间比较图 6.2 检索关键字”database”用时比较图 6.3 检索关键字”database”和”xml”的用时比较从图中可以看到我们的索引建立时间和sql server差不多,但是我们的查询时间要比sql server快两倍.实验的结果说明我们codb系统实用性还是很强的.另外我们还测试了1些带连接,聚集的复杂查询,codb的速度依然要快于sql server两倍左右,这说明我们的全文检索可以很好的和数据库查询结合到了1起.在删除索引和更新索引方面codb和sql server速度查不多.总

24、之,我们对目前的功能还是十分的满意的.总结和展望本文主要的工作在于在关系数据库codb中实现xml全文检索功能.对于xml数据的检索需求日趋强烈的情况下,本文的工作还是有1定意义的.我们将xml全文检索这1功能和数据库的存储,查询紧密的结合,用户可以执行1些3 传统搜索引擎不能实现的复杂查询.同时我们还支持了不同粒度的检索,可以在元素级别,也可以在文档级别,用户可以根据需要进行选择.此外我们还实现了简单重要度排序.目前为止,我们已经在关系数据库codb中实现了xml全文检索.xml全文检索功能还有需要完善的地方.首先可以进1步提高建立索引和查询的速度,实现动态更新索引的功能.其次随着关系数据库

25、的发展,会有越来越多的需求摆在数据面前.我们需要不断地在codb数据库系统中增加新的功能.我们忠心的祝愿能够有更多的人来使用我们的国产关系数据库codb系统.附录1.selectstmt结构(src/include/nodes/nodes.h)typedef struct selectstmt nodetag type; /* 标志节点的类型.继承node类型 */ * 下面的结构是叶节点的selectstmt所特有的.select是1颗树.因为简单的select语句可以通过union,intersect,except等操作形成1颗树.*/list *distinctclause; /* 所有

26、distinct子句中的条目 */rangevar *into; /* 目标表,用于select into 子句 */list *intocolnames; /* select into 中的列名 */list *targetlist; /* 目标条目的列表 */list *fromclause; /* from子句中的表*/node *whereclause; /* where中的条件 */list *groupclause; /* group by 子句 */node *havingclause; /* having 条件表达式 */* 下面这些域是叶节点和非叶节点都会有的*/list *

27、sortclause; /* sort子句 */char *portalname; /* 游标的名字 */node *limitoffset; /* 结果需要跳多少个元组 */node *limitcount; /* 返回多少个元组 */list *forupdate; /* update子句*/* 非叶节点的selectstmts才会有的域*/setoperation op; /* 操作类型*/bool all; /* 是否指定了all */struct selectstmt *larg; /* 左子树 */struct selectstmt *rarg; /* 右子树 */ selects

28、tmt;2.query结构(src/include/nodes/nodes.h)typedef struct querynodetag type; /* 节点类型 */cmdtype commandtype; /* select | insert | update | delete | utility */querysource querysource; /* 查询的来源 */node *utilitystmt; /* 非空如果这是1个不能优化的命令*/int resultrelation; /* into目标关系 (索引到rtable)*/rangevar *into; /* 目标关系或者是

29、游标,对于游标portal只是名字是有意义的*/bool isportal; /* 这是对游标的检索吗 */bool isbinary; /* 2进制游标 */bool hasaggs; /* 是否有有聚集函数吗 */bool hassublinks; /* 是否有子查询的 */list *rtable; /* 范围表的列表 */fromexpr *jointree; /* 表的连接树(from和where子句) */list *rowmarks; /* 关系的rt index的整数链表,被for update选择*/list *targetlist; /* 结果列的列表 */list *gr

30、oupclause; /* group子句的列表 */node *havingqual; /* 应用到分组的having条件 */list *distinctclause; /* distinct子句的排序列表 */list *sortclause; /* orderby子句的排序列表 */node *limitoffset; /* limit语句中标志跳过的结果元组数 */node *limitcount; /* limit语句中要返回的结果元组数 */node *setoperations; /* 集合操作符树如果是1个union ,intersect,except的查询 */* 如果re

31、sultrelation是继承树的父亲,计划器将所有的child tables加入到* rtable,并且存储所有结果关系的rtindexes list.* 这是在计划的时候完成,而不是在分析的时候,既然* 我们不希望在分析的时候提交确切的child table的集合.* */list *resultrelations; /* rt索引的整数链表, 或者是nil */* 计划器内部用的 */list *base_rel_list; /* 基本关系的reloptinfos的链表 */list *other_rel_list; /* 1-关系的reloptinfos的链表 */list *join

32、_rel_list; /* 连接关系的reloptinfos的链表 */list *equi_key_list; /* 相等连接的pathkeyitems链表的链表 */list *query_pathkeys; /* query_planner结果的pathkeys */ query;3.plan结构(src/include/nodes/plannodes.h)typedef struct plannodetag type;/* 估计计划的运行代价*/cost startup_cost; /* 在取元组之前的代价*/cost total_cost; /* 整个的代价(包括所有元组的获取) *

33、/ * 计划器对于结果大小的估计(注意: 如果有limit,那么在设置plan_rows中不考虑)*/double plan_rows; /* 计划可能提交的行数 */int plan_width; /* 平均行宽度(字节为单位) */ * 运行的状态数据.* /estate *state; /* 执行时,每个节点的状态都指向1个高层的estate */struct instrumentation *instrument; /* 可选的运行时刻的状态 */* 所有计划类型的1般的结构数据.*/list *targetlist;list *qual; /* 条件谓词 */struct plan

34、*lefttree;struct plan *righttree;list *extparam; /* 外部参数 */list *locparam; /* 本地参数 */list *chgparam; /* 被改变的参数 */list *initplan; /* 初始化的计划节点 */list *subplan; /* 其他子查询节点 */int nparamexec; /* 在整个查询执行中的参数的数量.*/ plan;4.codb_proc结构 (/src/include/catalog/codb_proc.h)catalog(codb_proc) bootstrapnamedata pr

35、oname; /* 函数名 */oid pronamespace; /* oid的名字空间1般为codbnsp */int4 proowner; /* 用户id 1般为codbuid */oid prolang; /* codb_language的oid c语言为12 */bool proisagg; /* 是否为聚集函数 */bool prosecdef; /* 安全定义security definer */bool proisstrict; /* strict with respect to nulls */bool proretset; /* 是否返回集合 */char provolat

36、ile; /* see provolatile_ categories below */int2 pronargs; /* 参数个数 */oid prorettype; * 返回值的oid */oidvector proargtypes; /* 参数oid列表*/text prosrc; /* 源代码 */bytea probin; /* 2进制代码 */aclitem proacl; /* 权限 */ formdata_codb_proc;5.codb_am结构 (src/include/catalog/codb_am.h)catalog(codb_am)namedata amname; /

37、* 方法的名字*/int4 amowner; /* 建立者的系统id*/int2 amstrategies; /* 全部策略(操作符)个数* by which we can traverse/search this am */int2 amsupport; /* 这个访问方法使用的所有支持函数的个数*/int2 amorderstrategy; /* 如果访问方法有顺序,该项描述的是排序操作符的个数.如果不排序则为0 */bool amcanunique; /* 是否支持唯1索引 */bool amcanmulticol; /* 访问方法支持多列索引 */bool amindexnulls;

38、/* 访问方法是否支持为null的索引项 */bool amconcurrent; /* 是否支持并发更新 */regproc amgettuple; /* 下1个有效元组的函数 */regproc aminsert; /* 插入这个元组的函数 */regproc ambeginscan; /* 开始新的扫描函数 */regproc amrescan; /* 重新扫描函数 */regproc amendscan; /* 结束这个扫描函数 */regproc ammarkpos; /* 标记并发扫描位置的函数”mark current scan position” function */regp

39、roc amrestrpos; /* 恢复标记的扫描位置的函数*/regproc ambuild; /* 建立新的索引的函数 */regproc ambulkdelete; /* bulk删除的函数 */regproc amvacuumcleanup;/* vacuum后的清除函数 */regproc amcostestimate; /* 估计索引扫描代价的函数 */ formdata_codb_am;6.indexscandescdata结构(src/include/access/relscan.h)typedef struct indexscandescdatarelation heapr

40、elation; /* 关系描述符或者为null */relation indexrelation; /* 搜索关系描述符*/snapshot xs_snapshot; /* 看到的快照 */int numberofkeys; /* 扫描码的个数*/scankey keydata; /* 扫描码描述符的数组*/* 索引方法kill索引元组的信号 */bool kill_prior_tuple; /* 上次的返回的元组是否无用了*/bool ignore_killed_tuples; /* 不要返回无用的条目*/* 如果扫描码有唯1约束他被索引访问方法设置 */bool keys_are_uni

41、que;/* 扫描的当前状态 */bool got_tuple; /* true如果成功的调用 index_getnext */void *opaque; /* 访问方法特定的信息*/itempointerdata currentitemdata; /* 当前索引指针 */itempointerdata currentmarkdata; /*标记信息如果有的话 */* xs_ctup/xs_cbuf为valid在成功的index_getnext. 在* index_getnext_indexitem后, xs_ctup.t_self从索引条目中得到元组的tid* 但是其他的字段不是valid.*/heaptupledata xs_ctup; /* 当前的堆元组, 如果有的话*/buffer xs