《计算机理论论文关系数据库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
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.
42、*/HeapTupleData xs_ctup; /* 当前的堆元组, 如果有的话*/Buffer xs_cbuf; /* 扫描过程中当前堆缓冲区*/* 如果xs_cbuf 不是InvalidBuffer, 我们再这个buffer上持有pin */FmgrInfo fn_getnext; /* getnext函数的cached查找信 */CoDBStat_Info xs_codbstat_info; /* 收集的统计信息 */ IndexScanDescData;参考论文CoDB关系数据系统: http:/ DB2 Text Extender: http:/ Maier, David Simm
43、en, DB2 Optimization in Support of Full Text Search, TCDE 2001. Vol 24.Paul Dixon, Basics of Oracle Text Retrieval, TCDE 2001. Vol 24.James R. Hamilton, Tapas K. Nayak, Microsoft SQL Server Full-Text Search, TCDE 2001. Vol 24.SQL Server Full-text Search: http:/ http:/www.w3.org/XMLXQuery: http:/www.
44、w3.org/TR/xquery/XQuery Tutorial : http:/ Guo, etc al, XRANK: Ranked Keyword Search over XML Documents, ACM SIGMOD2003David Dehaan, et al, “A Comprehensive XQuery to SQL Translation using Dynamic Interval Encoding”, SIGMOD 2003, June 9-12, 2003, San Diago, CA“Keyword Searching and Browsing in Databa
45、ses using BANKS”, ICDE Conf., 2002.DBXplorer: A System for Keyword-Based Search over Relational DatabasesDISCOVER: Keyword Search in Relational DatabasesD. Florescu, D. Kossmann, I. Manolescu, Integrating Keyword Search into XML Query Processing, WWW Conf., 2000.V. Aguilera, S. Cluet, F. Wattez, Xyleme Query A3