网站建设策划怎么谈,长沙铭万做网站,网站qq安全认证,昆山小程序制作PostgreSQL版本为8.4.1 #xff08;本文为《PostgreSQL数据库内核分析》一书的总结笔记#xff0c;需要电子版的可私信我#xff09; 索引篇#xff1a;
PostgreSQL索引篇 | BTreePostgreSQL索引篇 | GiST索引PostgreSQL索引篇 | Hash索引PostgreSQL索引篇 | GIN索引 (倒排…PostgreSQL版本为8.4.1 本文为《PostgreSQL数据库内核分析》一书的总结笔记需要电子版的可私信我 索引篇
PostgreSQL索引篇 | BTreePostgreSQL索引篇 | GiST索引PostgreSQL索引篇 | Hash索引PostgreSQL索引篇 | GIN索引 (倒排索引)
TSearch2 全文搜索
全文搜索文本搜索提供了一种可以检索出满足某个查询条件的自然语言文档的能力并且还可以根据文档的相关性对文档进行排序。最常见的搜索是找出所有包含给出的查询词的文档并且以它们符合查询的程度排序输出。
文本搜索操作符在数据库里已经存在很多年了。PostgreSQL有~、~*和LIKE操作符用于文本数据类型但是它们缺乏许多现代的信息系统需要的重要功能比如
没有语言支持不会对文本进行解析。不提供检索结果的排序ranking在找到上千个匹配文档的时候就不够高效了。没有索引支持所以会比较慢因为它们必须为每个查询处理所有的文档。
从PostgreSQL8.3开始提供了文本搜索模块TSearch(Text Search)文本搜索提供了一种可以标识满足某个查询的自然语言文档的能力并且还可以根据文档的相关性对文档进行排序。
PostgreSQL核心系统提供的TSearch模块提供了对文档在PostgreSQL里一个文档通常是一个表中的某个元组的一个文本属性或是几个属性的组合及查询条件进行解析的功能但并没有提供对解析后的结果进行进一步处理创建索引以支持快速的查找的功能。
PostgreSQL在扩展模块contrib里面提供了TSearch2来支持这些功能TSearch2实现了对文档创建GIN或者GiST索引的支持。本节将分析PostgreSQL核心系统提供的TSearch模块其代码位于src/backend/tsearch目录下。
全文索引的创建
全文索引允许对文档进行预处理并且可以保存为用于快速搜索的索引。
预处理包括文本解析、语义分析和词位存储。完成这三个过程后解析后的词语信息就存放在TSVector结构中。
从文本解析到词位存储这一系列过程是由函数to_tsvector_byid完成的 该函数首先调用parsetext函数对文本进行解析和语义分析然后再调用make_tsvector将词位信息构建成TSVector结构。
下面将对这三个过程依次进行分析。
文本解析
文本解析通过解析器将文档解析成一个个记号含位置信息类型信息该过程涉及的函数在wparser_def.c文件中。 目前PostgreSQL只提供一种解析器但它足够处理大多数纯文本及 HTML文件。
PostgreSQL中默认的记号对应表如表4-9所示。 语义分析
语义分析是对解析器处理过的token文本序列通过参照词典的审核规范成标准的词lexeme信息。
词典用于删除那些不应该在搜索中出现的词屏蔽词并规范化一些有多重形式的词这样同一个词的不同的衍生结果也可以被搜索到。
成功规范化之后的词被称作词位lexeme。除了改进搜索质量规范化和删除屏蔽词可以减少文档的尺寸从而提高性能。下面对各个词典的使用进行举例介绍
Ispell拼写词典例如“likes”将转换为“like”。Simple简单词典例如“A NAUGHTY DOG”将转换为“naughty dog”。Synonym同义词典例如“man”和“person”是同义词。Thesaurus知识词典例如“personal computer”将转换为PC。
完成语义分析后即得到一个全部处理后得到的单词信息这些单词信息保存在ParsedText结构中。
ParsedText结构保存解析后的文本其定义如数据结构4.20所示。 其中的words指向一个数组其中每一个元素都是ParsedWord类型用于保存分析后的一个单词其定义如数据结构4.21所示。 数据结构4.21中的pos和apos指针是用union结构允许在相同的内存位置存储不同的数据类型但只能存在一个来保存的。
当完成文本解析后可能会遇到相同的词出现了多次的情况这时会将相同的词合并在一起 对于只出现一次的词使用pos来保存其出现的位置即可 对于出现多次的词则使用apos指针来指向一个动态数组来保存所有出现的位置。apos[0]为该词出现的次数数组后面的值即为各次出现的位置。 由于数组的长度是不确定的所以使用alen字段来确定动态申请内存的空间alen初始化为2每当apos 的长度不够时alen即翻倍同时申请新内存将apos数组的长度翻倍。
上面介绍了用于存储语义分析后得到的单词信息的数据结构而这整个处理流程是由函数parsetext完成的其执行如图4-36所示。
函数parsetext /** Parse string and lexize words.** prs will be filled in.*/
void
parsetext(Oid cfgId, ParsedText *prs, char *buf, int buflen)
{int type,lenlemm;char *lemm NULL;LexizeData ldata;TSLexeme *norms;TSConfigCacheEntry *cfg;TSParserCacheEntry *prsobj;void *prsdata;cfg lookup_ts_config_cache(cfgId);prsobj lookup_ts_parser_cache(cfg-prsId);prsdata (void *) DatumGetPointer(FunctionCall2(prsobj-prsstart,PointerGetDatum(buf),Int32GetDatum(buflen)));LexizeInit(ldata, cfg);do{type DatumGetInt32(FunctionCall3((prsobj-prstoken),PointerGetDatum(prsdata),PointerGetDatum(lemm),PointerGetDatum(lenlemm)));// 类型合法单词长度过长if (type 0 lenlemm MAXSTRLEN){
#ifdef IGNORE_LONGLEXEMEereport(NOTICE,(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),errmsg(word is too long to be indexed),errdetail(Words longer than %d characters are ignored.,MAXSTRLEN)));continue;
#elseereport(ERROR,(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),errmsg(word is too long to be indexed),errdetail(Words longer than %d characters are ignored.,MAXSTRLEN)));
#endif}LexizeAddLemm(ldata, type, lemm, lenlemm);// 对token单词调用字典进行处理语义分析)while ((norms LexizeExec(ldata, NULL)) ! NULL){TSLexeme *ptr norms;// norms就是已规范后的一些词prs-pos; /* set pos */while (ptr-lexeme)// 若解析后的单词不为空则将词信息存放到Parsed Text结构中{if (prs-curwords prs-lenwords){prs-lenwords * 2;// words内存空间翻倍prs-words (ParsedWord *) repalloc((void *) prs-words, prs-lenwords * sizeof(ParsedWord));}if (ptr-flags TSL_ADDPOS)prs-pos;prs-words[prs-curwords].len strlen(ptr-lexeme);prs-words[prs-curwords].word ptr-lexeme;prs-words[prs-curwords].nvariant ptr-nvariant;prs-words[prs-curwords].flags ptr-flags TSL_PREFIX;prs-words[prs-curwords].alen 0;prs-words[prs-curwords].pos.pos LIMITPOS(prs-pos);ptr;prs-curwords;}pfree(norms);}} while (type 0);// 判断类型是否合法不合法的话说明已经分析完所有词了FunctionCall1((prsobj-prsend), PointerGetDatum(prsdata));
}词位存储
词位存储即为归总语义分析后的单词在文档中的位置并将其出现的次数及每个位置存储下来。
TSVector是一种可搜索的数据类型它是文档内容的一种表现形式是出现在文档中的每个重要单词及其所有位置信息的集合。它通过一种特殊的优化结构进行组织从而可方便快速地存取及查找。其定义如数据结构4.22所示。 TSVectorData结构中的WordEntry数组用于保存所有的关键字单词信息由于关键字的数目一开始并不确定所以使用一个数组指针该数组的实际长度根据关键字的个数在使用时进行分配。
WordEntry的定义见数据结构4.23。(结构体成员后面的数字用来限定成员变量占用的位数) 上面分析了TSVector 的数据结构词位存储即使用语义分析得到的ParsedText构建TSVector该过程由函数make_tsvector完成。其执行流程如图4-37所示。 /** make value of tsvector, given parsed text*/
TSVector
make_tsvector(ParsedText *prs)
{int i,j,lenstr 0,totallen;TSVector in;WordEntry *ptr;char *str;int stroff;prs-curwords uniqueWORD(prs-words, prs-curwords);// 合并相同单词的位置到apos中for (i 0; i prs-curwords; i){lenstr prs-words[i].len;if (prs-words[i].alen){lenstr SHORTALIGN(lenstr);lenstr sizeof(uint16) prs-words[i].pos.apos[0] * sizeof(WordEntryPos);}}if (lenstr MAXSTRPOS)ereport(ERROR,(errcode(ERRCODE_PROGRAM_LIMIT_EXCEEDED),errmsg(string is too long for tsvector (%d bytes, max %d bytes), lenstr, MAXSTRPOS)));// 根据ParsedText中唯一单词的数目(curwords)去计算TSVector所需空间totallen CALCDATASIZE(prs-curwords, lenstr);in (TSVector) palloc0(totallen);// 分配空间SET_VARSIZE(in, totallen);in-size prs-curwords;// 设置sizeptr ARRPTR(in);// ARRPTR(x) ( (x)-entries )str STRPTR(in);stroff 0;for (i 0; i prs-curwords; i)// 取ParsedText中下一个(第一个单词word{ // 将该单词的信息拷贝到TSVectorData.entries中ptr-len prs-words[i].len;ptr-pos stroff;memcpy(str stroff, prs-words[i].word, prs-words[i].len);stroff prs-words[i].len;pfree(prs-words[i].word);if (prs-words[i].alen)// 获取word的alen等于0说明没有位置信息{int k prs-words[i].pos.apos[0];// 出现次数WordEntryPos *wptr;if (k 0xFFFF)elog(ERROR, positions array too long);ptr-haspos 1;stroff SHORTALIGN(stroff);*(uint16 *) (str stroff) (uint16) k;wptr POSDATAPTR(in, ptr);for (j 0; j k; j){WEP_SETWEIGHT(wptr[j], 0);// 设置权重WEP_SETPOS(wptr[j], prs-words[i].pos.apos[j 1]);// 设置位置}stroff sizeof(uint16) k * sizeof(WordEntryPos);pfree(prs-words[i].pos.apos);}elseptr-haspos 0;ptr;}pfree(prs-words);return in;
}至此已经介绍了PostgreSQL内核中 TSearch模块提供的全部功能。之前讲过PostgreSQL把TSearch2作为一个扩展模块提供了对Entry创建GIN或者GiST索引的支持。通过对词位列创建GIN或GiST索引即可实现对文档的全文索引。
综上所述全文索引的创建流程图可归纳如图4-38所示其中创建GIN ( GiST)索引部分用虚线框,表示该步骤是需要用户额外编译并安装TSearch2模块才具有的功能。 由于GIN或者GiST索引结构的不同其创建、查询及更新的效率也有不同PostgreSQL 8.4.1官方手册上对这两种索引结构的优劣进行了比较
GIN 索引查询速度是GiST的3倍。GiST创建索引的速度是GIN的3倍。GiST索引的更新速度较GIN稍快。GIN索引的空间比GiST索引大2至3倍。
前面介绍了从文本解析一直到创建全文索引的全部过程。索引创建完成后即可利用全文索引进行查询。由于查询条件可能是自然语句也需要对查询进行一定的处理以获取准确的查询结果。
接下来将介绍如何利用这里建立的全文索引进行查询。
全文索引的查询
全文索引查询之前需要对检索的语句进行处理处理过程跟全文索引的创建过程类似要对查询语句进行文本解析及语义分析将分析后的结果封装成TSquery格式然后就可以通过对创建在TSvector上的索引进行匹配查询了。但与创建过程不同的是查询处理时各个处理后的单词需要使用布尔操作符与、│或和!非进行连接。
TSquery的格式如数据结构4.24所示。 PostgreSQL提供了to_tsquery和plainto_tsquery两个函数用于把查询转换成TSQuery数据类型。 to_tsquery的功能是将查询中的关键词在语义分析后转化成可与TSVector进行匹配的数据类型。该函数的参数要求很严格它们必须使用布尔操作符“”(与)、“|”(或)和“!”(非)分隔各个单词。 plainto_tsquery对查询的格式要求没有to_tsquery那么严格它把未格式化的文本查询转换成TSQuery。文本首先会像在to_tsvector里那样分析和规范化然后用布尔操作符“”(与)将解析后得到的单词进行连接最后得到TSQuery。
to_tsquery和plainto_tsquery函数的处理都是通过调用parse_tsquery函数来实现的。
parse_tsquery函数实现了对用户输入的查询条件的解析及语义分析过程使用布尔操作符将得到的关键字连接起来。通过调用makepol函数将查询语句转换成“波兰表示法”(“Polish notation”或称为波兰记法)。
对查询条件的解析过程与4.6.1节中的过程基本一样通过调用parsetext函数完成。当读取到查询条件中的操作符时只能是上面讲到的三种操作符对于其他操作符则报错plainto_tsquery函数则不会处理用户输入条件中的操作符它对查询条件进行解析后全部使用“”与操作符连接得到的关键词。
当得到TSquery后即可调用之前创建的全文索引进行查询全文索引查询的总体流程如图4-39所示。 查询结果处理
上面分析了全文索引的创建和查询处理过程。数据库系统提供了操作符可以对TSVector或处理后的TSQuery结构中的entry进行比较。下面给出一个使用操作符进行全文搜索的例子。
假设现在在数据库中有一个messages表其字段内容如表4-10所示。 如果要从上表中查出属性strMessage中包含“test”或者“king”的文档信息其tsearch语句如下
SELECT id, strtopic FROM Messages
WHERE to_tsvector(strMessage) to_tsquery( test | king );PostgreSQL会对messages表中的strMessage字段按4.6.1节中的介绍进行处理然后对“test | king采用全文索引的查询中的to_tsquery函数进行处理再调用操作符进行匹配。最后返回匹配成功的结果如表4-11所示。 对全文搜索的结果TSearch还提供了一些功能对结果进行处理包括权重设置、结果排序以及结果高亮显示下面将对这3种功能进行介绍。 设置文档部分的权重 权重用于标记单词来自于文档的哪个区域比如标题和开头的摘要这样就可以以不同的方式对待不同权重的单词。可以通过调用函数tsvector_setweight将一个TSVector中所有的关键字都设置为指定的权重。 对查询结果排序 排序主要是将匹配成功的搜索结果与查询表达式进行相关性比较将最相关的结果排在前面。相关性是评判文档与特定的查询之间相关程度的一个衡量标准。如果有很多匹配的项那么相关性高的项应该排在前面。 ts_rank和ts_rank_ed函数都可以用来对查询结果进行排序。 高亮显示 呈现搜索结果时最好是显示每个文档的一部分以及它和查询之间是如何关联的。通常搜索引擎会显示查询关键词所在的文档片段并且在其中将查询关键词高亮显示。PostgreSQL也提供一个函数ts_headline实现这个功能。 ts_headline接受一个文档以及对应的查询然后返回一个文档的摘要。在摘要里面查询是高亮显示的。ts_headline使用原始的文档而不是TSVector摘要所以它可能比较慢因此要小心使用。
索引篇小结
索引是提高数据库性能的常用方法它可以令数据库服务器以更快的速度查找和检索特定的行。不过索引也增加了数据库系统的负荷、成本因此应该恰当地使用它们。索引的优劣不仅仅与索引的查询效率有关同时与索引创建速度更新速度索引大小等因素有关。以上分析的几种索引使用环境不同相同环境下使用的优劣也各不相同。于是为了方便用户对特殊数据类型数据的查询PostgreSQL中提供了索引模板可方便用户对索引的扩展以支持自定义数据类型上的索引创建与查询。
通过使用索引能够快速查找数据库中的数据。但在添加索引的同时会增加数据库系统的负荷在增删修改数据时维护索引的一致性也需要一定的时间和空间。由于索引给查找数据带来的巨大的性能提升因此也得到了广泛的应用。在实际的使用中应该合理权衡使用索引带来的利弊恰当地使用索引。
